Джеймс Маккафри
Продукты и технологии:
C#, Visual Studio 2010
В статье рассматриваются:
Алгоритм кластеризации k-средних (k-means clustering algorithm);
Вычисление центров масс для кластеров (cluster centroids);
Евклидова метрика (Euclidian distance);
Поиск аномальных данных.
Исходный код можно скачать по ссылке.
Рассмотрим проблему идентификации аномальных элементов данных в очень большом наборе данных, например выявления потенциально мошеннических транзакций по кредитным картам, рискованных займов и т. д. Один из подходов к обнаружению аномальных данных заключается в группировании элементов данных в сходные кластеры с последующим поиском элементов данных в каждом кластере, чем-либо отличающихся от других элементов данных в кластере.
Алгоритмов кластеризации много. Один из старейших и наиболее широко применяемых — алгоритм (или метод) k-средних (k-means algorithm). В этой статье я объясню, как работает алгоритм k-средних, и представлю законченную демонстрационную программу на C#. Существует много отдельных инструментов для кластеризации данных, но тогда зачем может понадобиться писать код кластеризации k-средних с нуля? Существующие инструменты может быть трудно или невозможно интегрировать в программную систему, они могут оказаться не адаптируемыми под необычные сценарии, а кроме того, с ними могут быть связаны проблемы авторского права или других прав на интеллектуальную собственность. Прочитав эту статью, вы сможете экспериментировать с кластеризацией k-средних и получить базовые познания, необходимые для добавления функциональности кластеризации в какое-либо.NET-приложение.
Лучший способ прочувствовать, для чего нужна кластеризация k-средних, и понять, к чему я клоню в этой статье, — взглянуть на рис. 1. Демонстрационная программа начинает с создания фиктивного набора из 20 элементов данных. В терминологии кластеризации элементы данных иногда называют последовательностью из n -чисел (tuples). Здесь каждая такая последовательность представляет некое лицо (person) и имеет два числовых атрибута: рост в дюймах и вес в фунтах. Одно из ограничений алгоритма k-средних в том, что он применяется только в случаях, где последовательности данных полностью числовые.
Рис. 1. Кластеризация с применением k-средних
Фиктивные данные загружаются в память в виде массива. Затем количество кластеров задается равным трем. Хотя существуют более совершенные методы кластеризации, способные предложить оптимальное количество кластеров, в целом, кластеризация данных — процесс исследовательский, и подходящее число кластеров обычно подбирается методом проб и ошибок. Как вы вскоре увидите, кластеризация k-средних — это итеративный процесс. В демонстрационной программе есть переменная maxCount, которая ограничивает количество выполнений основного цикла кластеризации. Здесь это значение произвольно выбрано равным 30.
Потом «за кулисами» демонстрационная программа использует алгоритм k-средних, чтобы поместить каждую последовательность данных в один из трех кластеров. Способов кодирования кластеризации много. В данном случае кластеризация определяется массивом значений типа int, где индекс массива представляет последовательность данных (tuple), а связанное с массивом значение — идентификатор кластера с нумерацией от 0. Итак, на рис. 1 последовательность 0 (65.0, 220.0) назначена кластеру 0, последовательность 1 (73.0, 160.0) — кластеру 1, последовательность 2 (59.0, 110.0) — кластеру 2, последовательность 3 (61.0, 120.0) — кластеру 2 и т. д. Обратите внимание на то, что восемь последовательностей назначено кластеру 0, пять последовательностей — кластеру 1, а семь последовательностей — кластеру 2.
Далее демонстрационная программа отображает данные, сгруппированные по кластерам. Если вы изучите кластеризованные данные, то заметите, что кластер 0 можно было бы назвать кластером полных людей, кластер 1 — высоких людей, а кластер 2 — низкорослых людей. Анализируя последовательности, назначенные кластеру 0, демонстрационная программа определяет по некоему критерию, что последовательность 5 (67.0, 240.0) является наиболее аномальной.
В следующих разделах я пошагово пройду по коду, с помощью которого был получен результат на экране (рис. 1), чтобы вы смогли потом модифицировать этот код под свои потребности. В этой статье предполагается, что вы по крайней мере на среднем уровне владеете навыками программирования на языках семейства C, но ничего не знаете о кластеризации данных. Я кодировал демонстрационную программу на C#, но избегал стиля объектно-ориентированного программирования (ООП), поэтому у вас не возникнет особых трудностей в рефакторинге этой программы под другой язык. Весь исходный код демонстрационной программы представлен в этой статье; его также можно скачать по ссылкеarchive.msdn.microsoft.com/mag201302kmeans.
