Диссертация (792540), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

rx=0 и ry=0. Это означает, что точкиобразуют«облако»разбросанныхточек.коэффициента линейной корреляции Пирсона,Используявыражениедля158rx ry 21xi x j  xn i, j x221yi y j  yn i, j y2,(4.26),(4.27)r 2  rx2  ry2 ,(4.28)21xxx i j  0,n i, j(4.29)21yi y j  y  0 .n i, j(4.30)получимПодставив в выражение I1 выражения  xi x j  nxi, j2иy yi2j ny ,i, jполучим, что I1=2I2, что доказывает эквивалентность этих критериев длякластеров типа «облака». Если корреляция между точками существенная, т.е.когда точки образуют вытянутые области, то эти критерии различны.4.3 Решение экстремальной задачи о «центре», сумма расстояний от которогодо k точек плоскости минимальноЗадано n точек на плоскости A1, A2 … An с координатами Ai=(xi, yi).Необходимо найти координаты центра O=(x, y) такого, что сумма расстоянийот центра до всех точек была бы минимальной159nE   d ( Ai , O)  min .(4.31)iРанее были рассмотрены различные метрики расстояния между двумяточками в m-мерном пространстве.

Применим их для случая m=2.Евклидово расстояние. В этом случае необходимо найтиnE   ( xi  x) 2  ( yi  y ) 2  min .(4.32)iПрименим необходимое условие минимума и получим систему двухуравнений с двумя неизвестными x и y:E nx i 1E ny i 1( xi  x)( xi  x)  ( yi  y )22( yi  y )( xi  x) 2  ( yi  y ) 2 0,(4.33) 0.(4.34)При любом числе точек эта система содержит лишь две переменные илегко решается численными методами. Если каждая точка Аi имеет «вес» Vi,то, как легко показать, система, определяющая минимумnEV  Vi ( xi  x) 2  ( yi  y ) 2  min(4.35)iимеет видnEx i 1Vi ( xi  x)( xi  x)  ( yi  y )22 0,(4.36)160nEy i 1Vi ( yi  y )( xi  x) 2  ( yi  y ) 2 0.(4.37)Квадрат евклидова расстояния.

В этом случае необходимо найтиnE   ( xi  x) 2  ( yi  y ) 2  min .(4.38)iАналогично, применяя необходимое условие минимума, получаемnE  ( xi  x)  0 ,x i 1(4.39)nE  ( xi  y )  0 .y i 1(4.40)Откуда сразу получаем решение1 n xi ,n i 1(4.41)1 ny   yi .n i 1(4.42)xТаким образом, среднеарифметический центр точек минимизируетсумму квадратов евклидовых расстояний от этого центра до точек. Этот выводлежит в основе всего метода кластеризации, принятого в настоящей работе.Легко показать, что если каждая точка Аi имеет «вес» Vi, то координатысвоеобразного «центра тяжести» определяются формулами:161nxV xi ii 1nV,(4.43).(4.44)ii 1nyV yii 1niVi 1iДалее рассмотрим так называемое расстояние городских кварталов(Манхэттенское расстояние).

Здесь нужно минимизировать суммуnE   | xi  x |  | yi  y | min .(4.45)iПрименяя необходимое условие минимума, получаем нелинейнуюсистему уравнений:E n ( xi  x) 0,x i 1 | xi  x |(4.46)E n ( yi  y ) 0.y i 1 | yi  y |(4.47)Для точек с весом Vi получаем систему, решая которую, получаемкоординаты центра в случае городских кварталов:nEx i 1nEy i 1Vi ( xi  x)( xi  x) 2  ( yi  y ) 2Vi ( yi  y )( xi  x)  ( yi  y )22 0,(4.48) 0.(4.49)1624.4 Обоснование метода кластеризации k-средних (k-means) для решениязадач выбора месторасположения терминально-логистических объектовВо-первых, докажем идентичность критерия Q1 – «сумма квадратоврасстояний от точек до центра, определяемого как центр тяжести точек» и Q2– критерия «суммы квадратов расстояний между точками»:KQ1  S   kKQ2 ( S )  k 1d2X i Sk( X i , X j )Sk(Xi, Xk ),(4.50)d 2(Xi, X j ) .(4.51)ПустьmQl   ( xilk  xl )2 – сумма квадратов расстояний всех m признаков отkk 1 iGlточки i до центра кластера l.

Тогда,KQ1   Ql , где K – количество кластеров, аl 1KQ2  l 1nl  1Ql ; где nl – количество точек в l – м кластере.2Откуда получаем, что если количество точек в кластерах одинаково(nl=n0), то Q1 и Q2 эквивалентны, т.к. Q1  min равносильно Q2  min . Есличисло точек в кластерах различно, то они отличаются, но несущественно.Практические эксперименты подтверждают это.Как показано в [5], методы кластеризации на основе функционаловкачества разбиений вышеприведенного вида Q1 и Q2 позволяют получитьоптимальные разбиения, обладающие свойством несмещенности. Это значит,что можно найти вектор средних (центров) и получить минимальные163дистанционные разбиения «с точностью до множества меры нуль», т.е. слюбой точностью.Остановимся на вопросе о соотношении результатов, полученных прикластеризации по минимуму суммы квадратов расстояний от точек до центров(например, алгоритма k-means) и достигаемых при этом величинах суммырасстояний от точек до центров.

С практической точки зрения, именно, этавеличина определяет экономические показатели оптимизации разбиений.Рассмотрим величины:Среднее арифметическое чисел x1…xn – это величинаnxxii 1.n(4.52)Среднее квадратическое – величинаnsxi 12i.n(4.53)Известно, что среднее арифметическое не превышает среднегоквадратическогоxs.(4.54)Равенство достигается лишь при равенстве чисел xi=x.Из (4.54) вытекает, чтоnxi 1in n xi2 .i 1(4.55)164Величины x и s имеют свойстваxmin  s  xmax ,xmin  x  xmax .(4.56)Откуда следует, чтоn x2minnn  x  nxi 12i2maxn  xmin   xi  nxmax .,(4.57)i 1Рассмотренный алгоритм k-means обеспечивает разбиения на кластерыиз условия минимума суммы квадратов расстояний от точек до «центратяжести». Возникает вопрос о том, какова будет при этом величина суммырасстоянийотточекдоцентров.nОчевидно,вышеприведенный анализ выражений  xi2 иi 1nx2ii 1наэтодаетn x .

Действительно, минимумi 1inне совпадает с минимумом x , но гарантирует, чтоii 1nxi 1гдеответin min n xi2 ,Gi 1(4.58)G – всевозможные разбиения точек на заданное число кластеров.Поэтому правая часть последнего неравенства может служить верхнейграницей достигнутой величины суммарного расстояния от точек до центра.Возведем в квадрат выражение (4.55) и получим, что различие междуxnni 1i 122и s можно оценить разностью   n xi  ( xi ) .1654.5 Практические методы кластерного анализа для решения задачоптимального размещения терминально-логистических объектовМетоды и алгоритмы кластерного анализа изучены и описаны вобширной литературе как отечественных, так и зарубежных авторов.Основополагающими обзорами этих методов являются работы [5], [42], [111],[117]. В последнее время появилось множество программных систем, которыевключают модули кластеризации («Clastering»), в которых как опции задаютсявышеприведённые метрики расстояний, функционалы качества кластеризациии типы алгоритмов.

В дальнейшем при сравнении методов будемориентироваться на готовые программные средства, поэтому рассмотренытолько некоторые алгоритмы кластеризации, которые в дальнейшем будутиспользованы.В таблице 4.1 представлены некоторые программные системы иперечислены используемые в них алгоритмы.Таблица 4.1 – Программные системы с модулями кластерного анализа№1123Программы2Функции3- k-means clastering- EM (Expectation Optimization) – максимизация ожиданий- Joining (tree clastering) – объединение (иерархическаяSTATISTIKAкластеризация)- Two way joining (двухвходовое объединение) выбираются 7опций мер сходства и 6 видов метрик (расстояний)- Сobweb- DB Scan- EM- Fartest FirstWEKA- Filtered clusterer- Make Dansity Based Clusterer- OPTICS Simple- K-Means- X-MeansOrange Data- Hierarchical ClusteringMining166Продолжение таблицы 4.1145623- Самоорганизующаяся карта КохоненаDeductor- К-meansStudio- G-means- EM- Метод К-средних Мак-КуинаEXCEL+- Метод ближней связиAtteStat- Метод средней связи Кинга- Метод Уорда, есть все опции для выбора метрикИерархический кластерный анализ:Для определения расстояния между парой кластеров в SPSSпредусмотрены следующие методы:- Среднее расстояние между кластерами (Between-groupslinkage), устанавливается по умолчанию.- Среднее расстояние между всеми объектами пары кластеров сучетом расстояний внутри кластеров (Within-groups linkage).- Расстояние между ближайшими соседями - ближайшимиобъектами кластеров (Nearest neighbor).- Расстояние между самыми далекими соседями (FurthestSPSS–Statistics 17.0 neighbor).- Расстояние между центрами кластеров (Centroid clustering)или центроидный метод.

Недостатком этого метода является то, чтоцентр объединенного кластера вычисляется как среднее центровобъединяемых кластеров, без учета их объёма.- Метод медиан – тот же центроидный метод, но центробъединенного кластера вычисляется как среднее всех объектов.- Метод Варда.- Среднее расстояние между кластерами (Beetwin groupslincage).Метод k-средних4.6 Метод k-средних (k-means)В работе рассмотрены методы, основанные на так называемыхэталонных методах кластерного анализа. В них процесс кластеризацииначинается с некоторого своеобразного эталона совокупности кластеров – аименно, с задания центров этих кластеров.

Далее происходит итеративныйпроцесс изменения состава и центров кластеров до выполнения некоторого167правила остановки. Поэтому эти алгоритмы еще называют итеративнымиалгоритмами квадратичной ошибки.Методk-средних(k-means)-наиболеепопулярныйметодкластеризации в этой группе методов. Он был изобретён в 1950-х годахматематиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.Особую популярность и свое название он приобрёл после работы Мак-Куина[232] в 1967 году.Процесс кластеризации в этой группе методов начинается с заданиянекоторых начальных параметров: количество получаемых кластеров, порогзавершения процесса кластеризации и т.д. При этом в отличие от другихметодов кластеризации, например, иерархического метода, метод k-средних нетребует вычисления и хранения матрицы расстояний между объектами.Алгоритмметодаиспользуетk-среднихтолькоисходныезначенияхарактеристик объектов [19].Действие алгоритма таково, что он стремится минимизироватьсуммарное квадратичное отклонение точек кластеров от центров этихкластеров:KmQ     ( xijk  xjk ) 2  min ,(4.59)k 1 iGk j 1гдеxjk - координаты центра тяжести k-го кластера;K - число кластеров;Gk - полученные кластеры, k=1, 2, …;xk* - центры масс векторов – точек xi в m-мерном пространствеxi=(xi1,xi2,…xim).Для случая точек на плоскости m=2 с декартовыми координатами (xi,yi)KQ    ( xik  xk* ) 2  ( yik  yk* ) 2  min .k 1 iGk(4.60)168Центры кластеров называют также главными точками, поэтому и самэтот метод кластеризации иногда называют методом главных точек [5].Метод k-средних разбивает множество элементов векторного пространства назаранее известное число кластеров K.Начиная с некоторого «эталонного» разбиения, на каждой итерацииметода k-средних перевычисляется «центр масс» для каждого кластера,полученного на предыдущем шаге.

Затем векторы разбиваются на кластерывновь в соответствии с тем, какой из новых центров оказался ближе повыбранной метрике.Алгоритм завершается, когда на какой-то итерации не происходитизменения разбиения на кластеры. Так как количество возможных разбиенийконечного множества конечно, а на каждом шаге суммарное квадратичноеотклонение Q не увеличивается, поэтому решение задачи происходит законечное число итераций, и зацикливание невозможно.Как показано в [234], для некоторых классов исходных множествсложность этого алгоритма по времени определяется как2 n.Для начала процедуры кластеризации должны быть заданы kвыбранных объектов, которые будут служить эталонами, т.е.

центрамикластеров. Несмотря на сходимость алгоритма к некоторому решению, строгоговоря, полученное решение зависит от выбранного первоначального эталона,и поэтому является локально-оптимальным. В этом случае важную рольиграет выбор начальных условий и изучение результатов, получаемых придругих эталонах. Представляет также научный интерес оценки глобальногоминимума и получения среднестатистических результатов оптимизации.1694.6.1 Математическое описание алгоритма метода k-средних и егомодификацииПусть имеется n объектов, каждый из которых характеризуется mпризнаками X1, X2,…, Xn. Таким образом, эти объекты задаются n точками в mмерном пространстве.

Характеристики

Список файлов диссертации