Диссертация (792540), страница 25
Текст из файла (страница 25)
Все объекты необходимо разбить на K кластеров. Дляэтого сначала из n точек каким-то способом выбирается K точек (объектов).Этот выбор можно сделать случайным образом или, исходя из каких-либоаприорных соображений (например, выбрать точки наиболее равномерно повсему диапазону параметров). Примем эти точки за эталоны и каждомуэталону присвоим порядковый номер, который является номером кластера.На первом шаге из оставшихся (n-K) точек выбирается точка Xi скоординатами (xi1, xi2, …, xim) и проверяется, к какому из эталонов онанаходится ближе всего.
Как правило, для этого используется одна из метрик,например, евклидово расстояние. Проверяемый объект привязывается к томуцентру (эталону), для которого расстояние минимально. Эталон заменяетсяновым, пересчитанным с учетом присоединенной точки, причем вес его(количество объектов кластера) увеличивается на единицу. Если встретятсянесколько минимальных расстояний, то i-ый объект присоединяют к центру снаименьшим порядковым номером.Далее выбираем следующую точку Xi+1, и для неё повторяем всевышеперечисленные действия.
Присоединив все точки исходного множествак K эталонам, получаем первое разбиение на кластеры. Для точек каждогокластера вычисляем векторы средних значений (центры тяжести кластеров),согласно формулам (4.18), (4.19), которые и будут новым эталоном дляпоследующей итерации.После (n-K) шагов все точки будут принадлежать одному из Kкластеров. На этом процесс разбиения на кластеры не заканчивается. Чтобыдобиться устойчивости разбиения, все точки X1, X2, …, Xn по тому же правилу170опятьприсоединяютсякполученнымкластерам.Новоеразбиениесравнивается с предыдущим.
Если они совпадают, то работа алгоритмазавершается. В противном случае цикл повторяется. Центры тяжести дляокончательного разбиения не совпадают с первоначальными эталонами,обозначим их C1, C2, …, CK. В результате каждая точка Xi (i=1, 2, …, n) будетотноситься к такому кластеру, для которого расстояние между Xi и центромсвоего кластера минимально среди всех центров.Заметим, что возможны две модификации метода k-средних.
В первой- пересчет центра тяжести кластера производится после каждого измененияего состава, а во второй модификации такой пересчет производится лишьпосле того, как будет завершен просмотр всех данных. В любом случаеитерационный алгоритм этого метода минимизирует дисперсию расстоянийвнутри каждого кластера.Суммарные расстояния между точками, представляющими объекты, ицентрами соответствующих кластеров, представленными звездами – сутькритерия метода k-средних (см. рис. 4.2).Существуют разнообразные расширения и вариации методов k-средних(k-means )[16], [19].Широко известна и используется нейросетевая реализация k-means –одна из версий нейронных сетей Кохонена. Существует расширение kmeans++, которое направлено на оптимальный выбор начальных значенийцентров кластеров.
В программных системах используются и алгоритмы снезаданным числом классов: методы g-means, c-means и x-means.Методg-meansпозволяетпроизводитьавтоматическийвыбороптимального числа кластеров на основании гауссовского (нормального)закона распределения, откуда и название алгоритма.171Рисунок 4.2 – Кластеризация по методу k-среднихМетод c-means – это метод нечеткой кластеризации (fuzzy clasterization[117]).
Цель его такая же, как и у алгоритма метода k-means: распределитьточки входного множества на кластеры так, чтобы средние точки (центры)разных кластеров различались как можно сильнее. Метод k-means даётоднозначный ответ, принадлежит ли какая-то точка тому или иному кластеру.При использовании метода c-means разрешается одной точке лежатьодновременно в двух или более кластерах. Степень принадлежности точки iкластеру j характеризуется величиной µij∈[0,1].Кластеризация x-means означает расширение метода k-средних сэффективной оценкой количества кластеров.В таблицах 4.2 и 4.3 представлены некоторые параметры сравнениявышеприведенных методов и указана их вычислительная сложность [5], [111].172Таблица 4.2 – Сравнительная таблица методов кластеризацииМетодыкластеризацииФорма кластеровИерархическийПроизвольнаяk-среднихГиперсфераc-среднихГиперсфераЧисло кластеров,степень нечеткостиПроизвольнаяПорог расстояния RДревовиднаяструктура кластеровПроизвольнаяЧисло кластеров илипорог расстояния дляудаления реберДревовидная структуракластеровПроизвольнаяПоследовательностьпорогов расстоянияДревовидная структуракластеров с разнымиуровнями иерархииВыделениесвязныхкомпонентМинимальноепокрывающеедеревоПослойнаякластеризацияВходные данныеЧисло кластеров илипорог расстояния дляусечения иерархииЧисло кластеровРезультатыБинарное деревокластеровЦентры кластеровЦентры кластеров,матрицапринадлежностиТаблица 4.3 – Вычислительная сложность некоторых методов кластеризацииМетоды кластеризацииИерархическийk-среднихc-среднихВыделение связных компонентМинимальное покрывающее деревоПослойная кластеризацияВычислительная сложностьO(n2)O(nKl), где K – число кластеров,l – число итерацийзависит от алгоритмаO(n2log n)O(max(n, m)), где m<n(n-1)/21734.7 Выводы по главе1.
В четвертой главе впервые предложен новый методологическийподход к определению количества и мест размещения терминальнологистических объектов на основе методов кластерного анализа. Подробноизучена и доказана правомерность и преимущества использования методовкластерного анализа для решения практических задач, связанных сразмещением объектов терминально-логистической инфраструктуры.2. Показано, что минимизация суммарного расстояния перевозки отпредприятий рассматриваемого региона до КТ на первом уровне и от КТ доКНРЦ на втором уровне предлагаемой модели КТС достигается вариациейсамих подмножеств предприятий и КТ, что приводит к математической задачеоптимальной кластеризации исходного множества предприятий и КТ дляопределения оптимального места размещения КТ и КНРЦ.3.
Впервые предложено для решения задач, связанных с оптимизациейместоположения терминально-логистических объектов и определения ихпотребного количества, использовать методологию на основе кластерногоанализа.4. Исследованы методы кластеризации объектов, предложен в качествеосновного метода кластеризации алгоритм k-means Мак-Куина (k-средних),который определяет оптимальные кластеры (подмножества клиентов) сосвоими центрами: КТ на 1-м уровне и КНРЦ на 2-м уровне.5. Исследованы наиболее известные системы с модулями кластерногоанализа STATISTIKA, WEKA, DEDUKTOR STUDIO, Orange Data Mining,SPSS-STATISTIKA 17.1745 МЕТОДОЛОГИЯ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯТЕРМИНАЛЬНО-ЛОГИСТИЧЕСКИХ ОБЪЕКТОВ НА ОСНОВЕНОВЫХ МЕТОДОВ И АЛГОРИТМОВДля реализации массового внедрения технологии контейнерныхпоездов, создания клиентоориентированной КТС, повышения уровняконтейнеризации была предложена модель организации функционированиядвухуровневой сети терминально-логистических объектов.На первом уровне все предприятия, добывающие или производящиеконтейнеропригодную продукцию, необходимо прикрепить к КТ, а на второмуровне создать КНРЦ, к которым будут прикреплены подмножества КТ (см.рис.
5.1) [135], [136], [137], [138], [149], [150], [151].Рисунок 5.1 – Модель двухуровневой сети терминально-логистическихобъектов КТС: • – месторасположение предприятий(грузополучателей/грузоотправителей); – КТ; ∆ – КНРЦКТ и КНРЦ являются центрами обслуживания грузопотоков своегоуровня: 1-й уровень – от центров производства до КТ и 2-й уровень от КТ доКНРЦ. Предполагается, что между КТ и КНРЦ, а также между КНРЦ регионовперевозки осуществляются контейнерными поездами.175Наиболее актуальной среди множества задач создания единой сетиКТСявляетсязадачаоптимизацииместрасположенияуказанныхтерминально-логистических объектов, при этом необходим подход, которыйбыувязывалданныеоместорасположениигрузоотправителейигрузополучателей (геоинформационные параметры), объём грузовой базы сгеоинформационными параметрами конкретной сети железных дорог длявозможногоразмещениявэтихточкахтерминально-логистическойинфраструктуры.
При этом необходимо учитывать группы факторов,влияющих на дальнейшую эффективную эксплуатацию инфраструктуры, наоснове минимизации затрат на подвоз контейнеропригодной продукции наКТ, на перевозку от КТ до КНРЦ, на перевозку между КНРЦ, а такжеинвестиций в развитие терминально-логистической инфраструктуры.Вглаве2диссертационногоисследованияустановлено,чторассмотренные классические задачи определяют оптимальные свойстванекоторых точек - «центров», когда множество точек задано. Необходимоотметить, что в поставленной выше задачи оптимизации двухуровневой сетиКТС «центры» должны соответствовать не заданному исходному множествуточек, а подмножествам заданного множества, которые заранее неизвестны.Их вариация и даёт дополнительный резерв оптимизации.Выявлено, что решение оптимизационных задач по выбору местрасположения КТ и КНРЦ при помощи графовых моделей и математическогопрограммирования при многих комбинаторных ограничениях приводят ксложным вычислительным процедурам переборного характера, что непозволяет применять их в рамках территорий федеральных округов или всейстраны.Врезультатеопределенияанализасуществующихместоположенияпрактическихтерминально-логистическихметодикобъектовустановлено, что они не учитывают количество объектов, места ихразмещенияотносительнопромышленногопроизводства,объёмы176грузопотоков от отдельных грузоотправителей и грузополучателей, а такжесуществующую топологию железных дорог.В главе 4 настоящей работы для решения поставленных задачоптимизации производственно-транспортных систем предложена процедуракластеризации объектов – применение универсальной методологии разбиениямножества объектов на подмножества со своими центрами, обладающимиоптимальными свойствами.
При этом использование метрик близости точек,применяемых в кластерном анализе, моделирует минимизацию расстоянийпри перевозке, а если в качестве «веса» каждой точки принять объёмпроизводимой/добываемой продукции производства, то можно решать задачуминимизации издержек при перевозках как задачу оптимизации кластеров иих центров.Засчетсокращениясреднейдальностиперевозоквцелом,обеспечивается снижение грузооборота в тонно-километрах, что являетсяположительным фактором, поскольку тарифы на перевозку являютсянелинейными по отношению к расстоянию и увеличение дальности перевозокне прямо пропорционально доходам от перевозок.Рассмотренный в 4 главе метод кластеризации на основе метода kmeans находит оптимальный «центр» в любой геометрической точкепространства. Вместе с тем, при определении мест расположения объектовтерминально-логистической инфраструктуры (КТ и КНРЦ) необходимоучитывать их расположение на железнодорожной сети.
Поэтому предложенопроизводить проектирование центра, получаемого классическим методом, сучётом существующей топологии железных дорог - на железнодорожнуюстанцию. В этих целях в настоящей работе разработан метод кластеризации «спроекцией», названный k-means pro [135], [136], [137], [138], [149], [150], [151].1775.1 Разработка метода кластеризации с возможностью проекции центровкластеров на сеть железных дорог (k-means pro)Приведем описание метода кластеризации «с проекцией» k-means pro[136].Пусть задано исходное множество объектов J (j=1,n), подлежащихкластеризации, характеризуемые своими координатами X = {x1,…,xn}, их весаV = {v1,…,vn} и допустимое множество проекций P (r=1,p) со своимикоординатами Y = {y1,…,yp}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
