Разработка интерактивного 2D-проекционного метода классификации многомерных данных
Низаметдинов Ш.У., Сафиуллин А. Э.
Национальный исследовательский ядерный университет «МИФИ», Москва, Россия
e-mail: sh_nizam@mail.ru, amir147@rambler.ru
Содержание
2. Интерактивный 2D проекционный метод кластеризации
3. Программное средство для решения задачи кластеризации интерактивным 2D-проекционным методом
4. Применение программного средства
Аннотация
В данном сообщении представлены метод и программное средство классификации многомерных данных на базе матрицы двумерных проекций, сочетающие визуальные и численные методы кластеризации.
Ключевые слова: визуальная аналитика, анализ многомерных данных, кластерный анализ, интерактивный интерфейс, метод главных компонент, выделение аномалий, понижение размерности.
Одной из основных задач, возникающих на начальных этапах анализа многомерных данных, является их классификация. В отсутствие обучающих выборок либо их недостаточной представительности используется кластерный анализ, направленный на выделение групп («скоплений», кластеров) сходных объектов. На сегодняшний день существует множество различных алгоритмов решения задачи кластерного анализа, как численных, так и использующих визуализацию.
В данной работе предлагается решать задачу кластерного анализа, используя интерактивный 2D-проекционный метод. Данный метод будет использоваться как для получения конечного результата, так и для получения начального приближения с последующим использованием численных методов.
В основе разрабатываемого метода разбиения исходного множества на кластеры лежит использование гипотезы компактности [1]. Полагаясь на данную гипотезу, можно сделать суждение о том, что точки, близкие в каждом двумерном подпространстве, близки в n-мерном пространстве, а точки далекие в исходном пространстве, далеки в одном из двумерных подпространств.
Алгоритм решения задачи [2]:
1. Точки многомерного множества данных проецируются во все двумерные арифметические пространства; в итоге получается «матрица проекций».
2. На одной из проекций выделяем характерные образования – кандидаты на скопление.
3. Анализируем остальные проекции и в случае обнаружения точек, лежащих далеко от скопления, исключаем их.
4. Помечаем оставшиеся выделенные точки как кластер и исключаем данные точки из рассмотрения. Если сгустков не осталось (то есть остались лишь одиночные (изолированные) точки, либо все точки помечены как кластер) то переходим к пункту 5, иначе – к пункту 2.
5. Кластеры получены.
Полученные визуальным методом кластеры при необходимости можно использовать как начальное приближение для модифицированного метода k-средних. Количество кластеров, подающихся на вход модифицированного алгоритма k–средних, равняется числу выделенных кластеров плюс число оставшихся одиночных точек.
Разработанное программное средство, реализующее описанный метод кластеризации, позволяет выполнять следующие операции:
– визуализировать исходные данные в виде матрицы двумерных проекций;
– выделять группы точек заданием ограничивающего их контура;
– добавлять выделенные точки в кластер;
– переходить в пространство главных компонент для снижения размерности;
– вычислять количественные характеристики кластеров и разбиения в целом (диаметр, дисперсия, доля межгруппового и внутригруппового разброса [3]);
– выделять центры потенциальных кластеров как начальные приближения для алгоритма k-средних;
– проводить кластеризацию методом k-средних;
– проводить иерархический кластерный анализ;
– визуализировать результаты кластерного анализа.
Описанное программное средство было использовано:
а) на данных о деятельности кредитных организаций (900 объектов, обладающих 40 параметрами) [4];
б) на данных по изображению лиц различных этнических групп (60 объектов-изображений размерностью 1350 х 900).
В результате проведенного тестирования, были выделены аномальные кредитные организации, кластеризация изображений лиц дает однозначное разбиение изображений по национальностям.
В данной работе описан метод решения задачи кластерного анализа 2D-проекционным методом. По данному методу было реализовано программное средство, которое затем было успешно протестировано на данных различных предметных областей.
1. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999. 270 с.
2. О. П. Масленников, И.Е. Мильман, А.Э. Сафиуллин, А.Е. Бондарев, Ш.У. Низаметдинов, В.В. Пилюгин. Разработка системы интерактивного визуального анализа многомерных данных. Научная визуализация, 2014, 4, с. 30-49. URL: http://sv-journal.org/2014-4/08.php?lang=ru
3. Айвазян C.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерности. М.: Финансы и статистика, 1989.
4. Евстифеева Н.А., Крылов Г.О., Рябков В.Е. Формирование признакового пространства для решения задач анализа репутационных рисков кредитных организаций как субъектов финансовой и информационной безопасности. Информатизация и связь, 2012, №8.
Development of interactive 2D-projection method for classification of multidimensional data
Nizametdinov S.U., Safiullin A.E.
National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)
e-mail: sh_nizam@mail.ru, amir147@rambler.ru
Abstract
This paper presents the methods and software classification of multidimensional data based on a matrix of two-dimensional projection, combining visual and numerical methods of clustering.
Keywords: visual analysis, multidimensional data analysis, cluster analysis, interactive interface, principal components method, anomalies selection, lower dimension.
1. Zagoruiko N.G. Prikladnye metody analiza dannyh i znanij [Applied methods of data analysis and knowledge]. Novosibirsk: Publishing House of the Institute of Mathematics, 1999. 270 p.
2. Maslennikov O.P., Milman I.E., Safiullin A.E., Bondarev A.E., Nizametdinov S.U., Pilyugin V.V. The development of interactive visual analysis of multivariate data. Scientific Visualization, 2014, 4, P.30-49, URL: http://sv-journal.org/2014-4/08.php?lang=en.
3. Ayvazyan S.A., Enyukov I.S., Meshalkin L.D. Prikladnaja statistika. Klassifikacija i snizhenie razmernosti. [Applied Statistics. Classification and dimension reduction]. M.: Finance and Statistics, 1989.
4. Evstifeeva N.A., Krylov G.O., Ryabkov V.E. Formirovanie priznakovogo prostranstva dlja reshenija zadach analiza reputacionnyh riskov kreditnyh organizacij kak sub#ektov finansovoj i informacionnoj bezopasnosti [Formation of the feature space to solve the problems of analysis of reputational risks of credit institutions as subjects of financial and information security]. Informatization and Communications, 2012, no 8.