Алгоритм кластеризации HCS - Википедия - HCS clustering algorithm

Алгоритм кластеризации HCS
Учебный классКластерный анализ (на графе подобия)
Структура данныхГрафик
Худший случай спектакльО(2N x f (n, м))
Худший случай космическая сложность{{{Космос}}}

В Алгоритм кластеризации HCS (Highly Connected Subgraphs)[1] (также известный как Алгоритм HCS, и другие имена, такие как Высокосвязанные кластеры / компоненты / ядра) - алгоритм, основанный на связности графа для кластерный анализ. Он работает, представляя данные сходства в граф сходства, а затем найти все сильно связанные подграфы. Он не делает никаких предварительных предположений о количестве кластеров. Этот алгоритм был опубликован Erez Hartuv и Рон Шамир в 2000 г.

Алгоритм HCS дает решение для кластеризации, которое по своей сути имеет смысл в прикладной области, поскольку каждый кластер решений должен иметь диаметр 2, а объединение двух кластеров решений будет иметь диаметр 3.

Моделирование подобия и предварительная обработка

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

Алгоритм

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

Смотрите также: Связь (graph_theory)

Алгоритм кластеризации HCS находит все подграфы с n вершинами, так что минимальный разрез этих подграфов содержит более n / 2 ребер, и идентифицирует их как кластеры. Такой подграф называется Сильносвязанный подграф (HCS). Отдельные вершины не считаются кластерами и группируются в одноэлементное множество S.

Смотрите также: Минимальный разрез

Учитывая граф подобия G (V, E), алгоритм кластеризации HCS проверит, является ли он уже сильно связанным, если да, возвращает G, в противном случае использует минимальный разрез G для разделения G на два подграфа H и H 'и рекурсивно запускает Алгоритм кластеризации HCS на H и H '.

Пример

На следующей анимации показано, как алгоритм кластеризации HCS разбивает граф сходства на три кластера.

HCS Algorithm.gif

Псевдокод

функция HCS (G (V, E)) является    если грамм тесно связан тогда        возвращаться (грамм)    еще        (H1, H2, C) ← МИНИМУМ ВЫРЕЗАТЬ (грамм) HCS (H1) HCS (H2)    конец, есликонечная функция

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

Сложность

Время работы алгоритма кластеризации HCS ограничено N × f (n, m). f (n, m) - временная сложность вычисления минимального разреза в графе с n вершинами и m ребрами, и N количество найденных кластеров. Во многих приложениях N << n.

Для быстрых алгоритмов поиска минимального разреза на невзвешенном графе:

Смотрите также: Алгоритм Каргера

Доказательства собственности

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

Теорема 1. Диаметр каждого сильно связного графа не более двух.

Доказательство: Пусть n = | G |. Если G имеет вершину x со степенью <= n / 2, то G имеет минимальный разрез (который изолирует x) с ребрами <= n / 2, поэтому G не является сильно связным. Таким образом, если G сильно связна, каждая вершина имеет степень> = n / 2. В теории графов есть известная теорема, которая гласит, что если каждая вершина имеет степень> = n / 2, то диаметр G (самый длинный путь между любыми двумя узлами) <= 2.

Смотрите также: Расстояние (теория графов)

Теорема 2. (а) Количество ребер в сильно связном графе квадратично. (b) Количество ребер, удаляемых каждой итерацией алгоритма HCS, не более чем линейно.

Доказательство: (a) Из теоремы 1 мы знаем, что каждая вершина имеет степень> = n / 2. Следовательно, количество ребер в высокосвязном графе должно быть не менее (n × n / 2) / 2, где мы суммируем степени каждой вершины и делим на 2.

(b) По определению, каждая итерация удаляет минимальный разрез с <= n / 2 ребрами.

Теоремы 1 и 2a четко указывают на однородность конечного кластера. Работа лучше подходит к случаю, когда все вершины кластера соединены, что слишком жестко, а также NP-жесткий.

Теорема 2b указывает на разделение, поскольку любые два конечных кластера C1 и C2 не были бы разделены, если бы между ними не было не более O (C1 + C2) ребер (в отличие от квадратичных ребер внутри кластеров).

Вариации

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

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

Примеры использования ЖКХ

  • Анализ экспрессии генов[2] Гибридизация синтетических олигонуклеотидов с матричными кДНК дает отпечаток пальца для каждого клона кДНК. Алгоритм запуска HCS по этим отпечаткам пальцев позволяет идентифицировать клоны, соответствующие одному и тому же гену.
  • Обнаружение сетевой структуры PPI[3] Использование кластеризации HCS для обнаружения плотных подсетей в PPI, которые могут иметь биологическое значение и представлять биологические процессы.
  • «Обзор алгоритмов кластеризации». Нейронные сети, транзакции IEEE [4]
  • Алгоритм кластеризации CLICK[5] представляет собой адаптацию алгоритма HCS на взвешенных графах подобия, где вес присваивается с учетом вероятности.
  • https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Разделение биологических сетей на кластеры с высокой степенью связи с максимальным пограничным покрытием][6]

Рекомендации

  1. ^ Hartuv, E .; Шамир, Р. (2000), «Алгоритм кластеризации, основанный на связности графов», Письма об обработке информации, 76 (4–6): 175–181, Дои:10.1016 / S0020-0190 (00) 00142-3
  2. ^ E Hartuv, A. O Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir. «Алгоритм кластеризации отпечатков пальцев кДНК». Геномика 66, вып. 3 (2000): 249-256.
  3. ^ Юрисица, Игорь и Деннис Вигле. Открытие знаний в протеомике. Vol. 8. CRC press, 2006.
  4. ^ Сюй, Руи и Дональд Вунш. «Обзор алгоритмов кластеризации». Нейронные сети, Транзакции IEEE на 16, вып. 3 (2005): 645-678.
  5. ^ Шаран, Р .; Шамир, Р. (2000), "ЩЕЛЧОК: алгоритм кластеризации с приложениями к анализу экспрессии генов", Труды ISMB '00, 8: 307–316 ° C
  6. ^ Хаффнер, Ф .; Komusiewicz, C .; Liebtrau, A; Нидермайер, Р. (2014), «Разделение биологических сетей на высокосвязанные кластеры с максимальным пограничным покрытием», IEEE / ACM Transactions по вычислительной биологии и биоинформатике, 11 (3): 455–467, CiteSeerX  10.1.1.377.1900, Дои:10.1109 / TCBB.2013.177, PMID  26356014