Участник:Pushnyakov Alexey

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Весна 2014, 8-й семестр)
Текущая версия (19:19, 24 августа 2015) (править) (отменить)
(Отчеты о научно-исследовательской работе)
 
(5 промежуточных версий не показаны.)
Строка 36: Строка 36:
'''On combinatorial bounds for maximal ε-partitions of a finite metric space'''
'''On combinatorial bounds for maximal ε-partitions of a finite metric space'''
-
A special class of partitions of finite metric space called maximal ε-partitions is studied. Let there be an upper bound for the number of distances which are greater than ε. We consider lower bounds for cardinality of the largest subset with diameter less than ε'. It is shown that in case where ε' < 2ε we cannot guarantee any linear bound. In case where ε' ≥ 2ε the best possible bound is obtained.
+
A finite metric space (X,ρ) is studied. By ε-cluster we mean a subset of X with diameter at most ε. Let there be an upper bound for the number of distances which are greater than ε. We consider lower bounds for maximal cardinality of ε'-cluster. An important question is to find dependence between ε and ε'. It is shown that in case where ε' < 2ε we cannot guarantee any linear bound. In case where ε' ≥ 2ε the best possible bound is obtained. A maximal ε'-partition is a partition into ε'-clusters constructed according to greedy procedure described below. Using Hall's marriage theorem we prove existence of special matching between every two elements of maximal ε'-partition. Considering maximal matching between ε'-cluster with maximal cardinality and its complement we can calculate number of pairs (x,y) such that ρ(x,y) > ε and obtain lower bound for maximal cardinality of ε'-cluster. In some particular cases value of ε' can be decreased. For instance, in case of Euclidean metric we can assume ε' = √2ε and obtain linear bound. However, it is unknown whether this bound could be improved.
'''Публикации'''
'''Публикации'''
''А.С.Пушняков'' [http://svn.code.sf.net/p/mlalgorithms/code/Group074/Pushnyakov2014MetricPartition/Pushnyakov2014MetricPartition.pdf О комбинаторных оценках максимальных ε-разбиений метрических конфигураций] // Машинное обучение и анализ данных, 2014, T.1, №7.
''А.С.Пушняков'' [http://svn.code.sf.net/p/mlalgorithms/code/Group074/Pushnyakov2014MetricPartition/Pushnyakov2014MetricPartition.pdf О комбинаторных оценках максимальных ε-разбиений метрических конфигураций] // Машинное обучение и анализ данных, 2014, T.1, №7.
 +
 +
=== Осень 2014, 9-й семестр ===
 +
 +
Улучшена нижняя на мощность максимального ε-кластера в случае евклидовой метрики. Рассматривается задача существования кластерного покрытия метрического пространства. Под ε-кластерным покрытием называется совокупность подмножеств пространства диаметра не более ε, отделенных друг от друга на расстояние не менее ε. Предлагается разделять расстояния на три группы: короткие (не больше ε), длинные (больше R) и средние. В зависимости от числа расстояний каждого типа получена оптимизационная задача, позволяющая получить нижнюю оценку на мощность максимального покрытия.
 +
 +
'''Выступления на конференциях'''
 +
 +
''А.С.Пушняков'' О комбинаторных оценках максимальных ε-разбиений метрических конфигураций. // [http://www.mmro.ru 10-я международная конференция «Интеллектуализация обработки информации»], Греция, о. Крит, 4-11 октября, 2014 г.: Тезисы докладов. – С. 42-43
 +
 +
 +
===Весна 2015, 10-й семестр ===
 +
 +
Получена нижняя оценка на мощность кластерного покрытия метрического пространства в случае двух кластеров в зависимости от числа коротких расстояний и числа треугольников, не содержащих коротких расстояний.
 +
 +
На множестве отрезков и углов метрической конфигурации введем отношение порядка («длина» угла – это сумма длин отрезков, образующих угол). Рассматривается факторизация полуметрического конуса по данному отношению. Комбинаторное расстояние до оси полуметрического конуса – это число нарушений неравенства ρ(x,y) ≤ ρ(a, b) + ρ(b, c). Исследуется зависимость комбинаторного и <tex>l_1</tex> расстояний.

Текущая версия

Пушняков Алексей Сергеевич

МФТИ, ФУПМ, 074

Кафедра "Интеллектуальные системы"

Направление "Интеллектуальный анализ данных"

aleksey.pushnyakov@phystech.edu

Содержание

Отчеты о научно-исследовательской работе

Весна 2013, 6-й семестр

Использование спектрального преобразования для распознавания напечатанного изображения

В работе решается задача классификации двух типов изображений глаз: реального и напечатанного. На основании того, что напечатанное изображение, в отличие от реального, содержит периодическую структуру зёрен печати, предлагается использовать спектральное преобразование, выделяющее соответствующую гармонику. Рассматривается зависимость энергии от частоты фурье-спектра, и по ней строится пространство признаков. Задача классификации решается с помощью метрического классификатора.

Публикации

А.С.Пушняков Использование спектрального преобразования для распознавания напечатанного изображения // Машинное обучение и анализ данных, 2013, T.1, №5, С.534-541.

Осень 2013, 7-й семестр

Сегментация цветных изображений

В работе решается задача сегментации цветного изображения. Для приближения распределения пикселов по цветам используется модель смеси нормальных распределений. Разделение смеси производится EM алгоритмом с последовательным добавлением компонент. Кластеризация выполняется согласно принципу максимума правдоподобия. Качество сегментации оценивается по величине искажения исходного изображения.

Публикации

А.С.Пушняков Сегментация цветных изображений: технический отчет // Вычислительный сервер журнала "Машинное обучение и анализ данных" [Электронный ресурс] URL: mvr.jmlda.org (дата обращения: 04.12.2013).

Весна 2014, 8-й семестр

On combinatorial bounds for maximal ε-partitions of a finite metric space

A finite metric space (X,ρ) is studied. By ε-cluster we mean a subset of X with diameter at most ε. Let there be an upper bound for the number of distances which are greater than ε. We consider lower bounds for maximal cardinality of ε'-cluster. An important question is to find dependence between ε and ε'. It is shown that in case where ε' < 2ε we cannot guarantee any linear bound. In case where ε' ≥ 2ε the best possible bound is obtained. A maximal ε'-partition is a partition into ε'-clusters constructed according to greedy procedure described below. Using Hall's marriage theorem we prove existence of special matching between every two elements of maximal ε'-partition. Considering maximal matching between ε'-cluster with maximal cardinality and its complement we can calculate number of pairs (x,y) such that ρ(x,y) > ε and obtain lower bound for maximal cardinality of ε'-cluster. In some particular cases value of ε' can be decreased. For instance, in case of Euclidean metric we can assume ε' = √2ε and obtain linear bound. However, it is unknown whether this bound could be improved.

Публикации

А.С.Пушняков О комбинаторных оценках максимальных ε-разбиений метрических конфигураций // Машинное обучение и анализ данных, 2014, T.1, №7.

Осень 2014, 9-й семестр

Улучшена нижняя на мощность максимального ε-кластера в случае евклидовой метрики. Рассматривается задача существования кластерного покрытия метрического пространства. Под ε-кластерным покрытием называется совокупность подмножеств пространства диаметра не более ε, отделенных друг от друга на расстояние не менее ε. Предлагается разделять расстояния на три группы: короткие (не больше ε), длинные (больше R) и средние. В зависимости от числа расстояний каждого типа получена оптимизационная задача, позволяющая получить нижнюю оценку на мощность максимального покрытия.

Выступления на конференциях

А.С.Пушняков О комбинаторных оценках максимальных ε-разбиений метрических конфигураций. // 10-я международная конференция «Интеллектуализация обработки информации», Греция, о. Крит, 4-11 октября, 2014 г.: Тезисы докладов. – С. 42-43


Весна 2015, 10-й семестр

Получена нижняя оценка на мощность кластерного покрытия метрического пространства в случае двух кластеров в зависимости от числа коротких расстояний и числа треугольников, не содержащих коротких расстояний.

На множестве отрезков и углов метрической конфигурации введем отношение порядка («длина» угла – это сумма длин отрезков, образующих угол). Рассматривается факторизация полуметрического конуса по данному отношению. Комбинаторное расстояние до оси полуметрического конуса – это число нарушений неравенства ρ(x,y) ≤ ρ(a, b) + ρ(b, c). Исследуется зависимость комбинаторного и l_1 расстояний.

Личные инструменты