АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Расстояние между объектами (кластерами) и мера близости

Читайте также:
  1. I Раздел 1. Международные яиившжоши. «пююеям как процесс...
  2. I. О различии между чистым и эмпирическим познанием
  3. II. Типы отношений между членами синтагмы
  4. III. Разрешение споров в международных организациях.
  5. IV. О различии между аналитическими и синтетическими суждениями
  6. Анализ взаимосвязей между показателями эффективности инвестиционно-инновационных проектов и показателями эффективности хозяйственной деятельности предприятия
  7. Анализ взаимосвязи между обобщающими, частными показателями экономической эффективности деятельности предприятия и эффективностью каждого научно-технического мероприятия
  8. Анализ затрат с учетом международных стандартов
  9. Анализ равновесия между активами предприятия и источниками их формирования. Оценка финансовой устойчивости предприятия
  10. Анализ стратегических альтернатив международной деятельности
  11. Анализ функциональной связи между затратами, объемом продаж и прибылью. Определение безубыточного объема продаж и зоны безопасности предприятия
  12. Анализ функциональной связи между издержками и объемом производства продукции

 

Наиболее трудным и наименее формализованным в задаче классификации является определение понятия однородности объектов.

В общем случае понятие однородности объектов задается введением либо правила вычисления расстояний ρ(xi, хj) между любой парой исследуемых объектов (x1, x2,...,xn), либо некоторой функцией r(хi, xj), характеризующей степень близости i -го и j -го объектов.

Если задана функция ρ(xi, хj), то близкие с точки зрения этой метрики объекты считаются однородными, принадлежащими к одному классу. Очевидно, что необходимо при этом сопоставлять ρ(xi, хj) с некоторыми пороговыми значениями, определяемыми в каждом конкретном случае по-своему.

Аналогично используется и мера близости r (xi, хj), при задании которой мы должны помнить о необходимости выполнения следующих условий: симметрии r (xi, хj) = r(xj, хi); максимального сходства объекта с самим собой r (xi, хi) = r (xi, хj), 1 ≤ i, j ≤ п, и монотонного убывания r (xi, хj) по мере увеличения ρ (xi, хj), т.е. из ρ (xk, хl) ≥ ρ (xi, хj) должно следовать неравенство r (xk, хl) ≤ ρ (xi, хj).

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

Рассмотрим наиболее широко используемые в задачахкластерногоанализа расстояния и меры близости.

Обычное евклидово расстояние определяется по формуле

 

(53.43)

 

где xil, хjl значения l -го признака у i -го (j -го) объекта (l = 1, 2,..., k, i,j = 1, 2,.... п).

Оно используется в следующих случаях:

а) наблюдения берутся из генеральной совокупности, имеющей многомерное нормальное распределение с ковариационной матрицей вида σ2 Ek, где Еk единичная матрица, т.е. исходные признаки взаимно независимы и имеют одну и ту же дисперсию;

б) исходные признаки однородны по физическому смыслу и одинаково важны для классификации.

Естественное с геометрической точки зрения евклидово пространство может оказаться бессмысленным (с точки зрения содержательной интерпретации), если признаки измерены в разных единицах. Чтобы исправить положение, прибегают к нормированию каждого признака путем деления центрированной величины на среднее квадратическое отклонение и переходят от матрицы Х к нормированнойматрице с элементами

 

 

где xil значение l -го признака у i -го объекта;

— среднее значение l -го признака;

— среднее квадратическое отклонение l -го признака.

Однако эта операция может привести к нежелательным последствиям. Если кластеры хорошо разделимы по одному признаку и не разделимы по другому, то после нормирования дискриминирующие возможности первого признака будут уменьшены в связи с усилением «шумового» эффекта второго.

«Взвешенное» евклидово расстояние определяется из выражения

 

(53.44)

 

Оно применяется в тех случаях, когда каждой l -й компоненте вектора наблюдений Х удается приписать некоторый «вес» ω1, пропорциональный степени важности признака в задаче классификации. Обычно принимают 0 ≤ ω l ≤ 1, где l = 1,2,..., k.

Определение весов, как правило, связано с дополнительными исследованиями, например с организацией опроса экспертов и обработкой их мнений. Определение весов ω l только по данным выборки может привести к ложным выводам.

Хеммингово расстояние используется как мера различия объектов, задаваемых дихотомическими признаками. Это расстояние определяется по формуле

 

(53.45)

 

и равно числу несовпадений значений соответствующих признаков в рассматриваемых i -м и j- м объектах.

Как правило, решение задач классификации многомерных данных предусматривает в качестве предварительного этапа исследования реализацию методов, позволяющих выбрать из k исходных признаков x1, x2,..., xk сравнительно небольшое число наиболее информативных, т.е. уменьшить размерность наблюдаемого пространства.

В ряде процедур классификации (кластер-процедур) используют понятия расстояния между группами объектов и меры близости двух групп объектов.

Пусть Si — i- я группа (класс, кластер), состоящая из ni объектов;

— среднее арифметическое векторных наблюдений группы Si, т.е. «центр тяжести»;

ρ(Sl, Sm) — расстояние между группами Sl и Sm.

Наиболее употребительными расстояниями и мерами близости между классами объектов являются:

• расстояние, измеряемое по принципу «ближайшего соседа»:

 

(53.46)

 

• расстояние, измеряемое по принципу «дальнего соседа»:

 

(53.47)

 

• расстояние, измеряемое по «центрам тяжести» групп:

 

(53.48)

 

где xl и xm векторы средних соответственно Sl и Sm кластеров;

• расстояние, измеряемое по принципу «средней связи», определяемое как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп:

 

(53.49)

 

Академиком А.Н. Колмогоровым было предложено «обобщенное расстояние» между классами, которое включает в себя в качестве частных случаев все рассмотренные выше виды расстояний.

Расстояния между группами элементов — особенно важный параметр в так называемых агломеративных иерархических кластер-процедурах, так как принцип работы таких алгоритмов состоит в последовательном объединении элементов, а затем и целых групп: сначала — самых близких, а впоследствии — все более и более отдаленных друг от друга. При этом расстояние между кластером Sl и кластером S(m,q), являющимся объединением двух других кластеров — Sm и Sq можно определить по формуле

 

(53.50)

 

где ρ lm = ρ (Sl, Sm); ρ lq = ρ (Sl, Sq) и ρ mq = ρ (Sm, Sq) - расстояния между кластерами Sl, Sm и Sq;

α, β, γ и δ — числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм.

Например, при α = β = -δ = 1/2 и γ = 0 приходим к расстоянию, построенному по принципу «ближайшего соседа». При α = β = δ = 1/2 и γ = 0 расстояние между классами определяется по принципу «дальнего соседа», т.е. как расстояние между двумя самыми дальними элементами этих классов.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)