Что такое кластеризация

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

В качестве еще одного примера групп (или кластеров) можно привести возрастной состав участников демонстрации против введения повременной оплаты за телефонные разговоры, состоявшейся в одном из крупных российских городов несколько лет назад. Эта демонстрация состояла в основном из молодых людей преимущественно мужского пола (пользователей Интернета) и очень пожилых людей преимущественно женского пола (одиноких пенсионерок, для которых телефон — практически единственное средство общения с друзьями). При этом в демонстрации практически не участвовали ни люди среднего возраста, ни дети. Схематически состав этих групп можно изобразить так, как это представлено на рис. 1.

                     рис. 1

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

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

Как же работают подобные алгоритмы? Обычно они осуществляют итеративный поиск групп данных на основании заранее заданного числа кластеров. Изначально центры будущих кластеров представляют собой случайным образом выбранные точки в n-мерном пространстве возможных значений (где n — число параметров). Затем все исходные данные перебираются и в зависимости от значений параметров помещаются в тот или иной кластер, при этом постоянно происходит поиск точек, сумма расстояний которых до остальных точек в данном кластере является минимальной. Эти точки становятся центрами новых кластеров, и процедура повторяется до тех пор, пока центры и границы новых кластеров не перестанут перемещаться.

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

Выяснив, что такое кластеризация, рассмотрим пример ее реализации. Для выполнения примера нам потребуется Microsoft SQL Server 2000 (Enterprise Edition, Standard Edition или Personal Edition) с установленными аналитическими службами, причем можно использовать и ознакомительную версию.