• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Версия для слабовидящихЛичный кабинет сотрудника ВШЭПоиск

Разработка метода аномальных кластеров с автоматическим выбором числа и местоположения кластеров

2016

Кластер-анализ – популярный подход в машинном обучении и анализе данных, ориентированный на разбиение множества объектов на однородные подгруппы (кластеры),  уже используется в практической работе в маркетинговых агентствах, банках, программах интерпретации изображений  и т.д. Ожидается ещё большая отдача в связи с необходимостью автоматизации семантического анализа текстов и другой информации интернета. Метод к-средних – самый популярный метод кластер-анализа, так как он соответствует интуиции и работает быстро. Однако этот метод трудно автоматизировать из-за отсутствия адекватных средств определения числа и начальной локализации кластеров. В проекте исследуется возможность использования с этой целью эквивалентной формулировки критерия к-средних, найденной автором и приводящей к необходимости построения больших аномальных кластеров. Речь идёт о необходимости определения некой реперной точки – обычно центра тяжести множества многомерных точек, представляющих данные объекты – и переноса туда начала координат. При этом эквивалентный критерий представляет собой сумму квадратов Евклидовых расстояний между началом координат и центрами искомых кластеров, взвешенных их численностями. Ожидание успеха связано с  тем, что даже наивный вариант использования аномальности в так называемой интеллектуальной версии метода к-средних, предложенной автором, оказался лучше многих популярных методов в серии вычислительных экспериментов, проведённых М. Чаном и автором (2010).  В проекте предполагается разработка двух версий метода аномальных кластеров. Первая представляет собой модификацию ранее предложенного автором интеллектуальной версии метода к-средних. В этой версии аномальные кластеры отщепляются один за одним, независимо от их количества объектов в них. Эксперименты показывают, что при этом число получаемых кластеров слишком велико. Идея – применить недавнюю разработку Тасулиса и др. (2010) для объединения каких-то из полученных аномальных кластеров так, чтобы это не противоречило критерию однородности. Вторая версия будет получать аномальные кластеры параллельно, а не последовательно. Для верификации разработанных методов будет применяться схема, апробированная в предыдущих публикациях автора и других исследователей: (1) генерация данных как совокупности Гауссовых кластеров с контролируемыми разбросами внутри кластеров и между кластерами уровнем шума; (2) применение к этим данным «линейки» сравниваемых методов; (3) оценка близости между сгенерированными и полученными кластерами на основе популярных  метрик – точности и так называемого модифицированного индекса Рэнда. Усреднение оценок по данным, сгенерированным при одних и тех же значениях параметров Гауссовых распределений, даёт достаточно надёжные оценки качества. 

Публикации по проекту:


Mirkin B., Amorim R., Makarenkov V., Shestakoff A. The Minkowski central partition as a pointer to a suitable distance exponent and consensus partitioning // Pattern Recognition. 2017. Vol. 67. P. 62-72. 
undefined., Mirkin B. Capturing the right number of clusters with K-Means using the complementary criterion and affinity propagation // Journal of Classification. 2017. doi