Вычислительная реализация рангового метода кластеризации

Кластеризация - это разбиение множества объектов на классы, в каждом из которых объекты похожи друг на друга. Каждый объект описывается некоторым набором признаков x₁, x₂, ..., x_n. Каждому объекту ставится в соответствие точка в n-мерном признаковом пространстве.

Обычно в кластер-анализе выбирается метрика, которая характеризует меру сходства двух объектов (расстояние между соответствующими точками), и применяется некоторый алгоритм кластеризации, который позволяет разбить объекты на кластеры.

 В статье [1] был предложен так называемый ранговый метод кластеризации одномерных эмпирических данных. В этом методе не используется метрика.
Имеются исходные эмпирические данные - набор положительных чисел w_i (i = 1, 2, ..., n). Эти числа упорядочиваются по возрастанию, и каждому значению w ставится в соответствие порядковый номер - ранг r. Данные анализируются с помощью соотношения

которое представляет собой модифицированный В.П. Масловым закон Ципфа (в [1] принято N = 2n + 1). Рассматриваются точки в логарифмических координатах (ln R, ln w). Суть рангового метода кластеризации в следующем. Для объектов, объединённых некоторым набором признаков, т.е. для определённой группы или кластера, справедлив модифицированный В.П. Масловым закон Ципфа. При этом существенной характеристикой кластера являются параметры , c. Если данные следует разбить на кластеры, то способ разбиения можно сформулировать так: на каждом из кластеров справедлив модифицированный В.П. Масловым закон Ципфа со своими значениями параметров (, c), которые меняются при переходе от кластера к кластеру. Геометрически это означает, что на каждом из кластеров точки близки к прямой, при переходе от кластера к кластеру прямая меняется.

Моя курсовая работа была посвящена автоматизации процесса кластеризации эмпирических данных ранговым методом. Результаты курсовой работы опубликованы в статье [2].
В первую очередь необходимо отметить, что задача кластеризации эмпирических данных ранговым методом изначально является нечётко поставленной. Исходную нечёткую постановку задачи необходимо формализовать. Нужно ответить на вопрос: какую информацию об исходных данных нужно получить? Поэтому нужно построить математическую модель.
Введём меру отклонения точки от прямой как отклонение точки от прямой по вертикали.

Введём пороговое значение и потребуем, чтобы мера отклонения каждой точки кластера [a...b] от прямой не превосходила . Будем считать, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа с параметрами , если

Введём величину

Будем считать, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа, если

Теперь введём понятие аномальных точек - точек, которые можно выбросить. Зачем они нужны? Дело в том, что максимум обладает таким свойством, что одна единственная точка может сильно повлиять на максимум. Может оказаться, что после выбрасывания небольшого количества точек все оставшиеся точки будут очень близки к прямой.
Введём величину

Здесь max_j - j-е по максимальности число.
Будем считать, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа, если

Также введём величину

Рассмотрим множество максимальных промежутков, которое включает в себя промежутки, на которых справедлив модифицированный В.П. Масловым закон Ципфа, но которые нельзя расширить так, чтобы на расширенном промежутке также был справедлив этот закон.
Множество максимальных промежутков можно рассматривать как результат кластеризации - оно позволяет определить, как данные разбиваются на кластеры. При этом максимальные промежутки, как правило, будут пересекаться, и выбор конкретного разбиения остаётся за пользователем (здесь пользователь может использовать априорную информацию).
Отметим, что здесь важно, что используется именно наибольшее отклонение точек от прямой, а не какая-либо усреднённая характеристика. Максимум всегда не уменьшается при расширении промежутка, а среднее значение этим свойством не обладает. Поэтому если бы использовалась усреднённая характеристика, то множество максимальных промежутков теряло бы смысл.
Таким образом, построена математическая модель: необходимо найти множество максимальных промежутков, а также может пригодиться таблица, содержащая значения величин и для всех возможных промежутков [a...b].

О вычислении можно прочитать здесь.
Разработана программа [3], в которой реализованы разработанные методы. В Роспатенте зарегистрирована первая версия программы. Первая версия программы вычисляет множество максимальных промежутков, а также три таблицы: половина минимальной высоты полосы (), значение параметра , минимальное количество аномальных точек () для всех возможных промежутков [a...b]. Вторая версия программы не вычисляет большие таблицы, а вместо этого вычисляет значения величины и значения параметра только для интересующих промежутков (список интересующих промежутков задаётся пользователем).

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

Приведём пример применения программы. На рисунке цветом выделено разбиение данных на кластеры, приведённое в статье [1]. Это разбиение было найдено вручную. Фигурными скобками выделено множество максимальных промежутков, выданное программой (). Отметим, что разбиение, приведённое в статье [1], отличается от множества максимальных промежутков. Таким образом, программа позволяет избавиться от субъективности при нахождении разбиения.

На следующем рисунке приведён пример кластеризации стран мира по численности населения. Кластеризация проводилась с помощью разработанной программы. На самом левом и самом правом кластерах значение параметра близко к 1, а на среднем кластере оно близко к 2. На рисунке кластеры пересекаются, потому что однозначно разбить данные на кластеры невозможно.

Более подробно данная тема освещена в моих курсовых работах.
Курсовая работа за 3 курс: http://imcs.dvgu.ru/works/work?wid=13420
Курсовая работа за 4 курс: http://imcs.dvgu.ru/works/work?wid=14975

[1] Гузев М.А., Черныш Е.В. Ранговый анализ в задачах кластеризации // Информатика и системы управления. – 2009. – №3(21). – С. 13-19. [ссылка]
[2] Гренкин Г.В. Методы вычислительной реализации рангового метода кластеризации // Информатика и системы управления. 2012. № 1(31). С. 71–79. [ссылка]
[3] Гренкин Г.В., Черныш Е.В. ClRank // Свидетельство Роспатента о государственной регистрации программы для ЭВМ. — Рег. № 2012612452 от 06.03.2012.