Manajemen Data

DECISION SUPPORT SYSTEM [D10K-5B01]

Sub Capaian Pembelajaran MK

We Are Here!!! 
AGENDA

1. Pendahuluan Subsistem Manajemen Data

2. Model Data Mining
3. Klasifikasi
4. Clustering
Clustering
What is Cluster Analysis?

• Cluster: A collection of data objects

• similar (or related) to one another within the same group
• dissimilar (or unrelated) to the objects in other groups
• Cluster analysis (or clustering, data segmentation, …)
• Finding similarities between data according to the characteristics found in
the data and grouping similar data objects into clusters
• Unsupervised learning: no predefined classes (i.e., learning
by observations vs. learning by examples: supervised)
• Typical applications
• As a stand-alone tool to get insight into data distribution
• As a preprocessing step for other algorithms

5
Quality: What Is Good Clustering?

• A good clustering method will produce high quality clusters

• high intra-class similarity: cohesive within clusters
• low inter-class similarity: distinctive between clusters

• The quality of a clustering method depends on

• the similarity measure used by the method
• its implementation, and
• Its ability to discover some or all of the hidden patterns

6
 Major Clustering Approaches 1
• Partitioning approach:
• Construct various partitions and then evaluate them by some criterion, e.g.,
minimizing the sum of square errors
• Typical methods: k-means, k-medoids, CLARANS
• Hierarchical approach:
• Create a hierarchical decomposition of the set of data (or objects) using
some criterion
• Typical methods: Diana, Agnes, BIRCH, CAMELEON
• Density-based approach:
• Based on connectivity and density functions
• Typical methods: DBSACN, OPTICS, DenClue
• Grid-based approach:
• based on a multiple-level granularity structure
• Typical methods: STING, WaveCluster, CLIQUE

7
Major Clustering Approaches 2

• Model-based:
• A model is hypothesized for each of the clusters and tries to find the best fit
of that model to each other
• Typical methods: EM, SOM, COBWEB
• Frequent pattern-based:
• Based on the analysis of frequent patterns
• Typical methods: p-Cluster
• User-guided or constraint-based:
• Clustering by considering user-specified or application-specific constraints
• Typical methods: COD (obstacles), constrained clustering
• Link-based clustering:
• Objects are often linked together in various ways
• Massive links can be used to cluster objects: SimRank, LinkClus

8
Partitioning Methods

9
Partitioning Algorithms: Basic Concept

• Partitioning method: Partitioning a database D of n objects

into a set of k clusters, such that the sum of squared
distances is minimized (where ci is the centroid or medoid of
cluster Ci)
E  ik1 pCi (d ( p, ci )) 2

• Given k, find a partition of k clusters that optimizes the

chosen partitioning criterion
• Global optimal: exhaustively enumerate all partitions
• Heuristic methods: k-means and k-medoids algorithms
• k-means (MacQueen’67, Lloyd’57/’82): Each cluster is represented by the
center of the cluster
• k-medoids or PAM (Partition around medoids) (Kaufman &
Rousseeuw’87): Each cluster is represented by one of the objects in the
cluster 10
 An Example of K-Means Clustering

K=2

Arbitrarily Update the

partition cluster
objects into centroids
k groups

The initial data set Loop if Reassign objects

needed
 Partition objects into k
nonempty subsets
 Repeat
 Compute centroid (i.e., mean
point) for each partition Update the
 Assign each object to the cluster
cluster of its nearest centroid centroids

 Until no change

11
 Tahapan Algoritma k-Means
1. Pilih jumlah klaster k yang diinginkan
2. Inisialisasi k pusat klaster (centroid) secara random
3. Tempatkan setiap data atau objek ke klaster terdekat. Kedekatan dua objek
ditentukan berdasar jarak. Jarak yang dipakai pada algoritma k-Means adalah
Euclidean distance (d)
n
d Euclideanx, y   
 i i  2
x y
i 1

• x = x1, x2, . . . , xn, dan y = y1, y2, . . . , yn merupakan banyaknya

n atribut(kolom) antara 2 record
4. Hitung kembali pusat klaster dengan keanggotaan klaster yang sekarang.
Pusat klaster adalah rata-rata (mean) dari semua data atau objek dalam
klaster tertentu
5. Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Jika pusat
klaster sudah tidak berubah lagi, maka proses pengklasteran selesai. Atau,
kembali lagi ke langkah nomor 3 sampai pusat klaster tidak berubah lagi
(stabil) atau tidak ada penurunan yang signifikan dari nilai SSE (Sum of
Squared Errors)
12
Contoh Kasus – Iterasi 1
1. Tentukan jumlah klaster k=2
2. Tentukan centroid awal secara acak
misal dari data disamping m1 =(1,1),
m2=(2,1)
3. Tempatkan tiap objek ke klaster
terdekat berdasarkan nilai centroid
yang paling dekat selisihnya
(jaraknya). Didapatkan hasil, anggota
cluster1 = {A,E,G}, cluster2={B,C,D,F,H}
Nilai SSE yaitu:
k 2

SSE    d  p, mi 
i 1 pCi

13
 Interasi 2

4. Menghitung nilai centroid yang baru

m1  1  1  1 / 3, 3  2  1 / 3  1,2

m2  3  4  5  4  2 / 5, 3  3  3  2  1 / 5  3,6;2,4

5. Tugaskan lagi setiap objek dengan

memakai pusat klaster yang baru.
Nilai SSE yang baru:

14
Iterasi 3
4. Terdapat perubahan anggota
cluster yaitu cluster1={A,E,G,H},
cluster2={B,C,D,F}, maka cari lagi
nilai centroid yang baru yaitu:
m1=(1,25;1,75) dan m2=(4;2,75)
5. Tugaskan lagi setiap objek
dengan memakai pusat klaster
yang baru
Nilai SSE yang baru:

15
Hasil Akhir
• Dapat dilihat pada tabel.
Tidak ada perubahan anggota
lagi pada masing-masing
cluster
• Hasil akhir yaitu:
cluster1={A,E,G,H}, dan
cluster2={B,C,D,F}
Dengan nilai SSE = 6,25 dan
jumlah iterasi 3

16
Density-Based Methods

17
Density-Based Clustering Methods

• Pengelompokan berdasarkan kepadatan (kriteria cluster lokal),

seperti titik yang terhubung dengan kepadatan
• Fitur utama:
• Temukan kelompok dengan bentuk yang berubah-ubah
• Dapat menangani noise
• Satu pemindaian
• Perlu parameter kepadatan sebagai kondisi terminasi
• Several interesting studies:
• DBSCAN: Ester, et al. (KDD’96)
• OPTICS: Ankerst, et al (SIGMOD’99).
• DENCLUE: Hinneburg & D. Keim (KDD’98)
• CLIQUE: Agrawal, et al. (SIGMOD’98) (more grid-based)

18
Density-Based Clustering: Basic Concepts

• Dua parameter:
• Eps: Radius maksimum lingkungan
• MinPts: Jumlah minimum poin di lingkungan Eps dari titik itu

• NEps(q): {p belongs to D | dist(p,q) ≤ Eps}

• Directly density-reachable: Sebuah titik p secara langsung
dapat dicapai dengan kerapatan dari titik q w.r.t. Eps, MinPts
jika
• p belongs to NEps(q)
• core point condition: p MinPts = 5
|NEps (q)| ≥ MinPts Eps = 1 cm
q
19
Density-Reachable and Density-Connected

• Density-reachable: p
• Titik p dapat dicapai dengan kerapatan dari titik q p1
jika ada rantai titik p1, …, pn, p1 = q, pn = p q
sedemikian rupa sehingga pi+1 dapat dicapai
langsung oleh kerapatan dari pi

• Density-connected
• Sebuah titik p terhubung dengan kepadatan ke titik
q jika ada titik o sehingga keduanya, p dan q dapat
dicapai kerapatan dari o p q

20
DBSCAN: Density-Based Spatial Clustering of
Applications with Noise
• Menggunakan ide pembentukan cluster berbasis kepadatan:
cluster didefinisikan sebagai kumpulan maksimal titik yang
terhubung dengan kepadatan
• Menemukan cluster dengan berbagai bentuk dalam
database spasial dengan adanya noise

Outlier

Border
Eps = 1cm
Core MinPts = 5

21
 DBSCAN: The Algorithm
1. Pilih sembarang titik p
2. Ambil semua titik yang density-reachable dari p
3. Jika p adalah titik inti, maka terbentuk cluster
4. Jika p adalah titik batas, tidak ada titik yang density-
reachable oleh i p dan DBSCAN mengunjungi titik
database berikutnya
5. Lanjutkan proses hingga semua poin selesai diproses

Jika indeks spasial digunakan, kompleksitas komputasi DBSCAN adalah O (nlogn),

di mana n adalah jumlah objek database. Jika tidak, kompleksitasnya adalah O (n2)

22
DBSCAN: Sensitive to Parameters

http://webdocs.cs.ualberta.ca/~yaling/Cluster/Applet/Code/Cluster.html
23
Soal DBSCAN

Dengan parameter input

a. MinPts : 5
b. Eps : 4

24
Iterasi 1

• Misal titik B sebagai pusat

• Hit jarak masing masing titik terhadap titik pusat B (mis. Dengan
Euclidean Distance)

NB:
Dilakukan hal yang sama untuk
titik yang lain

25
Pengambilan titik yang density reachable

• Ambil semua point yang density reachable terhadap titik

pusatnya. Karena Eps=4 maka nilai titik yang memenuhi
syarat adalah
Dari jumlah titik yang terpilih tersebut
yaitu berjumlah 6. Jumlah ini sudah
memenuhi untuk terbentuknya
neighborhood core object karena jumlah
objek e- neighborhood sudah memenuhi
jumlah MinPts=5

26
Hasil iterasi 1

27
Iterasi 2

• Pilih titik yang memiliki jarak terjauh yang masih termasuk dalam dari
core object pada iterasi pertama.

28
Iterasi 2 (lanjutan)
1. hitung jarak masing-masing titik dengan core point untuk iterasi
kedua,
2. Ambil semua point yang density
reachable terhadap titik pusatnya.

Dari jumlah titik yang terpilih adalah 10. Jumlah ini sudah
memenuhi untuk terbentuknya neighborhood core object
29
Hasil Akhir

30
Note

Contoh soal dan penyelesaian K-means clustering dan DBSCAN

disediakan di regular.live.unpad.ac.id