7.1.2. Меры близости, основанные на расстояниях, используемые в алгоритмах кластеризации
Расстояния между объектами предполагают их представление в виде точек m-мерного пространства Rm. В этом случае могут быть использованы различные подходы к вычислению расстояний.
Рассмотренные ниже меры определяют расстояния между двумя точками, принадлежащими пространству входных переменных. Используются следующие обозначения:
— множество данных, являющееся подмножеством m-мерного
вещественного пространства;
— элементы множества данных;
— среднее значение точек данных;
— ковариационная матрица{т x т).
Итак, приведем наиболее известные меры близости.
Евклидово расстояние. Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
(7.1)
Расстояние по Хеммингу. Это расстояние является просто средним разностей по координатам. В большинстве случаев данная мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида, однако для нее влияние отдельных больших разностей (выбросов) уменьшается (т. к. они не возводятся в квадрат). Расстояние по Хеммингу вычисляется по формуле:
(7.2)
Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как "различные", если они различаются по какой-либо одной координате (каким-либо одним измерением). Расстояние Чебышева вычисляется по формуле:
(7.3)
Расстояние Махаланобиса преодолевает этот недостаток, но данная мера расстояния плохо работает, если ковариационная матрица высчитываете» на всем множестве входных данных. В то же время, будучи сосредоточенной на конкретном классе (группе данных), данная мера расстояния показывает хорошие результаты:
(7.4)
Пиковое расстояние предполагает независимость между случайными переменными, что говорит о расстоянии в ортогональном пространстве. Но в практических приложениях эти переменные не являются независимыми:
(7.5)
Любую из приведенных мер расстояния можно выбирать с уверенностью лишь в том случае, если имеется информация о характере данных, подвергаемых кластеризации.
Так, например, пиковое расстояние предполагает независимость между случайными переменными, что говорит о расстоянии в ортогональном пространстве. Но в практических приложениях эти переменные не являются независимыми.
7.2. Представление результатов
Результатом кластерного анализа является набор кластеров, содержащих элементы исходного множества. Кластерная модель должна описывать как сами кластеры, так и принадлежность каждого объекта к одному из них.
Для небольшого числа объектов, характеризующихся двумя переменными, результаты кластерного анализа изображают графически. Элементы представляются точками, кластеры разделяются прямыми, которые описываются линейными функциями. Для примера с данными из табл. 7.1 результат кластеризации можно представить диаграммой, изображенной на рис. 7.1.
Если кластеры нельзя разделить прямыми, то рисуются ломаные линии, которые описываются нелинейными функциями.
В случае если элемент может принадлежать нескольким кластерам, то можно использовать Венские диаграммы, например, как на рис. 7.2.
Некоторые алгоритмы не просто относят элемент к одному из кластеров, а определяют вероятность его принадлежности. В этом случае удобнее представлять результат их работы в виде таблицы. В ней строки соответствуют элементам исходного множества, столбцы — кластерам, а в ячейках указывается вероятность принадлежности элемента к кластеру.
Ряд алгоритмов кластеризации строят иерархические структуры кластеров. В таких структурах самый верхний уровень соответствует всему множеству объектов, т. е. одному-единственному кластеру. На следующем уровне он делится на несколько подкластеров. Каждый из них делится еще на несколько и т. д. Построение такой иерархии может происходить до тех пор, пока кластеры не будут соответствовать отдельным объектам. Такие диаграммы называются дендрограммами (dendrograms). Этот термин подчеркивает древовидную структуру диаграмм (от греч. dendron — дерево).
Существует много способов построения дендрограмм. Для примера с ирисами дендрограмма будет выглядеть так, как показано на рис. 7.3.