Есть ли метод кластеризации с фиксированными начальными центрами?
Доброй ночи. Разрабатываю модель грузоперевозок. Есть координаты центров (они же склады), они фиксированные. А также есть несколько десятков-сотен заказов на поставки товара (тоже имеют свои координаты на карте). И это все дело нужно разбить на зоны(кластеры) в которых будет происходить развозка товаров: на каждую зону отдельная машина. Так вот возник такой вопрос: какой метод(алгоритм) больше всего подходит под эту схему? Знаю есть метод k-means, но там центры не фиксированы, они вычисляются самим алгоритмом. У меня немного другая ситуация, но схожая, ведь мне тоже нужно разбивать на кластеры. Может сделать типа упрощенный метод k-means с уже заданными центрами или что посоветуете?
Если центр фиксирован, то и кластеры фиксированы - измерьте расстояния от каждой точки до каждого склада, прикрепляйте точку к складу с наименьшим расстоянием до него - вот и ваши кластеры...
Таким образом кластеризацию нужно заменить расчётом расстояний.
__________
Также для решения этой задачи можно использовать теорию графов.
Ну я делаю так: к какому центру ближе точка к тому она и принадлежит. Меня интересует вопрос есть ли такой метод работающий по такому принципу или это можно назвать Упрощенный метод k-means?(мне для дипломной это как-то назвать нужно). А в чем мне тут графы помогут?(я в них не вникал, поэтому нигде их не использую)
Делаете правильно, только это не кластеризация...
Ваша задача очень похожа на транспортную задачу линейного программирования (можно гуглить).
Один из способов её решения - с применением теории графов.
В любом случаем это больше похоже на задачи теории игр или теории графов, нежели на задачу из области data-mining...
Даня DS28: нет, я сначала разбиваю все заказы на зоны где есть склады, а потом внутри этих зон методом Кларка-Райта + Яндекс карты прокладываю маршруты между точками заказов. Все это будет выглядеть как мини цмс со своей админкой.
Dark19: тоже алгоритм из теории игр. Если вас волнует только вопрос грамотного написания, то пишите: "для каждой точки-заказа рассчитывается расстояние до каждого склада и выбирается наименьшее" - вам никто не скажет, что вы не знаете какого-то особого названия для банального алгоритма...
Но есть такой момент: если машина проезжает несколько точек за один выезд, может оказаться, что некоторые, не принадлежащие её складу точки, будут для неё ближе, чем для машины из другого склада...
Даня: не только грамотного описания, мне еще это нужно будет рассказать, может посоветуете, что лучше почитать на этот счет?
В принципе может быть и такое, можно сделать как исключение и проверять по условию, но там тогда мороки будет, нужно будет из этой ближней зоны точку исключать, которая ближе к соседней машине будет.
Dark19: У вас целый диплом, чтобы рассказывать - расскажите про что-нибудь другое.
Выступление вроде не больше 10 минут должно быть - проверьте себя на секундомере.
Почитать можете что угодно по тегам: "транспортная задача", "теория графов" и т.п. Можете почитать про расстояния, они бывают разные, но не думаю, что имеет смысл вносить исправления в диплом на такой поздней стадии.
Про возможный недостаток: если такое может быть - исправить будет дольше, лучше презентовать что-то вроде схемы, когда машина возвращается на склад после каждого заказа, но это может быть оценено не очень хорошо. Можно сдать так, а на вопрос - сообщить, что эта проблема известна и в дальнейшем вы планируете её доработать, изменив алгоритм подбора точек, а в данный момент вы фокусировались на создании рабочего варианта, с некоторыми недостатками...
Даня: Это я оставлю, но Кларка-Райта нужно будет делать, у меня тема по кольцевым маршрутам. Я вот почитал теорию игр немного, интересно, но как это в дипломную работу вписать не понимаю?
Dark19: Не нужно вписывать лишнего, максимум можете описать алгоритмы, от которых отказались в пользу Кларка-Райта, общую постановку задачи и т.д. Если уж дошли до диплома должны суметь.
По изначальному вопросу:
Замените кластеризацию на расчёт расстояния. Проработку особых точек, которые могут перейти к другому складу при определённых обстоятельствах можете преподнести, как дальнейшее развитие и оптимизацию программы. Сразу всё хорошим быть не может - это нормально. Это всё будет хорошо воспринято комиссией, при хорошем уровне реализации остальных частей задачи.
Средний
Простой
