Использование Machine Learning для планирования туристических маршрутов Львова

Достопримечательности Львова
Достопримечательности Львова

Львов – самый популярный у туристов город в Украине. Можно днями бродить по его улочкам, особенно по старому городу. А что делать, если мы заходим обойти все достопримечательности? Во время самостоятельных экскурсий иногда возникает вопрос – каким маршрутом сегодня лучше пойти, чтобы увидеть как можно больше достопримечательностей за максимально короткое расстояние. Порой мы составляем расписание по дням своих будущих маршрутов, полагаясь на собственную интуицию. Это хорошо, но что скажет Data Science на этот счет? Существуют ли алгоритмы, которые могут нам хоть как-то помочь? И если да, то где достать данные? Ответы на эти вопросы мы найдем в данной статье.

Используем алгоритмы машинного обучения без учителя

Для поиска алгоритма можно сформулировать условие задачи: «давайте пойдем только в те места, где сосредоточены наибольшее число достопримечательностей». Места, которые находятся в каком-то районе? Хм, это похоже на задачу кластеризации. Значит нам необходимо будет получить список достопримечательностей и их кластеризировать по координатам или другим атрибутам.

Алгоритмов кластеризации множество, DBSCAN, HDBSCAN, GMM, HAC, Mean-Shift,  из самый простой без учителя — метод k-средних или k-means

k-means математическая формула
k-means математическая формула

Из Вики: «Метод стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров», т.е. алгоритм Machine Learning определяет кластерные центроиды как среднее арифметическое всех точек, принадлежащих кластеру и определяет кластеры таким образом, что каждая точка в наборе данных ближе к собственному центру кластера, чем к другим кластерным центрам. Что же, давайте с него и начнем.

Поиск данных

Алгоритм есть, а где и как получить для него данные? Вернемся к нашему условию задачи и выберем фичи (атрибуты), которые будем использовать для алгоритма. Задача связана с расстояниями, значит можно использовать geo – координаты. Также нам может потребоваться решить вопрос с приоритетностью в каком направлении нам начать свой путь по городу Львов, т.е. нужны рейтинги достопримечательностей. Давайте поищем где-то из открытых источников. Первое что приходит на ум – Википедия, взглянем туда (https://uk.wikipedia.org/wiki/Категорія:Визначні_місця_Львова). Отлично! На Вики в UK – версии, есть как достопримечательности, так и сервис, который предоставляет geo – координаты. Тогда как нам быть с рейтингами достопримечательностей? Если присмотреться к вики – статьям, то можно заметить, что для популярных объектов длина статьи выше среднего. За рейтинг можно принять длину текста статьи описывающей достопримечательность. Теперь у нас есть алгоритм и место, где можно получить данные. Составим план работы:

  1. Спарсить wiki и получить данные в формате: название, координаты, длина текста
  2. Применить k-means
  3. Вывести в файле и на графиках кластеры для каждой достопримеательности

Инструменты Data Science

Можно использовать разные инструменты, как языки, так и приложения, вплоть до плагинов браузера, что кому нравится. Здесь мы будем использовать язык R. Он лаконичен, прост для визуализации и под него создано огромное количество библиотек.

Пишем парсер Wiki на R

Итак, откроем R – Studio или другой редактор и начнем писать парсер wiki:

Sys.setlocale("LC_ALL","Russian_Russia")
install.packages('rvest')
install.packages('ggmap')
library('ggmap')
require(gdata)
library('rvest')
url <- 'https://uk.wikipedia.org/wiki/Категорія:Визначні_місця_Львова'
webpage <- read_html(url)
links_data_html <- html_nodes(webpage,'.mw-category-group > ul > li > a') %>%  html_attr("href")

df <- data.frame(title=character(), latitude=double(), longitude=double(),length=numeric(), stringsAsFactors=FALSE )
for (link in c(links_data_html)){
  fullLink <-  paste("https://uk.wikipedia.org", link, sep="")

  webpage <- read_html(fullLink, encoding = "utf8")
 
  gpsLink <- trim(html_nodes(webpage,'#coordinates .plainlinks .external') %>%  html_attr("href"))
 
  if(!is.null(gpsLink) & length(gpsLink) > 0) {
    
    gpspage <- read_html(paste('http:',gpsLink, sep=''), encoding = "utf8")
    latitude <- html_text(html_nodes(gpspage,'span.geo > span.latitude'))
    longitude <- html_text(html_nodes(gpspage,'span.geo > span.longitude'))
    
    if(!is.null(latitude) & length(latitude) > 0) {
    
      title <- html_text(html_nodes(webpage,'h1'))
      length <-  nchar(html_text(webpage))
      print(title)
      df[nrow(df) + 1,] = list(title, as.double(latitude), as.double(longitude), length)
   
   }
  }
  
}

Работаем с данными

Отлично, в df мы получили данные в формате title, latitude, longitude, length

Если посмотреть на содержимое можно заметить выбросы, которые могут подпортить нам картинку, давайте избавимся от них:

lviv <- subset(df, latitude > 40 & latitude < 50)

Построим график, отношения ширины к долготе

ggplot(lviv,aes(x=latitude,y=longitude))+ geom_point(aes(size=length,col=length))
Исходные данные
Исходные данные

Мы видим, что есть хорошая возможность для кластеризации. Подчистим немного данные:

k <- data.frame(lviv$latitude, lviv$longitude, lviv$length)

Собственно, сам k-means

fit <- kmeans(k, 10)
k$cluster <- as.factor(fit$cluster)

Теперь наши кластера содержатся в памяти в датафрейме k. Было бы круто визуализировать их прямо на карте Львова. Хорошая новость, R поддерживает и такую возможность:

LvivMap <- get_map("Lviv", zoom = 14)
ggmap(LvivMap) + geom_point(aes(x =lviv.longitude, y = lviv.latitude, size=lviv.length,colour = as.factor(cluster)),data = k) + ggtitle("Lviv using KMean")
K-means расстония и рейтинг достопримечательностей Львова
K-means расстония и рейтинг достопримечательностей Львова

Вот и первый результат! Неплохо, цвета – это кластеры, с учетом популярности места. Т.е. мы вычислили  не только самые близкие места, но и популярные. Размер кружков – это длина текста в Вики — статье.

Есть шанс получить более красивую картинку, если мы не будем использовать фичу «длина текста», а только координаты. Давайте посмотрим что из этого выйдет.

Очистим данные от популярности достопримечательности и заново применим метод k-means:

latlon <- k
latlon$lviv.length <- NULL
latlon$cluster <- NULL
latlonfit <- kmeans(latlon, 10)
latlon$cluster <- as.factor(latlonfit$cluster)
ggmap(LvivMap) + geom_point(aes(x =lviv.longitude, y = lviv.latitude, size=10,colour = as.factor(cluster)),data = latlon) + ggtitle("Lviv using KMean")
K-means кластера достопримечательностей Львова
K-means кластера достопримечательностей Львова

Отлично, это то что нужно. Метод k – средних посчитал за нас, в какой район Львова нам отправляться для максимального наслаждения. Мы использовали разбивку на 10 кластеров, что сопоставимо с 10-ю днями отдыха во Львове. На каждый день есть свой цвет, куда можно отправляться в тур по городу.

Для распечатки нам необходим текстовый список, сохраним данные в файл:

lviv$cluster <- as.factor(latlon$cluster)
write.table(lviv, "c:/local/lviv.txt", sep="\t")

И напоследок посмотрим, как наши кластера выглядят в «классике»

ggplot(lviv,aes(x=latitude,y=longitude))+ geom_point(aes(size=length,col=cluster))
k-means только по координатам
k-means только по координатам

Пример получился, почти как на данных Iris? Мы видим несколько крупных достопримечательностей, которые расположены в разных районах Львова. В последнем применении K-means был исключен атрибут популярности, чтобы лучше раскрасить ближайших соседей.

Текстовый файл с результатами кластеризации достопримечательностей Львова доступен здесь

Выводы

В статье мы научились:

— парсить сайты на R

— применять элементы машинного обучения на практике

— генерировать экскурсионные маршруты, что равнозначно написанию простенького ИИ

Поздравляю с окончанием чтения, впереди нас ждут еще больше вдохновения и интересные задачи!

Spread the love

Оставьте первый комментарий

Оставить комментарий