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

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

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

Совсем недавно, компания 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 раза

4 раза

4 раза

5 раз

6 раз

---

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

---

---

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

---

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

---

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

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