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

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

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

Таким образом j-й объект и r-я допустимая точкапроекция задаются в G-мерном пространстве RG, а именно: xj = (xj1,…,xjG) иyr = (yr1,…,yrG). Обозначим разбиение исходного множества на k кластеров ввиде набора подмножеств S  {S1 ,..., Sk } .Задан параметр k - число кластеров, на которые производится разбиениемножества Х. В результате необходимо получить оптимальное разбиениеS *  {S1* ,..., Sk*} , центры которого являются оптимальным множествомпроекций C  Y .*Обозначим: i, i’ - номера кластеров, j - номер объекта, r - номер точкимножества проекций, l - номер координаты точки, m - текущая итерация, G размерность пространства, в котором выполняется кластеризация, n количество объектов исходного множества, p - количество точек допустимогомножества проекций.Расстояние между точками tl и t2 в G-мерном пространстве найдем поЕвклидовой метрике:d (t1 , t2 ) G (tl 11l t2l ) 2 .(5.1)1781.

Выбираем начальное разбиение S  {S1 ,..., S k } :0S   x ,..., x0i0i10in,k00Si0  X , Si0  Si0' Ø , i  i .(5.2)i 1S m  {S1m ,..., S km } , начиная с2. Для каждого m-го разбиенияS 0  {S10 ,..., S k0 } , вычислим набор средних векторов (центров)E m  {e1m ,..., ekm } , т.е. eim  (eim1 ,..., eiGm ) ,здесьnie milv xj 1nvj 1гдеjjl,(5.3)jni - количество элементов (точек) i-го кластера.3. Для m-го разбиения вычислим также множество проекций средних:C m  { y  Y : i, d * ( y, eim )  min d ( yr , eim )} .1 r  p(5.4)4. Вычислим разбиение, порождаемое множеством С m , и возьмем его вкачестве Sm1 ( S1m1 ,..., Skm1 ) , т.е.Sim1  x  X : d ( x, cim )  min d ( x, cim' ) , 1  i  k .5. Проверяем: если S1i 'km 1(5.5) S m , то заменяем m на m + 1 и переходим кп.

2, а если S m1  S m , то на этом алгоритм заканчивается. Полагаем S m  S *, С m  C* .179Критерием оптимизации в классическом алгоритме k-means являетсяфункционал [5]kF  S     X  ei  S i 1 X S2.iФункционал F(S) при переборе разбиений S0, S1,…,Sm,…, не возрастает,причем равенство F(Sm) = F(Sm+1), возможно только если выполняетсяравенство Sm = Sm+1 . Таким образом, через конечное число шагов алгоритмзаканчивает работу для любого начального разбиения S0.

В нашем случае,достигаемый критерий оптимизации для найденных центров ci*имеет видkF '  S     X  ci*  S i 1 X S.(5.6)iВ результате расчетов каждый раз получаем локальный минимум F(S),при этом результат кластеризации зависит от выбора начального эталона е0.Координаты е0 можно получать различными способами. Так, например, внастоящей работе они выбирались случайными числами, равномернораспределенными в пределах возможных координат исходных точек.

Чтобыпроверить устойчивость результатов и получать различные усредненныезависимости, выбор е0 можно изменять.На рисунке 5.2 схематически показана работа метода кластеризации «спроекцией». Кружки – это точки производства, линия – это железная дорога,квадраты – это центры кластеров на каждой итерации, курсором заданыжелезнодорожные станции.180Рисунок 5.2 – Иллюстрация работы метода k-means proРазработан программный продукт, позволяющий реализовать метод kmeans pro и другие известные методы кластеризации.На рисунке 5.3, для примера, показаны результаты кластеризации точекна основе метода k-means, а на рисунке 5.4 – соответственно на основе k-meanspro.

Железнодорожная магистраль в данном примере представлена в виде181«синусоиды» (+ изображены центры кластеров, o – железнодорожныестанции) [150].Рисунок 5.3 – Результаты кластеризации для тестового примера по методу kmeansРисунок 5.4 – Результаты кластеризации для тестового примера по методу kmeans pro1825.2 Исследование свойств различных методов кластеризации на основеинтерактивной программы анализаРабота любого метода кластеризации существенно зависит отрасположения исходных объектов в пространстве параметров.

В настоящейработе, исходные точки – это координаты и объёмы производств, а такжеконкретный «рисунок» железнодорожной сети и станций. Опыт примененияразличных методов кластеризации для задач кластеризации производств иопределения местоположения КТ показал, что результаты существеннозависят от расположения исходных объектов (производств и станций). Дляизучения свойств различных методов кластеризации и получения информациидля разработки метода кластеризации «с проекцией» было разработанопрограммноесредство,позволяющеезадаватьразличныевариантырасположения объектов, и проверять различные параметры алгоритмов.Координаты производств, вид железнодорожной сети и расположениежелезнодорожных станций в этой программе задаются курсором на условнойкарте местности. Можно придать каждой точке-производства «вес», условносоответствующий объёму производства.

Такой режим ввода данных позволяетпроиграть разнообразные варианты расположения объектов и получатьсоответствующие параметры работы алгоритмов. Были исследованы наиболееизвестные методы: метод кратчайшего дерева, метод минимальногопокрывающего дерева, метод k-means и предложенный в данной работе методk-means pro.На рисунке 5.5 показано изображение точек производств в этойпрограмме.

Размер точки соответствует объему производства (указывается«мышью»). Курсором заданы железнодорожные станции на выбраннойжелезнодорожной сети (направлении).183Рисунок 5.5 – Интерфейс интерактивной программы для исследованияметодов кластеризации при заданных исходных данныхДалее можно указать количество кластеров и выбрать тот или инойметод.

Можно проанализировать работу алгоритма по шагам или получитьокончательный результат (рис. 5.6 и рис.5.7).Рисунок 5.6 – Одна из форм интерфейса интерактивной программы дляисследования методов кластеризации при просмотре результата работыметода k-means184Рисунок 5.7 – Одна из форм интерфейса интерактивной программы дляисследования методов кластеризации при просмотре результата работыметода минимального покрывающего дереваВ другой опции этой программы можно сравнить результаты работыразличных методов, одновременно выведя их на экран ПЭВМ (рис. 5.8).Рисунок 5.8 – Пример сравнения результатов работы различных методов натестовых примерахИспользование разработанной интерактивной программы позволилопровести большое количество экспериментов по исследованию свойств этих185методов.

При этом оказалось, что предложенный метод k-means pro неуступает другим методам при малой размерности задач и превосходит другиеметоды для задач сверхбольшой размерности, и особенно в случае сильныхсгущений объектов, что характерно для реальной «карты» производств ижелезных дорог.5.3 Решение задачи оптимизации мест расположения контейнерныхтерминалов на основе различных модификаций метода кластеризацииk-means proВ качестве исходных данных для отработки методов, их анализа ивыявления закономерностей в этом разделе исследования выбрано 900крупнейших промышленных предприятий Приволжского федеральногоокруга (ПФО). Каждое такое предприятие имеет номер i, и определяется тремяпараметрами: координатами xi, yi и годовым объёмом контейнеропригоднойпродукции vi.

Железнодорожные станции заданы на сети 6 железных дорог,проходящих по территории ПФО [136]. А также условно были заданынекоторые другие значения, необходимые для проведения экспериментов.Это предопределило большую размерность решаемых задач, позволилопроверить работоспособность предлагаемых методов в реальных условиях иоценить сложность и быстродействие в решаемых задачах, а также оценитьвозможность применения разработанных моделей, методов, алгоритмов иметодик для всей территории Российской Федерации.Обоснованность формируемых кластеров в работе, т.е. приемлемостьполученных результатов по определению мест расположения контейнерныхтерминалов, определялось валидацией полученных кластеров [136], [151].Различают два типа валидации: внутреннюю – по тому, насколькокластеры соответствуют исходным данным, и внешнюю (целевую) – по тому,186насколько кластеры соответствуют информации, не учитывающийся при ихпостроении, но известной специалистам, которые используют кластеризациюв своих целях.Для внутренней валидации в литературе используются самыеразнообразные индексы, выражающие качество результатов кластеризации.Наиболее популярным является индекс Дэвиса – Болдина, который былиспользован в настоящей работе [151]:DB 1Kkmax{i 1 i  jS k (Qi )  S k (Q j )S (Qi , Q j )},(5.7)где k – количество кластеров, Sk – среднее расстояние от объектов до центракластера, S(Qi,Qj) – расстояние между центрами кластеров.Чем меньше значение этого индекса, тем кластеры компактнее иудалённее друг от друга.

Это позволяет обосновать количество кластеров k.Этот вопрос является важным, поскольку при кластеризациипроизводств количество центров-КТ k может быть, в общем случае, не задано,и должно находиться из условия оптимизации какого-то дополнительногокритерия.Рассмотрим критерий, который выражает целевое предназначениекластеризации: определение мест расположения КТ как центров кластеровсреди всех заданных станций сети железных дорог. Здесь есть два варианта[136].1. Количество центров (КТ) задано. Это будет тогда, когда припроектировании определены инвестиционные ресурсы на создание всех КТ, иизвестна средняя нормативная стоимость одного КТ.

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

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