Участник:Pushnyakov Alexey

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

(Различия между версиями)
Перейти к: навигация, поиск
(Весна 2014, 8-й семестр)
(Весна 2014, 8-й семестр)
Строка 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.

Версия 19:31, 23 августа 2014

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

МФТИ, ФУПМ, 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.

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