Архив метки: Машинное обучение

Кластеризация данных

Кластеризация данных – это метод обнаружения и визуализации групп связанных между собой предметов. Данный инструмент часто используется в приложениях, обрабатывающих большие объемы данных. Кластеризация – пример обучения без учителя. В отличие от нейронных сетей или деревьев решений, алгоритмам обучения без учителя не сообщаются правильные ответы. Их задача – обнаружить структуру в наборе данных, когда ни один элемент данных не является ответом.

Постановка задачи

Совсем недавно, компания Adobe, выпустила на iPhone програмку Adobe Color CC. До меня дошла эта новость и я понял, что пора объяснить, как же это делается!) Метод известный и описан во многих местах, но наше — всегда лучше))) Задача у нас простая, методом K-средних сделать K кластеров цветов картинки и выявив центры кластеров, посмотреть какому цвету он соответствует. Таким образом мы узнаем основные тона картинки 😉 Но сначала, немножко теории.

Иерархическая кластеризация

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

Иерархическая кластеризация в действии

Здесь схожесть элементов представлена их относительным расположением – чем элементы ближе друг к другу, тем более они схожи. В начале каждый элемент – это отдельная группа. На втором шаге два самых лизких элемента A и B объединены в новую группу, расположенную посередине между исходными. На третьем шаге эта новая группа объединяется с элементом C. Поскольку теперь два ближайших элемента – это D и E, то из них образуется новая группа. И на последнем шаге две оставшиеся группы объединяются в одну.

Результаты иерархической кластеризации обычно представляются в виде графа, который называется дендрограммой. На нем изображено, как из узлов формировалась иерархия.

Дендрограмма как способ визуализации иерархической кластеризации

На дендрограмме представлены не только ребра графа, показывающие, из каких элементов составлен каждый кластер, но и расстояния, говорящие о том, как далеко эти элементы отстояли друг от друга. Кластер AB гораздо ближе к составляющим его элементам A и B, чем кластер DE к элементам D и E. Изображение графа таким образом помогает понять, насколько схожи элементы, вошедшие в кластер. Эта характеристика называется теснотой (tightness) кластера.

Иерархическая кластеризация дает на выходе симпатичное дерево, но у этого метода есть два недостатка. Древовидное представление само по себе не разбивает данные на группы, для этого нужна дополнительная работа. Кроме того, алгоритм требует очень большого объем
а вычисле- ний. Поскольку необходимо вычислять попарные соотношения, а затем вычислять их заново после объединения элементов, то на больших наборах данных алгоритм работает медленно. И тут на помощь приходит другой метод!)

Кластеризация методом k-средних

Он в корне отличается от иерархической кластеризации, поскольку ему нужно заранее указать, сколько кластеров генерировать. Алгоритм определяет размеры кластеров исходя из структуры данных.
Кластеризация методом K-средних начинается с выбора k случайно расположенных центроидов (точек, представляющих центр кластера). Каждому элементу назначается ближайший центроид. После того как назначение выполнено, каждый центроид перемещается в точку, рассчитываемую как среднее по всем приписанным к нему элементам. Затем назначение выполняется снова. Эта процедура повторяется до тех пор, пока назначения не прекратят изменяться.

На первом шаге случайно размещены два центроида (изображены темными кружками). На втором шаге каждый элемент приписан к ближайшему центроиду. В данном случае A и B приписаны к верхнему центроиду, а C, D и E – к нижнему. На третьем шаге каждый центроид перемещен в точку, рассчитанную как среднее по всем приписанным к нему элементам. После пересчета назначений оказалось, что C теперь ближе к верхнему центроиду, а D и E – по-прежнему ближе к нижнему. Окончательный результат достигается, когда A, B и C помещены в один кластер, а D и E – в другой.

В данном методе, ОЧЕНЬ важен выбор центроидов, т.к. в конечном итоге все точки к ним стянутся, но если все 4 будут очень близкие цвета и из них будут состоять большие области, то в конечном итоге вы и получите приблизительно одинаковые центры. Таким образом центроиды должны быть максимально разнесены (желательно равномерно и равноудаленно).

Для большего понимания приведу пример. Давайте рассмотрим такую картинку.

Чтобы решить поставленную задачу в такой, монотонной четко разделенной картинке, достаточно написать небольшой код:

def k_cluster_by_area(points, k=4):

 clusters_by_area = {}

 for point in points:
  clusters_by_area[point] = clusters_by_area.setdefault(point, 0) + 1

 sorted_x = sorted(clusters_by_area.items(), key=operator.itemgetter(1))

 return sorted_x[-k:]

Тут мы просто посчитали, сколько раз, какой цвет встречается, отсортировали и вывели k результатов. Этот метод можно применить к любому изображению, работает достаточно быстро, но есть НО! А именно, мы не получим ТОНАЛЬНОСТЬ картинки! Однако, как я писал выше, в нашей задаче важны центры, вот эту задачу и решает этот код!) Мы берем самые популярные цвета, за изначальные центры кластеров, а потом они постепенно мутируют) На самом деле, желательно брать не просто первые k, а посчитать все комбанации расстояний и выбрать k по макс расстояниям, чтобы центры не оказались рядом (например 2 оттенка серого). Но мне влом и вы сделаете это сами)

Надеюсь, стало яснее. Таким образом, как найти изначальные центры кластеров нам известно, осталось только свести все пиксели в эти точки. А теперь сам код:

def k_cluster(img, distance=euclidean, k=4):
 
 points = get_points(img)
 clusters = {}

 # центры кластеры
 cluster_centers = k_cluster_by_area(points, k)
 for cluster_center in cluster_centers:
  # avg_sum_coords - список сумм r, g, b координат всех пикселей кластера
  # count_points - кол-во пикселей в кластере
  # какие конкретно пиксели в кластере не запоминаем в целях экономии памяти и времени
  clusters[cluster_center] = {'avg_sum_coords':list(cluster_center), 'count_points':1}

 while len(points):

  # находим ближайшие точки к центрам кластеров
  bestmatches = {}
  for point in points:

   # расстояние каждой точки до каждого центра кластера
   for cluster_center in clusters:
    d = distance(cluster_center, point)
    if not bestmatches:
     bestmatches = {'distance':d, 'point': point, 'cluster_center': cluster_center}

    if d < bestmatches['distance']:
     bestmatches = {'distance': d, 'point': point, 'cluster_center': cluster_center}

  # перекидываем ближайшие точки в соответствующий кластер
  bestmatch = bestmatches['point']
  cluster_center = bestmatches[
'cluster_center']
  points2 = []
  new_points = []

  for point in points:
   if point == bestmatch:
    new_points.append(point)
   else:
    points2.append(point)


  points = points2[:]

  # меняем центр кластера
  print clusters.keys(), len(points)

  r_avg, g_avg, b_avg = 0, 0, 0
  cluster_avg_coord = clusters[cluster_center]['avg_sum_coords']

  new_points_len = len(new_points)
  clusters[cluster_center]['count_points'] += new_points_len
  claster_count_points = clusters[cluster_center]['count_points']

  cluster_avg_coord[0] += bestmatch[0]*new_points_len
  cluster_avg_coord[1] += bestmatch[1]*new_points_len
  cluster_avg_coord[2] += bestmatch[2]*new_points_len


  new_center = cluster_avg_coord[0]/claster_count_points, cluster_avg_coord[1]/claster_count_points, cluster_avg_coord[2]/claster_count_points
  
  # если новый центр кластера отличается от предыдущего
  if not new_center in clusters:
   clusters[new_center] = clusters.pop(cluster_center)

 return clusters.keys()

Работает это дело не быстро ;(, поэтому я советую сжимать картинку, хотя бы до разрешения 100 на 100.
Понятно, что идея не нова и сравнить вы можете, например с данным сайтом http://design-seeds.com
Давайте разберем пример. С указанного выше сайта взяли картинку и их разбиение на цвета. Здесь можно заметить, что их задача — это выбрать основные центровые цвета, что немного отличается от нашей задачи, но все же.

Пример с сайта

Сначала посмотрим на наш метод выбора первоначальных центров, исходя из предположения простого количественного показателя использования цветов. Изначальные центры ниже подписано, сколько раз цвет встречался на картинке.

7 раз

4 раза

5 раз

6 раз

Ммммм, кто бы сказал по картинке, что это самые часто встречающиеся цвета? Понятно, что это вызвано так же и сжатием до 100 пикселей по меньшей из сторон, но все же. Сразу можно сказать, что притягивать к таким центрам остальные цвета сложно. В результате:

Все плохо, как и следовало ожидать. А что если попробовать представить спектр цветов в виде прямой от 0 до 255, равномерно разбить его на k отрезков и сделать центры точками с одинаковыми равномерными координатами? По понятным причинам они все будут оттенками серого. Пример для 6:

В результате:

Вот, уже лучше) Однако, чем плох этот метод? А тем, что этих цветов может и не быть на картинке (она может просто красная), получается, что изначально мы как бы сбиваем мишень(

Как вывод, могу сказать, что метод k-средних очень чувствителен к этим самы центроидам. И их поиск — это не менее важная задача, которую я Вам и предлагаю решить) Например, представьте что вы как бы объединяете точки, расширяя территории. Объединяя их в 3х мерном пространстве линейно увеличивая координаты. И без учета количественных показателей весов!)

Автор: Pavel Petropavlov

Оптимизация с учетом предпочтений

В прошлый раз, мы рассмотрели пример одной задачи, которую можно решить методами оптимизации. Напомним, что для применения оптимизации должны выполняться два основных требования: наличие целевой функции и тот факт, что близкие параметры дают близкие решения. Не каждую задачу, удовлетворяющую этим требованиям, можно решить методами оптимизации, но есть неплохие шансы, что попытка применить эти методы даст интересные результаты, о которых вы даже не подозревали.

На этот раз, мы займемся другой задачей, для которой оптимизация просто напрашивается. Общая формулировка такова: распределить ограниченные ресурсы между людьми, у которых есть явно выраженные предпочтения, так чтобы все были максимально счастливы (или, в зависимости от склада характера, минимально недовольны))))

Оптимизация распределения студентов по комнатам

Сегодня мы решим задачу о распределении студентов по комнатам в общежитии с учетом их основного и альтернативного пожеланий. Хотя формулировка довольно специфична, ее можно легко обобщить на похожие задачи, – тот же самый код годится для распределения игроков по столам в онлайновой карточной игре, для распределения ошибок между разработчиками в большом программном проекте и даже для распределения работы по дому между прислугой. Как и раньше, наша цель – собрать информацию об отдельных людях и найти такое сочетание, которое приводит к оптимальному результату.

В нашем примере будет пять двухместных комнат и десять претендующих на них студентов. У каждого студента есть основное и альтернативное пожелание.

# Двухместные комнаты
dorms = ['Zeus','Athena','Hercules','Bacchus','Pluto']

# Люди и два пожелания у каждого (основное, второстепенное)
prefs = [('Toby', ('Bacchus', 'Hercules')),
       ('Steve', ('Zeus', 'Pluto')),
       ('Karen', ('Athena', 'Zeus')),
       ('Sarah', ('Zeus', 'Pluto')),
       ('Dave', ('Athena', 'Bacchus')), 
       ('Jeff', ('Hercules', 'Pluto')), 
       ('Fred', ('Pluto', 'Athena')), 
       ('Suzie', ('Bacchus', 'Hercules')), 
       ('Laura', ('Bacchus', 'Hercules')), 
       ('James', ('Hercules', 'Athena'))]

Сразу видно, что удовлетворить основное пожелание каждого человека не удастся, так как на два места в комнате Bacchus имеется три претендента. Поместить любого из этих трех в ту комнату, которую он указал в качестве альтернативы, тоже невозможно, так как в комнате Hercules всего два места.

В приведенном примере общее число вариантов порядка 100 000, то можно перебрать их все и найти оптимальный. Но если комнаты будут четырехместными, то количество вариантов будет исчислять триллионами.

Представление решения

В каждой комнате должно оказаться ровно два студента. Будем считать, что в каждой комнате есть два отсека, то есть всего их в нашем случае будет десять. Каждому студенту по очереди назначается один из незанятых отсеков; первого можно поместить в любой из десяти отсеков, второго – в любой из оставшихся девяти и т. д.

Область определения для поиска (смотри предыдущую статью):

# [9, 8, 7, 6,..., 1]
domain = [i for i in xrange(9, 0, -1)]

Целевая функция

Целевая функция работает следующим образом. Создается начальный список отсеков, и уже использованные отсеки из него удаляются. Стоимость вычисляется путем сравнения комнаты, в которую студент помещен, с двумя его пожеланиями. Стоимость не изменяется, если студенту досталась та комната, в которую он больше всего хотел поселиться; увеличивается на 1, если это второе из его пожеланий; и увеличивается на 3, если он вообще не хотел жить в этой комнате.

def dorm_cost(vec):
 cost=0

 # Создаем список отсеков, т.е. первые 2 места - 0 отсек и т.д.
 slots = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

 # Цикл по студентам, i - порядковый номер студента
 for i in xrange(len(vec)):
  x = int(vec[i])
  dorm = dorms[slots[x]]
  pref = prefs[i][1]
  print x, '->', slots[x],'->', prefs[i][0], pref, '->', dorm

  # Стоимость основного пожелания равна 0, альтернативного – 1
  # Если комната не входит в список пожеланий, стоимость увеличивается на 3
  if pref[0] == dorm: cost += 0
  elif pref[1] == dorm: cost += 1
  else: cost += 3

  # Удалить выбранны
й отсек
  # Это самое важное действие тут,
  # прошу особо обратить на него внимание и учесть, что элементы сдвигаются
  del slots[x]

 return cost

При конструировании целевой функции полезно стремиться к тому, чтобы стоимость идеального решения (в данном случае каждый студент заселился в комнату, которую поставил на первое место в своем списке предпочтений) была равна нулю. В рассматриваемом примере мы уже убедились, что идеальное решение недостижимо, но, зная о том, что его стоимость равна нулю, можно оценить, насколько мы к нему приблизились. У этого правила есть еще одно достоинство – алгоритм оптимизации может прекратить поиск, если уже найдено идеальное решение.

Оптимизация

Всем кто не изучил методы оптимизации в предыдущей статье, бегом изучать!) Хорошим мальчикам и может даже девочкам, импортировать любой из методов и запустить!) Я, для примера, попробую на генетическом алгоритме.

result, score = genetic_optimize(domain, dorm_cost)
print result, score

Например у меня, нашелся такой результат [7, 1, 2, 0, 0, 1, 2, 1, 0] 1, что соответствует следующему выводу:

7 -> 3 -> Toby (‘Bacchus’, ‘Hercules’) -> Bacchus
1 -> 0 -> Steve (‘Zeus’, ‘Pluto’) -> Zeus
2 -> 1 -> Karen (‘Athena’, ‘Zeus’) -> Athena
0 -> 0 -> Sarah (‘Zeus’, ‘Pluto’) -> Zeus
0 -> 1 -> Dave (‘Athena’, ‘Bacchus’) -> Athena
1 -> 2 -> Jeff (‘Hercules’, ‘Pluto’) -> Hercules
2 -> 4 -> Fred (‘Pluto’, ‘Athena’) -> Pluto
1 -> 3 -> Suzie (‘Bacchus’, ‘Hercules’) -> Bacchus
0 -> 2 -> Laura (‘Bacchus’, ‘Hercules’) -> Hercules

Т.е. не устроило только Lauru и то, учтен был ее 2й вариант)

Вместо вывода

Итак, надеюсь, я показал, что используя одни алгоритмы, но меняя область определения и принцип расчета целевой функции, мы можем решить абсолютно разные оптимизационные задачи!)

Автор: Pavel Petropavlov

Задачи оптимизации

Давайте разберемся, как решать задачи со множеством участников, применяя технику стохастической оптимизации. По существу, оптимизация сводится к поиску наилучшего решения задачи путем апробирования различных решений и сравнения их между собой для оценки качества. Обычно оптимизация применяется в тех случаях, когда число решений слишком велико и перебрать их все невозможно.

У методов оптимизации весьма широкая область применения: в физике они используются для изучения молекулярной динамики, в биологии – для прогнозирования белковых структур, а в информатике – для определения времени работы алгоритма в худшем случае. В НАСА методы оптимизации применяют даже для проектирования антенн с наилучшими эксплуатационными характеристиками. Выглядят они так, как ни один человек не мог бы вообразить.

Мы же, для примера, возьмем классическую задачу группового путешествия!)

Наш пример относится к планированию группового путешествия дружеской компании из разных частей света. Всякий, кто пытался планировать поездку группы людей или даже одного человека, понимает, что нужно учитывать множество исходных данных, например: каким рейсом должен лететь каждый человек, сколько нужно арендовать машин и от какого аэропорта удобнее всего добираться. Также следует принять во внимание ряд выходных переменных: полная стоимость, время ожидания в аэропортах и непроизводительно потраченное время.

Формат данных

Планирование путешествия группы людей (в данном примере семейства Сидоровых), которые, отправляясь из разных мест, должны прибыть в одно и то же место.

Члены семьи живут в разных концах страны и хотят встретиться в Урюпинске. Все они должны вылететь в один день и в один день улететь и при этом в целях экономии хотели бы уехать из аэропорта и приехать в него на одной арендованной машине. Ежедневно, в славный город Урюпинск, из мест проживания любого члена семьи отправляются десятки рейсов, все в разное время. Цена билета и время в пути для каждого рейса разные.

Начнем со списка самих Сидоровых:

peoples = [('Seymour','BOS'),
    ('Franny','DAL'),
    ('Zooey','CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]

# место назначения
destination = 'LGA'

# словарь рейсов

flights = {('LGA', 'CAK'): [('6:58', '9:01', 238), ('8:19', '11:16', 122), ('9:58', '12:56', 249), ('10:32', '13:16', 139), ('12:01', '13:41', 267), ('13:37', '15:33', 142), ('15:50', '18:45', 243), ('16:33', '18:15', 253), ('18:17', '21:04', 259), ('19:46', '21:45', 214)], ('DAL', 'LGA'): [('6:12', '10:22', 230), ('7:53', '11:37', 433), ('9:08', '12:12', 364), ('10:30', '14:57', 290), ('12:19', '15:25', 342), ('13:54', '18:02', 294), ('15:44', '18:55', 382), ('16:52', '20:48', 448), ('18:26', '21:29', 464), ('20:07', '23:27', 473)], ('LGA', 'BOS'): [('6:39', '8:09', 86), ('8:23', '10:28', 149), ('9:58', '11:18', 130), ('10:33', '12:03', 74), ('12:08', '14:05', 142), ('13:39', '15:30', 74), ('15:25', '16:58', 62), ('17:03', '18:03', 103), ('18:24', '20:49', 124), ('19:58', '21:23', 142)], ('LGA', 'MIA'): [('6:33', '9:14', 172), ('8:23', '11:07', 143), ('9:25', '12:46', 295), ('11:08', '14:38', 262), ('12:37', '15:05', 170), ('14:08', '16:09', 232), ('15:23', '18:49', 150), ('16:50', '19:26', 304), ('18:07', '21:30', 355), ('20:27', '23:42', 169)], ('LGA', 'OMA'): [('6:19', '8:13', 239), ('8:04', '10:59', 136), ('9:31', '11:43', 210), ('11:07', '13:24', 171), ('12:31', '14:02', 234), ('14:05', '15:47', 226), ('15:07', '17:21', 129), ('16:35', '18:56', 144), ('18:25', '20:34', 205), ('20:05', '21:44', 172)], ('OMA', 'LGA'): [('6:11', '8:31', 249), ('7:39', '10:24', 219), ('9:15', '12:03', 99), ('11:08', '13:07', 175), ('12:18', '14:56', 172), ('13:37', '15:08', 250), ('15:03', '16:42', 135), ('16:51', '19:09', 147), ('18:12', '20:17', 242), ('20:05', '22:06', 261)], ('CAK', 'LGA'): [('6:08', '8:06', 224), ('8:27', '10:45', 139), ('9:15', '12:14', 247), ('10:53', '13:36', 189), ('12:08', '14:59', 149), ('13:40', '15:38', 137), ('15:23', '17:25', 232), ('17:08', '19:08', 262), ('18:35', '20:28', 204), ('20:30', '23:11', 114)], ('LGA', 'DAL'): [('6:09', '9:49', 414), ('7:57', '11:15', 347), ('9:49', '13:51', 229), ('10:51', '14:16', 256), ('12:20', '16:34', 500), ('14:20', '17:32', 332), ('15:49', '20:10', 497), ('17:14', '20:59', 277), ('18:44', '22:42', 351), ('19:57', '23:15', 512)], ('LGA', 'ORD'): [('6:03', '8:43', 219), ('7:50', '10:08', 164), ('9:11', '10:42', 172), ('10:33', '13:11', 132), ('12:08', '14:47', 231), ('14:19', '17:09', 190), ('15:04', '17:23', 189), ('17:06', '20:00', 95), ('18:33', '20:22', 143), ('19:32', '21:25', 160)], ('ORD', 'LGA'): [('6:05', '8:32', 174), ('8:25', '10:34', 157), ('9:42', '11:32', 169), ('11:01', '12:39', 260), ('12:44', '14:17', 134), ('14:22', '16:32', 126), ('15:58', '18:40', 173), ('16:43', '19:00', 246), ('18:48', '21:45', 246), ('19:50', '22:24', 269)], ('MIA', 'LGA'): [('6:25', '9:30', 335), ('7:34', '9:40', 324), ('9:15', '12:29', 225), ('11:28', '14:40', 248), ('12:05', '15:30', 330), ('14:01', '17:24', 338), ('15:34', '18:11', 326), ('17:07', '20:04', 291), ('18:23', '21:35', 134), ('19:53', '22:21', 173)], ('BOS', 'LGA'): [('6:17', '8:26', 89), ('8:04', '10:11', 95), ('9:45', '11:50', 172), ('11:16', '13:29', 83), ('12:34', '15:02', 109), ('13:40', '15:37', 138), ('15:27', '17:18', 151), ('17:11', '18:30', 108), ('18:34', '19:36', 136), ('20:17', '22:22', 102)]}

Словарь
рейсов имеет следующий формат: {(‘LGA’, ‘CAK’): [(‘6:58’, ‘9:01’, 238), (‘8:19′, ’11:16’, 122),….], …..} — (аэропорт вылета, прилета), как ключ и (время вылета, время прилета, стоимость), как значение. Заполните его произвольным способом, можно поискать на сайтах авиа и заполнить реальной ситуацией))

Для подобных задач необходимо определиться со способом представления потенциальных решений. Функции оптимизации, с которыми вы вскоре ознакомитесь, достаточно общие и применимы к различным задачам, поэтому так важно выбрать простое представление, которое не было бы привязано к конкретной задаче о групповом путешествии. Очень часто для этой цели выбирают список чисел. Каждое число обозначает рейс, которым решил лететь участник группы.

Например, в решении, представленном списком [1,4,3,2,7,3,6,3,2,4,5,3]
Сеймур (Seymour) летит первым рейсом из Бостона в Нью-Йорк и четвертым рейсом из Нью-Йорка в Бостон, а Фрэнни (Franny) – третьим рейсом из Далласа в Нью-Йорк и вторым обратно.

Целевая функция

Ключом к решению любой задачи оптимизации является целевая функция, и именно ее обычно труднее всего отыскать. Цель оптимизационного алгоритма состоит в том, чтобы найти такой набор входных переменных, который минимизирует целевую функцию. Поэтому целевая функция должна возвращать значение, показывающее, насколько данное решение неудовлетворительно. Возвращаемое значение должно быть тем больше, чем хуже решение.

Рассмотрим несколько параметров, которые можно измерить в примере с групповым путешествием:

Цена

Полная стоимость всех билетов или, возможно, среднее значение, взвешенное с учетом финансовых возможностей.

Время в пути

Суммарное время, проведенное всеми членами семьи в полете.

Время ожидания

Время, проведенное в аэропорту в ожидании прибытия остальных членов группы.

Время вылета

Если самолет вылетает рано утром, это может увеличивать общую стоимость из-за того, что путешественники не выспятся.

Время аренды автомобилей

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

Определившись с тем, какие переменные влияют на стоимость, нужно решить, как из них составить одно число. В нашем случае можно, например, выразить в деньгах время в пути или время ожидания в аэропорту. Скажем, каждая минута в воздухе эквивалентна $1 (иначе гово- ря, можно потратить лишние $90 на прямой рейс, экономящий полтора часа), а каждая минута ожидания в аэропорту эквивалентна $0,50. Можно было бы также приплюсовать стоимость лишнего дня аренды машины, если для всех имеет смысл вернуться в аэропорт к более поз- днему часу.

Определенная ниже, целевая функция shedule_cost принимает во внимание полную стоимость поездки и общее время ожидания в аэропорту всеми членами семьи. Кроме того, она добавляет штраф $50, если машина возвращена в более поздний час, чем арендована.

# время в минутах
def get_minutes(t):
 x=time.strptime(t,'%H:%M')
 return x[3]*60+x[4]

def schedule_cost(sol):
 totalprice = 0
 latestarrival = 0
 earliestdep = 24*60

 for d in xrange(len(sol)/2):
  # Получить список прибывающих и убывающих реисов
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]

  # Полная цена равна сумме цен на билет туда и обратно
  totalprice += outbound[2]
  totalprice += returnf[2]

  # Находим самыи позднии прилет и самыи раннии вылет
  if latestarrival < get_minutes(outbound[1]): latestarrival = get_minutes(outbound[1])
  if earliestdep > get_minutes(returnf[0]): earliestdep = get_minutes(returnf[0])

 # Все должны ждать в аэропорту прибытия последнего участника группы.
 # Обратно все прибывают одновременно и должны ждать свои реисы.
 totalwait = 0  
 for d in xrange(len(sol)/2):
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]
  totalwait += latestarrival - get_minutes(outbound[1])
  totalwait += get_minutes(returnf[0]) - earliestdep  

 # Для этого решения требуется оплачивать дополнительныи день аренды?
 # Если да, это обоидется в лишние $50!
 if latestarrival > earliestdep: totalprice += 50

 return totalprice + totalwait

Логика этой функции очень проста, но суть вопроса она отражает. Улучшить ее можно несколькими способами. Так, в текущей версии предполагается, что все члены семьи уезжают из аэропорта вместе, когда прибывает самый последний, а возвращаются в аэропорт к моменту вылета самого раннего рейса. Можно поступить по-другому: если человеку приходится ждать два часа или дольше, то он арендует отдельную машину, а
цены и время ожидания соответственно корректируются.

Случайный поиск

Случайный поиск – не самый лучший метод оптимизации, но он позволит нам ясно понять, чего пытаются достичь все алгоритмы, а также послужит эталоном, с которым можно будет сравнивать другие алгоритмы.

Соответствующая функция принимает два параметра. Domain – это список значений, определяющих количество вариантов рейсов каждого из участников путешествия. Важно что они отсортированы в том же порядке, что и сами участники, сначала идут в Урюпинск, потом оттуда. Длина решения совпадает с длиной этого списка.

Второй параметр, costf, – это целевая функция; в нашем примере в этом качестве используется schedule_cost. Она передается в виде параметра, чтобы алгоритм можно было использовать повторно и для других задач оптимизации. Алгоритм случайным образом генерирует 1000 гипотез и для каждой вызывает функцию costf. Возвращается наилучшая гипотеза (с минимальной стоимостью).

domain = []
for people in peoples:
 domain.append(len(flights[(people[1], destination)]) - 1)
 domain.append(len(flights[(destination, people[1])]) - 1)
print domain

def random_optimize(domain, costf):
 best=999999999
 bestr=None

 for i in xrange(0, 1000):
  # Выбрать случаиное решение
  r = [random.randint(0, domain[i]) for i in xrange(len(domain))]

  # Get the cost
  cost = costf(r)

  # Сравнить со стоимостью наилучшего наиденного к этому моменту решения
  if cost < best:
   best = cost
   bestr = r
 return r, best

result, score = random_optimize(domain, schedule_cost)
print result, score

Позапускав, я получил макс хороший вариант (из 10 запусков по 1000 вариантов) 3208$, будем с ним и сравнивать)

Алгоритм спуска с горы

Случайное апробирование решений очень неэффективно, потому что пренебрегает выгодами, которые можно получить от анализа уже найденных хороших решений. В нашем примере можно предположить, что расписание с низкой полной стоимостью похоже на другие расписания с низкой стоимостью.

Альтернативный метод случайного поиска называется алгоритмом спуска с горы (hill climbing). Он начинает со случайного решения и ищет лучшие решения (с меньшим значением целевой функции) по соседству. Можно провести аналогию со спуском с горы.

Представьте, что человечек на рисунке – это вы и оказались в этом месте по воле случая. Вы хотите добраться до самой низкой точки, чтобы найти воду. Для этого вы, наверное, осмотритесь и направитесь туда, где склон самый крутой. И будете двигаться в направлении наибольшей крутизны, пока не дойдете до точки, где местность становится ровной или начинается подъем.

Применим этот подход. Начнем со случайно выбранного расписания и просмотрим все расписания в его окрестности. В данном случае это означает просмотр таких расписаний, для которых один человек выбирает рейс, вылетающий чуть раньше или чуть позже. Для каждого из соседних расписаний вычисляется стоимость, и расписание с наименьшей стоимостью становится новым решением. Этот процесс повторяется и завершается, когда ни одно из соседних расписаний не дает улучшения стоимости.

def hill_climb(domain, costf):

 # Выбрать случаиное решение
 sol = [random.randint(0, domain[i]) for i in xrange(len(domain))]
 best = costf(sol)

 # Главныи цикл
 is_stop = False
 while not is_stop:
  # Создать список соседних решении
  neighbors = []
  for j in xrange(len(domain)):

   # Отходим на один шаг в каждом направлении
   if 0 < sol[j] < 9:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

   if 0 == sol[j]:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])

   if sol[j] == domain[j]:
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

  # Ищем наилучшее из соседних решении

  is_stop = True
  for j in xrange(len(neighbors)):
   cost = costf(neighbors[j])
   if cost < best:
    is_stop = False
    best = cost
    sol = neighbors[j]

 return sol, best

result, score = hill_climb(domain, schedule_cost)
print result, score

Для выбора начального решения эта функция генерирует случайный список чисел из заданного диапазона. Соседи текущего решения ищутся путем посещения каждого элемента списка и создания двух новых списков, в одном из которых этот элемент увеличен на единицу, а в другом уменьшен на единицу. Лучшее из соседних решений становится новым решением.

На самом деле, в данном случае
этот мест даст так себе результаты. Хотя, в большинстве случаев, лучше чем 1000 случайных вариантов. Однако у алгоритма спуска с горы, есть один существенный недостаток.

Из рисунка видно, что, спускаясь по склону, мы необязательно отыщем наилучшее возможное решение. Найденное решение будет локальным минимумом, то есть лучшим из всех в ближайшей окрестности, но это не означает, что оно вообще лучшее. Решение, лучшее среди всех возможных, называется глобальным минимумом, и именно его хотят найти все алгоритмы оптимизации. Один из возможных подходов к решению проблемы называется спуском с горы со случайным перезапуском. В этом случае алгоритм спуска выполняется несколько раз со случайными начальными точками в надежде, что какое-нибудь из найденных решений будет близко к глобальному минимуму. Так же, все усугубляется тем, что у такой ф-ии как наша, большая импульсивность (много локальных минимумов и максимумов), очень не линейная скорость роста в разных точках, в общем очень много факторов, с учетом того, что мы рассматриваем ф-ию в 12 мерном пространстве и в каждом из них она ведет себя по-разному…

Алгоритм имитации отжига

Алгоритм имитации отжига навеян физическими аналогиями. Отжигом называется процесс нагрева образца с последующим медленным охлаждением. Поскольку сначала атомы заставляют попрыгать, а затем постепенно «отпускают вожжи», то они переходят в новую низко-энергетичную конфигурацию.

Алгоритмическая версия отжига начинается с выбора случайного решения задачи. В ней используется переменная, интерпретируемая как температура, начальное значение которой очень велико, но постепенно уменьшается. На каждой итерации случайным образом выбирается один из параметров решения и изменяется в определенном направлении.

Тут есть важная деталь: если новая стоимость ниже, то новое решение становится текущим, как и в алгоритме спуска с горы. Но, даже если новая стоимость выше, новое решение все равно может стать текущим с некоторой вероятностью. Так мы пытаемся избежать ситуации скатывания в локальный минимум.

Иногда необходимо перейти к худшему решению, чтобы найти лучшее. Алгоритм имитации отжига работает, потому что всегда готов перейти к лучшему решению, но ближе к началу процесса соглашается принять и худшее. По мере того как процесс развивается, алгоритм соглашается на худшее решение все с меньшей охотой, а в конце работы принимает только лучшее. Вероятность того, что будет принято решение с более высокой стоимостью, рассчитывается по формуле:

Поскольку температура (готовность принять худшее решение) вначале очень высока, то показатель степени близок к 0, поэтому вероятность равна почти 1. По мере уменьшения температуры разность между высокой стоимостью и низкой стоимостью становится более значимой, а чем больше разность, тем ниже вероятность, поэтому алгоритм из всех худших решений будет выбирать те, что лишь немногим хуже текущего.

def annealing_optimize(domain, costf, T=10000.0, cool=0.99, step=1):
 
 # Выбрать случаиное решение
 vec = [random.randint(0, domain[i]) for i in xrange(len(domain))]

 while T > 0.1:
  # Выбрать один из индексов
  i = random.randint(0, len(domain)-1)

  # Выбрать направление изменения
  dir = random.randint(-step, step)

  # Создать новыи список, в котором одно значение изменено
  vecb = vec[:]
  vecb[i] += dir
  if vecb[i] < 0: vecb[i] = 0
  elif vecb[i] > domain[i]: vecb[i] = domain[i]

  # Вычислить текущую и новую стоимость
  ea = costf(vec)
  eb = costf(vecb)
  p = pow(math.e, (-eb-ea)/T)

  # Новое решение лучше? Если нет, метнем кости
  if (eb < ea or random.random() < p):
   vec = vecb      

  # Уменьшить температуру
  T = T * cool
 return vec, eb

result, score = annealing_optimize(domain, schedule_cost)
print result, score

На каждой итерации в качестве i случайно выбирается одна из переменных решения, а dir случайно выбирается межд

Поиск и ранжирование

Сегодня мы рассмотрим систему полнотекстового поиска, она позволяют искать слова в большом наборе документов и сортируют результаты поиска по релевантности найденных документов запросу. Алгоритмы полнотекстового поиска относятся к числу важнейших среди алгоритмов коллективного разума. Новые идеи в этой области помогли сколотить целые состояния. Широко распространено мнение, что своей быстрой эволюцией от академического проекта к самой популярной поисковой машине в мире система Google обязана прежде всего алгоритму ранжирования страниц PageRank.

Что такое поисковая машина

Итак, давайте же создадим здоровую конкуренцию мировым поисковикам!) Статья так же будет полезна начинающим SEO специалистам, т.к. покажет некоторые величины, которые могут влиять на позиции вашего сайта в поиске.

Первый шаг при создании поисковой машины – разработать методику сбора документов. Иногда для этого применяется ползание (начинаем с небольшого набора документов и переходим по имеющимся в них ссылкам), а иногда отправной точкой служит фиксированный набор документов, быть может, хранящихся в корпоративной сети интранет.

Далее собранные документы необходимо проиндексировать. Обычно для этого строится большая таблица, содержащая список документов и вхождений различных слов. В зависимости от конкретного приложения сами документы могут и не храниться в базе данных; в индексе находится лишь ссылка (путь в файловой системе или URL) на их местонахождение

Ну и последний шаг – это, конечно, возврат ранжированного списка документов в ответ на запрос. Имея индекс, найти документы, содержащие заданные слова, сравнительно несложно; хитрость заключается в том, как отсортировать результаты. Можно придумать огромное количество метрик, и недостатков в них.

Итак, для данной задачи нам потребуется DB (PostgreSQL) и Python (библиотека Grab). А за источник индексирования, новостную ленту rambler’а.

Все функции, описаные ниже, у меня являются методами классов, с такой инициализацией:

class Indexer:

 def __init__(self):
   
  self.conn = psycopg2.connect("dbname='postgres' user='postgres' password='120789' host='localhost'")

  self.cur = self.conn.cursor()
  self.cur.execute("set search_path to 'rambler_search'")

  self.grab = Grab()

 def __del__(self):
  self.conn.close()

 def dbcommit(self):
  self.conn.commit()

Код паука

Для начала, рассмотрим код функции, которая будет забирать страницу статьи, разбивать ее на текст, вычленяя ссылки и передавать их индексирующим функциям. На вход подается список ссылок, являющихся вхождением для паука.

Эта функция в цикле обходит список страниц, вызывая для каждой функцию addtoindex. Далее она получает все ссылки на данной странице и добавляет их URL в список newpages. В конце цикла newpages присваивается pages, и процесс повторяется.

Эту функцию можно было бы определить рекурсивно, так что при обработке каждой ссылки она вызывала бы сама себя. Но, реализовав поиск в ширину, мы упростим модификацию кода в будущем, позволив пауку ползать непрерывно или сохранять список неиндексированных страниц для последующего индексирования. Кроме того, таким образом мы избегаем опасности переполнить стек.

  
  # Начинаем со списка страниц для индексации
  # опускаемся в глубину на 2 уровня
 def crawl(self, pages, depth=2):

  rambler_news_href_pattern = re.compile(r'(^http://news.rambler.ru/[d]+)')

  for i in range(depth):
   newpages={}

   for page in pages:

    try:
      self.grab.go(page)

    except:
      print "Could not open %s" % page
      continue

    try:
      article_text = '' # текст статьи
      for paragraph in self.grab.tree.xpath("//p[contains(@class, 'b-article__paragraph')]"):
      article_text += paragraph.text_content()

      self.addtoindex(page, article_text) # записываем в базу текст статьи с индексацией

      links = self.grab.tree.xpath("//a")
      for link in links:

     if ('href' in link.attrib):
       url = urljoin(page, link.attrib['href']).split('#')[0]# делаем полную ссылку и удаляем часть за # если она есть

       match = rambler_news_href_pattern.findall(url)
       if match:
        url = match[0]

      if url[0:4] == 'http' and not self.isindexed(url):
       newpages[url] = 1

      linkText = link.text_content() # текст ссылки
      self.addlinkref(page, url, linkText) # записываем в базу текст ссылки с индексацией

      self.dbcommit()

    except Exception, e:
      print "Could not parse page %s" % page, e


   pages = newpages

Построение индекса

Наш следующий шаг – подготовка базы данных для хранения полнотекстового индекса. Я уже говорил, что такой индекс представляет собой список слов, с каждым из которых ассоциировано множество документов, где это слово встречается, и место вхождения слова в документ. В данном примере мы анализируем только текст на странице, игнорируя все нетекстовые элементы. Кроме того, индексируются только сами слова, а все знаки препинания удаляются. Такой метод выделения слов несовершенен, но для построения простой поисковой машины сойдет.

Создание схемы

Подождите запускать программу – нужно сначала подготовить базу данных. Схема простого индекса состоит из пяти таблиц. Первая (url_list) – это список проиндексированных URL. Вторая (word_list) – список слов, а третья (word_location) – список мест вхождения слов в документы. В оставшихся двух таблицах хранятся ссылки между документами. В таблице link хранятся идентификаторы двух URL, связанных ссылкой, а в таблице link_words есть два столбца – word_id и link_id – для хранения слов, составляющих ссылку. Вся схема изображена на рисунке ниже. Код запросов приводить не буду, должны ведь и вы поработать)))

Выделение слов на странице

Для решения данной задачи, воспользуемся простейшей функцией. Мы не будем вводить стоп слова, которые не нужно индексировать, а просто введем ограничение на длину слова в 3 символа, тем самым убрав предлоги и другой мусор (хоть и пострадают всякие мелкие слова, типа «мир», «тир», «пир»).

def getwords(html):
    words = []
    for split_str in html.split():
        t = re.split("[s;:-_*".,?!()'&#«»]", split_str)
        words += [a.lower() for a in t if a != '' and len(a) > 3]
    return words

Добавление в индекс

Теперь мы готовы написать код метода addtoindex. Он вызывает две функции, написанные в предыдущем разделе, чтобы получить список слов на странице. Затем эта страница и все найденные на ней слова добавляются в индекс и создаются ссылки между словами и их вхождениями в документ. В нашем примере адресом вхождения будет считаться номер слова в списке слов.

  
        def addtoindex(self, url, text):

  if self.isindexed(url): return # если уже индексирована - пропускаем
  print 'Indexing %s' % url

  # Получаем слова из текста
  words = getwords(text)

  # Получаем id url'а
  url_id = self.getentryid('url_list', 'url', url)

  # Связываем слова с этим урлом
  for i, word in enumerate(words): # пронумеруем слова
    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into word_location(url_id, word_id, location) values (%d, %d, %d)" % (url_id, word_id, i))
    self.dbcommit()

Хорошо, теперь нужно описать функцию getentryid — возвращающую id записи из бд и isindexed — проверяющую, не индексировали ли мы эту страницу раньше.

  
        # Узнаем id записи в БД, если нет
        # иначе записываем и возвращаем новый
 def getentryid(self, table, field, value, createnew=True):

  self.cur.execute("select id from %s where %s = '%s'" % (table, field, value))
  cur = self.cur.fetchone()

  if not cur:
   # print (table, field, value)
   self.cur.execute("insert into %s (%s) values ('%s') returning %s.id" % (table, field, value, table))
   cur = self.cur.fetchone()
   self.dbcommit()

   return cur[0]

  else:
    return cur[0]

       # Возвращаем True, если посещали страницу
 def isindexed(self, url):
  self.cur.execute("select id from url_list where url = '%s'" % url)
  u = self.cur.fetchone()

  if u:
   # Проверяем, что паук посещал страницу
   self.cur.execute("select count(1) from word_location where url_id = %d" % u[0])
   v = self.cur.fetchone()

   if v[0]:
    return True

  return False

Последняя функция, необходимая нам для начала индексирования — это addlinkref. Как следует из ее названия, она заносит ссылки и слова из которых они состоят к нам в БД.

 def addlinkref(self, urlFrom, urlTo, linkText):

  words = getwords(linkText)
  from_id = self.getentryid('url_list', 'url', urlFrom)
  to_id = self.getentryid('url_list', 'url', urlTo)

  if from_id == to_id: return

  self.cur.execute("insert into link(from_id, to_id) values (%d, %d) returning link.id" % (from_id, to_id))
  link_id = self.cur.fetchone()[0]

  for word in words:

    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into link_words(link_id, word_id) values (%d, %d)" % (link_id, word_id))

Ну что же, на этом этапе мы можем запустить паука и создать базу данных)

Запросы

Теперь, когда у нас есть материал, с которым можно работать, необходимо написать сам поисковик. Начнем мы с мал
ого, грубого поиска, по абсолютному вхождению фразы в новость.

Таблица word_location обеспечивает простой способ связать слова с документами, так что мы можем легко найти, какие страницы содержат данное слово. Однако поисковая машина была бы довольно слабой, если бы не позволяла задавать запросы с несколькими словами. Чтобы исправить это упущение, нам понадобится функция, которая принимает строку запроса, разбивает ее на слова и строит SQL-запрос для поиска URL тех документов, в которые входят все указанные слова.

 def get_match_rows(self, query):

  select_query_add = []
  join_query_add = []
  where_query_add = []

  main_search_query = """ 
     SELECT wl0.url_id, %s
     FROM word_location wl0
     %s 
     WHERE %s
    """

  query_words = getwords(query)

  query_word_ids = []
  for query_word in query_words:

   self.cur.execute("select id from word_list where word = '%s'" % query_word)
   query_word_id = self.cur.fetchone()

   if query_word_id:
    query_word_ids.append(query_word_id[0])

  if query_word_ids:
   for position, query_word_id in enumerate(query_word_ids):

    if position:
     join_query_add.append('JOIN word_location wl%d ON wl%d.url_id = wl%d.url_id' % (position, position-1, position))

    select_query_add.append('wl%d.location' % position)
    where_query_add.append('wl%d.word_id = %d' % (position, query_word_id))

   main_search_query = main_search_query % (', '.join(select_query_add), ' '.join(join_query_add), ' and '.join(where_query_add))

   self.cur.execute(main_search_query)
   search_results = self.cur.fetchall()
   
   return search_results, query_word_ids

Данная функция всего лишь создает строгий JOIN, типа такого:

 
 SELECT wl0.url_id, wl0.location, wl1.location
 FROM word_location wl0
 JOIN word_location wl1 ON wl0.url_id = wl1.url_id 
 WHERE wl0.word_id = 2734 and wl1.word_id = 2698

В результате, получаем список кортежей и список с id слов. Каждый кортеж — это сто список вида (id новости, позиция 1го слова, позиция 2го слова…)

Ранжирование по содержимому

Итак, худо-бедно, но мы научились искать по индексу. Однако возвращаем мы их в том порядке, в котором они посещались пауком. Чтобы решить эту проблему, необходимо как-то присвоить страницам ранг относительно данного запроса и уметь возвращать их в порядке убывания рангов.

В этом разделе мы рассмотрим несколько способов вычисления ранга
на основе самого запроса и содержимого страницы, а именно:

Частота слов

Количество вхождений в документ слова, указанного в запросе, помогает определить степень релевантности документа.

Расположение в документе

Основная тема документа, скорее всего, раскрывается ближе к его началу.

Расстояние между словами

Если в запросе несколько слов, то они должны встречаться в документе рядом.

Самые первые поисковые машины (кстати rambler.ru) часто работали только с подобными метриками и тем не менее давали пристойные результаты. Давайте добавим следующие методы:

 # Функция, которая взвешивает результаты
 def get_scored_list(self, rows, word_ids):

  total_scores = {row[0]: 0 for row in rows}

  if rows:
   # Список весовых функций
   weight_functions = [
      ]

   for (weight, scores) in weight_functions:
     for url in total_scores:
    total_scores[url] += weight * scores[url]

  return total_scores

 # Возвращает полный урл по id
 def get_url_name(self, url_id):

  self.cur.execute("select url from url_list where id = %d" % url_id)

  return self.cur.fetchone()[0]

 # Основная функция поиска
 def search(self, search_sentence):

  search_results, word_ids = self.get_match_rows(search_sentence)
  scores = self.get_scored_list(search_results, word_ids)

  ranked_scores = [(score, url) for (url, score) in scores.items()]
  ranked_scores.sort()
  ranked_scores.reverse()

  for (score, url_id) in ranked_scores[0:10]:
    print '%ft%s' % (score, self.get_url_name(url_id))

  return word_ids, [r[1] for r in ranked_scores[0:10]]

Наиболее важна здесь функция get_scored_list, код которой мы будем постепенно уточнять. По мере добавления функций ранжирования мы будем вводить их в список weight_functions и начнем взвешивать полученные результаты.

Функция нормализации

Все рассматриваемые ниже функции ранжирования возвращают словарь, в котором ключом является идентификатор URL, а значением – числовой ранг. Иногда лучшим считается больший ранг, иногда – меньший. Чтобы сравнивать результаты, получаемые разными методами, необход
имо как-то нормализовать их, то есть привести к одному и тому же диапазону и направлению.
Функция нормализации принимает на входе словарь идентификаторов и рангов и возвращает новый словарь, в котором идентификаторы те же самые, а ранг находится в диапазоне от 0 до 1. Ранги масштабируются по близости к наилучшему результату, которому всегда припи- сывается ранг 1. От вас требуется лишь передать функции список рангов и указать, какой ранг лучше – меньший или больший:

 def normalize_scores(self, scores, smallIsBetter=0):

  vsmall = 0.00001 # Avoid division by zero errors

  if smallIsBetter:
   minscore = min(scores.values())
   return {u: float(minscore)/max(vsmall, l) for (u,l) in scores.items()}

  else:
   maxscore = max(scores.values())
   if maxscore == 0: maxscore = vsmall
   return {u: float(c)/maxscore for (u,c) in scores.items()}

  return scores

Отлично! Пора заняться весовыми функциями, для которых мы и придумали эту нормализацию.

Весовые функции

Частота слов

Метрика, основанная на частоте слов, ранжирует страницу исходя из того, сколько раз в ней встречаются слова, упомянутые в запросе. Если я выполняю поиск по слову python, то в начале списка скорее получу страницу, где это слово встречается много раз, а не страницу о музыканте, который где-то в конце упомянул, что у него дома живет питон.

def frequency_score(self, rows):

  counts = {row[0]:0 for row in rows}
  for row in rows: 
   counts[row[0]] += 1

  return self.normalize_scores(counts)

Чтобы активировать ранжирование документов по частоте слов, измените строку функции get_scored_list, где определяется список weight_functions, следующим образом:

weight_functions = [(1.0,self.frequency_score(rows))]

Запустите поиск снова и радуйтесь!)

Расположение в документе

Еще одна простая метрика для определения релевантности страницы запросу – расположение поисковых слов на странице. Обычно, если страница релевантна поисковому слову, то это слово расположено близко к началу страницы, быть может, даже находится в заголовке.

def location_score(self, rows):

  locations = {}
  for row in rows:
   loc = sum(row[1:])
   if locations.has_key(row[0]):
    if loc < locations[row[0]]:
     locations[row[0]] = loc
   else:
    locations[row[0]] = loc

  return self.normalizescores(locations, smallIsBetter=1)

Расстояние между словами

Если запрос содержит несколько слов, то часто бывает полезно ранжировать результаты в зависимости от того, насколько близко друг к другу встречаются поисковые слова. Как правило, вводя запрос из нескольких слов, человек хочет найти документы, в которых эти слова концептуально связаны. Рассматриваемая метрика допускает изменение порядка и наличие дополнительных слов между поисковыми.

 def distance_score(self, rows):

  mindistance = {}

  # Если только 1 слово, любой документ выигрывает
  if len(rows[0]) <= 2:
   return {row[0]: 1.0 for row in rows}

  mindistance = {}

  for row in rows:
   dist = sum([abs(row[i]-row[i-1]) for i in xrange(2, len(row))])

   if mindistance.has_key(row[0]):
    if dist < mindistance[row[0]]:
     mindistance[row[0]] = dist
   else:
    mindistance[row[0]] = dist

  return self.normalize_scores(mindistance, smallIsBetter=1)

Использование внешних ссылок на сайт

Все обсуждавшиеся до сих пор метрики ранжирования были основаны на содержимом страницы. Часто результаты можно улучшить, приняв во внимание, что говорят об этой странице другие, а точнее те сайты, на которых размещена ссылка на нее. Особенно это полезно при индексировании страниц сомнительного содержания или таких, которые могли быть созданы спамерами, поскольку маловероятно, что на такие страницы есть ссылки с настоящих сайтов.

Простой подсчет ссылок

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

def inbound_link_score(self, rows):

  unique_urls = {row[0]: 1 for row in rows}
  inbound_count = {}
  
  for url_id in unique_urls:
   self.cur.execute('select count(*) from link where to_id = %d' % url_id)
   inbound_count[url_id] = self.cur.fetchone()[0]

  return self.normalize_scores(inbound_count)

Описанный алгоритм трактует все внешние ссылки одинаково, но такой уравнительный подход открывает возможность для манипулирования, поскольку кто угодно может создать несколько сайтов, указывающих на страницу, ранг которой он хочет поднять. Также возможно, что людям более интерес

Рекомендование предметов

В прошлом посте мы с Вами разобрались, как ранжировать людей по вкусам и говорить кто на нас похож больше всех. Теперь займемся связанной задачей — рекомендацией фильмов!

Фильтрация по схожести образцов

Мы реализовали механизм рекомендования таким образом, что для создания набора данных необходимы оценки, выставленные каждым пользователем. Для нескольких тысяч людей или предметов это, возможно, и будет работать, но на таком большом сайте, как kinopoisk.ru, сравнение каждого пользователя со всеми другими, а затем сравнение товаров, которым каждый пользователь выставил оценки, займет недопустимо много времени.

Техника, которую мы применяли до сих пор, называется коллаборативной фильтрацией по схожести пользователей. Альтернатива известна под названием «коллаборативная фильтрация по схожести образцов». Когда набор данных очень велик, коллаборативная фильтрация по схожести образцов может давать лучшие результаты, причем многие вычисления можно выполнить заранее, поэтому пользователь получит рекомендации быстрее.

Процедура фильтрации по схожести образцов во многом основана на уже рассмотренном материале. Основная идея заключается в том, чтобы для каждого образца заранее вычислить большинство похожих на него, при помощи запроса выше. Тогда для выработки рекомендаций пользователю достаточно будет найти те образцы, которым он выставил наивысшие оценки, и создать взвешенный список образцов, максимально похожих на эти. Отметим одно существенное отличие: хотя на первом шаге необходимо исследовать все данные, результаты сравнения образцов изменяются не так часто, как результаты сравнения пользователей. Это означает, что не нужно постоянно пересчитывать для каждого образца список похожих на него; это можно делать, когда нагрузка на сайт невелика, или вообще на отдельном компьютере.

Итак, создадим табличку, куда будем записывать коэффициенты схожести фильмов между собой.

CREATE TABLE movies_similarity
(
  id serial NOT NULL,
  film_id1 integer NOT NULL,
  film_id2 integer NOT NULL,
  pirson_koef double precision NOT NULL,
  CONSTRAINT movies_similarity_pk PRIMARY KEY (id)
)

Туда при помощи запроса и конструкции INSERT INTO запишем данные фильмов, которые мы оценили уже на сайте.

Выдача рекомендаций

Теперь вы готовы выдавать рекомендации, пользуясь словарем данных о схожести образцов без обращения ко всему набору данных. Необходимо получить список всех образцов, которым пользователь выставлял оценки, найти похожие и взвесить их с учетом коэффициентов подобия. Давайте разберем пример:

В каждой строке указан фильм, который я смотрел, и оценка, которую я ему выставил. Для каждого фильма, который я не смотрел, имеется столбец, где показано, насколько он похож на виденные мной фильмы. Например, коэффициент подобия между фильмами «Superman» и «The Night Listener» равен 0,103. В столбцах с названиями, начинающимися с О.x, показана моя оценка, умноженная на коэффициент подобия; поскольку я поставил фильму «Superman» оценку 4,0, то, умножая число на пересечении строки «Superman» и столбца «Night» на 4,0, получаем: 4,0 × 0,103 = 0,412.

В строке «Итого» просуммированы коэффициенты подобия и значения в столбцах «О.x» для каждого фильма. Чтобы предсказать мою оценку фильма, достаточно разделить итог для колонки «О.x» на суммарный коэффициент подобия. Так, для фильма «The Night Listener» прогноз моей оценки равен 1,378/0,433 = 3,183.

Если алгоритм понятен, давайте реализуем его:

select
ms.film_id1, 
case when sum(ms.pirson_koef)<>0
then
 sum(v.vote*ms.pirson_koef)/sum(ms.pirson_koef) 
else 
 0
end
from votes v
join movies_similarity ms on ms.film_id2=v.film_id
where v.user_id=4722023
group by ms.film_id1
order by case when sum(ms.pirson_koef)<>0
then
 sum(v.vote*ms.pirson_koef)/sum(ms.pirson_koef) 
else 
 0
end desc

В общем из тех 14 фильмов, что я лайкнул мне посоветовали посмотреть — «Голова-ластик»
Ну что же…думаю этим и займусь) А вы найдите себе фильм на вечер!)

Автор: Pavel Petropavlov

Подбор предметов

Теперь вы знаете, как искать похожих людей и рекомендовать предметы данному человеку. Но что если нужно узнать, какие предметы похожи друг на друга? В данном случае вы можете определить степень сходства, выявив людей, которым понравился данный товар, и посмотрев, что еще им понравилось. По существу, это тот же метод, которым мы уже пользовались для определения похожести людей, – нужно лишь вместо людей всюду подставить товары. Излогаясь математическим языком — транспонировать)

Подбор схожих предметов

Произвидя поиск таким образом логика будет следующей: сравниваем 2 фильма и находим всех людей, которые смотрели оба фильма и смотрим оценки выставленные второму, если они хорошие, а лучше все 10ки)

Практика Евклида

select
v1.film_id, v2.film_id,
1/(1+(|/sum((v1.vote-v2.vote)^2))),--евклидово не взвешенное расстояние
count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326
group by v1.film_id, v2.film_id
--having count(1)>10
order by 1/(1+(|/sum((v1.vote-v2.vote)^2))) desc, count(1) desc

Для сравнения возьмем фильм «Побег из Шоушенка». Метод Евклида посчитал, что на него больше всего похож фильм «Реал Мадрид». Спросите чем? Отвечу:

select
v1.film_id, v2.film_id,
v1.vote vote1, v2.vote vote2, v1.user_id, v2.user_id 
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326
and v1.film_id=155080

5 разных людей смотрели оба фильма и поставили не много не мало все 10ки!!! Но конечно, данный алгоритм никак не учитывает жанры, режиссеров или актеров. Однако никто не мешает ввести вам такие дополнительные фильтрующие весовые функции.

Практика Пирсона

select
v1.film_id,
case when ((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float) <> 0
then
	(sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float))
else
	0
end,
count(1)--кол-во общих критиков(вес для ф-ии)
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326 --фильм для сравнения
group by v1.film_id, v2.film_id
--having count(1)>10
order by 
case when ((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float) <> 0
then
	(sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float))
else
	0
end
desc,
count(1) desc

Запустив пирсона, получим совсем другой фильм — «Крезанутые». И это всего при 2х общих критиках. В общем советую Вам обратить внимание на закомментированную строку с having, считаю что нужно ее применить для более точного совпадения)

Автор: Pavel Petropavlov