고차원 데이터 클러스터링

Clustering high-dimensional data

고차원 데이터 군집화는 수십에서 수천의 차원을 가진 데이터의 군집 분석이다.이와 같은 고차원적인 데이터 공간은 DNA 마이크로어레이 기술이 한 번에 많은 측정치를 생산할 수 있는 의학, 그리고 단어 주파수 벡터를 사용한다면 차원의 수가 어휘의 크기와 동일한 텍스트 문서의 군집화와 같은 영역에서 자주 접하게 된다.

문제

고차원 데이터에서 클러스터링하려면 네 가지 문제를 극복해야 한다.[1]

  • 다차원은 생각하기 어렵고 시각화가 불가능하며, 각 차원과 함께 가능한 값의 수가 기하급수적으로 증가하기 때문에 차원성이 증가함에 따라 모든 하위 영역의 완전한 열거가 난해해진다.이 문제는 차원성의 저주라고 알려져 있다.
  • 거리 개념은 주어진 데이터 집합에서 두 점 사이의 거리가 수렴되기 때문에 치수의 수가 증가함에 따라 덜 정밀해진다.특히 가장 가까운 지점과 가장 먼 지점의 차별은 무의미해진다.
  • 군집은 그 속성 값의 관찰에 기초하여 관련된 객체를 그룹화하기 위한 것이다.그러나, 많은 수의 속성이 주어진다면, 일부 속성은 일반적으로 주어진 클러스터에 의미가 없을 것이다.예를 들어 신생아 선별 검사에서 표본 군집은 유사한 혈액 값을 공유하는 신생아를 식별하여 질병에 대한 특정 혈액 값의 관련성에 대한 통찰력을 얻을 수 있다.그러나 다른 질병의 경우 다른 혈액이 군집을 형성할 수 있고, 다른 혈액은 상관관계가 없을 수 있다.이를 로컬 기능 관련 문제로 알려져 있는데, 서로 다른 하위 공간에서 서로 다른 클러스터가 발견될 수 있기 때문에 속성의 전역 필터링만으로는 충분하지 않다.
  • 많은 수의 속성으로 볼 때, 일부 속성은 상관관계가 있을 가능성이 있다.따라서 클러스터는 임의로 지향하는 부속 공간에 존재할 수 있다.

최근의 연구는 차별 문제는 관련 없는 차원이 많을 때에만 발생하며, 가장 가까운 공유 접근법이 결과를 개선할 수 있다는 것을 보여준다.[2]

접근

축-병렬 또는 임의 지향 아핀 서브스페이스에서 클러스터링에 대한 접근방식은 높은 치수성을 가진 데이터에서 클러스터를 찾는 전체적인 목표를 해석하는 방법에 따라 다르다.[1]전체적으로 다른 접근방식은 종종 생물정보학에서 자주 사용되는 기술인 바이클러스터링(biclustering)으로 불리는 데이터 매트릭스의 패턴을 기반으로 클러스터를 찾는 것이다.

서브공간 군집화

하위 공간 클러스터가 있는 2D 공간 예제

인접한 이미지는 여러 군집을 식별할 수 있는 2차원 공간만 보여준다.In the one-dimensional subspaces, the clusters (in subspace ) and , , (in subspace ) can be found. 은(는) x축에 너무 희박하게 분포되어 있으므로 2차원(하위)공간의 클러스터로 볼 수 없다.2차원에서는 두 군집 a 와 를 식별할 수 있다.

서브 스페이스 클러스터링 문제는 d {\차원의 공간에 서로 다른 서브스페이스가 있다는 사실에 의해 주어진다.서브스페이스가 축 평행하지 않으면 무한히 많은 서브스페이스가 가능하다.따라서 하위 공간 군집화 알고리즘은 열등한 결과를 산출할 위험에서 계산적으로 실현 가능한 상태를 유지하기 위해 일종의 휴리스틱을 이용한다.예를 들어, downward-closure 속성(비교하라. 협회 규칙)higher-dimensional subspaces을 짓는 데 단지lower-dimensional들 결합해 어떤 부분 공간 T가 클러스터가 포함된 것으로, S또한 그 클러스터(포지티브 S⊆ T)고 진입 CLIQUE,[3]SUB 같은 전통적인 알고리즘의 대부분에 의해 취해 포함하는 전체 우주로 이어질 것이다 사용될 수 있다.CLU.[4] 또한 iMWK-Means,[5] EBK-Modes[6] 및 CBK-Modes에 의해 취해진 접근방식, 각 차원에 대해 서로 다른 수준의 관련성을 사용하여 하위 공간을 정의할 수도 있다.[7]

예상 군집화

예상 클러스터링은 각 점을 고유한 클러스터에 할당하려고 하지만 클러스터는 서로 다른 하위 영역에 존재할 수 있다.일반적인 접근방식은 일반 클러스터링 알고리즘과 함께 특수 거리 함수를 사용하는 것이다.

예를 들어 PreDeCon 알고리즘은 어떤 속성이 각 점의 클러스터링을 지원하는 것처럼 보이는지 확인하고, 거리 함수에 분산성이 낮은 치수가 증폭되도록 거리 함수를 조정한다.[8]위의 그림에서 c 클러스터 는 - 축을 덜 강조하여 - 축의 낮은 차이를 클러스터로 그룹화하기에 충분할 정도로 과장하는 거리 함수의 DBSCAN을 사용하여 찾을 수 있다.

PROLOCUS는 k-medoid 클러스터링과 유사한 접근방식을 사용한다.[9]초기 메이드로이드는 추측되며, 각 메이드로이드에 대해 분산이 낮은 속성에 의해 확장된 아공간이 결정된다.거리를 결정할 때 해당 중간의 하위 공간만 고려하여 가장 가까운 중합체에 점을 할당한다.그런 다음 알고리즘은 정규 PAM 알고리즘으로 진행된다.

거리 함수의 가중치 속성은 다르지만 0으로는 결코 속성이 없는 경우(따라서 관련 없는 속성은 절대 떨어뜨리지 않는 경우), 알고리즘을 "소프트"로 투영된 클러스터링 알고리즘이라고 한다.

투영 기반 클러스터링

투영 기반 클러스터링은 고차원 데이터를 2차원 공간으로 비선형 투영하는 것을 기반으로 한다.[10]t-분산 확률적 인접 임베딩(t-SNE)[11] 또는 인접 검색 비주얼라이저(NerV)와 같은 전형적인 투영 방법은 데이터를 2차원 이상의 하위 공간을 무시하고 고차원 데이터로 관련 인접 영역만 보존하는 2차원으로 명시적으로 투영하는 데 사용된다.다음 단계에서는 투영점 사이의 델로나이 그래프를[13] 계산하고, 두 투영점 사이의 각 꼭지점에 해당하는 고차원 데이터점 사이의 고차원 거리에 가중치를 부여한다.이후 모든 점 쌍 사이의 최단 경로가 Dijkstra 알고리즘을 사용하여 계산된다.[14]다음으로 최단 경로는 클러스터링 프로세스에 사용되며, 고차원 데이터의 구조 유형에 따라 두 가지 선택이 수반된다.[10]이 부울 선택은 고차원 구조물의 지형도를 보고 결정할 수 있다.[15]34가지 비교 가능한 클러스터링 방법의 벤치마킹에서 투영 기반 클러스터링은 데이터 집합의 고차원 거리 또는 밀도 기반 구조를 항상 찾을 수 있는 유일한 알고리즘이었다.[10]투영 기반 클러스터링은 CRAN의 오픈 소스 R 패키지 "ProjectBasedClustering"에서 액세스할 수 있다.[16]

하이브리드 접근 방식

모든 알고리즘이 각 지점 또는 모든 서브스페이스의 모든 클러스터에 대해 고유한 클러스터 할당을 찾으려고 하는 것은 아니며, 많은 알고리즘이 여러 개의 클러스터가 중복될 수 있지만 반드시 전체 클러스터 집합이 발견되지는 않는 사이에 결과에 만족한다.예를 들어, Fires는 하위공간 군집화 알고리즘을 기본 접근방식으로 사용하지만 모든 하위공간 군집을 믿을 수 없을 정도로 공격적인 휴리스틱을 사용한다.[17]또 다른 하이브리드 접근방식은 알고리즘 루프를 인간에 포함시키는 것이다.the-the-Algorithm-Loop)를 포함하는 것이다.휴먼 도메인 전문지식은 경험적인 샘플 선택을 통해 기하급수적인 검색 공간을 줄이는 데 도움을 줄 수 있다.이는 예를 들어, 의사들이 환자 상태에 대한 고차원적 설명과 특정 치료법의 성공에 대한 측정에 직면하는 건강 영역에서 유익할 수 있다.그러한 데이터에서 중요한 질문은 치수의 조합과 함께 환자의 상태와 치료 결과를 비교하고 상관관계를 분석하는 것이다.치수의 수는 종종 매우 크므로, 전문가 분석에 더 적합하도록 관련 치수의 적은 수로 치수를 매핑할 필요가 있다.이는 관련성이 없고 중복되며 상충되는 차원이 전체 분석 과정의 효과성과 효율성에 부정적인 영향을 미칠 수 있기 때문이다.[18]

상관 군집화

상관 군집화(Data Mining)에서는 또 다른 유형의 서브스페이스가 고려한다.

소프트웨어

  • ELKI는 다양한 하위 공간 및 상관 관계 클러스터링 알고리즘을 포함한다.
  • FCPS에는 50개 이상의 클러스터링 알고리즘이[19] 포함됨

참조

  1. ^ a b 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.
  2. ^ Houle, M. E.; Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2010). Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? (PDF). Scientific and Statistical Database Management. Lecture Notes in Computer Science. Vol. 6187. p. 482. doi:10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
  3. ^ Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). "Automatic Subspace Clustering of High Dimensional Data". Data Mining and Knowledge Discovery. 11: 5–33. CiteSeerX 10.1.1.131.5152. doi:10.1007/s10618-005-1396-1.
  4. ^ Kailing, K.; Kriegel, H. P.; Kröger, P. (2004). Density-Connected Subspace Clustering for High-Dimensional Data. Proceedings of the 2004 SIAM International Conference on Data Mining. pp. 246. doi:10.1137/1.9781611972740.23. ISBN 978-0-89871-568-2.
  5. ^ De Amorim, R.C.; Mirkin, B. (2012). "Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering". Pattern Recognition. 45 (3): 1061. doi:10.1016/j.patcog.2011.08.012.
  6. ^ Carbonera, Joel Luis; Abel, Mara (November 2014). An Entropy-Based Subspace Clustering Algorithm for Categorical Data. 2014 IEEE 26th International Conference on Tools with Artificial Intelligence. IEEE. doi:10.1109/ictai.2014.48. ISBN 9781479965724.
  7. ^ Carbonera, Joel Luis; Abel, Mara (2015). CBK-Modes: A Correlation-based Algorithm for Categorical Data Clustering. Proceedings of the 17th International Conference on Enterprise Information Systems. SCITEPRESS - Science and Technology Publications. doi:10.5220/0005367106030608. ISBN 9789897580963.
  8. ^ Böhm, C.; Kailing, K.; Kriegel, H. -P.; Kröger, P. (2004). Density Connected Clustering with Local Subspace Preferences (PDF). Fourth IEEE International Conference on Data Mining (ICDM'04). p. 27. doi:10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
  9. ^ Aggarwal, C. C.; Wolf, J. L.; Yu, P. S.; Procopiuc, C.; Park, J. S. (1999). "Fast algorithms for projected clustering". ACM SIGMOD Record. 28 (2): 61. CiteSeerX 10.1.1.681.7363. doi:10.1145/304181.304188.
  10. ^ a b c 스룬, M. C., & Ultsch, A. : 투영 기반 클러스터링을 사용하여 고차원 데이터, J. Classif, 1-33, doi: 10.1007/s00357-020-09373-2.
  11. ^ 반 데르 마텐, L&Hinton, G.T-SNE, Journal of Machine Learning Research, Vol. 9(11) 페이지 2579-2605. 2008을 사용하여 데이터 시각화.
  12. ^ Venna, J, Peltonen, J, Nybo, K, Aidos, H, & Kaski, S.: 정보 검색 관점은 데이터 시각화를 위한 비선형 차원성 저감에 대한 것이다. The Journal of Machine Learning Research, Vol. 11, 페이지 451-490. 2010.
  13. ^ 딜라우나이, B:수르 라 구 비디오, 이즈브 Akad. Nauk SSSR, Otdelenie Matematiceskii i Estestvennyka Nauk, vol. 7권(793-800), 1-2. 1934.
  14. ^ Dijkstra, E. W.: 그래프와의 연결에서 두 가지 문제에 대한 참고 사항, 그림 1(1), 페이지 269-271. 1959.
  15. ^ 스룬, M. C. & Ultsch, A.치수 감소 방법, MethodX, Vol. 7, 페이지 101093, doi: 10.1016/j.mex.20200.101093,2020에서 투영 고차원 구조 발견.
  16. ^ "CRAN - Package ProjectionBasedClustering". Archived from the original on 2018-03-17.
  17. ^ Kriegel, H.; Kröger, P.; Renz, M.; Wurst, S. (2005). A Generic Framework for Efficient Subspace Clustering of High-Dimensional Data (PDF). Fifth IEEE International Conference on Data Mining (ICDM'05). p. 250. doi:10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
  18. ^ Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, D.A.; Majnaric, L.; Holzinger, A. (2016). "Visual analytics for concept exploration in subspaces of patient groups: Making sense of complex datasets with the Doctor-in-the-loop". Brain Informatics. 3 (4): 233–247. doi:10.1007/s40708-016-0043-5. PMC 5106406. PMID 27747817.
  19. ^ 스룬, M. C. & Stier, Q.기본 클러스터링 알고리즘 제품군, 소프트웨어X, Vol. 13(C), 페이지 100642, doi: 10.1016/j.softx.2020.100642, 2021.