상관 군집화

Correlation clustering

군집화는 데이터 포인트를 유사성에 따라 그룹으로 나누는 문제다.상관 군집화는 사전에 개체 수를 지정하지 않고 개체 집합을 최적의 군집 수로 군집화하는 방법을 제공한다.[1]

문제 설명

주요 기사:군집 분석

머신러닝(machine learning)에서, 상관 군집화(correlation clustering)나 클러스터 편집(cluster editing)은 객체의 실제 표현 대신 객체 간의 관계를 알 수 있는 시나리오에서 동작한다.예를 들어, 가중 그래프 =(, E) G이(가) 에지 가중치가 두 노드의 유사(양수 에지 가중치) 또는 상이(음수 에지 가중치)인지 여부를 나타내는 경우, 이 작업은 합의(클러스터 내의 양의 에지 가중치 합계와 s의 절대값 합)를 최대화하는 클러스터링을 찾는 것이다.군집 간 음의 에지 가중치) 또는 불일치 최소화(군집 내 음의 에지 가중치 합계에 군집 전체의 양의 에지 가중치 합계를 더한 값).다른 클러스터링 알고리즘과는 달리, 컷 에지의 가중치 합계를 최소화하기 위한 목적은 클러스터 수와 독립적이기 때문에 사전에 클러스터 수 을 선택할 필요가 없다.

유사한 항목이 모두 한 군집에 있는 반면 다른 모든 항목이 다른 군집에 있는 완벽한 군집을 찾을 수 없을 수 있다.그래프가 정말로 완벽한 군집을 허용하는 경우, 음의 가장자리를 모두 삭제하고 나머지 그래프에서 연결된 구성요소를 찾기만 하면 필요한 군집이 반환된다.

그러나 일반적으로 그래프에는 완벽한 군집화가 없을 수 있다.예를 들어, a,b 및 a,c가 유사한 반면 b,c가 서로 다른 노드 a,b,c를 고려할 때 완벽한 클러스터링은 불가능하다.이 경우 합의 수(클러스터 내부의 + 에지 수 + 클러스터 간의 - 에지 수)를 최대화하거나 불일치 수(클러스터 내부의 - 에지 수 + 클러스터 간의 + 에지 수)를 최소화하는 클러스터링을 찾는 것이 과제다.이 협정 최대화의 문제는 NP-완전(다중간 컷 문제는 가중 합의의 최대화로 감소하고 삼각형으로[2] 분할하는 문제는 가중되지 않은 버전으로 축소할 수 있다)

알고리즘

Vansal 등은 NP-완전성 입증에 대해 논의하고 이 설정에서 클러스터를 찾기 위한 상수 인자 근사 알고리즘과 다항 시간 근사 방법을 모두 제시한다.[3]Ailon 외.[4]는 동일한 문제에 대해 무작위화된 3-대략 알고리즘을 제안한다. 

CC-Pivot(G=(V,E+,E−))     Pick random pivot i ∈ V     Set , V'=Ø     For all j ∈ V, j ≠ i;         If (i,j) ∈ E+ then             Add j to C         Else (If (i,j) ∈ E−)             Add j to V'     Let G' be the subgraph induced by V'     Return clustering C,CC-Pivot(G')

저자들은 위의 알고리즘이 상관 군집화를 위한 3-대략 알고리즘임을 보여준다.이 문제에 대해 현재 알려진 최고의 다항식 시간 근사 알고리즘은 차울라, 마카리체프, 슈람, 야로슬라브체프에서 볼 수 있듯이 선형 프로그램을 반올림하여 약 2.06 근사치를 달성한다.[5]

Karpinski와 Schudy는[6] 완전한 그래프와 고정된 수의 군집을 통해 이 문제에 대한 다항 시간 근사 체계(PTAS)의 존재를 증명했다.

최적 군집 수

2011년에는 Bagon과 Galun에[7] 의해 상관관계 클러스터링 기능의 최적화가 잘 알려진 이산 최적화 방법과 밀접하게 관련되어 있음을 보여주었다.그들은 연구에서 상관 군집화 함수가 기초 군집 수를 추정할 수 있도록 하는 기초 암묵적 모델에 대한 확률론적 분석을 제안했다.이 분석은 기능이 클러스터 수에 관계없이 가능한 모든 파티션에 걸쳐 균일하다고 가정한다는 것을 시사한다.따라서 군집 수에 비해 균일하지 않은 이전이 나타난다.

요소 수에 따라 우아하게 확장되는 몇 가지 이산 최적화 알고리즘이 본 연구에서는 제안된다(실험에서는 10만개 이상의 변수를 가진 결과를 보여준다).Bagon과 Galun의 작업은 또한 여러 애플리케이션에서 기본 클러스터 수 회복의 효과성을 평가했다.

상관 군집화(데이터 마이닝)

상관 군집화는 또한 다른 작업과 관련이 있는데, 여기서 고차원 공간에서 형상 벡터의 속성들 간의 상관관계가 군집화 과정을 안내하는 것으로 가정된다.이러한 상관관계는 다른 군집마다 다를 수 있기 때문에, 전지구적 장식관계는 이것을 전통적인 (비상관적) 군집화로 축소할 수 없다.

속성 하위 집합 간의 상관관계는 군집의 공간적 형태를 다르게 만든다.따라서 군집 개체 간의 유사성은 국소 상관 패턴을 고려하여 정의된다.이 개념과 함께 위에서 논의된 개념과 동시에 이 용어가 도입되었다.이 유형의 상관계 군집화 방법은 에서 논의하고 다른 유형의 군집화와의 관계는 에서 논의한다.[10]고차원 데이터 클러스터링을 참조하십시오.

(이 정의에 따라) 상관 군집화는 바이클러스터링과 밀접하게 관련되어 있음을 보여줄 수 있다.바이클러스터링에서와 같이, 목표는 일부 속성에서 상관 관계를 공유하는 개체 그룹을 식별하는 것이다. 일반적으로 상관 관계가 개별 클러스터에 대해 일반적인 경우.

참조

  1. ^ Becker, Hila, "상관 군집화 조사", 2005년 5월 5일
  2. ^ Garey, M. and Johnson, D (W.H. Freeman and Company). (2000). Computers and Intractability: A Guide to the Theory of NP-Completeness.{{cite conference}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  3. ^ Bansal, N.; Blum, A.; Chawla, S. (2004). "Correlation Clustering". Machine Learning. 56 (1–3): 89–113. doi:10.1023/B:MACH.0000033116.57574.95.
  4. ^ Ailon, N.; Charikar, M.; Newman, A. (2005). "Aggregating inconsistent information". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05. p. 684. doi:10.1145/1060590.1060692. ISBN 1581139608.
  5. ^ Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory. "Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs". Proceedings of the 46th Annual ACM on Symposium on Theory of Computing.
  6. ^ Karpinski, M.; Schudy, W. (2009). "Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems". Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09. p. 313. arXiv:0811.3244. doi:10.1145/1536414.1536458. ISBN 9781605585062.
  7. ^ Bagon, S.; Galun, M.(2011) "대규모 상관 군집화 최적화" arXiv:1112.2903v1
  8. ^ Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Computing Clusters of Correlation Connected objects". Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04. p. 455. CiteSeerX 10.1.1.5.1279. doi:10.1145/1007568.1007620. ISBN 978-1581138597.
  9. ^ Zimek, A. (2008). "Correlation Clustering". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  10. ^ Kriegel, H. P.; Kröger, P.; Zimek, A. (2009). "Clustering high-dimensional data". ACM Transactions on Knowledge Discovery from Data. 3: 1–58. doi:10.1145/1497577.1497578.