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

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

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

Очевидно, что такая модель должнабыть универсальной и позволять уточнять различные параметры как центровпроизводства и потребления, так и ограничения, связанные с инфраструктуройтранспортной сети [135].Попыткипоставитьоптимизационныезадачивыбораместрасположения КТ и КНРЦ в рамках графовых моделей и в виде задачматематическогопрограммированияпримногихкомбинаторныхограничениях приводят к сложным вычислительным процедурам переборногохарактера, что не позволяет использовать их для решения поставленной задачив рамках федеральных округов или всей страны.В связи с этим, представляется целесообразным для решения задач,связанных с выбором мест расположения объектов КТС страны, использоватьединую методологию, основанную на методах кластерного анализа [135].

Этиметоды основаны на математической теории разбиения множеств наподмножества и включают многие алгоритмы практического решения задачпри значительно меньшей сложности вычислений [5].Поскольку, так или иначе, выбор мест расположения КТ (на первомуровне) и КНРЦ (на втором уровне) связан с разбиением всего множестваобъектов – (центров производства на первом уровне и КТ на втором уровне)на кластеры по признаку «близости» к некоторым искомым «центрам», то143можно использовать весь богатый арсенал моделей, методов и алгоритмовоптимизации кластерного анализа [5], [42], [111].Методы кластерного анализа позволяют производить разбиениеобъектов по целому набору признаков.

Так, например, в задачах разбиенияклиентов(грузовладельцев)наподмножества,обслуживаемыхтерриториальными КТ, в качестве признаков могут быть: координатыклиентов – (x,y), а также другие показатели, используемые для нахождениясходства или различия объектов [135]. Анализ сложности алгоритмовкластерного анализа, а также опыт использования программных средствкластерного анализа доказывает возможность применения их в практическихзадачах размещения транспортных объектов большой размерности как длярегионов, так и в целом для всей страны.Постановкаирешениепрактическихзадачоптимизацииместорасположения объектов КТС приводят к новым научным задачам,которые развивают сами алгоритмы и методы кластерного анализа.

Прииспользовании классического метода k-средних оптимальный центр кластераможет определяться в любой из точек заданного параметрами пространства.Если в качестве параметров задать координаты предприятий, то центркластера может находится в любой области рассматриваемых параметров.Однако при решении поставленной задачи, например, привязки КТ к КНРЦнеобходимо,чтобыцентркластераобязательнонаходилсянажелезнодорожной сети, т.е. необходимо решить задачу кластеризации спроекцией на функцию.1444.1 Анализ возможностей и обоснование корректности использованияметодов кластерного анализа для разработки методологии размещениятерминально-логистических объектов транспортной сетиКластерный анализ включает методы группировки многомерныхобъектов, основанные на математической обработке координат точекподходящего геометрического пространства с выделением групп как«сгустков» этих точек (кластеров).Процедура кластеризации заключается в том, чтобы на основанииданных X о множестве объектов G, разбить это множество объектов на Kподмножеств (кластеров) G1,G2,…,GK так, чтобы каждый объект Gkпринадлежал одному и только одному подмножеству разбиения – кластеру.Объекты одного кластера должны быть близкими, в то время как объекты,принадлежащие разным кластерам, должны быть далекими, в смыслевведённой метрики.Решением задачи кластеризации являются оптимальные разбиения,удовлетворяющие некоторому критерию оптимальности, количественноизмеряющему качество кластеризации.

Он представляет собой функционалили целевую функцию, количественно выражающие уровень качестваразличных разбиений. Следует отметить, что выбор функционала зависит отточногоопределенияжелательныхсвойствкластеров,необходимыхспециалисту [42], [111].Рассмотрим математическую постановку задачи кластерного анализа ипотенциальную сложность ее решения.Пусть множество I={I1,I2,…,In} обозначает n объектов. Результатизмерения j-й характеристики i-го объекта обозначим символом xij.

Всегохарактеристик m, тогда вектор Xi=[xij] соответствует всем характеристикам iго объекта. Таким образом, множество I объектов описывается множеством145векторов измерений X = {X1, X2,…,Xn}. При этом, множество X может бытьпредставлено как множество координат n точек в m-мерном пространстве.Обозначим K – количество кластеров. Это целое число, меньшее, чемколичество объектов n. Задача кластеризации заключается в том, чтобы наоснове данных об объектах, находящихся в множестве Х, разбить всёмножество объектов I на K кластеров (подмножеств) G1, G2,…, GK так, чтобыкаждый объект принадлежал одному и только одному кластеру.

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

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

Это число определяет полный перебор146вариантов при решении задачи кластеризации и определяется формулойСтирлинга1 K jS (n, K )   CK (1) j ( K  j ) n .K ! j 0(4.1)Если K неизвестно, т.е. производится классификация при не заданномчисле классов, то общее число возможных разбиений будетnn1 k jCk (1) j (k  j ) n .k 1 k ! j 0S (n)   S (n, k )  k 1(4.2)При достаточно больших n ( n   )S  n, K   K n1 .(4.3)Формулы показывают, что простой перебор вариантов кластеризациидля реальных задач, где K сотни, а n тысячи объектов, невозможен.Алгоритмыкластеризациирадикальноограничиваютпереборвариантов, при этом сложность алгоритмов кластеризации определяетсяскоростью возрастания количества производимых операций от «размерности»задачи [5], [111].

Обычно интересуются зависимостью сложности от n –количества объектов исходного множества. При этом используютсяобозначения О(f) – сложность растет не быстрее, чем f, и  (f) – сложностьрастет быстрее, чем f. Например, O(n2).Дляколичественнойоценкиблизости(сходства)объектоввкластерном анализе вводится понятие метрики, определяющей близость наоснове метрического расстояния между ними. Каждый объект описывается mпризнаками, поэтому он представляется точкой в m-мерном пространстве.Таким образом, близость (сходство) с другими объектами можно определитькак соответствующее расстояние между точками в m-мерном пространстве[19].147Выбор расстояния между объектами (метрики) является узловыммоментом исследования, от него во многом зависит окончательный вариантразбиения объектов на кластеры при данном алгоритме разбиения.В кластерном анализе применяются следующие основные способыопределения расстояния между объектами i и p для количественных шкал.Далее будем использовать обозначение d(i,p)=dip.

Каждый объект iопределяется точкой в m-мерном пространстве координат xij.m1.dip   | xij  x pj |;Линейное расстояниеj 12.1j 2 2pmdip  ( ( xi  x ) ) ;Евклидово расстояниеjj 1m3.Квадрат евклидова расстоянияd2ip  ( xij  x pj ) 2 ;j 1m4.1j q qpОбобщенное степенное расстояние Минковского dip  ( ( xi  x ) ) ;jj 15.Расстояние Чебышева6.Расстояниегородскихdip  max | xij  x pj |;(i , p , j )кварталов(Манхэттенскоерасстояние)mdip   | xij  x pj |;j 17.Взвешенное евклидово расстояниеm1j 2 2pdip  (  j ( xi  x ) ) .jj 1Евклидово расстояние попросту является геометрическим расстояниеми лучше всего объединяет объекты в кругообразных скоплениях.Квадрат евклидова расстояния придаёт больший вес более отдаленнымдруг от друга объектам.Обобщенное степенное расстояние представляет математическийинтерес как универсальная метрика.148Расстояние Чебышева, как правило, используется, когда два объектаразличаются по какому-то одному измерению.Манхэттенскоерасстояние(расстояниегородскихкварталов)учитывает, что расстояние между пунктами в черте городов складывается изотрезков улиц, расположенных перпендикулярно друг другу.Отметимещеодинспособописанияблизостиобъектов–непосредственное указание меры близости (расстояния) между любыми двумяобъектами заданного множества объектов.

Для этого составляется квадратнаяматрица D, каждый элемент которой dip – это величина, выражающаянекоторое смысловое понимание расстояния (близости). 0 d12 d13 ...d1n d 21 0 d 23 ...d 2 n D ....................  . d n1d n 2 d n 3 ...0 Например, если объекты - это города, то для решения задачиразмещения транспортных объектов удобно в качестве dip взять расстояние вкилометрах шоссейных или железных дорог между пунктами i и p. Этавеличина может учесть многочисленные особенности пути из i в p(извилистость и рельеф дорог, наличие мостов, загруженность, пропускнуюспособность и т.д.). Фактическое «расстояние», как правило, не совпадает срасстоянием по вышеприведенным «классическим» метрикам, использующимкоординаты xij.

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

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