클러스터링 메트릭으로 미지 항목 식별

클러스터링은 각 샘플의 기능만을 기반으로 주어진 데이터를 그룹으로 나누는 비지도 머신 러닝 방법입니다. 데이터를 클러스터로 정렬하면 샘플 간의 알려지지 않은 유사성을 식별하거나 데이터 세트의 이상값을 표시하는 데 도움이 될 수 있습니다. 현실 세계에서 클러스터링은 마케팅에서 생물학에 이르기까지 다양한 분야에서 의미가 있습니다. 클러스터링 애플리케이션에는 시장 세분화, 소셜 네트워크 분석 및 진단 의료 영상이 포함됩니다.

이 프로세스는 감독되지 않기 때문에 여러 클러스터링 결과가 다양한 기능을 중심으로 형성될 수 있습니다. 예를 들어 빨간색 바지, 검은색 바지, 빨간색 셔츠 및 검은색 셔츠의 다양한 이미지로 구성된 데이터 세트가 있다고 가정합니다. 한 알고리즘은 옷 모양을 기반으로 클러스터를 찾고 다른 알고리즘은 색상을 기반으로 그룹을 만들 수 있습니다.

데이터 세트를 분석할 때 서로 다른 클러스터링 알고리즘의 성능을 정확하게 측정하는 방법이 필요합니다. 두 알고리즘의 솔루션을 대조하거나 클러스터링 결과가 예상 솔루션에 얼마나 가까운지 확인하고자 할 수 있습니다. 이 기사에서는 동일한 데이터에서 얻은 다양한 클러스터링 결과를 비교하는 데 사용할 수 있는 몇 가지 메트릭을 탐색합니다.

클러스터링 이해: 간단한 예

다양한 클러스터링 메트릭 개념을 설명하고 생성할 수 있는 클러스터의 종류를 조사하는 데 사용할 예제 데이터 세트를 정의해 보겠습니다.

먼저 몇 가지 일반적인 표기법과 용어:

• $D$: 데이터 세트
• $A$, $B$: 데이터 세트의 하위 집합인 두 개의 클러스터
• $C$: 다른 클러스터와 비교할 $D$의 실제 클러스터링
  • $C$ 클러스터링에는 $K$ 클러스터가 있습니다. $C = {C_1, …, C_k}$
• $C'$: $D$의 두 번째 클러스터링
  • $C'$ 클러스터링에는 $K'$ 클러스터가 있습니다. $C' = {C^\prime_1, ..., C^\prime_{k^\prime}}$

클러스터링 결과는 정렬 기능뿐만 아니라 총 클러스터 수에 따라 달라질 수 있습니다. 결과는 알고리즘, 작은 섭동에 대한 민감도, 모델의 매개변수 및 데이터의 기능에 따라 다릅니다. 앞서 언급한 검정 및 빨강 바지와 셔츠의 데이터 세트를 사용하면 다양한 알고리즘에서 생성될 수 있는 다양한 클러스터링 결과가 있습니다.

일반 클러스터링 $C$와 예제 클러스터링을 구별하기 위해 소문자 $c$를 사용하여 예제 클러스터링을 설명합니다.

• $c$, 모양 기반 클러스터 포함: $c = {c_1, c_2}$, 여기서 $c_1$는 바지를 나타내고 $c_2$는 셔츠를 나타냅니다.
• $c'$, 색상 기반 클러스터 포함: $c' = {c'_1, c'_2}$, 여기서 $c'_1$는 빨간색 옷을 나타내고 $c'_2$는 검은 옷을 나타냅니다.
• $c''$, 모양 및 색상 기반 클러스터 포함: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, 여기서 ${c^{\prime \prime}}_1$는 빨간 바지, ${c^{\prime \prime}}_2 $는 검은색 바지, ${c^{\prime \prime}}_3$는 빨간색 셔츠, ${c^{\prime \prime}}_4$는 검은색 셔츠를 나타냅니다.

추가 클러스터링에는 셔츠가 민소매인지 소매가 있는지와 같은 다양한 기능을 기반으로 하는 4개 이상의 클러스터가 포함될 수 있습니다.

이 예에서 볼 수 있듯이 클러스터링 방법은 데이터 세트의 모든 샘플을 비어 있지 않은 분리된 하위 집합으로 나눕니다. $c$ 클러스터에는 바지 하위 집합과 셔츠 하위 집합에 모두 속하는 이미지가 없습니다. $c_1 \cap c_2 = \emptyset$. 이 개념은 확장될 수 있습니다. 클러스터의 두 하위 집합에는 동일한 샘플이 없습니다.

클러스터링 비교 메트릭 개요

클러스터링을 비교하는 대부분의 기준은 $C, C'$ 쌍의 혼동 행렬을 사용하여 설명할 수 있습니다. 정오분류표는 $kk'$th 요소($k$th 행 및 $k'$th 열의 요소)가 클러스터 교차점의 샘플 수인 $K \times K'$ 행렬입니다. $C$의 C_k$ 및 $C'$의 $C'_{k'}$:

\[n_{kk'} = |C_k \cap C'_{k'}|\]

데이터 세트 $D$에 빨간색 바지 100개, 검은색 바지 200개, 빨간색 셔츠 200개, 검은색 셔츠 300개가 있다고 가정하고 단순화된 검정 및 빨간색 바지와 셔츠 예제를 사용하여 이를 분해할 것입니다. $c$와 $c''$의 혼동 행렬을 살펴보겠습니다.

$K = 2$ 및 $K'' = 4$이므로 이것은 $2 \times 4$ 행렬입니다. $k = 2$와 $k'' = 3$를 선택합시다. $n_{kk'} = n_{23} = 200$라는 요소를 볼 수 있습니다. 이것은 $c_2$(셔츠)와 ${c^{\prime\prime}}_3$(빨간 셔츠)의 교집합이 200이라는 것을 의미하며, 이는 $c_2 \cap {c^{\prime\prime}이므로 정확합니다. }_3$는 단순히 빨간 셔츠 세트입니다.

클러스터링 메트릭은 기본 클러스터 비교 방법에 따라 크게 세 그룹으로 분류할 수 있습니다.

이 기사에서는 사용 가능한 많은 메트릭 중 몇 가지만 다루지만 예제는 세 가지 클러스터링 메트릭 그룹을 정의하는 데 도움이 됩니다.

페어 카운팅

쌍을 계산하려면 모든 샘플 쌍을 검사한 다음 클러스터링이 일치하고 동의하지 않는 쌍을 계산해야 합니다. 각 샘플 쌍은 4개 세트 중 하나에 속할 수 있으며, 여기서 세트 요소 수($N_{ij}$)는 혼동 행렬에서 얻습니다.

• $S_{11}$, $N_{11}$ 요소 포함: 쌍의 요소는 $C$ 및 $C'$ 아래 동일한 클러스터에 있습니다.
  • $c$와 $c''$를 비교할 때 두 켤레의 빨간색 셔츠는 $S_{11}$에 해당합니다.
• $S_{00}$, $N_{00}$ 요소 포함: 쌍의 요소는 $C$ 및 $C'$ 아래 서로 다른 클러스터에 있습니다.
  • $c$와 $c''$를 비교할 때 빨간색 셔츠와 검은색 바지 한 켤레는 $S_{00}$에 해당합니다.
• $S_{10}$, $N_{10}$ 요소 포함: 쌍의 요소는 $C$의 동일한 클러스터에 있고 $C'$의 다른 클러스터에 있습니다.
  • $c$와 $c''$를 비교할 때 빨간색 셔츠와 검은색 셔츠 한 켤레는 $S_{10}$에 해당합니다.
• $S_{01}$, $N_{01}$ 요소 포함: 쌍의 요소는 $C$의 다른 클러스터에 있고 $C'$의 동일한 클러스터에 있습니다.
  • $S_{01}$에는 $c$와 $c''$를 비교할 때 요소가 없습니다($N_{01} = 0$).

Rand 색인 은 $(N_{00} + N_{11})/(n(n-1)/2)$로 정의되며, 여기서 $n$는 샘플 수를 나타냅니다. (유사하게 처리된 쌍의 수)/(총 쌍의 수)로 읽을 수도 있습니다. 이론적으로 값의 범위는 0과 1 사이이지만 실제로는 그 범위가 훨씬 좁은 경우가 많습니다. 값이 높을수록 클러스터링 간의 유사성이 높아집니다. (Rand 인덱스가 1이면 두 클러스터링에 동일한 클러스터가 있는 완벽한 일치를 나타냅니다.)

Rand 인덱스의 한 가지 제한 사항은 클러스터 수가 요소 수에 근접하도록 증가할 때의 동작입니다. 이 경우 1로 수렴하여 클러스터링 유사성을 정확하게 측정하는 데 어려움이 있습니다. 이 문제를 해결하기 위해 Rand 색인의 몇 가지 개선되거나 수정된 ​​버전이 도입되었습니다. 한 가지 변형은 조정된 Rand 지수입니다 . 그러나 고정된 수의 클러스터와 클러스터 요소를 사용하여 두 개의 클러스터링이 무작위로 그려졌다고 가정합니다.

정보이론

이러한 메트릭은 정보 이론의 일반적인 개념을 기반으로 합니다. 우리는 그들 중 두 가지인 엔트로피와 상호 정보(MI)에 대해 논의할 것입니다.

엔트로피는 클러스터링에 얼마나 많은 정보가 있는지 설명합니다. 클러스터링과 관련된 엔트로피가 0이면 무작위로 선택된 샘플의 클러스터에 대한 불확실성이 없으며 클러스터가 하나만 있는 경우에도 마찬가지입니다.

MI는 한 클러스터링이 다른 클러스터링에 대해 제공하는 정보의 양을 설명합니다. MI는 $C$의 샘플 클러스터를 아는 것이 $C'$의 샘플 클러스터에 대한 불확실성을 얼마나 줄이는지 나타낼 수 있습니다.

정규화된 상호 정보 는 클러스터링의 엔트로피의 기하 또는 산술 평균으로 정규화된 MI입니다. 표준 MI는 상수 값으로 제한되지 않으므로 정규화된 상호 정보는 더 해석 가능한 클러스터링 메트릭을 제공합니다.

이 범주에서 널리 사용되는 또 다른 메트릭은 클러스터링의 엔트로피와 MI 모두에 의존하는 정보의 변화 (VI)입니다. $H(C)$를 클러스터링의 엔트로피라고 하고 $I(C, C')$를 두 클러스터링 간의 MI라고 하자. 두 클러스터링 사이의 VI는 $VI(C,C') = H(C)+H(C')-2I(C,C')$로 정의할 수 있습니다. 0의 VI는 두 클러스터링 간의 완벽한 일치를 나타냅니다.

겹침 설정

중첩 메트릭 설정에는 클러스터 간의 최대 중첩을 기반으로 $C'$의 클러스터와 $C$의 클러스터에 대한 최상의 일치를 결정하는 작업이 포함됩니다. 이 범주의 모든 메트릭에서 1은 클러스터링이 동일함을 의미합니다.

최대 일치 측정 은 내림차순으로 정오분류표를 스캔하고 정오분류표의 가장 큰 항목을 먼저 일치시킵니다. 그런 다음 일치하는 클러스터를 제거하고 클러스터가 소진될 때까지 프로세스를 순차적으로 반복합니다.

F-측정 은 또 다른 집합 중첩 메트릭입니다. 최대 일치 측정과 달리 F-측정은 두 클러스터링을 비교하는 대신 클러스터링을 최적 솔루션과 비교하는 데 자주 사용됩니다.

F-측정을 사용하여 클러스터링 메트릭 적용

기계 학습 모델 및 검색 엔진과 같은 중요한 응용 프로그램에서 F-측정이 일반적으로 사용되기 때문에 예를 통해 F-측정을 더 자세히 살펴보겠습니다.

F-측정 정의

$C$가 실제 또는 최적의 솔루션이라고 가정해 보겠습니다. $C$의 $k$번째 클러스터에 대해 $k \in [1, K]$인 경우 클러스터링 결과 $C'$의 모든 클러스터로 개별 F-측정값을 계산합니다. 이 개별 F-측정은 $C^\prime_{k'}$ 클러스터가 $C_k$ 클러스터를 얼마나 잘 설명하는지 나타내며 이러한 클러스터에 대한 정밀도 및 재현율(2개의 모델 평가 메트릭)을 통해 결정할 수 있습니다. $I_{kk'}$를 $C$의 $k$th 클러스터와 $C'$의 $k'$th 클러스터에 있는 요소의 교집합으로 정의하고 $\lvert C_k \rvert$를 숫자로 정의합니다. $k$th 클러스터의 요소 수.

• 정밀도 $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

• $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$ 기억

그런 다음 $k$th 및 $k'$th 클러스터의 개별 F-측정값은 이러한 클러스터에 대한 정밀도 및 재현율의 조화 평균으로 계산할 수 있습니다.

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

이제 $C$와 $C'$를 비교하기 위해 전체 F 측정값을 살펴보겠습니다. 먼저 값이 클러스터의 개별 F-측정값인 분할표와 유사한 행렬을 만듭니다. $C$의 클러스터를 테이블의 행으로 매핑하고 $C'$의 클러스터를 개별 F-측정값에 해당하는 테이블 값과 함께 열로 매핑했다고 가정해 보겠습니다. 최대 개별 F-측정값이 있는 군집 쌍을 식별하고 이러한 군집에 해당하는 행과 열을 제거합니다. 클러스터가 소진될 때까지 이 작업을 반복합니다. 마지막으로 전체 F-측정을 정의할 수 있습니다.

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

보시다시피, 전체 F-측정은 클러스터에 대한 최대 개별 F-측정의 가중치 합입니다.

데이터 설정 및 예상 결과

Jupyter 노트북과 같이 기계 학습에 적합한 모든 Python 노트북은 우리 환경으로 작동합니다. 시작하기 전에 GitHub 리포지토리의 README, 확장된 readme_help_example.ipynb 예제 파일 및 requirements.txt 파일(필수 라이브러리)을 검사할 수 있습니다.

뉴스 기사로 구성된 GitHub 리포지토리의 샘플 데이터를 사용합니다. 데이터는 category , headline , date 및 short_description 을 포함한 정보로 정렬됩니다.

판다를 사용하여 데이터를 읽고, 분석하고, 조작할 수 있습니다. 전체 데이터 세트가 크기 때문에 데이터를 날짜별로 정렬하고 데모용으로 작은 샘플(10,000개의 뉴스 헤드라인)을 선택합니다.

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

이 데이터 샘플에는 30개의 범주가 있으므로 실행하면 노트북 출력 결과 30이 표시되어야 합니다. df.head(4) 를 실행하여 데이터가 어떻게 저장되는지 확인할 수도 있습니다. (이 섹션에 표시된 표와 일치해야 합니다.)

클러스터링 기능 최적화

클러스터링을 적용하기 전에 먼저 다음을 포함하여 모델의 중복 기능을 줄이기 위해 텍스트를 사전 처리해야 합니다.

• 균일한 대소문자를 갖도록 텍스트를 업데이트합니다.
• 숫자 또는 특수 문자 제거.
• 표제어를 수행합니다.
• 중지 단어 제거.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

결과로 사전 processed_input 된 헤드라인은 df.head(4) 를 다시 실행하여 관찰할 수 있는 processing_input 으로 표시됩니다.

이제 모든 기계 학습 모델을 적용할 수 있도록 각 헤드라인을 숫자 벡터로 나타내야 합니다. 이를 달성하기 위한 다양한 특징 추출 기술이 있습니다. 우리는 TF-IDF(term frequency-inverse document frequency)를 사용할 것입니다. 이 기술은 문서(이 예에서는 뉴스 헤드라인)에서 빈도가 높은 단어의 영향을 줄여줍니다. 이러한 단어는 클러스터링 또는 분류에서 결정적인 특징이 되어서는 안 되기 때문입니다.

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

다음으로 이러한 특징 벡터에 대한 첫 번째 클러스터링 방법인 응집 클러스터링을 시도합니다.

클러스터링 방법 1: 응집 클러스터링

주어진 뉴스 카테고리를 최적의 솔루션으로 고려하여 이러한 결과를 응집 클러스터링(데이터 세트에 30개의 카테고리가 있으므로 원하는 클러스터 수를 30으로 함)의 결과와 비교해 보겠습니다.

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

결과 클러스터를 정수 레이블로 식별합니다. 동일한 클러스터에 속하는 헤드라인에는 동일한 정수 레이블이 할당됩니다. GitHub 리포지토리의 compare_clusters 모듈에 있는 cluster_measure 함수는 집계 F-측정 및 완벽하게 일치하는 클러스터 수를 반환하므로 클러스터링 결과가 얼마나 정확한지 확인할 수 있습니다.

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

이러한 클러스터 결과를 최적의 솔루션과 비교할 때 실제 클래스 그룹과 일치하는 0.198의 낮은 F-측정값과 0개의 클러스터를 얻습니다. 이는 응집 클러스터가 우리가 선택한 헤드라인 범주와 일치하지 않음을 나타냅니다. 결과에서 클러스터가 어떻게 보이는지 확인합시다.

 df[df['class_prd'] == 0]['category'].value_counts()

결과를 검토하면 이 클러스터에 모든 범주의 헤드라인이 포함되어 있음을 알 수 있습니다.

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

따라서 결과의 클러스터가 최적의 솔루션과 일치하지 않는다는 점을 고려하면 낮은 F 측정값이 의미가 있습니다. 그러나 우리가 선택한 카테고리 분류는 데이터 세트의 가능한 한 부분만을 반영한다는 점을 기억하는 것이 중요합니다. 여기서 낮은 F-측정은 클러스터링 결과가 잘못되었음을 의미하는 것이 아니라 클러스터링 결과가 원하는 데이터 분할 방법과 일치하지 않는다는 것을 의미합니다.

클러스터링 방법 2: K-평균

동일한 데이터 세트에 대해 또 다른 인기 있는 클러스터링 알고리즘인 k-평균 클러스터링을 시도해 보겠습니다. 새 데이터 프레임을 만들고 cluster_measure 함수를 다시 사용합니다.

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

응집 클러스터링 결과와 마찬가지로 k-평균 클러스터링 결과는 주어진 범주와 유사하지 않은 클러스터를 형성했습니다. 최적 솔루션과 비교할 때 F-측정값이 0.18입니다. 두 클러스터링 결과는 유사한 F-측정값을 가지므로 서로 비교하는 것이 흥미로울 것입니다. 클러스터링이 이미 있으므로 F-측정값을 계산하기만 하면 됩니다. 먼저 class_gt 가 집적 클러스터링 출력을 갖고 class_prd 가 k-means 클러스터링 출력을 갖는 두 결과를 하나의 열로 가져옵니다.

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

0.4의 더 높은 F 측정값으로 두 알고리즘의 클러스터링이 최적 솔루션보다 서로 더 유사함을 관찰할 수 있습니다.

향상된 클러스터링 결과에 대해 자세히 알아보기

사용 가능한 클러스터링 비교 메트릭을 이해하면 기계 학습 모델 분석이 확장됩니다. F-측정 클러스터링 메트릭이 작동하는 것을 보았고 이러한 학습을 ​​다음 클러스터링 결과에 적용하는 데 필요한 기본 사항을 제공했습니다. 더 자세히 알아보려면 다음을 참조하십시오.

• 클러스터링 비교 - Dorothea Wagner 및 Silke Wagner의 개요
• 군집 비교—Marina Meila의 정보 기반 거리
• 클러스터링 비교를 위한 정보 이론 측정: Nguyen Xuan Vinh, Julien Epps 및 James Bailey의 확률에 대한 변형, 속성, 정규화 및 수정

---

Toptal 엔지니어링 블로그에 대한 추가 정보:

• Python/NetworkX를 사용한 그래프 데이터 과학
• 레이블이 지정되지 않은 데이터를 사용한 반 지도 이미지 분류
• 머신 러닝의 임베딩: 복잡한 데이터를 단순하게 만들기

Toptal 엔지니어링 블로그는 이 기사에 제공된 코드 샘플을 검토한 Luis Broncha에게 감사를 표합니다.