Кластеризация

Типология задач кластеризации

Типы входных данных

  • Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми.
  • Матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов метрического пространства.
  • между объектами. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется Q-типом анализа, а в случае сравнения признаков, на основе объектов — R-типом анализа. Существуют попытки использования гибридных типов анализа (например, RQ-анализ), но данная методология ещё должным образом не разработана.

Цели кластеризации

  • Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).
  • Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
  • Обнаружение новизны (англ. novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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

Методы кластеризации

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

  1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).
    • K-средних
    • К-медиан
    • EM-алгоритм
    • Алгоритмы семейства FOREL
    • Дискриминантный анализ
  2. Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны.
    • Метод нечеткой кластеризации C-средних (C-means)
    • Нейронная сеть Кохонена
    • Генетический алгоритм
  3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.
  4. Теоретико-графовый подход.
  5. Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.
  6. Другие методы. Не вошедшие в предыдущие группы.
    • Статистические алгоритмы кластеризации
    • Ансамбль кластеризаторов
    • Алгоритмы семейства KRAB
    • Алгоритм, основанный на методе просеивания
    • DBSCAN и др.

Подходы 4 и 5 иногда объединяют под названием структурного или геометрического подхода, обладающего большей формализованностью понятия близости. Несмотря на значительные различия между перечисленными методами все они опираются на исходную «гипотезу компактности»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

Задачи и условия

Кластерный анализ выполняет следующие основные задачи:

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

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

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

Можно встретить описание двух фундаментальных требований, предъявляемых к данным — однородность и полнота. Однородность требует, чтобы все кластеризуемые сущности были одной природы, описывались сходным набором характеристик. Если кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» — изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство — z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.

Алгоритм CLOPE

Пусть имеется база транзакций D, состоящая из множества транзакций \{ t_1,t_2,…,t_n \}. Каждая транзакция есть набор объектов \{ i_1,…,i_m \}. Множество кластеров \{ C_1,…,C_k \} есть разбиение множества \{ t_1,…,t_n \}, такое, что C_1…C_k = \{ t_1,…,t_n \} и C_i\neq \varnothing \wedge C_i \bigcap C_j = \varnothing, для 1<=i, j<=k. Каждый элемент C_i называется кластером, n, m, k — количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер C имеет следующие характеристики:

  • D(C) — множество уникальных объектов;
  • Occ(i,C) — количество вхождений (частота) объекта i в кластер C;
  • S(C)=\sum_{i\in\ D(C)}\ Occ\ (i, C)=\sum_{t_i\in C}\mid t_i \mid;
  • W (C) = | D (C) |;
  • H(C)=S(C)/W(C).

Гистограммой кластера C называется графическое изображение его расчетных характеристик: по оси OX откладываются объекты кластера в порядке убывания величины Occ(i,C), а сама величина Occ(i,C) — по оси OY (рис. 2).

Рисунок 2. Иллюстрация гистограммы кластера

На рис. 2 S(C)=8, соответствует площади прямоугольника, ограниченного осями координат и пунктирной линией. Очевидно, что чем больше значение H, тем более «похожи» две транзакции. Поэтому алгоритм должен выбирать такие разбиения, которые максимизируют H.

Однако учитывать одно только значение высоты H недостаточно. Возьмем базу, состоящую из 2-х транзакций: \{ abc,def \}. Они не содержат общих объектов, но разбиение \{ \{abc,def \} \} и разбиение \{ \{ abc \}, \{ def \} \} характеризуются одинаковой высотой H=1. Получается, оба варианта разбиения равноценны. Но если для оценки вместо H(C) использовать градиент G(C)=H(C)/W(C)=S(C)/W(C)^2, то разбиение \{ \{ abc \}, \{ def \} \} будет лучше (градиент каждого кластера равен 1/3 против 1/6 у разбиения \{ \{ abc,def \} \}).

Обобщив вышесказанное, запишем формулу для вычисления глобального критерия – функции стоимости Profit(C):

Profit (C) = \frac {\sum_{i=1}^k G(C_i)\times\mid C_i\mid}{\sum_{i=1}^k \mid C_i\mid}=\frac {\sum_{i=1}^k \frac{S(C_i)}{W(C_i)^r}\times\mid C_i\mid}{\sum_{i=1}^k \mid C_i\mid}

где:

  • |Ci| — количество транзакций в i-том кластере
  • k — количество кластеров
  • r — положительное вещественное число большее 1.

С помощью параметра r, названного авторами CLOPE коэффициентом отталкивания (repulsion), регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше r, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом: для заданных D и r найти разбиение C: Profit(C,r) -> max.

Кластеризация на основе плотности

Кластеризация

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

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

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

Основной недостаток DBSCAN и OPTICS заключается в том, что они ожидают некоторого падения плотности для обнаружения границ кластера. Например, в наборах данных с перекрывающимися распределениями Гаусса — распространенный случай использования искусственных объектов — границы кластеров, создаваемые этими алгоритмами, часто выглядят произвольно. Происходит это, поскольку плотность групп непрерывно уменьшается. А в наборе данных, состоящем из смесей гауссианов, эти алгоритмы почти всегда превосходят такие методы, как EM-кластеризация, которые способны точно моделировать системы такого типа.

Среднее смещение — это кластерный подход, при котором каждый объект перемещается в самую плотную область в окрестности на основе оценки всего ядра. В конце концов, объекты сходятся к локальным максимумам непроницаемости. Подобно кластеризации методом к-средних, эти «аттракторы плотности» могут служить представителями для набора данных. Но среднее смещение может обнаруживать кластеры произвольной формы, аналогичные DBSCAN. Из-за дорогой итеративной процедуры и оценки плотности среднее перемещение обычно медленнее, чем DBSCAN или k-Means. Кроме того, применимость алгоритма типичного сдвига к многомерным данным затруднена из-за неравномерного поведения оценки плотности ядра, что приводит к чрезмерной фрагментации хвостов кластеров.

Оценка

Кластеризация

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

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

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

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

Кластеризация в Data Mining

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

Очень часто данные, с которыми сталкивается технология Data Mining, имеют следующие важные особенности:

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

Все атрибуты или признаки объектов делятся на числовые (numerical) и категорийные (categorical). Числовые атрибуты – это такие, которые могут быть упорядочены в пространстве, соответственно категорийные – которое не могут быть упорядочены. Например, атрибут «возраст» – числовой, а «цвет» – категорийный. Приписывание атрибутам значений происходит во время измерений выбранным типом шкалы, а это, вообще говоря, представляет собой отдельную задачу.

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

D(x, y)=\sqrt{\sum_{i}{(x-y)^2}}

Для категорийных атрибутов распространена мера сходства Чекановского-Серенсена и Жаккара ( \mid t_1 \cap t_2\mid/\mid t_1\cup t_2 \mid).

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

  1. Минимально возможное количество проходов по базе данных;
  2. Работа в ограниченном объеме оперативной памяти компьютера;
  3. Работу алгоритма можно прервать с сохранением промежуточных результатов, чтобы продолжить вычисления позже;
  4. Алгоритм должен работать, когда объекты из базы данных могут извлекаться только в режиме однонаправленного курсора (т.е. в режиме навигации по записям).

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

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

Трудно соблюсти баланс между высоким качеством кластеризации и масштабируемостью. Поэтому в идеале в арсенале Data Mining должны присутствовать как эффективные алгоритмы кластеризации микромассивов (microarrays), так и масштабируемые для обработки сверхбольших баз данных (large databases).

Для чего кластеризовать семантическое ядро

Кластеризация запросов нужна для решения следующих задач:

  • Планирование структуры будущего сайта. В идеале, сколько кластеров получилось – столько и должно быть страниц. В реальности же ресурсы ограничены, поэтому стоит выбирать наиболее приоритетные. Тип будущей страницы в свою очередь зависит от типа запросов, входящих в кластер. В одну группу попали информационные запросы – планируем написание статьи, если коммерческие запросы – делаем посадочную страницу и т. д.
  • Оптимизация имеющихся страниц на сайте. Полученные кластеры распределяются по страницам, которые затем оптимизируются в соответствии со сгруппированными поисковыми запросами.
  • Подбор целевых страниц для объявлений в контекстной рекламе. Если ключевые фразы, по которым настраивается реклама, находятся в одном кластере – можно спокойно направлять трафик по всем им на одну целевую страницу.
  • Чистка семантического ядра, поиск минус-слов. Нерелевантные, нетематические ключи тоже объединяются в кластеры, поэтому их легко находить и удалять из семантического ядра или же заносить в список минус-слов.

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

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

Инструкция

Кластеризация

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

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

Термин

Кластеризация

Понятие «кластер» не может быть точно определено. Это является одной из причин, по которой имеется так много методов кластеризации. Существует общий знаменатель: группа объектов данных. Однако всевозможные исследователи используют разные модели. И каждое из этих использований методов кластеризации включает в себя различные данные. Понятия найденного всевозможными алгоритмами существенно различается по его свойствам.

Использование метода кластеризации является ключом к пониманию отличий между инструкциями. Типичные кластерные модели включают в себя:

  • Центроид s. Это, например, когда кластеризация методом к-средних представляет каждый кластер с одним средним вектором.
  • Модель связности s. Это уже, например, иерархическая кластеризация, которая строит модели на основе дистанционной связности.
  • Модель распределения s. В данном случае кластеры моделируются с использованием метода кластеризации для формирования метапредметных статистических распределений. Таких как многомерное нормальное разделение, которое применимо для алгоритма максимизации ожидания.
  • Модель плотности s. Это, например, DBSCAN (алгоритм пространственной кластеризации с присутствием шума) и OPTICS (точки заказа для определения структуры), которые определяют группы как связанные плотные области в пространстве данных.
  • Модель подпространства с. В biclustering (также известный как со-кластеризация или два режима) группы моделируются с обоими элементами и с соответствующими атрибутами.
  • Модель s. Некоторые алгоритмы не дают уточненную связь для их метода кластеризации для формирования метапредметных результатов и просто обеспечивают группировку информации.
  • Модель на основе графа s. Клик, то есть подмножество узлов, такой, что каждые два соединения в реберной части можно рассматривать как прототип формы кластера. Ослабление полного требования известны как квазиклики. Точно такое же название представлено в алгоритме кластеризации HCS.
  • Нейронные модели s. Наиболее известной сетью без надзора является самоорганизующаяся карта. И именно эти модели обычно можно охарактеризовать как аналогичные одному или нескольким из вышеуказанных методов кластеризации для формирования метапредметных результатов. Включает он в себя подпространственные системы тогда, когда нейронные сети реализуют необходимую форму анализа главных или независимых компонентов.

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

  • Жесткий центроидный метод кластеризации. Здесь каждый объект принадлежит группе или находится вне ее.
  • Мягкая или нечеткая система. В данном пункте уже каждый объект в определенной степени принадлежит всякому кластеру. Называется он также методом нечеткой кластеризации c-средних.

И также возможны более тонкие различия. Например:

  • Строгая секционирующая кластеризация. Здесь каждый объект принадлежит ровно одной группе.
  • Строгая секционирующая кластеризация с выбросами. В данном случае, объекты также могут не принадлежать ни к одному кластеру и считаться ненужными.
  • Перекрывающаяся кластеризация (также альтернативная, с несколькими представлениями). Здесь объекты могут принадлежать более чем к одному ответвлению. Как правило, с участием твердых кластеров.
  • Иерархические методы кластеризации. Объекты, принадлежащие дочерней группе, также принадлежат родительской подсистеме.
  • Формирования подпространства. Хотя они и похожи на кластеры с перекрытием, внутри уникально определенной системы взаимные группы не должны загораживаться.

Формальная постановка задачи кластеризации

Пусть X{\displaystyle X} — множество объектов, Y{\displaystyle Y} — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами ρ(x,x′){\displaystyle \rho (x,x’)}. Имеется конечная обучающая выборка объектов Xm={x1,…,xm}⊂X{\displaystyle X^{m}=\{x_{1},\dots ,x_{m}\}\subset X}. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике ρ{\displaystyle \rho }, а объекты разных кластеров существенно отличались. При этом каждому объекту xi∈Xm{\displaystyle x_{i}\in X^{m}}
приписывается номер кластера yi{\displaystyle y_{i}}.

Алгоритм кластеризации — это функция aX→Y{\displaystyle a\colon X\to Y}, которая любому объекту x∈X{\displaystyle x\in X} ставит в соответствие номер кластера y∈Y{\displaystyle y\in Y}. Множество Y{\displaystyle Y} в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки исходных объектов yi{\displaystyle y_{i}} изначально не заданы, и даже может быть неизвестно само множество Y{\displaystyle Y}.

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин (как считает ряд авторов):

  • не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. Следовательно, для определения качества кластеризации требуется эксперт предметной области, который бы мог оценить осмысленность выделения кластеров.
  • число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. Это справедливо только для методов дискриминации, так как в методах кластеризации выделение кластеров идёт за счёт формализованного подхода на основе мер близости.
  • результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом. Но стоит отметить, что есть ряд рекомендаций к выбору мер близости для различных задач.

Что делать после кластеризации

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

Каждой группе соответствует отдельная страница сайта. Для каждой страницы нужно подготовить Title, Description, H1 и URL, в которых будут использованы поисковые запросы из кластера, а также атрибут alt для тега img и предусмотреть использование запросов в других зонах.

Некластеризованные запросы

Запросы, которые не были включены ни в один кластер, удалять не нужно. Вы можете добавить их на отдельные страницы сайта (например, в разделах «Статьи» или «Блог») или включить в какой-то из имеющихся кластеров по смыслу.

Финальная проверка

Финальная проверка делается на этапе составления контент-плана – определяется соответствие запросов в кластере интентам пользователей и возможная полнота раскрытия темы.

Диаграмма Чекановского

Метод «диагонализации» матрицы различия и графическое изображение кластеров вдоль главной диагонали матрицы различия (диаграмма Чекановского) впервые предложен Яном Чекановским в 1909 году. Приведём описание методики:

Приведём гипотетический пример получения вышеуказанной диаграммы. Основой метода является построение матрицы транзитивного замыкания.

Пример расчёта диаграммы Чекановского

Для построения матрицы транзитивного замыкания возьмём простую матрицу сходства и её саму на себя:


K(2)(i,j)=max(min(K(i,1),K(1,j)),…,min(K(i,q),K(q,j))){\displaystyle K^{(2)}(i,j)=max(min(K(i,1),K(1,j)),…,min(K(i,q),K(q,j)))},

где K(i,j){\displaystyle K(i,j)} — элемент, стоящий на пересечении i{\displaystyle i}-ой строки и j{\displaystyle j}-го столбца в новой (второй) матрице, полученной после первой итерации; q{\displaystyle q} — общее количество строк (столбцов) матрицы сходства. Данную процедуру необходимо продолжать, пока матрица не станет идемпотентной (то есть самоподобной): K(n)(i,j)=K(n−1)(i,j){\displaystyle K^{(n)}(i,j)=K^{(n-1)}(i,j)}, где n — число итераций.

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