V Международная студенческая научная конференция Студенческий научный форум - 2013

Введение

В различных областях знаний, содержащих большие массивы данных, нередко возникает необходимость группировать эти данные по тем или иным признакам, т.е. кластеризовать. Известными примерами подобных систематизаций являются иерархическая классификация растений и видов М. Адансона (1757), периодическая система элементов Д.И. Менделеева (1869). В то время способы классификации сводились к методу так называемой комбинационной группировки (все характеризующие объект признаки носят дискретный характер). Однако по мере развития электронно-вычислительной техники появилась возможность для этих целей использовать аппарат многомерного статистического анализа, который позволяет всю анализируемую совокупность объектов разбить на сравнительно небольшое число однородных, в определённом смысле, групп или классов [1].

Современные методы кластеризации довольно разнообразны, поскольку в них по-разному выбирается способ определения близости между объектами, а также используются различные алгоритмы вычислений. Оригинальный метод кластеризации, в котором не используется мера близости и который основан на модифицированном В.П. Масловым законе Ципфа, был предложен в статье М.А. Гузева и Е.В. Черныш [2]. Этот метод получил название рангового метода кластеризации. В статье [2] авторы рассматривают одномерные эмпирические данные: w₁, w₂, ..., wn, – эти данные упорядочиваются по возрастанию, и каждому значению w ставится в соответствие порядковый номер – ранг r. Исходные данные анализируются с помощью соотношения

, (1)

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

Рис. 1. Ранговый метод кластеризации.

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

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

Таким образом, нужно ответить на вопрос: какую информацию нужно получить?

Математическая модель

Исходная формулировка рангового метода кластеризации представляет собой два требования к искомому разбиению: 1) точки каждого кластера близки к прямой ; 2) параметры  и c меняются при переходе от кластера к кластеру.

Возникают две задачи: 1) оценка заданного разбиения данных на кластеры; 2) нахождение разбиения.

В ранговом методе кластеризации кластер – это совокупность точек с последовательными рангами r = a, ..., b, т.е. промежуток [a...b]. Требуется формализовать приближённое соотношение (1) для кластера [a...b]. Введём меру отклонения точки (ln R, ln w) от прямой :

.

Зададим пороговое значение ₀ и потребуем, чтобы для всех точек кластера [a...b] выполнялось условие:

.

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

.

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

.

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

.

Точку, для которой не выполняется неравенство

, (2)

будем называть аномальной. Потребуем, чтобы для всех точек кластера [a...b] выполнялось неравенство (2), при этом допускается ₀ аномальных точек, для которых, однако, должно выполняться неравенство

.

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

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

Рассмотрим множество промежутков, на которых справедлив модифицированный В.П. Масловым закон Ципфа на уровне L. Те из них, которые нельзя расширить так, чтобы на расширенном промежутке также был справедлив этот закон, образуют множество максимальных промежутков на уровне L.

Пусть задан кластер [a...b] и задана некоторая точка (ln R₀, ln w₀), не принадлежащая этому кластеру. Введём расстояние от точки (ln R₀, ln w₀) до кластера [a...b]. Рассмотрим множество значений параметров (, c), таких, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа с такими значениями параметров. Выберем из этого множества те значения (, c), при которых величина принимает наименьшее значение. Это значение и будет расстоянием от точки (ln R₀, ln w₀) до кластера [a...b] (измеренным как отклонение точки от прямой). Также введём расстояние от точки до кластера, измеренное в количестве точек кластера. Зададим пороговое значение ₀ и рассмотрим множество значений параметров (, c), для которых . Выберем из этого множества такие значения (, c), что неравенство (2) не выполняется для наименьшего количества точек кластера [a...b]. Это количество точек и будет расстоянием от точки (ln R₀, ln w₀) до кластера [a...b].

Рассмотрим задачу оценки заданного разбиения данных на кластеры. Требуется оценить разбиение, т.е. определить, удовлетворяет ли оно двум требованиям (см. выше). Во-первых, для оценки каждого кластера в отдельности применим величины _min и _min (эти величины характеризуют качество кластера). Во-вторых, проанализируем, как изменяются данные величины при расширении и сужении каждого из кластеров разбиения. Для этого построим таблицу, содержащую значения величины _min (или _min) для всех возможных промежутков [a...b]. В-третьих, для каждого кластера разбиения вычислим расстояния от нескольких точек слева и справа от кластера до этого кластера.

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

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

Алгоритмы

Обозначим x = ln R, y = ln w.

Рассмотрим задачу вычисления величины

.

Эту задачу можно рассматривать как задачу нахождения многочлена наилучшего равномерного приближения первой степени (см., например, [3]). Многочлен наилучшего равномерного приближения существует и единствен. Если – многочлен наилучшего равномерного приближения, то существуют 3 узла , в которых разность достигает максимального по модулю значения с последовательной переменой знака (условие альтернанса). Из условия альтернанса вытекает, что прямая параллельна одному из рёбер выпуклой оболочки множества точек .

Выпуклой оболочкой множества точек называется наименьший выпуклый многоугольник, содержащий все точки данного множества. Для построения выпуклой оболочки в вычислительной геометрии есть алгоритм Грэхема и алгоритм Джарвиса [4].

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

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

Введём оператор проектирования . Проведём через точку (x, y) прямую с угловым коэффициентом (–), тогда проекция точки (x, y) на ось ординат – это точка пересечения данной прямой с осью ординат. Пусть – координата проекции:

.

Тогда

.

Рассмотрим следующие функции:

,

,

.

Требуется найти минимум функции . Функции и кусочно-линейные, следовательно, – кусочно-линейная функция. Значит, минимум достигается в одной из точек излома.

Возникает задача нахождения точек излома функций и . Графики этих функций – это ломаные.

Рассмотрим алгоритм построения ломаной – графика функции (см. рис. 2). Начинаем строить ломаную с прямой – графика функции (эта прямая – текущий максимум). Находим точки пересечения этой прямой с прямыми – графиками функций , …, . Выбираем точку пересечения с наименьшей абсциссой ₁. Пусть это точка пересечения с графиком функции . Прямая – график функции – становится текущим максимумом. Далее находим точки пересечения этой прямой с прямыми – графиками функций , …, . Выбираем точку пересечения с наименьшей абсциссой ₂. Пусть это точка пересечения с графиком функции . Прямая – график функции – становится текущим максимумом. Этот процесс продолжается, пока текущим максимумом не станет прямая – график функции .

Рис. 2. Алгоритм Джарвиса (пунктиром выделен график функции ).

Описанный алгоритм представляет собой алгоритм Джарвиса построения выпуклой оболочки. Прямые, образующие ломаную, соответствуют вершинам выпуклой оболочки, а абсциссы вершин ломаной соответствуют угловым коэффициентам прямых, содержащих рёбра выпуклой оболочки. Время выполнения алгоритма – , где M – количество точек, h – число вершин выпуклой оболочки.

Опишем алгоритм Грэхема, который имеет оптимальное время выполнения (см. рис. 3). Будем добавлять прямые по одной: сначала , затем , …, . Будем последовательно находить , , …, .

Предположим, что ломаная – график функции – уже построена. Укажем, как построить ломаную – график функции .

Можно показать, что прямая – график функции – пересекает ломаную – график функции – ровно в одной точке с абсциссой .

Ломаную – график функции – можно получить так: на промежутке эта ломаная совпадает с ломаной – графиком функции , – а на промежутке – с прямой – графиком функции .

Рис. 3. Алгоритм Грэхема (пунктиром выделен график функции , жирная прямая – график функции ).

Рассмотрим задачу вычисления величины

,

где – j-й по максимальности элемент последовательности z_a, ..., zb.

Заметим, что

.

Рассмотрим следующие функции:

,

,

.

Требуется найти минимумы функций . – кусочно-линейная функция, минимум достигается в точке излома.

Возникает задача нахождения точек излома функций и , .

Рассмотрим алгоритм построения ломаных – графиков функций , , …, (см. рис. 4). Будем добавлять прямые по одной: сначала , затем , …, . Будем последовательно находить () для .

Предположим, что ломаные – графики функций () – уже построены. Укажем, как построить ломаные – графики функций ().

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

Ломаные — графики функций () – можно получить следующим образом. Ломаная – график функции – на промежутке (–, ′₍₀₎] совпадает с ломаной – графиком функции , – а на промежутке [′₍₀₎, +) – с прямой – графиком функции . Ломаная – график функции – на промежутке (–, ′₍₁₎] совпадает с ломаной – графиком функции , – на промежутке [′₍₁₎, ′₍₀₎] – с прямой – графиком функции , – а на промежутке [′₍₀₎, +) – с ломаной – графиком функции . Ломаная – график функции – на промежутке (–, ′(_)] совпадает с ломаной – графиком функции , – на промежутке – с прямой – графиком функции , – а на промежутке [′(_–1), +) – с ломаной – графиком функции .

Данный алгоритм представляет собой обобщение алгоритма Грэхема. Время выполнения алгоритма – .

Рис. 4. Обобщённый алгоритм Грэхема.

Программная реализация

Разработана программная система [5], в которой реализованы разработанные методы. Программа написана на языке программирования C++.

Программа принимает на вход входные данные в формате CSV и входные параметры: ₀ (пороговое значение для половины минимальной высоты полосы), ₀ (допустимое количество аномальных точек), x (код функциональной зависимости: если x= 1, то используется соотношение N = n + 1, а если x = 2, то соотношение N = 2n + 1).

Программа выводит результаты вычислений в файл в формате HTML. Программа вычисляет множество максимальных промежутков. Также имеется возможность вычисления значения параметра и половины минимальной высоты полосы для интересующих промежутков.

Примеры применения программы

Приведём пример применения программы. На рис. 5 цветом выделено разбиение данных на кластеры, приведённое в статье [2]. Это разбиение было найдено вручную. Фигурными скобками выделено множество максимальных промежутков, выданное программой (₀ = 0,03, ₀ = 0).

Отметим, что разбиение, приведённое в статье [2], отличается от множества максимальных промежутков. Таким образом, программа позволяет избавиться от субъективности при нахождении разбиения.

Рис. 5. Пример применения программы.

На рис. 6 приведён пример кластеризации стран мира по численности населения. Кластеризация проводилась при помощи разработанной программы.

Рис. 6. Пример применения программы.

Заключение

Таким образом, в данной работе сформулированы требования к программной системе (т.е. какую информацию она должна выводить). Для оценки заданного разбиения данных на кластеры предлагается оценить каждый кластер в отдельности, вычислив _min и _min для каждого кластера, а также проанализировать изменение данных величин при расширении и сужении кластеров разбиения и вычислить расстояния от соседствующих с кластерами точек до кластеров. Для нахождения разбиения можно найти множество максимальных промежутков, а также построить таблицу _min и _min для всех возможных промежутков. Данная информация может позволить пользователю анализировать исходные данные с точки зрения рангового метода кластеризации.

Разработаны численные алгоритмы. Применены алгоритмы Джарвиса и Грэхема построения выпуклой оболочки, а также получено обобщение алгоритма Грэхема.

Результаты данной работы опубликованы в научном журнале «Информатика и системы управления» [6]. На основе данных результатов разработана программная система, в которой реализованы описанные методы.

ЛИТЕРАТУРА

1. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. и др. Прикладная статистика: Классификация и снижение размерности. – М.: Финансы и статистика, 1989.

2. Гузев М.А., Черныш Е.В. Ранговый анализ в задачах кластеризации // Информатика и системы управления. – 2009. – №3(21). – С. 13-19.

3. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. – М.: Наука, 1972.

4. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. – М.: Мир, 1989.

5. Гренкин Г.В., Черныш Е.В. ClRank // Свидетельство Роспатента о государственной регистрации программы для ЭВМ. — Рег. № 2012612452 от 06.03.2012.

6. Гренкин Г.В. Методы вычислительной реализации рангового метода кластеризации // Информатика и системы управления. 2012. № 1(31). С. 71–79.

E-mail:[email protected].

Код для цитирования: Скопировать