Участник:Pushnyakov Alexey
Материал из MachineLearning.
(→Весна 2014, 8-й семестр) |
(→Отчеты о научно-исследовательской работе) |
||
| (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 | + | 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). Исследуется зависимость комбинаторного и расстояний.
