Облако тегов для сайта (кластеризация)

Владимир | | CodeIgniter, PHP, Web разработка.

tag cloud clusterized

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

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

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

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

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) Алгоритм завершается, когда распределение тегов по кластерам перестает изменяться.

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

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

<?php
class TagCloudModel extends Model {
	
	private $centroids;
	private $cloud;
	private $clusters;
	
	function TagCloudModel() {
		parent::Model();
	}
	
	/**
	 * Возвращает данные, необходимые для построения облака тегов
	 * (без разбиения на кластеры)
	 *
	 * @return массив с облаком
	 */
	function getTagCloudData() {
		$qGetCloud = "SELECT tags.tag, COUNT(posts_tags.tagid) AS posts_count".
					" FROM posts_tags LEFT JOIN tags ON posts_tags.tagid=tags.id".
					" GROUP BY tags.id";
		$res = $this->db->query($qGetCloud);
		if ($res->num_rows() == 0) {
			return false;
		}
		else {
			return $res->result_array();
		}
	}
	
	/**
	 * Разбивает облако тегов на заданное количество кластеров.
	 *
	 * @param $clustersNum количество кластеров
	 * @return массив с результатами
	 * 	$res[0] - первый кластер, содержит массив со всеми рубриками, которые в него входят
	 * 	вывод записей для всех кластеров
	 * 	foreach ($res as $cluster) {
	 * 		foreach ($cluster as $tag) {
	 * 			echo $tag['tag'].'('.$tag['posts_count'].')';
	 * 		}
	 * 	}
	 */
	function getClusteredCloud($clustersNum) {
		//получаем общее облако тегов
		$this->cloud = $this->getTagCloudData();
		//разбиваем его на заданное количество кластеров
		//определяем начальные центры масс каждого кластера
		//для этого находим теги с максимальным и минимальным количеством постов
		$min = $this->cloud[0]['posts_count'];
		$max = $this->cloud[0]['posts_count'];
		for ($i = 1; $i < count($this->cloud); $i++) {
			if ($this->cloud[$i]['posts_count'] > $max) {
				$max = $this->cloud[$i]['posts_count'];
			}
			if ($this->cloud[$i]['posts_count'] < $min) {
				$min = $this->cloud[$i]['posts_count'];
			}
		}
		//формируем массив с начальными центрами масс
		//идея такая: первый центр масс равен минимальному элементу,
		//последний - максимальному, все остальные - равномерно распределены
		//между ними
		$step = ($max - $min) / ($clustersNum - 1);
		$this->centroids = array();
		for ($i = 0; $i < $clustersNum; $i++) {
			$this->centroids[$i] = $min + $i*$step;
		}
		//первоначальная разбивка на группы
		$prevClusters = array();
		while (TRUE) {
			//рассчитываем расстояние от каждого тега до центра масс
			$distances = $this->_getDistances();
			$this->clusters = $this->_clasterizeTags($distances);
			if ($prevClusters === $this->clusters) {
				break;
			}
			else {
				$prevClusters = $this->clusters;
				$this->centroids = $this->_recalcCentroids();
			}
		}
		//формируем облако тегов, разбитое на кластеры
		//все кластеры, которые не содержат тегов, будут пропущены
		foreach ($this->clusters as $cIndex => $cluster) {
			$cur = 0;
			foreach ($cluster as $tIndex => $tag) {
				if ($tag === 1) {
					$clusteredCloud[$cIndex][$cur] = $this->cloud[$tIndex];
					$cur++;
				}
			}
		}
		return $clusteredCloud;
	}
	
	/**
	 * Определяет расстояния от центров масс до тегов
	 *
	 * @return массив с расстояниями. Его размер [ N x M ], где
	 * 		N - количество элементов в массиве $this->$centroids
	 * 		M - количество элементов в массиве $this->cloud
	 */
	function _getDistances() {
		$distancies = array();
		foreach ($this->centroids as $i => $centroid) {
			foreach ($this->cloud as $j => $tag) {
				$distancies[$i][$j] = abs($centroid - $tag['posts_count']);
			}
		}
		return $distancies;
	}
	
	/**
	 * Возвращает массив с разбивкой тегов на кластеры.
	 *
	 * @param $distances массив с расстояниями
	 * @return массив с разбивкой тегов на кластеры. Его размер [ N x M ], где
	 * 		каждая строка соответсвует кластеру,
	 * 		столбец - тегу,
	 * 		если элемент массива [2][1] равен "1", значит первый тег входит во второй кластер
	 */
	function _clasterizeTags($distances) {
		$clasters = array();
		//определяем число строк и столбцов в массиве
		$rowsNum = count($distances);
		$colsNum = count($distances[0]);
		//просматриваем каждый столбец
		//находим в какой колонке находится минимальный элемент
		//и записываем в нее "1"
		for ($j = 0; $j < $colsNum; $j++) {
			$min = $distances[0][$j];
			$minIndex = 0;
			for ($i = 0; $i < $rowsNum; $i++) {
				$clasters[$i][$j] = 0;
				if ($distances[$i][$j] < $min) {
					$minIndex = $i;
				}
			}
			$clasters[$minIndex][$j] = 1;
		}
		return $clasters;
	}
	
	/**
	 * Пересчитывает центры масс на основе разбивки на группы
	 *
	 * @return новый массив $this->centroids
	 */
	function _recalcCentroids() {
		$newCentroids = array();
		for ($centrIndex = 0; $centrIndex < count($this->centroids); $centrIndex++) {
			$newCentroids[$centrIndex] = 0;
			$n = 0;
			foreach ($this->clusters[$centrIndex] as $key => $val) {
				if ($val === 1) {
					$newCentroids[$centrIndex] += $this->cloud[$key]['posts_count'];
					$n++;
				}
			}
			if ($n > 0) {
				$newCentroids[$centrIndex] /= $n;
			}
			else {
				//оставляем старый центр масс, если в группу не вошел ни один тег
				$newCentroids[$centrIndex] = $this->centroids[$centrIndex];
			}
		}
		return $newCentroids;
	}
}
?>

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

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

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

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

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

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

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

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

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

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

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

clustered tag cloud

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

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

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

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

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

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

До встречи!

  • Супер.
    Пожалуй лучшая статья в этом месяце.
    Ну, и конечно почитал http://i-novice.net/oblako-tegov/
    Буду у себя переделывать.

    • Спасибо. Но месяц еще не закончился 🙂

      • Звучит многообещающе 🙂

  • Супер.
    Пожалуй лучшая статья в этом месяце.
    Ну, и конечно почитал http://i-novice.net/oblako-tegov/
    Буду у себя переделывать.

    • Спасибо. Но месяц еще не закончился 🙂

      • Звучит многообещающе 🙂

  • Боюсь, ты не совсем правильно понял идею использования кластерного анализа для отображения облака тегов. Попробую пояснить.

    Возьмем рассмотренный пример с пятью тегами. Предположим, что мы выделили 5 размеров шрифта для отображения каждого тега. Но в случае пропорционалного деления популярность тега JavaScript приведет к тому, что теги php, html и java будут отображены одним шрифтом, хотя для каждого тега есть свободный шрифт. Кластерные методы как раз позволяют исключить такое влияние.

    P.S. Описанный тобой вариант использования, тоже, имеет право на существование, просто надо понимать, что изначально идея была не в этом.

    • изначально идея была не в этом

      Согласен, не в этом. Но, по-сути, я только немного развил идею.
      В оригинальной статье теги разбиты на 5 групп для каждой из которых использован свой размер шрифта и свой цвет (последний скриншот). Т.е. глядя на облако невозможно определить, что тег sit используется в 1.7 раз чаще, чем quod.

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

      P.S. Есть еще одна проблема: относительная популярность групп.

  • Боюсь, ты не совсем правильно понял идею использования кластерного анализа для отображения облака тегов. Попробую пояснить.

    Возьмем рассмотренный пример с пятью тегами. Предположим, что мы выделили 5 размеров шрифта для отображения каждого тега. Но в случае пропорционалного деления популярность тега JavaScript приведет к тому, что теги php, html и java будут отображены одним шрифтом, хотя для каждого тега есть свободный шрифт. Кластерные методы как раз позволяют исключить такое влияние.

    P.S. Описанный тобой вариант использования, тоже, имеет право на существование, просто надо понимать, что изначально идея была не в этом.

    • изначально идея была не в этом

      Согласен, не в этом. Но, по-сути, я только немного развил идею.
      В оригинальной статье теги разбиты на 5 групп для каждой из которых использован свой размер шрифта и свой цвет (последний скриншот). Т.е. глядя на облако невозможно определить, что тег sit используется в 1.7 раз чаще, чем quod.

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

      P.S. Есть еще одна проблема: относительная популярность групп.

  • мне больше понравилось облаго тегов на вордпрессе сделанное во flash. там просто сказка..

  • мне больше понравилось облаго тегов на вордпрессе сделанное во flash. там просто сказка..

  • Просто красота получается, вот бы еще как то его прикрутить к всоему сайту.
    http://myclimax.ru/

  • Просто красота получается, вот бы еще как то его прикрутить к всоему сайту.
    http://myclimax.ru/

  • да.. соглашусь что теги нада все равно делать красивыми.. а так пфф… (

  • да.. соглашусь что теги нада все равно делать красивыми.. а так пфф… (

  • Pingback: Пример нишевого аффилиэйт сайта. | Affiliate Marketing: Инструкция по применению.()

  • Максим

    Большое спасибо за разработанный метод!

    Для пущего эффекта и, чтобы все было окончательно правильно саму модель tagcloudmodel.php следует немного подкорректировать:

    В функции getClusteredCloud после строчки
    $this->cloud = $this->getTagCloudData();
    следует весь код обрамить в if.


    $this->cloud = $this->getTagCloudData();
    if ($this->cloud)
    {
    ...
    ...
    ...
    }
    else
    return false;

    • Точно, вы правы! Спасибо!
      В методе getTagCloudData() обработку ошибок я предусмотрел, а использовать ее в getClusteredCloud — забыл.
      Еще раз спасибо!

  • Максим

    Большое спасибо за разработанный метод!

    Для пущего эффекта и, чтобы все было окончательно правильно саму модель tagcloudmodel.php следует немного подкорректировать:

    В функции getClusteredCloud после строчки
    $this->cloud = $this->getTagCloudData();
    следует весь код обрамить в if.


    $this->cloud = $this->getTagCloudData();
    if ($this->cloud)
    {
    ...
    ...
    ...
    }
    else
    return false;

    • Точно, вы правы! Спасибо!
      В методе getTagCloudData() обработку ошибок я предусмотрел, а использовать ее в getClusteredCloud — забыл.
      Еще раз спасибо!

  • Николай

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

    <?php
    $tags = '
    <a href="http://mysite.com/about&quot; rel="nofollow">Обо мне</a>
    <a href="http://mysite.com/prtfolio&quot; rel="nofollow">Портфолио</a>
    <a href="http://mysite.com/blog&quot; rel="nofollow">Блог</a>
    <a href="http://mysite.com/download&quot; rel="nofollow">Скачать</a>
    <a href="http://mysite.com/contact&quot; rel="nofollow">Контакты</a>
    <a href="http://mysite.com/glossary&quot; rel="nofollow">Глоссарий</a>
    ';
    ?>

    var rnumber = Math.floor(Math.random()*9999999);
    var widget_so = new SWFObject(«tagcloud.swf?r=»+rnumber, «tagcloudflash», «630», «340», «9», «#ffffff»);
    widget_so.addParam(«allowScriptAccess», «always»);
    widget_so.addVariable(«tcolor», «0x333333»);
    widget_so.addVariable(«tspeed», «115»);
    widget_so.addVariable(«distr», «true»);
    widget_so.addVariable(«mode», «tags»);
    widget_so.addVariable(«tagcloud», «»);
    widget_so.write(«tags»);

    Мне необходимо в те места где «http://mysite.com/about» вставить данные из базы (это ссылки),а в те места где >Обо мне< и т.д.
    нужно вывести другую информацию из базы. Дело в том,что я не знаю как эту процедуру сформулировать и прошу помочь Вас.
    Заранее ОГРОМНОЕ СПАСИБО! Когда решится эта проблема и если Вам будет интересно,я поделюсь уже готовым материалом

    • Насколько я понял, вы хотите получить ссылки из базы и из этих данных сформировать массив $tags?

      Вам нужно.
      1) Сформировать и отправить запрос.
      2) В цикле добавить найденные данные в массив.

      Т.е. код будет выглядеть примерно так.

      $tags = array();
      $res = $this->db->query('SELECT * FROM links');
      foreach ($res->result() as $link) {
          $tags[] = '<a href="'.$link->url.'">'.$link->ancor.'</a>'
      }

      Код написан с использованием библиотеки CI для работы с БД. Названия полей я взял первые попавшиеся.

  • Николай

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

    <?php
    $tags = '
    <a href="http://mysite.com/about&quot; rel="nofollow">Обо мне</a>
    <a href="http://mysite.com/prtfolio&quot; rel="nofollow">Портфолио</a>
    <a href="http://mysite.com/blog&quot; rel="nofollow">Блог</a>
    <a href="http://mysite.com/download&quot; rel="nofollow">Скачать</a>
    <a href="http://mysite.com/contact&quot; rel="nofollow">Контакты</a>
    <a href="http://mysite.com/glossary&quot; rel="nofollow">Глоссарий</a>
    ';
    ?>

    var rnumber = Math.floor(Math.random()*9999999);
    var widget_so = new SWFObject(«tagcloud.swf?r=»+rnumber, «tagcloudflash», «630», «340», «9», «#ffffff»);
    widget_so.addParam(«allowScriptAccess», «always»);
    widget_so.addVariable(«tcolor», «0x333333»);
    widget_so.addVariable(«tspeed», «115»);
    widget_so.addVariable(«distr», «true»);
    widget_so.addVariable(«mode», «tags»);
    widget_so.addVariable(«tagcloud», «»);
    widget_so.write(«tags»);

    Мне необходимо в те места где «http://mysite.com/about» вставить данные из базы (это ссылки),а в те места где >Обо мне< и т.д.
    нужно вывести другую информацию из базы. Дело в том,что я не знаю как эту процедуру сформулировать и прошу помочь Вас.
    Заранее ОГРОМНОЕ СПАСИБО! Когда решится эта проблема и если Вам будет интересно,я поделюсь уже готовым материалом

    • Насколько я понял, вы хотите получить ссылки из базы и из этих данных сформировать массив $tags?

      Вам нужно.
      1) Сформировать и отправить запрос.
      2) В цикле добавить найденные данные в массив.

      Т.е. код будет выглядеть примерно так.
      $tags = array();
      $res = $this->db->query('SELECT * FROM links');
      foreach ($res->result() as $link) {
      $tags[] = '<a href="'.$link->url.'">'.$link->ancor.'</a>'
      }

      Код написан с использованием библиотеки CI для работы с БД. Названия полей я взял первые попавшиеся.

  • Николай

    Может я не могу правильно выразить свою мысль…Вот полный файл рнр

    Документ без названия

    <?php
    $tags = '
    <a href="localhost/php" rel="nofollow">Zildjian</a>
    <a href="localhost/php" rel="nofollow">DiMarzio</a>
    <a href="localhost/php" rel="nofollow">Tama</a>
    <a href="localhost/php" rel="nofollow">Seymour Duncan</a>
    <a href="localhost/php" rel="nofollow">VOX</a>
    <a href="localhost/php" rel="nofollow">Whilkinson</a>
    <a href="localhost/php" rel="nofollow">Schecter</a>
    <a href="localhost/php" rel="nofollow">Peavey</a>
    <a href="localhost/php" rel="nofollow">Fender</a>
    ';
    ?>

    var rnumber = Math.floor(Math.random()*9999999);
    var widget_so = new SWFObject(«tagcloud.swf?r=»+rnumber, «tagcloudflash», «630», «340», «9», «#ffffff»);
    widget_so.addParam(«allowScriptAccess», «always»);
    widget_so.addVariable(«tcolor», «0x333333»);
    widget_so.addVariable(«tspeed», «115»);
    widget_so.addVariable(«distr», «true»);
    widget_so.addVariable(«mode», «tags»);
    widget_so.addVariable(«tagcloud», «»);
    widget_so.write(«tags»);

    Мне необходимо в те места где localhost/php вставить данные из базы (это ссылки),а в те места где >Zildjian< и т.д.
    нужно вывести другую информацию из базы.Это всё будет выводиться в 3D облако.

    • Я, в принципе, так и понял. Только не обратил внимания, что в переменную $tags нужно записать строку, а не массив.
      $tags = »;
      Внутри цикла код будет таким
      $tags .= '<a href=»'.$link->url.'»>'.$link->ancor.'</a>';

  • Николай

    Может я не могу правильно выразить свою мысль…Вот полный файл рнр

    Документ без названия

    <?php
    $tags = '
    <a href="localhost/php" rel="nofollow">Zildjian</a>
    <a href="localhost/php" rel="nofollow">DiMarzio</a>
    <a href="localhost/php" rel="nofollow">Tama</a>
    <a href="localhost/php" rel="nofollow">Seymour Duncan</a>
    <a href="localhost/php" rel="nofollow">VOX</a>
    <a href="localhost/php" rel="nofollow">Whilkinson</a>
    <a href="localhost/php" rel="nofollow">Schecter</a>
    <a href="localhost/php" rel="nofollow">Peavey</a>
    <a href="localhost/php" rel="nofollow">Fender</a>
    ';
    ?>

    var rnumber = Math.floor(Math.random()*9999999);
    var widget_so = new SWFObject(«tagcloud.swf?r=»+rnumber, «tagcloudflash», «630», «340», «9», «#ffffff»);
    widget_so.addParam(«allowScriptAccess», «always»);
    widget_so.addVariable(«tcolor», «0x333333»);
    widget_so.addVariable(«tspeed», «115»);
    widget_so.addVariable(«distr», «true»);
    widget_so.addVariable(«mode», «tags»);
    widget_so.addVariable(«tagcloud», «»);
    widget_so.write(«tags»);

    Мне необходимо в те места где localhost/php вставить данные из базы (это ссылки),а в те места где >Zildjian< и т.д.
    нужно вывести другую информацию из базы.Это всё будет выводиться в 3D облако.

    • Я, в принципе, так и понял. Только не обратил внимания, что в переменную $tags нужно записать строку, а не массив.
      $tags = »;
      Внутри цикла код будет таким
      $tags .= '<a href=»'.$link->url.'»>'.$link->ancor.'</a>';