Основные идеи и методы
кластерного анализа История кластерного анализа
Классификация была издревле известна человечеству. Прообраз этого понятия можно найти в первых строках книги Бытия (Быт. 1:21). Известны классические примеры классификации у Платона и Аристотеля [Новая философская энциклопедия, 2001], однако систематизация процесса классификации долгое время не проводилась. В начале XIX века французский ботаник Огюстен Декандоль [Брокгауз, Ефрон 1907] предложил свою теорию классификации и систематизации, названную впоследствии таксономией. Декантоль стремился классифицировать все существующие растения, объединяя их в однородные группы разных уровней, образующих иерархическую структуру (вид, род, семейство, класс, отдел). Данный метод вскоре получил широкое распространение и за пределами биологии. Теперь он положен в основу иерархических методов кластеризации.
Немецким биологом Ф. Гейнке был предложен метод группировки объектов по нескольким признакам. Всякий новый объект принадлежал той группе, к центру которой он ближе всего – идея, легшая в основу метода k средних.
Пионером применения базовых принципов кластеризации считается польский антрополог К. Чекановский. В 1913 году он предложил идею «структурной классификации» [Плюта 1980]: выделять компактные группы объектов. Для этого он разработал и оригинальный метод, применяемый при диагонализации признаковой матрицы.
В 1925 году советским гидробиологом П.В. Терентьевым был разработан метод корреляционных плеяд [Терентьев 1959] – это по-видимому первый алгоритм, направленный на выявление групп тесно коррелирующих признаков. Идеи этого алгоритма легли в основу многих пороговых алгоритмов на графах, например метода связных компонент.
Термин кластерный анализ впервые применил английский ученый Р. Трион [Trion 1939].
В 50-х годах ситуация стала развиваться значительно быстрее. Появились ЭВМ, способные обрабатывать данные гораздо быстрее человека. Алгоритмы усложнялись и совершенствовались, объемы данных росли и вскоре кластерный анализ завоевал прочное место в ряду прикладных дисциплин. Появилась возможность обрабатывать такое количество информации, которое прежде было человеку не под силу.
Следующие два десятилетия считаются золотым веком кластерного анализа. Тогда были получены основные результаты, изучен метод k-средних, иерархические процедуры, диагонализация и пр. Важную роль в этом сыграли и советские ученые [Мандель 1988].
Сегодня существует не меньше сотни методов кластеризации, которые применяются в тех или иных задачах, однако нет ни одного универсального алгоритма. На практике приходится не только выбирать наиболее подходящий для данной задачи алгоритм, но и настраивать его параметры. Чтобы оценить качество кластеризации, необходимы некоторые метрики, описание которых мы дадим в предстоящем разделе.
Кластеризация как нечеткая классификация
Кластерный анализ – бурно развивающаяся область прикладной математики, тем не менее, специалисты обычно не оперируют какими-либо строгими определениями, опираясь лишь на интуитивное представление о кластеризации. Кластеризация – это нечеткая классификация, некоторое её приближение, основанное на взаимном расположении классифицируемых объектов. В основном своем значении термин cluster может быть переведен как скопление. Близкие объекты относятся к одному классу, а далекие объекты, наоборот, – к разным классам. Для этого между объектами должно быть введено некоторое расстояние. Результат кластеризации существенно зависит от выбора метрики.
Чтобы сформулировать и другие параметры процедуры кластерного анализа, нам следует в первую очередь определить самое базовое понятие – классификацию.
Ограничения, определяющие классификацию
Представим себе несколько объектов, про каждый из которых можно сказать, обладает ли он данным признаком или нет. В результате объекты распределяются на две группы – обладающие и не обладающие признаком. Такую операцию называют дихотомией. Иногда может существовать более двух состояний по отношению к признаку, например, цвет глаз у людей, – в таком случае принято говорить о классификации на несколько групп.
Обычно при классификации вводят некоторые ограничения. Во-первых, должно однозначно определяться состояние объекта по отношению к признаку, т.е. группы не могут пересекаться. Во-вторых, состояние может зависеть только от внутренних свойств объекта и не должно прямо зависеть от других выбранных объектов. Условно говоря, разделение чисел на четные и нечетные – это классификация, т.к. четность числа не зависит от того, какие числа выбраны для проверки, а распределение чисел на большие и меньшие не является классификацией, потому что не выполняется ни одно из условий. Классификацию как логическое действие называют делением, а как математическую операцию – факторизацией.
Простейший пример факторизации – остатки от деления по модулю. Здесь множество объектов классификации – это натуральные числа, а признак, относительно которого происходит классификация – это остаток от деления по некоторому модулю. Если число имеет остаток 1, то оно относится к первой группе, если остаток 2, то ко второй и т.д. Каждое число может иметь ровно один остаток, поэтому оба ограничения выполнены, т.е. перед нами действительно классификация.
Формальное описание классификации
Теперь формализуем полученное интуитивное определение, чтобы в дальнейшем как можно нагляднее показать разницу между классификацией и кластерным анализом.
Представим некоторое множество  , элементы которого мы будем называть объектами. На множестве объектов определим функцию  , называемую признаком. Эта функция каждому объекту ставит в соответствие номер группы, к которой он принадлежит. Примеры признаковой функции – цвет глаз человека или остаток от деления по модулю для некоторого числа.
Все объекты множества  , которые относительно признака  принадлежат к одной и той же группе  называют классом  . Разбиение  множества на непересекающиеся классы ,  и есть классификация.
Нечеткая и зависимость параметра от выборки
Не всегда признаковую функцию классификация можно определить однозначно. В некоторых случаях граница между классами достаточно условна и определяется пороговым значением параметра. Пороговые значения требует, например, классификация боксеров по весовой категории на тяжелую, среднюю и легкую.
Зачастую нельзя выделить единственный признак, классифицирующий объекты, поэтому используют методы многомерной классификации и факторного анализа: выделяются наиболее значимые признаки.
При нечеткой классификации предполагается, что параметр каждого объекта определяется однозначно и не зависит от других объектов. Иногда задание такой функции невозможно в принципе, например, в задаче разбиения группы людей на дружественные компании. Здесь само отношение дружбы подразумевает участие нескольких объектов.
На практике, во многих задачах использовать модель нечеткой классификации хотя и возможно, но само формирование признаковых описаний представляет большие трудности. Так, например, гораздо проще сравнить два романа и определить, что они написаны одним и тем же человеком, чем описать, на основе каких признаков они схожи. Точно так же можно определить, что данное письмо является спамом, сравнив его с другими письмами, уже помеченными как спам, чем описать все возможные признаки рекламной рассылки. В всех этих случаях удобнее разбить множество объектов на «дружные компании», в каждой из которых будут похожие объекты, а объекты разных классов, наоборот, будут отличаться.
Метрическое пространство объектов
Итак, в некоторых задачах нам необходимо ввести понятие расстояния  между объектами. Двум объектам  ,  поставим в соответствие некоторое число  . Естественно задать расстояние так, что для него выполнены стандартные свойства метрики, в частности, расстояние объекта до самого себя должно быть нулевым. Чем ближе объекты, тем скорее их следует отнести в одну группу и наоборот, чем они дальше друг от друга, тем скорее их следует отнести в разные группы.
Чтобы оценить близость двух объектов, нам, вообще говоря, понадобится какое-то математическое представление пространства . Один из традиционных способов – представить каждый объект в виде числового вектора, характеризующего его свойства. В таком случае, естественно расстоянием между объектами считать евклидовым расстоянием между векторами.
В задаче разделения группы людей на дружественные компании удобнее использовать графовое представление пространства, объекты считая вершинами, а ребра устанавливая в случае выполнения условия (дружбы), возможно, с некоторым «весом». Тогда естественное расстояние между двумя объектами – длина кратчайшего пути между соответствующими вершинами графа.
Кластерный анализ как поиск оптимальной классификации
Прежде чем формально определить кластерный анализ, введем еще одно понятие – критерий качества классификации относительно метрики  . Критерий качества  должен отражать насколько объекты одного класса близки друг к другу, а объекты разных классов друг от друга далеки. Классификация, оптимизирующая функционал качества, таким образом, группирует каждое скопление объектов в соответствующий класс.
Наконец, можно сформулировать следующее определение: кластеризация – поиск классификации, оптимальной относительно критерия качества. То есть кластеризация  , где
Особенности кластеризации
Окончив формальное описание, мы можем сказать о некоторых отличительных особенностях кластеризации. Итак, было замечено, что каждый объект классифицируется однозначно и значение соответствующей признаковой функции определяется его внутренними свойствами и не зависит от всего множества объектов. Не так при кластеризации. Процесс минимизации критерия качества требует знания всего пространства объектов. Замена нескольких объектов в может привести и к изменению оптимальной классификации.
Кластеризация существенно зависит от заданной метрики и критерия качества  . Но структура этой зависимости непредсказуема и универсальных параметров нет.
Наконец, отыскание глобального минимума критерия качества не всегда возможно, особенно, когда пространство объектов велико. В таком случае ведется поиск локального минимума одним из оптимизационных алгоритмов.
|
