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

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

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

Отметим, что в качестве «расстояния» между i и p можноиспользовать и другие показатели: затраты на перевозку между i и p, время,затрачиваемое на перевозку из i в p, и другие.Использование непосредственно матрицы расстояний D меняетматематические преобразования в алгоритмах кластеризации, но не вызываеттрудностей для работы алгоритмов.Для математического определения кластеров следует рассмотретьвиды искомой кластерной структуры [117].149Кластерный анализ (clastering) – предполагает, во-первых, точноематематическое определение понятия кластера. Дело в том, что различныепостановки задач могут использовать математически различные определениякластера.

Вот почему, прежде чем перейти к практическим задачамразмещения транспортно-логистических объектов, рассмотрим проблематикуопределения понятия кластера и самой процедуры кластеризации. Здесьнеобходимо рассмотреть следующие основополагающие проблемы:1.точноематематическоеопределениеисходногомножестваобъектов и его кластеров;2.вопрос о том, является ли заданным количество кластеров;3.математическое описание функционала качества кластеризации.Кластерный анализ выделяет компактные группы объектов путёмразбиения всего множества объектов на подмножества скопления объектов.Для использования кластерного анализа исходные данные представляются ввиде расстояний между объектами или матриц близости.

Наибольшеераспространение получили данные первого вида. В этом случае кластерныйанализ позволяет выделить некоторые геометрически удаленные группы,внутри которых объекты близки [42], [111].Дадимболеестрогиеопределениякластера,которыеможноиспользовать для оценки качества разбиения.Определение 1. Кластером называется группа (подмножество) объектовGk, такая, что выполняется неравенство: средний квадрат внутригрупповогорасстояния до центра группы меньше среднего квадрата расстояния до общегоцентра исходной совокупности объектовd k2  d 2 ,(4.4)Gk  G .(4.5)150Чем больше среди всяких групп (подмножеств) Gl кластеров Gk, темболее успешным можно считать разбиение (кластеризацию-clastering).Gl  G .(4.6)lТакое определение предполагает, что не обязательно каждый объектпринадлежит какому-нибудь кластеру [4].Определение 2. Группа объектов Gp называется «сгущением», еслимаксимальный квадрат расстояния от объектов из Gp до центра группы меньшесреднего квадрата расстояния от объектов исходной совокупности до общегоцентраmax d 2 ( X p , X i )  d 2 .X i G p(4.7)Определение 3.

Кластер – это такое скопление точек Gk, в которомсреднее межточечное расстояние меньше среднего расстояния от точеккластера до остальных точек исходного множества.d (X i , X j )  d ( X i , X q ) ,(4.8)( X i , X j )  Gk ,(4.9)X q  Gk .(4.10)Определение 4. Кластер «сгущение» – это группа объектов (класс,подмножество), где все расстояния между объектами этой группы меньшелюбого расстояния между объектами кластера и объектами остальной частимножества. Кластеры такого вида еще называют компактной группой или151классом типа ядра. Такими кластерами на рисунке 4.1 являются А и В.Заметим, что классы Е, С, L, M не разделяются с помощью этого определения.На основе этого определения нельзя различить В и С, пересекающиеся классыК и Н, и отличить большие классы от малых R и O [111].Определение 5.

Кластер с центром. Пусть заданы порог τ>0 и некотораяточка пространства, занимаемого объектами кластера Gk (в частном случаеэлемент этого кластера), - Xk*, такая, что если X i  Gk , то d(Xi, Xk*)<τ, а еслиX i  Gk , то d(Xi,Xk*)>τ. Точка Xk* называется центром класса. Эта точка можетбыть центром тяжести класса, определяемым как средневзвешенное признаковобъектов класса.

Так, на рисунке 4.1 в паре В и С класс В является классом сцентром, а С таковым не является. В паре Е и Р класс Р – с центром, а класс Е– нет [111].Определение 6. Кластер «слабое сгущение». Пусть τ>0 такое, что длялюбого X i  Gk найдется такой объект X j  Gk , что d(Xi,Xj)<τ, а для любогоX q  Gk справедливо d(Xi,Xq)>τ. Кластеры В, С, Е, Р, К, Н, показанные нарисунке 4.1, представляют собой слабые сгущения.Определение 7. Кластер «сгущение в среднем».

Здесь среднеерасстояние внутри кластера меньше среднего расстояния от объектовкластера до всех остальных объектов. Многие кластеры, показанные нарисунке 4.1, являются сгущением в среднем, кроме пары E и F [111].Определение 8. Сильным кластером называют такой, для которогосреднее внутреннее расстояние не менее, чем в b>1 раз меньше среднегорасстояния от любого объекта, не принадлежащего кластеру, до всех объектовкластера (например, b=2) [111].Определение 9. Кластером типа среднего сгущения с центромназывается кластер, в котором среднее расстояние до центра объектовкластера меньше, чем их среднее расстояние до центра остальных объектов[111].152Определение10.Кластер«изолированноеоблако».ДлянегоX  Gkсуществует τ>0 такое, что для X i  Gk и q, d(Xi, Xq)>τ.

Это определениепредполагает самое слабое требование: учитывается только внешняяизоляция, внутренняя плотность кластера не важна. На рисунке 4.1 такимисвойствами обладают все непересекающиеся кластеры [111].РЕFKRQHOВАCMLРисунок 4.1 – Различные формы кластеровПриведенные типы определений исчерпывают основные способывыделения кластеров и дают пищу для конкретного моделирования вприкладных задачах. Необходимо заметить, что в вышеупомянутыхопределенияхсреднююможнозаменитьмедианой,использоватьвышеприведенные понятия радиуса кластера, размера кластера и др.Определения кластеров можно ввести и для случая, когда используетсяне расстояние между объектами d(a,b), а мера близости между ними μ(a,b) [2],[111], [117].Само качество разбиения исходного множества объектов на кластерыоценивается по некоторому критерию.

Поэтому «хорошая» классификацияопределяется не только определением отдельных классов, но и введениемнекоторого функционала, экстремальное значение которого соответствуетнаилучшей классификации.153Впоследнеевремявкластер-анализеиспользуютсятолькооптимизационные критерии, хотя вначале развивались методы, основанные наматематическихопределенияхпонятия«кластер»,атакжечистоэвристические методы, в которых каждый шаг построения кластеровсоответствовал интуитивному представлению о них [111], [117].Естественно, попытаться определить качество различных способовразбиениязаданногомножестваобъектовнакластерынаосновеколичественного критерия.

Для этого в математическую постановку задачикластеризации необходимо ввести понятие функционала качества разбиенияQ(S), определенного на множестве всех возможных разбиений. Тогда поднаилучшим разбиением S* понимается такое, при котором достигаетсяэкстремум функционала качества [52].Выборфункционалакачествакластеризации,какправило,основывается на опыте и профессионально-интуитивных соображениях.Приведем примеры наиболее распространенных функционалов качестваразбиения и попытаемся обосновать выбор из них для решения поставленнойв работе задачи.Пусть выбрана метрика расстояний d в m-мерном пространстве X ипусть S=(S1,S2,…,SK) – некоторое фиксированное разбиение всех наблюденийX=(X1,X2,…,Xn) на заданное число классов K (K<<n).

Каждое наблюдение i-гообъекта характеризуется m количественными параметрами так, что всяинформация об классифицируемых объектах – это матрица X размерностиn×m.1.Сумма («взвешенная») внутриклассовых дисперсийKQ1  S   kdX i Sk2(Xi, Xk ).(4.11)1542.Сумма попарных внутриклассовых расстояний между элементамиKQ2 ( S )  k 1( X i , X j )Skd 2(Xi, X j ) ,(4.12)либоK1d 2(Xi, X j ) .k 1 nk ( X i , X j )SkQ '2 ( S )  (4.13)Как показывают результаты кластеризации функционалы Q2(S) и Q’2(S)приводят к тем же наилучшим разбиениям, что и Q1(S).

Ниже будет показано,что при определенных условиях эти критерии идентичны.3.Обобщеннаявнутриклассовая дисперсияQ3(S) является, какизвестно, одной из характеристик степени рассеивания многомерныхнаблюдений одного класса около своего «центра тяжести».1 KQ3 ( S )   ,K k 12k1 K 1 m 1 K k 1 m j 1 nknk(xi 1ij x j )2 .(4.14)Во многих прикладных задачах неизвестно на какое число классовнеобходимо разбить исходное множество. Например, в задаче оптимизациизатрат на доставку грузов от клиентов (грузовладельцев) на КТ, количествокластеров определяет количество КТ.

Но не факт, что при каком-то заданномих количестве затраты на доставку будут минимальны. Приходитсяварьировать количество КТ – кластеров. В этом случае, функционалы качестваразбиения Q(S) необходимо выбирать в виде алгебраической комбинации двухфункционалов I1(S) и I2(S), один из которых I1 является убывающей функциейчисла кластеров и характеризует внутриклассовый разброс параметров, авторой I2 – возрастающей функцией числа кластеров.Под I2 понимается некоторая мера взаимной удаленности (близости)кластеров.155В [5] предлагается братьKIi (S )  dk X i Sk-(Xi, Xk )суммарное расстояние от точек кластеров до своих центров иI 2 ( S )  ck  S -(4.15)(4.16)число кластеров, получающихся при разбиении S, а с – некотораяположительная величина, характеризующая потери при увеличении числакластеров на единицу.4.2 Связь функционалов качества кластеризации с экономическимикритериями в задаче выбора местоположения терминально-логистическихобъектовВыше была поставлена задача «привязки» клиентов к региональнымКТ.

В качестве критерия оптимизации целесообразно выбрать критерийминимума затрат на доставку грузов клиентов на КТ. Величина этих затратвыражается в затратах тонно-километров. Т.е. если каждый клиент перевозитобъем груза Vi до КТ, расположенного в центре кластера Xk*, то суммарныезатраты на перевозку определяются выражениемKЕ V d(X , Xk 1 X i Skiik*)  min .(4.17)156Отсюда следует, что разбиение на кластеры должно быть таким, чтобыименно величина Е была минимальна.Покажем, что при заданном числе кластеров необходимым условиемминимума функции Е является то, что центры кластеров должны находитьсяв «центрах тяжести» кластеров.Пусть координаты i-го клиента определяются в плоской системекоординат xi, yi и имеют «вес» Vi. Следовательно, имеем случай кластеризацииn объектов (клиентов), каждый из которых характеризуется двумяпараметрами (m=2) на K кластеров.Центры тяжести кластеров определяются формулами:x  xk*kV xViGki iiGky  yk*kV yViGkiGk,(4.18).(4.19)iiiiЗаметим, что, вообще говоря, наилучшее качество кластеризации,выраженное функционалами (4.11), (4.12), (4.14), может не совпадать скачеством кластеризации в интересах минимума величины Е.Рассмотрим две критериальные величины:Сумма квадратов расстояний между всеми точками исходногомножестваI1   ( xi  x j ) 2  ( yi  y j ) 2i, j(4.20)157и сумма квадратов расстояний от центра тяжести до точек исходногомножестваnI 2   ( xi  x) 2  ( yi  y ) 2 ,(4.21)i 1где1 n xi ,n i 1(4.22)1 ny   yi .n i 1(4.23)xПокажем, являются ли эти два критерия эквивалентными, т.е.оптимальноеразбиениенаклассыминимизирующеекритерийI1соответствует минимуму I2.Возведя в квадрат скобки и выполнив суммирование отдельныхслагаемых, получимnnI1  2(( x   yi2 )  ( xi x j   yi y j )) ,i 12ii 1i, jnni 1i 1(4.24)i, jI 2  ( xi2   yi2 )  n( x  y ) .22(4.25)Рассмотрим случай, когда коэффициент линейной корреляции длякоординат точек (xi, yj) равен нулю, т.е.

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

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