Mengidentifikasi Yang Tidak Diketahui Dengan Metrik Pengelompokan

Clustering adalah metode pembelajaran mesin tanpa pengawasan untuk membagi data yang diberikan ke dalam kelompok hanya berdasarkan fitur dari setiap sampel. Menyortir data ke dalam kelompok dapat membantu mengidentifikasi kesamaan yang tidak diketahui antara sampel atau mengungkapkan outlier dalam kumpulan data. Di dunia nyata, pengelompokan memiliki arti penting di berbagai bidang mulai dari pemasaran hingga biologi: Aplikasi pengelompokan mencakup segmentasi pasar, analisis jaringan sosial, dan pencitraan medis diagnostik.

Karena proses ini tidak diawasi, beberapa hasil pengelompokan dapat terbentuk di sekitar fitur yang berbeda. Misalnya, bayangkan Anda memiliki kumpulan data yang terdiri dari berbagai gambar celana panjang merah, celana panjang hitam, kemeja merah, dan kemeja hitam. Satu algoritma mungkin menemukan kelompok berdasarkan bentuk pakaian, sementara yang lain mungkin membuat kelompok berdasarkan warna.

Saat menganalisis kumpulan data, kita membutuhkan cara untuk mengukur kinerja algoritma pengelompokan yang berbeda secara akurat; kita mungkin ingin membandingkan solusi dari dua algoritma, atau melihat seberapa dekat hasil pengelompokan dengan solusi yang diharapkan. Pada artikel ini, kita akan mengeksplorasi beberapa metrik yang dapat digunakan untuk membandingkan hasil pengelompokan berbeda yang diperoleh dari data yang sama.

Memahami Clustering: Contoh Singkat

Mari kita tentukan contoh kumpulan data yang akan kita gunakan untuk menjelaskan berbagai konsep metrik pengelompokan dan memeriksa jenis cluster apa yang mungkin dihasilkannya.

Pertama, beberapa notasi dan istilah umum:

• $D$: kumpulan data
• $A$, $B$: dua cluster yang merupakan subset dari kumpulan data kami
• $C$: pengelompokan kebenaran dasar $D$ yang akan kita bandingkan dengan cluster lain
  • Pengelompokan $C$ memiliki gugus $K$, $C = {C_1, …, C_k}$
• $C'$: pengelompokan kedua dari $D$
  • Pengelompokan $C'$ memiliki $K'$ cluster, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Hasil pengelompokan dapat bervariasi tidak hanya berdasarkan fitur pengurutan tetapi juga jumlah total cluster. Hasilnya tergantung pada algoritme, sensitivitasnya terhadap gangguan kecil, parameter model, dan fitur data. Menggunakan kumpulan data celana dan kemeja hitam dan merah yang disebutkan sebelumnya, ada berbagai hasil pengelompokan yang mungkin dihasilkan dari algoritme yang berbeda.

Untuk membedakan antara pengelompokan umum $C$ dan pengelompokan contoh kami, kami akan menggunakan huruf kecil $c$ untuk menggambarkan pengelompokan contoh kami:

• $c$, dengan kelompok berdasarkan bentuk: $c = {c_1, c_2}$, dengan $c_1$ mewakili celana panjang dan $c_2$ mewakili kemeja
• $c'$, dengan kelompok berdasarkan warna: $c' = {c'_1, c'_2}$, dengan $c'_1$ mewakili pakaian merah dan $c'_2$ mewakili pakaian hitam
• $c''$, dengan kelompok berdasarkan bentuk dan warna: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, di mana ${c^{\prime \prime}}_1$ mewakili celana merah, ${c^{\prime \prime}}_2 $ mewakili celana hitam, ${c^{\prime \prime}}_3$ mewakili kemeja merah, dan ${c^{\prime \prime}}_4$ mewakili kemeja hitam

Pengelompokan tambahan dapat mencakup lebih dari empat kelompok berdasarkan fitur yang berbeda, seperti apakah kemeja tidak berlengan atau tidak berlengan.

Seperti yang terlihat dalam contoh kita, metode pengelompokan membagi semua sampel dalam kumpulan data menjadi himpunan bagian yang tidak kosong. Di kluster $c$, tidak ada gambar yang termasuk dalam subset celana dan subset baju: $c_1 \cap c_2 = \emptyset$. Konsep ini dapat diperluas; tidak ada dua himpunan bagian dari setiap cluster memiliki sampel yang sama.

Ikhtisar Metrik Perbandingan Pengelompokan

Sebagian besar kriteria untuk membandingkan pengelompokan dapat dijelaskan dengan menggunakan matriks konfusi dari pasangan $C, C'$. Matriks konfusi adalah matriks $K \times K'$ yang elemen $kk'$th (elemen pada baris $k$th dan kolom $k'$th) adalah jumlah sampel pada perpotongan cluster $ C_k$ dari $C$ dan $C'_{k'}$ dari $C'$:

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

Kami akan memecahnya menggunakan contoh celana dan kemeja hitam dan merah yang disederhanakan, dengan asumsi bahwa kumpulan data $D$ memiliki 100 celana merah, 200 celana hitam, 200 kemeja merah, dan 300 kemeja hitam. Mari kita periksa matriks konfusi dari $c$ dan $c''$:

Karena $K = 2$ dan $K'' = 4$, ini adalah matriks $2 \kali 4$. Mari kita pilih $k = 2$ dan $k'' = 3$. Kita melihat bahwa elemen $n_{kk'} = n_{23} = 200$. Ini berarti perpotongan $c_2$ (baju) dan ${c^{\prime\prime}}_3$ (baju merah) adalah 200, yang benar karena $c_2 \cap {c^{\prime\prime} }_3$ hanya akan menjadi set kemeja merah.

Metrik pengelompokan dapat secara luas dikategorikan menjadi tiga kelompok berdasarkan metode perbandingan klaster yang mendasarinya:

Dalam artikel ini, kami hanya menyentuh beberapa metrik yang tersedia, tetapi contoh kami akan membantu menentukan tiga grup metrik pengelompokan.

Menghitung pasangan

Penghitungan pasangan membutuhkan pemeriksaan semua pasangan sampel, kemudian menghitung pasangan di mana pengelompokan setuju dan tidak setuju. Setiap pasangan sampel dapat menjadi bagian dari salah satu dari empat himpunan, di mana jumlah elemen himpunan ($N_{ij}$) diperoleh dari matriks konfusi:

• $S_{11}$, dengan elemen $N_{11}$: elemen pasangan berada di cluster yang sama di bawah $C$ dan $C'$
  • Sepasang dua kemeja merah akan jatuh di bawah $S_{11}$ saat membandingkan $c$ dan $c''$
• $S_{00}$, dengan elemen $N_{00}$: elemen pasangan berada di cluster yang berbeda di bawah $C$ dan $C'$
  • Sepasang kemeja merah dan celana panjang hitam akan jatuh di bawah $S_{00}$ saat membandingkan $c$ dan $c''$
• $S_{10}$, dengan elemen $N_{10}$: elemen pasangan berada di cluster yang sama di $C$ dan cluster yang berbeda di $C'$
  • Sepasang kemeja merah dan kemeja hitam akan jatuh di bawah $S_{10}$ saat membandingkan $c$ dan $c''$
• $S_{01}$, dengan elemen $N_{01}$: elemen pasangan berada di cluster yang berbeda di $C$ dan cluster yang sama di $C'$
  • $S_{01}$ tidak memiliki elemen ($N_{01} = 0$) saat membandingkan $c$ dan $c''$

Indeks Rand didefinisikan sebagai $(N_{00} + N_{11})/(n(n-1)/2)$, di mana $n$ mewakili jumlah sampel; itu juga dapat dibaca sebagai (jumlah pasangan yang diperlakukan sama)/(jumlah total pasangan). Meskipun secara teoritis nilainya berkisar antara 0 dan 1, kisarannya seringkali jauh lebih sempit dalam praktiknya. Nilai yang lebih tinggi berarti lebih banyak kesamaan antara pengelompokan. (Indeks Rand 1 akan mewakili kecocokan sempurna di mana dua pengelompokan memiliki cluster yang identik.)

Salah satu batasan indeks Rand adalah perilakunya ketika jumlah cluster meningkat mendekati jumlah elemen; dalam hal ini, konvergen menuju 1, menciptakan tantangan dalam mengukur kesamaan pengelompokan secara akurat. Beberapa versi indeks Rand yang ditingkatkan atau dimodifikasi telah diperkenalkan untuk mengatasi masalah ini. Salah satu variasinya adalah indeks Rand yang disesuaikan ; namun, ini mengasumsikan bahwa dua clustering digambar secara acak dengan jumlah cluster dan elemen cluster yang tetap.

Teori Informasi

Metrik ini didasarkan pada gagasan umum teori informasi. Kami akan membahas dua di antaranya: entropi dan mutual information (MI).

Entropi menggambarkan berapa banyak informasi yang ada dalam sebuah clustering. Jika entropi yang terkait dengan pengelompokan adalah 0, maka tidak ada ketidakpastian tentang cluster dari sampel yang diambil secara acak, yang benar ketika hanya ada satu cluster.

MI menjelaskan berapa banyak informasi yang diberikan satu pengelompokan tentang yang lain. MI dapat menunjukkan seberapa banyak mengetahui cluster sampel di $C$ mengurangi ketidakpastian tentang cluster sampel di $C'$.

Informasi timbal balik yang dinormalisasi adalah MI yang dinormalisasi oleh rata-rata geometrik atau aritmatika dari entropi pengelompokan. MI standar tidak terikat oleh nilai konstan, sehingga informasi timbal balik yang dinormalisasi memberikan metrik pengelompokan yang lebih dapat ditafsirkan.

Metrik populer lainnya dalam kategori ini adalah variasi informasi (VI) yang bergantung pada entropi dan MI pengelompokan. Biarkan $H(C)$ menjadi entropi dari sebuah pengelompokan dan $I(C, C')$ menjadi MI antara dua pengelompokan. VI antara dua pengelompokan dapat didefinisikan sebagai $VI(C,C') = H(C)+H(C')-2I(C,C')$. VI dari 0 mewakili kecocokan sempurna antara dua pengelompokan.

Setel Tumpang Tindih

Menetapkan metrik tumpang tindih melibatkan penentuan kecocokan terbaik untuk kluster di $C$ dengan kluster di $C'$ berdasarkan tumpang tindih maksimum antara kluster. Untuk semua metrik dalam kategori ini, 1 berarti pengelompokannya identik.

Ukuran pencocokan maksimum memindai matriks kebingungan dalam urutan menurun dan mencocokkan entri terbesar dari matriks kebingungan terlebih dahulu. Kemudian menghapus cluster yang cocok dan mengulangi proses secara berurutan sampai cluster habis.

Ukuran -F adalah metrik tumpang tindih set lainnya. Berbeda dengan ukuran pencocokan maksimum, ukuran F sering digunakan untuk membandingkan pengelompokan dengan solusi optimal, daripada membandingkan dua pengelompokan.

Menerapkan Metrik Pengelompokan Dengan F-measure

Karena ukuran F umum digunakan dalam model pembelajaran mesin dan aplikasi penting seperti mesin telusur, kami akan menjelajahi ukuran-F lebih detail dengan sebuah contoh.

Definisi ukuran-F

Mari kita asumsikan bahwa $C$ adalah kebenaran dasar, atau solusi optimal kita. Untuk setiap $k$th cluster di $C$, di mana $k \in [1, K]$, kami akan menghitung F-measure individual dengan setiap cluster dalam hasil clustering $C'$. F-measure individual ini menunjukkan seberapa baik cluster $C^\prime_{k'}$ menggambarkan cluster $C_k$ dan dapat ditentukan melalui presisi dan recall (dua metrik evaluasi model) untuk cluster ini. Mari kita definisikan $I_{kk'}$ sebagai perpotongan elemen dalam klaster $k$th $C$ dan klaster $k'$th $C'$, dan $\lvert C_k \rvert$ sebagai angka elemen dalam cluster $k$th.

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

  

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

Kemudian, ukuran-F individual dari kluster $k$th dan $k'$th dapat dihitung sebagai rata-rata harmonik dari presisi dan recall untuk kluster-kluster ini:

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

Sekarang, untuk membandingkan $C$ dan $C'$, mari kita lihat ukuran F secara keseluruhan. Pertama, kita akan membuat matriks yang mirip dengan tabel kontingensi yang nilainya adalah ukuran-F individual dari cluster. Mari kita asumsikan bahwa kita telah memetakan klaster $C$ sebagai baris tabel dan klaster $C'$ sebagai kolom, dengan nilai tabel yang sesuai dengan ukuran-F individual. Identifikasi pasangan cluster dengan ukuran F individu maksimum, dan hapus baris dan kolom yang sesuai dengan cluster ini. Ulangi ini sampai cluster habis. Akhirnya, kita dapat mendefinisikan ukuran-F keseluruhan:

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

Seperti yang Anda lihat, ukuran-F keseluruhan adalah jumlah tertimbang dari ukuran-F individual maksimum kami untuk cluster.

Penyiapan Data dan Hasil yang Diharapkan

Notebook Python apa pun yang cocok untuk pembelajaran mesin, seperti notebook Jupyter, akan berfungsi sebagai lingkungan kita. Sebelum kita mulai, Anda mungkin ingin memeriksa README repositori GitHub saya, file contoh readme_help_example.ipynb yang diperluas, dan file requirements.txt (perpustakaan yang diperlukan).

Kami akan menggunakan data sampel di repositori GitHub, yang terdiri dari artikel berita. Data tersebut disusun dengan informasi yang meliputi category , headline , date , dan short_description :

Kita dapat menggunakan panda untuk membaca, menganalisis, dan memanipulasi data. Kami akan mengurutkan data berdasarkan tanggal dan memilih sampel kecil (10.000 berita utama) untuk demo kami karena kumpulan data lengkapnya besar:

 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())

Saat dijalankan, Anda akan melihat notebook mengeluarkan hasil 30, karena ada 30 kategori dalam sampel data ini. Anda juga dapat menjalankan df.head(4) untuk melihat bagaimana data disimpan. (Ini harus cocok dengan tabel yang ditampilkan di bagian ini.)

Mengoptimalkan Fitur Pengelompokan

Sebelum menerapkan pengelompokan, pertama-tama kita harus melakukan praproses teks untuk mengurangi fitur yang berlebihan dari model kita, termasuk:

• Memperbarui teks agar memiliki kasus yang seragam.
• Menghapus karakter numerik atau khusus.
• Melakukan lemmatisasi.
• Menghapus stopword.

 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)

Judul yang telah processed_input sebelumnya ditampilkan sebagai processing_input , yang dapat Anda amati dengan menjalankan kembali df.head(4) :

Sekarang, kita perlu merepresentasikan setiap judul sebagai vektor numerik untuk dapat menerapkan model pembelajaran mesin apa pun ke dalamnya. Ada berbagai teknik ekstraksi fitur untuk mencapai hal ini; kita akan menggunakan TF-IDF (term frequency-inverse document frequency). Teknik ini mengurangi efek kata-kata yang muncul dengan frekuensi tinggi dalam dokumen (dalam contoh kita, berita utama), karena ini jelas tidak boleh menjadi fitur penentu dalam mengelompokkan atau mengklasifikasikannya.

 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

Selanjutnya, kami akan mencoba metode pengelompokan pertama kami, pengelompokan aglomeratif, pada vektor fitur ini.

Metode Pengelompokan 1: Pengelompokan Agglomerative

Mempertimbangkan kategori berita yang diberikan sebagai solusi optimal, mari kita bandingkan hasil ini dengan hasil pengelompokan aglomeratif (dengan jumlah cluster yang diinginkan sebanyak 30 karena ada 30 kategori dalam kumpulan data):

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

Kami akan mengidentifikasi cluster yang dihasilkan dengan label integer; headline milik cluster yang sama diberi label integer yang sama. Fungsi cluster_measure dari modul compare_clusters dari repositori GitHub kami mengembalikan agregat F-measure dan jumlah cluster yang sangat cocok sehingga kami dapat melihat seberapa akurat hasil clustering kami:

 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)

Saat membandingkan hasil klaster ini dengan solusi optimal, kami mendapatkan ukuran F rendah 0,198 dan klaster 0 yang cocok dengan kelompok kelas yang sebenarnya, yang menggambarkan bahwa klaster aglomerasi tidak selaras dengan kategori utama yang kami pilih. Mari kita periksa sebuah cluster di hasil untuk melihat seperti apa tampilannya.

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

Setelah memeriksa hasilnya, kami melihat bahwa cluster ini berisi berita utama dari semua kategori:

 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

Jadi, ukuran F kami yang rendah masuk akal mengingat cluster hasil kami tidak selaras dengan solusi optimal. Namun, penting untuk diingat bahwa klasifikasi kategori yang diberikan yang kami pilih hanya mencerminkan satu kemungkinan pembagian kumpulan data. Ukuran F yang rendah di sini tidak berarti bahwa hasil pengelompokan salah, tetapi hasil pengelompokan tidak sesuai dengan metode yang kami inginkan untuk mempartisi data.

Metode Pengelompokan 2: K-means

Mari kita coba algoritma pengelompokan populer lainnya pada kumpulan data yang sama: pengelompokan k-means. Kami akan membuat kerangka data baru dan menggunakan fungsi cluster_measure lagi:

 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)

Seperti hasil pengelompokan aglomeratif, hasil pengelompokan k-means kami telah membentuk cluster yang berbeda dengan kategori yang kami berikan: Memiliki ukuran F 0,18 jika dibandingkan dengan solusi optimal. Karena kedua hasil pengelompokan memiliki ukuran F yang serupa, akan menarik untuk membandingkannya satu sama lain. Kami sudah memiliki pengelompokan, jadi kami hanya perlu menghitung ukuran-F. Pertama, kita akan membawa kedua hasil ke dalam satu kolom, dengan class_gt memiliki output pengelompokan aglomeratif, dan class_prd memiliki output pengelompokan 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)

Dengan F-measure yang lebih tinggi dari 0,4, kita dapat mengamati bahwa pengelompokan kedua algoritma lebih mirip satu sama lain daripada solusi optimal.

Temukan Lebih Banyak Tentang Hasil Pengelompokan yang Ditingkatkan

Pemahaman tentang metrik perbandingan pengelompokan yang tersedia akan memperluas analisis model pembelajaran mesin Anda. Kami telah melihat metrik pengelompokan ukuran-F beraksi, dan memberi Anda dasar-dasar yang Anda butuhkan untuk menerapkan pembelajaran ini ke hasil pengelompokan berikutnya. Untuk mempelajari lebih lanjut, berikut adalah pilihan teratas saya untuk bacaan lebih lanjut:

• Membandingkan Clustering - Tinjauan oleh Dorothea Wagner dan Silke Wagner
• Membandingkan pengelompokan—jarak berbasis informasi oleh Marina Meila
• Pengukuran Teoritis Informasi untuk Perbandingan Clustering: Varian, Properti, Normalisasi, dan Koreksi Peluang oleh Nguyen Xuan Vinh, Julien Epps, dan James Bailey

---

Bacaan Lebih Lanjut di Blog Teknik Toptal:

• Ilmu Data Grafik Dengan Python/NetworkX
• Klasifikasi Gambar Semi-diawasi Dengan Data Tidak Berlabel
• Penyematan dalam Pembelajaran Mesin: Membuat Data Kompleks Menjadi Sederhana

Blog Teknik Toptal mengucapkan terima kasih kepada Luis Bronchal untuk meninjau contoh kode yang disajikan dalam artikel ini.