큐어 알고리즘

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

큐어(REPresentates를 사용한 클러스터화)는 대규모^{[citation needed]} 데이터베이스를 위한 효율적인 데이터 클러스터링 알고리즘입니다.K-평균 군집 분석과 비교할 때 특이치에 더 강력하며 비구면 모양과 크기 변동이 있는 군집을 식별할 수 있습니다.

기존 알고리즘의 결점

일반적인 K-평균 군집 분석 알고리즘은 오차 제곱의 합을 최소화합니다.

${{displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^2}$

서로 다른 군집의 크기 또는 기하학적 차이가 큰 경우, 제곱 오차 방법은 큰 군집을 분할하여 제곱 오차를 최소화할 수 있습니다. 이는 항상 올바른 것은 아닙니다.또한 계층형 클러스터링 알고리즘에서는 클러스터 간의 거리 ${\displaystyle {}_{}}$( ${\displaystyle {dm}_{}}$ ${\displaystyle i_{}}$n , ${\displaystyle {\mathrm{dm}}_{}}$ ${\displaystyle e_{}}$ ${\displaystyle a_{}}$ n$$\ $displaystyle d_{min$ , $d_{mean$ )이 모두 다른 클러스터 형상으로 동작하지 않기 때문에 이러한 문제가 발생합니다.또한 n이 클 경우 실행 시간이 높아집니다.

BIRCH 알고리즘의 문제는 3단계 이후에 클러스터가 생성되면 클러스터의 중심을 사용하고 각 데이터 점을 가장 가까운 중심을 ^{[citation needed]}가진 클러스터에 할당한다는 것입니다.군집의 크기와 모양이 일정하지 않은 경우 중심만 사용하여 데이터를 재배포하면 문제가 발생합니다.

큐어 클러스터링 알고리즘

크기가 균일하지 않거나 모양이 변형된 군집의 문제를 피하기 위해 CURE는 중심 기반과 모든 점 극단 사이의 중간 접지를 채택하는 계층적 군집 분석 알고리즘을 사용합니다.큐어에서는 클러스터의 잘 산란된 점의 정수 c를 선택하고, 그것들은 클러스터의 중심을 향해 분수α만큼 축소된다.축소 후 산란된 지점은 클러스터의 대표로 사용됩니다.대표자 쌍이 가장 가까운 군집은 큐어의 계층적 군집 분석 알고리즘의 각 단계에서 병합되는 군집입니다.이렇게 하면 CURE가 군집을 올바르게 식별하고 특이치에 덜 민감해집니다.

실행 시간은 O(n² log n)이므로 비용이 많이 들고 공간의 복잡성은 O(n)입니다.

런타임 복잡성이 높기 때문에 이 알고리즘을 대규모 데이터베이스에 직접 적용할 수 없습니다.이 요건은 확장으로 해결되었습니다.

• 랜덤 샘플링 : 랜덤샘플링은 대용량 데이터 세트를 지원합니다.일반적으로 랜덤 표본은 주 메모리에 적합합니다.랜덤 표본 추출에는 정확도와 효율성 사이의 균형이 포함됩니다.
• 파티션 분할 : 샘플 공간을 p개의 파티션으로 분할하는 것이 기본 개념입니다.각 파티션에는 n/p 요소가 포함되어 있습니다.첫 번째 패스는 클러스터의 최종 수가 일정q ≤ 1에 대해 n/pq로 감소할 때까지 각 파티션을 부분적으로 클러스터링합니다.두 번째 클러스터 패스는 n/q 파티션에 부분적으로 클러스터합니다.두 번째 패스의 경우 병합 절차에서는 병합된 클러스터의 대표점을 계산하기 전에 이전 클러스터의 대표점만 필요하므로 대표점만 저장됩니다.입력을 분할하면 실행 시간이 줄어듭니다.
• 디스크의 데이터 레이블 지정 : k개 군집의 대표점만 지정하면 나머지 데이터 지점도 군집에 할당됩니다.이를 위해 각 k개 군집의 랜덤하게 선택된 대표점 중 일부가 선택되고 데이터 점이 가장 가까운 대표점을 포함하는 군집에 할당됩니다.

유사 코드

큐어(점수,k)

입력 : 포인트 S 세트

출력 : k 클러스터

• 모든 군집 u(각 입력점)에 대해 평균 및 u.rep에는 군집 내 점의 평균과 군집의 c 대표점 집합이 저장됩니다(각 군집에는 하나의 데이터 점이 있으므로 c = 1).또한 u.closest는 u에 가장 가까운 클러스터를 저장합니다.
• 모든 입력 포인트가 k-d 트리 T에 삽입됩니다.
• 각 입력점을 개별 클러스터로 처리하여 각 u에 대해 u.closest를 계산한 다음 각 클러스터를 힙 Q에 삽입합니다(클러스터는 u.closest와 u.closest 사이의 거리 순으로 배열됩니다).
• 사이즈(Q) > k인 반면
• Q의 상위 요소(예: u)를 제거하고 가장 가까운 클러스터인 u.closest(예: v)와 병합하고 병합된 클러스터의 새 대표점을 계산합니다.
• T와 Q에서 u와 v를 제거합니다.
• Q의 모든 클러스터 x에 대해 x.closest를 업데이트하고 x를 재배치합니다.
• w를 Q에 삽입하다
• 따라하다

유용성

• pyclustering 오픈 소스 라이브러리에는 Python 및 C++의 CURE 알고리즘 구현이 포함되어 있습니다.

「 」를 참조해 주세요.

• k-표준 클러스터화 클러스터링
• BFR 알고리즘

레퍼런스

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: An Efficient Clustering Algorithm for Large Databases" (PDF). Information Systems. 26 (1): 35–58. doi:10.1016/S0306-4379(01)00008-4.
• Kogan, Jacob; Nicholas, Charles K.; Teboulle, M. (2006). Grouping multidimensional data: recent advances in clustering. Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Pattern recognition. Academic Press. pp. 572–574. ISBN 978-0-12-369531-4.