Алгоритм кластеризации HCS

Алгоритм кластеризации HCS
Сорт	Кластерный анализ (на графе сходства)
Структура данных	График
Худшая производительность	О (2N xf(n,m))

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

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

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

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

Алгоритм

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

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

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

Пример

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

Псевдокод

function HCS(G(V, E)) is
    if G is highly connected then
        return (G)
    else
        (H1, H2, C) ← MINIMUMCUT(G)
        HCS(H1)
        HCS(H2)
    end if
end function

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

Сложность

Время работы алгоритма кластеризации 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 (a) Число ребер в сильно связном графе квадратично. (б) Число ребер, удаляемых на каждой итерации алгоритма HCS, не более чем линейно.

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

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

Теоремы 1 и 2а убедительно свидетельствуют об однородности конечного кластера. Правило «лучше» подходит к случаю, когда все вершины кластера связаны, что является одновременно слишком строгим и NP-трудным .

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

Вариации

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

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

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

Анализ экспрессии генов ^[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]
Р Реализация
Реализация Python

Ссылки

^ Хартув, Э.; Шамир, Р. (2000), «Алгоритм кластеризации, основанный на связности графов», Information Processing Letters , 76 (4–6): 175–181, doi : 10.1016/S0020-0190(00)00142-3
^ Э. Хартув, А.О. Шмитт, Дж. Ланге, С. Мейер-Эверт, Х. Лерах, Р. Шамир. «Алгоритм кластеризации отпечатков кДНК». Геномика 66, вып. 3 (2000): 249-256.
^ Юришица, Игорь и Деннис Вигл. Открытие знаний в протеомике. Том. 8. ЦРК пресс, 2006.
^ Сюй, Руи и Дональд Вунш. «Обзор алгоритмов кластеризации». Нейронные сети, Транзакции IEEE на 16, вып. 3 (2005): 645-678.
^ Шаран, Р.; Шамир, Р. (2000), «CLICK: алгоритм кластеризации с применением к анализу экспрессии генов», Proceedings ISMB '00 , 8 : 307–316C, PMID 10977092
^ Хаффнер, Ф.; Комузевич, К.; Либтрау, А; Нидермейер, Р. (2014), «Разделение биологических сетей на высокосвязные кластеры с максимальным периферийным покрытием», Транзакции IEEE/ACM по вычислительной биологии и биоинформатике , 11 (3): 455–467, CiteSeerX 10.1.1.377.1900 , doi : 10.1109 /TCBB.2013.177 , PMID 26356014 , S2CID 991687

[1] Хартув, Э.; Шамир, Р. (2000), «Алгоритм кластеризации, основанный на связности графов», Information Processing Letters , 76 (4–6): 175–181, doi : 10.1016/S0020-0190(00)00142-3

[2] Э. Хартув, А.О. Шмитт, Дж. Ланге, С. Мейер-Эверт, Х. Лерах, Р. Шамир. «Алгоритм кластеризации отпечатков кДНК». Геномика 66, вып. 3 (2000): 249-256.

[3] Юришица, Игорь и Деннис Вигл. Открытие знаний в протеомике. Том. 8. ЦРК пресс, 2006.

[4] Сюй, Руи и Дональд Вунш. «Обзор алгоритмов кластеризации». Нейронные сети, Транзакции IEEE на 16, вып. 3 (2005): 645-678.

[5] Шаран, Р.; Шамир, Р. (2000), «CLICK: алгоритм кластеризации с применением к анализу экспрессии генов», Proceedings ISMB '00 , 8 : 307–316C, PMID 10977092

[6] Хаффнер, Ф.; Комузевич, К.; Либтрау, А; Нидермейер, Р. (2014), «Разделение биологических сетей на высокосвязные кластеры с максимальным периферийным покрытием», Транзакции IEEE/ACM по вычислительной биологии и биоинформатике , 11 (3): 455–467, CiteSeerX 10.1.1.377.1900 , doi : 10.1109 /TCBB.2013.177 , PMID 26356014 , S2CID 991687

[1]

[2]

[3]

[4]

[5]

[6]