HCS 클러스터링 알고리즘

HCS clustering algorithm
HCS 클러스터링 알고리즘
클래스군집 분석(유사성 그래프)
데이터 구조그래프
최악의 경우 공연O(2N x f(n,m)

HCS(Highly Connected Subgraphs) 클러스터링 알고리즘[1](HCS 알고리즘이라고도 하며, 고도로 연결된 클러스터/구성요소/커널 등의 다른 이름)은 클러스터 분석을 위한 그래프 연결을 기반으로 하는 알고리즘이다.유사성 그래프로 유사성 데이터를 표시한 다음, 고도로 연결된 모든 하위 그래프를 찾는 방식으로 작동한다.군집 수에 대해 어떠한 사전 가정도 하지 않는다.이 알고리즘은 2000년에 에레스 하투브와 론 샤미르에 의해 출판되었다.

HCS 알고리즘은 각 솔루션 클러스터는 직경 2를 가져야 하고, 솔루션 클러스터 2개의 조합은 직경 3을 가져야 하기 때문에 애플리케이션 영역에서 본질적으로 의미가 있는 클러스터링 솔루션을 제공한다.

유사성 모델링 및 사전 처리

군집 분석의 목적은 요소들 간의 유사성에 기초하여 요소들을 분리형 부분군, 즉 군집들로 분류하여 같은 군집의 요소들이 서로 매우 유사(동질성)하는 반면, 서로 다른 군집의 요소들은 서로에 대한 유사성이 낮다(분리)는 것이다.유사도 그래프는 요소들 간의 유사성을 나타내는 모델 중 하나이며, 군집 생성을 용이하게 한다.유사성 데이터에서 유사성 그래프를 구성하려면 요소를 정점으로 표시하고, 이들 요소 간의 유사성 값이 일부 임계값을 초과할 때 정점 사이의 가장자리를 유도하십시오.

알고리즘.

유사성 그래프에서, 주어진 정점 수에 대해 더 많은 에지가 존재할수록, 그러한 정점 집합은 서로 더 유사하다.즉, 가장자리를 제거하여 유사성 그래프를 분리하려고 하면, 그래프가 분리되기 전에 제거해야 할 가장자리가 많을수록 이 그래프의 꼭지점들은 더 비슷해진다.최소 절단은 그래프가 분리되지 않는 최소 에지 집합이다.

참고 항목:연결(그래프_이론)

HCS 클러스터링 알고리즘은 이러한 서브그래프의 최소 컷에 n/2 이상의 가장자리가 포함되도록 n 정점이 있는 모든 서브그래프를 찾아 클러스터로 식별한다.이러한 서브그래프를 HCS(High Connected Subgraph)라고 부른다.단일 꼭지점은 군집으로 간주되지 않으며 단골격 집합 S로 그룹화된다.

참고 항목:최소 절단

유사도 그래프 G(V,E)를 보면 HCS 클러스터링 알고리즘이 이미 고도로 연결되어 있는지, 그렇다면 G를 반환하고, 그렇지 않으면 G의 최소 절단을 사용하여 G를 두 개의 서브그래프 H와 H'로 분할하고, HCS 클러스터링 알고리즘을 H와 H'에서 재귀적으로 실행한다.

예

다음 애니메이션은 HCS 클러스터링 알고리즘이 유사성 그래프를 세 개의 클러스터로 분할하는 방법을 보여준다.

HCS Algorithm.gif

가성음

함수 HCS(G(V, E))는 G가 고도로 연결된 경우 리턴(G) 기타(H1, H2, C) ← 최소컷(G) HCS(H1) HCS(H2) 엔드 기능인 경우 종료(End function)

그래프에서 최소 절단을 찾는 단계G이 문제에 대해 다른 알고리즘을 사용하여 구현될 수 있는 서브루틴이다.랜덤화를 사용하여 최소 절단을 찾는 알고리즘의 예는 아래를 참조하십시오.

복잡성

HCS 클러스터링 알고리즘의 실행 시간은 다음과 같이 제한된다.N× f(n, m). f(n, m)는 정점과 m 가장자리가 있는 그래프에서 최소 절단을 계산하는 시간의 복잡성이다.N발견된 군집 수입니다.많은 애플리케이션에서 N.

가중치가 없는 그래프에서 최소 절단을 찾기 위한 빠른 알고리즘의 경우:

참고 항목: Karger 알고리즘

재산증명서

HCS 클러스터링 알고리즘에 의해 생성된 클러스터는 몇 가지 특성을 가지며, 이는 솔루션의 동질성과 분리를 증명할 수 있다.

정리 1 연결성이 높은 모든 그래프의 직경은 최대 두 개다.

증명: n= G. G가 도 <= n/2>의 정점 x를 가지고 있다면, G는 에지 <= n/2>와 함께 최소 절단(x를 절연하는 것)을 가지고 있으므로 G는 연결성이 높지 않다.그래서 G가 고도로 연결되어 있으면 모든 꼭지점에는 도 >= n/2가 있다.그래프 이론에는 모든 꼭지점에 도 >= n/2가 있으면 G의 지름(어떤 두 개의 노드 사이에 있는 가장 긴 경로) <= 2>라고 하는 유명한 정리가 있다.

참고 항목:거리(그래프 이론)

정리 2 (a) 고도로 연결된 그래프에서 가장자리 수는 이차적이다. (b) HCS 알고리즘의 각 반복에 의해 제거된 가장자리 수는 최대 선형이다.

증명: (a) 정리 1로부터 우리는 모든 꼭지점에 도 >= n/2가 있다는 것을 안다.따라서 고도로 연결된 그래프에서 가장자리 수는 (n × n/2)/2 이상이어야 하며 여기서 각 꼭지점의 정도를 합하여 2로 나눈다.

(b) 정의상 각 반복은 <= n/2 에지>로 최소 절단을 제거한다.

이론 1과 2a는 최종 군집의 동질성을 강하게 나타낸다.클러스터의 모든 정점이 연결되는 경우에 더 잘 접근하며, 이는 너무 엄격하고 또한 NP-경도도 높다.

정리 2b는 어떤 두 최종 군집 C1과 C2가 그들 사이에 최대 O(C1+C2) 에지가 있지 않는 한 분리되지 않았을 것이기 때문에 분리를 나타낸다.

변형

단골격 채택:초기 군집화 프로세스에 의해 단골격으로 남겨진 요소는 군집과의 유사성에 기초하여 군집별로 "적용"될 수 있다.특정 클러스터에 대한 최대 인접 항목 수가 충분히 큰 경우 해당 클러스터에 추가할 수 있다.

낮은 도 정점을 제거하는 중:입력 그래프가 낮은 도수의 정점을 갖는 경우, 알고리즘은 계산적으로 비싸고 정보를 제공하지 않기 때문에 실행할 가치가 없다.또는 알고리즘의 정교화는 먼저 특정 임계값보다 낮은 수준의 모든 정점을 제거할 수 있다.

HCS 사용 예

  • 유전자 표현 분석[2] 합성 올리고뉴클레오티드를 배열된 cDNA로 혼합하면 각 cDNA 복제에 지문이 생성된다.이 지문에 대한 HCS 알고리즘을 실행하면 동일한 유전자에 해당하는 클론을 식별할 수 있다.

참조

  1. ^ Hartuv, E.; Shamir, R. (2000), "A clustering algorithm based on graph connectivity", Information Processing Letters, 76 (4–6): 175–181, doi:10.1016/S0020-0190(00)00142-3
  2. ^ E Hartuv, A O Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir."cDNA 지문을 군집화하는 알고리즘."Genomics 66, 3번(2000): 249-256.
  3. ^ 쥬리시카, 이고르, 데니스 위글.프로테오믹스의 지식 발견.제8권. CRC 프레스, 2006.
  4. ^ 쉬, 루이, 도날드 운슈."군집화 알고리즘 조사."신경망, IEEE 16호 거래: 645-678호
  5. ^ Sharan, R.; Shamir, R. (2000), "CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis", Proceedings ISMB '00, 8: 307–316C, PMID 10977092
  6. ^ Huffner, F.; Komusiewicz, C.; Liebtrau, A; Niedermeier, R (2014), "Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage", IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11 (3): 455–467, CiteSeerX 10.1.1.377.1900, doi:10.1109/TCBB.2013.177, PMID 26356014, S2CID 991687