Кластеризация как нечеткая классификация

Кластерный анализ — бурно развивающаяся область прикладной математики, тем не менее, специалисты обычно не оперируют какими-либо строгими определениями, опираясь лишь на интуитивное представление о кластеризации. Кластеризация — это нечеткая классификация, некоторое её приближение, основанное на взаимном расположении классифицируемых объектов. В основном своем значении термин cluster может быть переведен как скопление. Близкие объекты относятся к одному классу, а далекие объекты, наоборот, — к разным классам. Для этого между объектами должно быть введено некоторое расстояние. Результат кластеризации существенно зависит от выбора метрики.

Чтобы сформулировать и другие параметры процедуры кластерного анализа, нам следует в первую очередь определить самое базовое понятие — классификацию.

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

Обычно при классификации вводят некоторые ограничения. Во-первых, должно однозначно определяться состояние объекта по отношению к признаку, т. е. группы не могут пересекаться. Во-вторых, состояние может зависеть только от внутренних свойств объекта и не должно прямо зависеть от других выбранных объектов. Условно говоря, разделение чисел на четные и нечетные — это классификация, т.к. четность числа не зависит от того, какие числа выбраны для проверки, а распределение чисел на большие и меньшие не является классификацией, потому что не выполняется ни одно из условий. Классификацию как логическое действие называют делением, а как математическую операцию — факторизацией.

Простейший пример факторизации — остатки от деления по модулю. Здесь множество объектов классификации — это натуральные числа, а признак, относительно которого происходит классификация — это остаток от деления по некоторому модулю. Если число имеет остаток 1, то оно относится к первой группе, если остаток 2, то ко второй и т. д. Каждое число может иметь ровно один остаток, поэтому оба ограничения выполнены, т. е. перед нами действительно классификация.

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

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

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

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

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

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

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

Метрическое пространство объектов.

Итак, в некоторых задачах нам необходимо ввести понятие расстояния между объектами. Двум объектам, поставим в соответствие некоторое число. Естественно задать расстояние так, что для него выполнены стандартные свойства метрики, в частности, расстояние объекта до самого себя должно быть нулевым. Чем ближе объекты, тем скорее их следует отнести в одну группу и наоборот, чем они дальше друг от друга, тем скорее их следует отнести в разные группы.

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

В задаче разделения группы людей на дружественные компании удобнее использовать графовое представление пространства, объекты считая вершинами, а ребра устанавливая в случае выполнения условия (дружбы), возможно, с некоторым «весом». Тогда естественное расстояние между двумя объектами — длина кратчайшего пути между соответствующими вершинами графа.

Кластерный анализ как поиск оптимальной классификации.

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

Наконец, можно сформулировать следующее определение: кластеризация — поиск классификации, оптимальной относительно критерия качества. То есть кластеризация, где.

Особенности кластеризации.

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

Кластеризация существенно зависит от заданной метрики и критерия качества. Но структура этой зависимости непредсказуема и универсальных параметров нет.

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