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

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

Я кратко поясню, в чем основной недостаток облака тегов. Представьте, что у вас есть парочка тегов, которые вы используете очень часто и несколько других тегов, которые встречаются от случая к случаю. Каким шрифтом будут написаны имена тегов?

Очевидно, что самые популярные теги будут написаны самым большим шрифтом, а остальные – самым мелким. Чтобы наглядно проиллюстрировать проблему я изменил частоту появления тегов в прошлом примере и сделал скриншот (число в скобках указываем количество использований тега).
simple tag cloud

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

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

Сами группы нужно будет как-нибудь визуально разделить. Например, показывать в отдельных блоках или выделить цветом. Вариантов масса.

Для нашего примера очевидно, что теги AJAX и JavaScript должны находиться в одной группе, а PHP, Java и HTML – в другой.

Кроме того, это разбиение на группы можно использовать и в SEO’шных целях. Например, есть у вас в блоге 20 постов. Допустим, для каждого вы задали по 2-3 общих тега и по 5 уникальных. Разбиваем все теги на две группы (общие теги будут сгруппированы отдельно от уникальных, т.к. встречаются значительно чаще) и формируем два облака.

Естественно, облака нужно показывать в табах и, по-умолчанию, должен быть открыт таб с общими тегами. Пример табов можно посмотреть у меня в сайдбаре. Таким образом, получается более 100 ссылок на страницы второго уровня, но посетитель (модератор) видит только общие теги (маленькое облако) такое же, как на большинстве «белых» сайтов. Чтобы увидеть остальные ссылки ему придется кликнуть по заголовку таба с уникальными тегами (большим облаком).

Вроде бы идея простая, но, алгоритм разделения немного сложнее. В данном случае удобнее всего использовать т.н. K-means algorithm (алгоритм k-means (иногда называют k-средних)).

Принцип работы алгоритма изображен на диаграмме.
k means algorithm

1) Задаем количество кластеров (групп).

2) Для каждой группы создаем центр масс. Это обычное число, которое связано с параметрами группы, по которым выполняется разбиение. В данном случае параметр один – частота использования тега.

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

3) Определяем расстояния от каждого центра масс до каждого тега. Нет, линейку брать не нужно . Достаточно отнять количество использований тега от центра масс.

4) Группируем теги в кластеры. Принцип простой. Находим, какой центр масс находится ближе всего от заданного тега. В этот кластер тег и добавляем.

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

6) Повторяем пункты 3-5.

7) Алгоритм завершается, когда распределение тегов по кластерам перестает изменяться.

Подробнее об этом алгоритме можно почитать в этой статье.

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

   1.
      <?php
   2.
      class TagCloudModel extends Model {
   3.
         
   4.
          private $centroids;
   5.
          private $cloud;
   6.
          private $clusters;
   7.
         
   8.
          function TagCloudModel() {
   9.
              parent::Model();
  10.
          }
  11.
         
  12.
          /**
  13.
           * Возвращает данные, необходимые для построения облака тегов
  14.
           * (без разбиения на кластеры)
  15.
           *
  16.
           * @return массив с облаком
  17.
           */
  18.
          function getTagCloudData() {
  19.
              $qGetCloud = "SELECT tags.tag, COUNT(posts_tags.tagid) AS posts_count".
  20.
                          " FROM posts_tags LEFT JOIN tags ON posts_tags.tagid=tags.id".
  21.
                          " GROUP BY tags.id";
  22.
              $res = $this->db->query($qGetCloud);
  23.
              if ($res->num_rows() == 0) {
  24.
                  return false;
  25.
              }
  26.
              else {
  27.
                  return $res->result_array();
  28.
              }
  29.
          }
  30.
         
  31.
          /**
  32.
           * Разбивает облако тегов на заданное количество кластеров.
  33.
           *
  34.
           * @param $clustersNum количество кластеров
  35.
           * @return массив с результатами
  36.
           *  $res[0] – первый кластер, содержит массив со всеми рубриками, которые в него входят
  37.
           *  вывод записей для всех кластеров
  38.
           *  foreach ($res as $cluster) {
  39.
           *      foreach ($cluster as $tag) {
  40.
           *          echo $tag['tag'].'('.$tag['posts_count'].')';
  41.
           *      }
  42.
           *  }
  43.
           */
  44.
          function getClusteredCloud($clustersNum) {
  45.
              //получаем общее облако тегов
  46.
              $this->cloud = $this->getTagCloudData();
  47.
              //разбиваем его на заданное количество кластеров
  48.
              //определяем начальные центры масс каждого кластера
  49.
              //для этого находим теги с максимальным и минимальным количеством постов
  50.
              $min = $this->cloud[0]['posts_count'];
  51.
              $max = $this->cloud[0]['posts_count'];
  52.
              for ($i = 1; $i < count($this->cloud); $i++) {
  53.
                  if ($this->cloud[$i]['posts_count'] > $max) {
  54.
                      $max = $this->cloud[$i]['posts_count'];
  55.
                  }
  56.
                  if ($this->cloud[$i]['posts_count'] < $min) {
  57.
                      $min = $this->cloud[$i]['posts_count'];
  58.
                  }
  59.
              }
  60.
              //формируем массив с начальными центрами масс
  61.
              //идея такая: первый центр масс равен минимальному элементу,
  62.
              //последний – максимальному, все остальные – равномерно распределены
  63.
              //между ними
  64.
              $step = ($max – $min) / ($clustersNum – 1);
  65.
              $this->centroids = array();
  66.
              for ($i = 0; $i < $clustersNum; $i++) {
  67.
                  $this->centroids[$i] = $min + $i*$step;
  68.
              }
  69.
              //первоначальная разбивка на группы
  70.
              $prevClusters = array();
  71.
              while (TRUE) {
  72.
                  //рассчитываем расстояние от каждого тега до центра масс
  73.
                  $distances = $this->_getDistances();
  74.
                  $this->clusters = $this->_clasterizeTags($distances);
  75.
                  if ($prevClusters === $this->clusters) {
  76.
                      break;
  77.
                  }
  78.
                  else {
  79.
                      $prevClusters = $this->clusters;
  80.
                      $this->centroids = $this->_recalcCentroids();
  81.
                  }
  82.
              }
  83.
              //формируем облако тегов, разбитое на кластеры
  84.
              //все кластеры, которые не содержат тегов, будут пропущены
  85.
              foreach ($this->clusters as $cIndex => $cluster) {
  86.
                  $cur = 0;
  87.
                  foreach ($cluster as $tIndex => $tag) {
  88.
                      if ($tag === 1) {
  89.
                          $clusteredCloud[$cIndex][$cur] = $this->cloud[$tIndex];
  90.
                          $cur++;
  91.
                      }
  92.
                  }
  93.
              }
  94.
              return $clusteredCloud;
  95.
          }
  96.
         
  97.
          /**
  98.
           * Определяет расстояния от центров масс до тегов
  99.
           *
100.
           * @return массив с расстояниями. Его размер [ N x M ], где
101.
           *      N – количество элементов в массиве $this->$centroids
102.
           *      M – количество элементов в массиве $this->cloud
103.
           */
104.
          function _getDistances() {
105.
              $distancies = array();
106.
              foreach ($this->centroids as $i => $centroid) {
107.
                  foreach ($this->cloud as $j => $tag) {
108.
                      $distancies[$i][$j] = abs($centroid – $tag['posts_count']);
109.
                  }
110.
              }
111.
              return $distancies;
112.
          }
113.
         
114.
          /**
115.
           * Возвращает массив с разбивкой тегов на кластеры.
116.
           *
117.
           * @param $distances массив с расстояниями
118.
           * @return массив с разбивкой тегов на кластеры. Его размер [ N x M ], где
119.
           *      каждая строка соответсвует кластеру,
120.
           *      столбец – тегу,
121.
           *      если элемент массива [2][1] равен "1", значит первый тег входит во второй кластер
122.
           */
123.
          function _clasterizeTags($distances) {
124.
              $clasters = array();
125.
              //определяем число строк и столбцов в массиве
126.
              $rowsNum = count($distances);
127.
              $colsNum = count($distances[0]);
128.
              //просматриваем каждый столбец
129.
              //находим в какой колонке находится минимальный элемент
130.
              //и записываем в нее "1"
131.
              for ($j = 0; $j < $colsNum; $j++) {
132.
                  $min = $distances[0][$j];
133.
                  $minIndex = 0;
134.
                  for ($i = 0; $i < $rowsNum; $i++) {
135.
                      $clasters[$i][$j] = 0;
136.
                      if ($distances[$i][$j] < $min) {
137.
                          $minIndex = $i;
138.
                      }
139.
                  }
140.
                  $clasters[$minIndex][$j] = 1;
141.
              }
142.
              return $clasters;
143.
          }
144.
         
145.
          /**
146.
           * Пересчитывает центры масс на основе разбивки на группы
147.
           *
148.
           * @return новый массив $this->centroids
149.
           */
150.
          function _recalcCentroids() {
151.
              $newCentroids = array();
152.
              for ($centrIndex = 0; $centrIndex < count($this->centroids); $centrIndex++) {
153.
                  $newCentroids[$centrIndex] = 0;
154.
                  $n = 0;
155.
                  foreach ($this->clusters[$centrIndex] as $key => $val) {
156.
                      if ($val === 1) {
157.
                          $newCentroids[$centrIndex] += $this->cloud[$key]['posts_count'];
158.
                          $n++;
159.
                      }
160.
                  }
161.
                  if ($n > 0) {
162.
                      $newCentroids[$centrIndex] /= $n;
163.
                  }
164.
                  else {
165.
                      //оставляем старый центр масс, если в группу не вошел ни один тег
166.
                      $newCentroids[$centrIndex] = $this->centroids[$centrIndex];
167.
                  }
168.
              }
169.
              return $newCentroids;
170.
          }
171.
      }
172.
      ?>

Этот пример написан для использования с фреймворком CodeIgniter и представляет собой класс модели. Но вы можете легко переделать его под любой другой фреймворк. Единственная функция, которая зависит от библиотек CodeIgniter – это получение данных из БД (в методе getTagCloudData).

Чтобы не писать все заново я взял код из предыдущего примера и просто добавил методы для кластеризации облака.

Метод getTagCloudData возвращает данные для создания обычного облака (он остался из предыдущего примера).

Для создания облака, разбитого на группы, нужно использовать getClusteredCloud($clustersNum), где clustersNum – количество групп (кластеров), которые вы хотите получить.

Методы _getDistances(), _clasterizeTags(...), _recalcCentroids(), используются внутри метода getClusteredCloud и вызывать их не нужно. Кстати, если метод начинается с символа «_», то CodeIgniter считает его приватным (private).

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

Использовать класс не сложно. Чтобы получить данные обычного облака в контроллере пишем что-то вроде:

   1.
      $this->load->model('tagcloudmodel');
   2.
      $pageData['tagcloud'] = $this->tagcloudmodel->getTagCloudData();

А для получения облака, разбитого на кластеры:

   1.
      $this->load->model('tagcloudmodel');
   2.
      $pageData['clusteredcloud'] = $this->tagcloudmodel->getClusteredCloud(2);

Результат разбиения выглядит так:
clustered tag cloud

Теперь о недостатках.

1) Ресурсоемкость алгоритма. Оптимальный вариант решения – кэшировать облако или всю страницу.

2) Могут возникать пустые кластеры (группы в которые не вошел ни один тег). Для того, чтобы немного исправить ситуацию при формировании облака я просто пропускал такие кластеры (строки 85-93, первый листинг). Но в любом случае, желательно вручную корректировать количество групп.

Скачать архив с примером.

Как обычно, выкладываю архив с примером. Подробные инструкции по установке и настройке в файле install.txt. Дамп базы данных – в файле dump.sql.

Если возникли вопросы – задавайте. Комментарии открыты .

До встречи!