Algoritma Hierarchical Clustering Tentang Pemahaman Pengelompokkan Data Bertingkat
Sebelum mempelajari materi tenatng Algoritma Hierarchical Clustering Tentang Pemahaman Pengelompokkan Data Bertingkat, terlebih dahulu pelajari materi tentang: Algoritma Klastering dan Penggalian Pola dari Kumpulan Data, Metode Elbow dalam Algoritma Klastering untuk Memilih Jumlah Klaster Optimal, dan Memahami Metode Silhouette Score dalam Analisis Klastering.
Konsep Dasar Hierarchical Clustering
Hierarchical clustering adalah teknik pengelompokkan data yang membangun hirarki kelompok. Proses ini dimulai dengan setiap data dianggap sebagai kelompok tunggal dan secara bertahap menggabungkan kelompok-kelompok yang mirip untuk membentuk kelompok yang lebih besar. Hasilnya adalah pohon atau dendrogram yang menggambarkan hubungan hierarkis antar kelompok.Algoritma hierarchical clustering memiliki dua pendekatan utama: agglomerative (penggabungan dari bawah ke atas) dan divisive (pembagian dari atas ke bawah). Dalam agglomerative clustering, setiap data awalnya dianggap sebagai satu kelompok, dan kemudian iteratif menggabungkan dua kelompok terdekat menjadi satu kelompok yang lebih besar. Sementara itu, divisive clustering memulai dengan satu kelompok besar dan membaginya menjadi kelompok yang lebih kecil hingga tiap data menjadi satu kelompok.
Langkah-langkah Algoritma Hierarchical Clustering
- Menghitung Matriks Jarak: Langkah pertama adalah menghitung matriks jarak antar datapoint. Jarak ini bisa diukur menggunakan berbagai metrik, seperti Euclidean, Manhattan, atau metrik lainnya, tergantung pada jenis data yang sedang diolah.
- Inisialisasi Kelompok: Setiap data awalnya dianggap sebagai satu kelompok terpisah.
- Menggabungkan Kelompok Terdekat: Dua kelompok dengan jarak terdekat digabungkan menjadi satu kelompok baru. Proses ini terus berlanjut hingga semua data menjadi satu kelompok.
- Membuat Dendrogram: Proses penggabungan kelompok direpresentasikan dalam bentuk dendrogram. Dendrogram adalah diagram berbentuk pohon yang menunjukkan hierarki pengelompokkan data.
- Menentukan Jumlah Kelompok: Berdasarkan dendrogram, penentuan jumlah kelompok bisa dilakukan dengan memotong dendrogram pada tingkat tertentu.
Kegunaan Hierarchical Clustering
- Biologi: Untuk mengelompokkan spesies berdasarkan karakteristik genetik atau morfologi.
- Ilmu sosial: Dalam analisis perilaku konsumen atau segmentasi pasar.
- Ilmu komputer: Untuk segmentasi citra atau analisis teks.
- Kedokteran: Dalam analisis data medis untuk pengelompokkan pasien berdasarkan gejala atau respons terhadap pengobatan.
Contoh Soal:
| Data Point | ||
|---|---|---|
| A | 2 | 3 |
| B | 3 | 3 |
| C | 3 | 4 |
| D | 5 | 3 |
| E | 8 | 7 |
| F | 7 | 5 |
| G | 9 | 6 |
Langkah 1: Menghitung Matriks Jarak
|
|
A |
B |
C |
D |
E |
F |
G |
|
A |
0,00 |
1,00 |
1,41 |
3,61 |
6,08 |
6,08 |
8,06 |
|
B |
1,00 |
0,00 |
1,00 |
2,83 |
7,07 |
5,10 |
7,07 |
|
C |
1,41 |
1,00 |
0,00 |
2,24 |
6,08 |
4,12 |
6,08 |
|
D |
3,61 |
2,83 |
2,24 |
0,00 |
5,83 |
4,12 |
6,08 |
|
E |
8,06 |
7,07 |
6,08 |
5,83 |
0,00 |
2,24 |
1,41 |
|
F |
6,08 |
5,10 |
4,12 |
4,12 |
2,24 |
0,00 |
2,24 |
|
G |
8,06 |
7,07 |
6,08 |
6,08 |
1,41 |
2,24 |
0,00 |
Langkah 2: Agglomerative Clustering
- A dan B memiliki jarak 1,00.
- C dan D memiliki jarak 2,24.
- E dan F memiliki jarak 2,24.
- B dan C memiliki jarak 1,00.
- E dan G memiliki jarak 1,41.
- A dan C memiliki jarak 1,41.
- B dan F memiliki jarak 5,10.
- A dan B memiliki jarak 1,00.
- C dan F memiliki jarak 4,12.
- D dan G memiliki jarak 6,08.
- B dan E memiliki jarak 7,07.
- C dan G memiliki jarak 6,08.
- D dan F memiliki jarak 4,12.
- A dan C memiliki jarak 1,41.
- E dan G memiliki jarak 1,41.
- B dan C memiliki jarak 1,00.
Langkah 3: Membuat Dendrogram
 |
| Gambar 1: Dendogram |
Langkah 4: Terakhir, Menentukan Jumlah Kelompok atau Klaster
Program Aplikasi
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_POINTS 100
typedef struct {
double x;
double y;
} Point;
typedef struct {
int cluster_id;
Point point;
} ClusterPoint;
double euclideanDistance(Point p1, Point p2)
{
return
sqrt(pow((p2.x - p1.x), 2)
+
pow((p2.y - p1.y), 2));
}
void
hierarchicalClustering(ClusterPoint* points,
int num_points,
int num_clusters)
{
double
distances[MAX_POINTS][MAX_POINTS]
= {{0}};
int merged[MAX_POINTS] = {0};
for (int i = 0;
i < num_points;
++i)
{
for (int j = i + 1;
j < num_points;
++j)
{
distances[i][j] =
euclideanDistance(points[i].point,
points[j].point);
distances[j][i] =
distances[i][j];
}
}
int num_remaining_clusters =
num_points;
int cluster_id = num_points;
while (num_remaining_clusters > num_clusters)
{
double min_distance =
INFINITY;
int min_i = -1, min_j = -1;
for (int i = 0;
i < num_points;
++i)
{
if (merged[i]) continue;
for (int j = i + 1;
j < num_points;
++j)
{
if (merged[j]) continue;
if (distances[i][j] < min_distance)
{
min_distance =
distances[i][j];
min_i = i;
min_j = j;
}
}
}
if (min_i != -1 && min_j != -1)
{
for (int k = 0;
k < num_points;
++k)
{
if (k != min_i && k != min_j && !merged[k])
{
distances[min_i][k] =
fmin(distances[min_i][k],
distances[min_j][k]);
distances[k][min_i] =
distances[min_i][k];
}
}
merged[min_j] = 1;
points[min_i].point.x =
(points[min_i].point.x
+ points[min_j].point.x)
/ 2.0;
points[min_i].point.y =
(points[min_i].point.y
+ points[min_j].point.y)
/ 2.0;
points[min_j].cluster_id =
cluster_id++;
num_remaining_clusters--;
}
}
printf("Clusters:\n");
for (int i = 0; i < num_points; ++i)
{
if (!merged[i]) {
printf("Cluster %d: (%.2f, %.2f)\n",
points[i].cluster_id,
points[i].point.x,
points[i].point.y);
}
}
}
int main() {
Point data_points[] = {
{2, 3},
{3, 3},
{3, 4},
{5, 3},
{8, 7},
{7, 5},
{9, 6}
};
int num_points =
sizeof(data_points)
/
sizeof(data_points[0]);
ClusterPoint* cluster_points =
(ClusterPoint*)malloc(num_points * sizeof(ClusterPoint));
for (int i = 0;
i < num_points;
++i)
{
cluster_points[i].cluster_id =
i;
cluster_points[i].point =
data_points[i];
}
int num_clusters = 2;
// Ganti sesuai dengan jumlah
// cluster yang diinginkan
hierarchicalClustering(cluster_points,
num_points,
num_clusters);
free(cluster_points);
return 0;
}
Kelebihan Algoritma Hierarchical Clustering dalam Analisis Data
Hierarki Kelompok yang Jelas
Tidak Memerlukan Jumlah Kelompok yang Ditetapkan Secara Awal
Tidak Rentan terhadap Outlier
Representasi Hierarki dalam Data Multidimensi
Interpretasi yang Mudah
Kesimpulan
10 komentar untuk "Algoritma Hierarchical Clustering Tentang Pemahaman Pengelompokkan Data Bertingkat"
Hubungi admin melalui Wa : +62-896-2414-6106
Respon komentar 7 x 24 jam, mohon bersabar jika komentar tidak langsung dipublikasi atau mendapatkan balasan secara langsung.
Bantu admin meningkatkan kualitas blog dengan melaporkan berbagai permasalahan seperti typo, link bermasalah, dan lain sebagainya melalui kolom komentar.
- Ikatlah Ilmu dengan Memostingkannya -
- Big things start from small things -
Apa itu algoritma hierarchical clustering?
BalasHapusAlgoritma hierarchical clustering merupakan metode pengelompokkan data di mana datapoint dikelompokkan secara bertingkat atau hierarkis berdasarkan kedekatan atau kesamaan karakteristiknya. Algoritma ini membangun struktur hierarkis dalam bentuk dendrogram yang menggambarkan hubungan antar kelompok data.
HapusApa perbedaan antara pendekatan agglomerative dan divisive dalam algoritma hierarchical clustering?
BalasHapusPendekatan agglomerative dimulai dengan setiap data dianggap sebagai satu kelompok dan secara bertahap menggabungkan kelompok-kelompok terdekat menjadi kelompok yang lebih besar. Sedangkan pendekatan divisive memulai dengan satu kelompok besar dan membaginya menjadi kelompok yang lebih kecil hingga tiap data menjadi satu kelompok.
HapusBagaimana langkah-langkah umum dalam algoritma hierarchical clustering?
BalasHapusLangkah-langkah umum dalam algoritma hierarchical clustering meliputi:
Hapus1. Menghitung matriks jarak antara semua pasang datapoint.
2. Inisialisasi setiap data sebagai satu kelompok terpisah.
3. Menggabungkan kelompok terdekat secara berulang hingga semua data menjadi satu kelompok.
4. Membuat dendrogram yang merepresentasikan struktur hierarkis dari proses penggabungan kelompok.
Bagaimana cara menentukan jumlah kelompok pada algoritma hierarchical clustering?
BalasHapusJumlah kelompok dapat ditentukan dengan memotong dendrogram pada tingkat tertentu. Pemotongan ini dapat dilakukan dengan memperhatikan tingkat percabangan pada dendrogram dan memilih jumlah kelompok yang diinginkan sesuai dengan interpretasi data.
HapusApa kelebihan utama dari algoritma hierarchical clustering?
BalasHapusSalah satu kelebihan utama algoritma hierarchical clustering adalah kemampuannya dalam menampilkan struktur hierarkis dari data tanpa memerlukan jumlah kelompok yang harus ditentukan sebelumnya. Algoritma ini juga memberikan representasi visual yang jelas tentang hubungan antar kelompok melalui dendrogram.
Hapus