11 Possibilistic C-Means Clustering
Algoritma Possibilistic C-Means (PCM), yang diperkenalkan oleh Krishnapuram dan Keller pada tahun 1993, dirancang untuk mengatasi kelemahan Fuzzy C-Means (FCM) dalam menghadapi noise. PCM menghasilkan pengelompokan data yang bersifat possibilistik, di mana nilai keanggotaan mencerminkan derajat kemungkinan bahwa suatu titik data termasuk dalam kluster tertentu, yaitu sejauh mana titik tersebut sesuai dengan prototipe kluster. Tidak seperti FCM, PCM tidak memberlakukan batasan probabilistik pada jumlah keanggotaan suatu objek terhadap seluruh kluster. Namun, parameter (Ω) dalam PCM dihitung berdasarkan hasil pengelompokan fuzzy yang diperoleh dari FCM. Meskipun PCM lebih tahan terhadap noise dibandingkan FCM, algoritma ini sangat bergantung pada inisialisasi awal dan rentan terhadap penurunan kinerja akibat masalah pengelompokan simultan.
Fungsi objektif pada algoritma Possibilistic C-Means (PCM) dirumuskan sebagai berikut:
\[ J_{PCM} = \sum_{i=1}^n \sum_{j=1}^c u_{ij}^m \|x_i - v_j\|^2 + \sum_{j=1}^c \eta_j \sum_{i=1}^n (1 - u_{ij})^m \]
Dengan keterangan:
- \(n\): Jumlah data.
- \(c\): Jumlah klaster.
- \(x_i\): Titik data ke-\(i\).
- \(v_j\): Prototipe (centroid) dari klaster ke-\(j\).
- \(u_{ij}\): Derajat keanggotaan \(x_i\) terhadap klaster \(j\).
- \(m\): Parameter fuzzy (\(m > 1\)).
- \(\eta_j\): Parameter skala untuk klaster \(j\), yang mengontrol pengaruh keanggotaan possibilistik.
Bagian pertama dari fungsi objektif meminimalkan jarak antara titik data dan pusat klaster, dengan mempertimbangkan derajat keanggotaan. Bagian kedua mendorong nilai keanggotaan possibilistik dengan memberikan penalti pada derajat keanggotaan yang rendah, sehingga mengurangi sensitivitas terhadap noise.
Pada fungsi objektif PCM yang telah dijelaskan sebelumnya, komponen pertama bertujuan meminimalkan jarak berbobot antara data dan pusat klaster, sementara komponen kedua mencegah solusi trivial (Timm et al., 2004).
Krishnapuram dan Keller kemudian mengusulkan fungsi objektif alternatif untuk PCM (Krishnapuram & Keller, 1996), yang dirumuskan sebagai berikut:
\[ J_{PCM_2}(\mathbf{X}; \mathbf{V}, \mathbf{T}) = \sum\limits_{i=1}^n t_{ij}^\eta \; d^2(\vec{x}_i, \vec{v}_j) + \sum\limits_{j=1}^k \Omega_j \sum\limits_{i=1}^n \big(t_{ij}^\eta \; \log{t_{ij}^\eta} - t_{ij}^\eta \big) \]
Dengan definisi:
\[ \vec{\Omega}_j = K \frac{\sum\limits_{i=1}^n u_{ij}^m \; d^2(\vec{x}_i, \vec{v}_j)}{\sum\limits_{i=1}^n u_{ij}^m} \]
Keanggotaan dalam PCM bersifat possibilistik, sehingga derajat keanggotaan dapat dianggap sebagai nilai tipikalitas yang merepresentasikan seberapa khas suatu objek data terhadap klaster tertentu, tanpa memperhatikan klaster lainnya. Persamaan pembaruan derajat tipikalitas serupa dengan yang digunakan dalam FCM dan diturunkan dari fungsi objektif PCM, yaitu:
\[ t_{ij} = \Bigg[ 1 + \Big(\frac{d^2(\vec{x}_i, \vec{v}_j)}{\Omega_j}\Big)^{1/(m-1)} \Bigg]^{-1} \;\;; \; 1 \leq i \leq n,\; 1 \leq j \leq k \]
Sedangkan, persamaan pembaruan prototipe klaster tetap sama seperti pada FCM:
\[ \vec{v}_j = \frac{\sum\limits_{i=1}^n t_{ij}^m \vec{x}_i}{\sum\limits_{i=1}^n t_{ij}^m} \;\;; \; 1 \leq j \leq k \]