В.С.Костин, А.С.Жданов

Статистическая проверка наличия кластерной структуры

В известных реализациях кластерного анализа отсутствует статистическая верификация полученных результатов: во многих случаях неясно, насколько неслучайна выявленная кластерная структура и на каком количестве кластеров необходимо остановить процесс разбиения. В представленной работе разработан метод статистической верификации наличия кластерной структуры. Для этого проводится сравнение полученной методом k-средних классификации с результатами классификации по случайным данным с однокластерной структурой.

Метод k-средних выбран из соображений скорости счета, что позволило обрабатывать большие массивы данных (порядка 1000 объектов по 10 признакам) и проводить большое количество (порядка 1000) статистических экспериментов в реальном времени.

Нулевая гипотеза состоит в том, что случайные данные представляют собой выборку из многомерной нормальной совокупности. Длины осей эллипсоида рассеяния определяются методом главных компонент по исходным данным.

В качестве критерия разбиения на кластеры выбрана сумма объясненной дисперсии переменных, а в качестве статистики критерия для проверки гипотезы используется ее отношение к сумме дисперсий переменных.

В результате проведения статистических экспериментов для каждого количества кластеров в заданном диапазоне накапливаются значения критерия. Получаемая выборка значений статистики критерия позволяет оценить функцию ее распределения и значимость отклонения критерия от случайного.

В программе встроена визуализация кластерной структуры. Для выбора проекции многомерного пространства признаков на двумерный экран, предусмотрен выбор двух любых show-переменных.

Также имеется режим замедленной демонстрации процесса разбиения на кластеры.

Работа поддержана грантом РФФИ 00-06-80221.