Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок, который называют целевой функцией. Например, в качестве целевой функции может быть взята внутригрупповая 2 > ,Т сумма квадратов отклонения: ‘~ л V» где X ] представляет собой измерения ]-го объекта. Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности. Понятно то, что объекты 1-ый и ры й попадали бы в один кластер, когда расстояние (отдаленность) между точками X, и X; было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х1 и Xj из Ер, где Ер р-мерное евклидово пространство. Неотрицательная функция б(Х(, ХД называется функцией расстояния (метрикой), если: а) б(Х ;, ХД > 0, для всех X, и Xj из Ер б) сЗ(Х;, ХД = 0, тогда и только тогда, когда X, = X; в) е д , х д = е д , ХО г) б(Х[, ХД < с!(Х(, Хк) + б(Хк, ХД, где Х^; Х; и Хк любые три вектора из Ер. Значение б(Х!? Xj) для Х-, и X] называется расстоянием между X,и Xj и эквивалентно расстоянию между б* и в; соответственно выбранным характеристикам (Рь Р2, Р з,..., Рр). Наиболее часто употребляется функция Евклидова расстояния: 179 ¿2(Х1,Х])= Пусть п измерений Х и Хл представлены в виде матрицы данных размером р х п: |
предположений о наличии некоторой структуры в изучаемой совокупности объектов, т.е. поиск существующей структуры; построение новых классификаций для слабоизученных явлений, когда необходимо установоть наличие связей внутри совокупности и попытаться привнести в нее структуру. Вычислительная задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множествеЛГ, разбить множество объектов G на т (т целое) кластеров (подмножеств) Qh Q2. ..., QMJ так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам, были разнородными. Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый фушщионал, выражающий уровни желательности различных разбиений и группировок, который называют целевой функцией. Налример, в качестве целевой функции может быть взята внутригрупповая сумма квадратов Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности. Понятно то, что объекты i-ый и у'-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Х\ и.Xj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между X, н Xj из Ер, где Е р р мерное евклидово пространство. Неотрицательная функция |