Участник: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 | + | 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.
