UPGMA

Pada post kali ini kita akan mengimplementasi algoritma UPGMA atau Unweighted Pair Group Method with Arithmetic Mean untuk melakukan clustering.

Algoritma
UPGMA bekerja dengan prinsip yang sederhana. Pada setiap iterasi, pilih pasangan point dengan point, atau point dengan cluster, atau cluster dengan cluster, yang memiliki jarak yang terpendek. Gabung kedua pasangan ini kedalam satu cluster. Hal ini dilakukan terus menerus hingga jumlah cluster berkurang menjadi jumlah yang diinginkan. Untuk menghitung jarak antar datapoint, kita bisa menggunakan berbagai kriteria jarak. Pada implementasi ini, kita menggunakan euclidean distance untuk menghitung jarak. Sedangkan untuk menghitung jarak antar cluster, kita hitung dengan cara merata-ratakan jarak antar semua pasang point dari cluster pertama ke cluster kedua, atau dengan kata lain:

\frac{1}{|A|.|B|} \sum_{x \in A} \sum_{y \in B} d(x,y)

Teknik UPGMA ini bisa digolongkan kepada teknik hierarchical clustering karena kita bisa melihat hirarki sebuah cluster yang dibentuk dari cluster-cluster lain yang lebih kecil.

Implementasi
Kita implementasikan UPGMA dalam bahasa Python. Pertama, kita butuh struktur data untuk menyimpan point yang terdapat pada sebuah cluster.

class Node:
    def __init__(self, p):
        self.points = p
        self.right = None
        self.left = None

Fungsi UPGMA menerima dua parameter. Parameter pertama adalah set yang berisi datapoints sebanyak n dengan masing-masing point memiliki dimensi d. Parameter kedua adalah jumlah cluster yang kita inginkan.

def upgma(points, k):
    """ Cluster based on distance matrix dist using Unweighted Pair Group Method with Arithmetic Mean algorithm up to k cluster"""

    # Initialize each cluster with one point
    nodes = []
    n = len(points)
    for i in xrange(n):
        node = Node([points[i]])
        nodes = nodes + [node]

    # Iterate until the number of clusters is k
    nc = n
    while nc > k:
        # Calculate the pairwise distance of each cluster, while searching for pair with least distance
        c1 = 0; c2 = 0; i1 = 0; i2 = 0;
        sdis = 9999999999
        for i in xrange(nc):
            for j in xrange(i+1, nc):
                dis = euclidistance(nodes[i], nodes[j])
                if dis < sdis:
                    sdis = dis
                    c1 = nodes[i]; c2 = nodes[j];
                    i1 = i; i2 = j;
        # Merge these two nodes into one new node
        node = Node(c1.points + c2.points)
        node.left = c1; node.right = c2;
        
        #Remove the previous nodes, and add the new node
        new_nodes = []
        for i in xrange(nc):
            if i != i1 and i != i2:
                new_nodes = new_nodes + [nodes[i]]
        new_nodes = new_nodes + [node]
        nodes = new_nodes[:]
        nc = nc - 1

    return nodes

Kemudian terakhir, kita definisikan fungsi jarak yang kita pakai. Selain jarak euclidean, kita bisa yang digunakan kriteria jarak lainnya seperti Manhattan distance atau Chebyshev distance.

import math

def euclidistance(c1, c2):
    """ Calculate the distance between two cluster """
    dist = .0
    n1 = len(c1.points)
    n2 = len(c2.points)
    for i in xrange(n1):
        for j in xrange(n2):
            p1 = c1.points[i]
            p2 = c2.points[j]
            dim = len(p1)
            d = 0
            for k in xrange(dim):
                d = d + (p1[k]-p2[k])**2
            d = math.sqrt(d)
            dist = dist + d
    dist = dist / (n1*n2)
    return dist

Contoh
Untuk contoh pertama kita pakai dataset sintesis yang dihasilkan oleh dua buah distribusi normal multidimensi.

import upgma
import random
import matplotlib.pyplot as plt
import math

# Example 1
datapoints = [(random.normalvariate(2.5, 1.0), random.normalvariate(1.5,1.0)) for i in xrange(100)] + \
				[(random.normalvariate(-1, 0.5), random.normalvariate(3,0.5)) for i in xrange(100)]

# Plot datapoints before clustering
plt.plot([x for (x,y) in datapoints], [y for (x,y) in datapoints], 'k^')
plt.show()

# Cluster the data
nodes = upgma.upgma(datapoints, 2)
plt.plot([x[0] for x in nodes[0].points], [x[1] for x in nodes[0].points], 'b*')
plt.plot([x[0] for x in nodes[1].points], [x[1] for x in nodes[1].points], 'ro')
plt.show()

dan berikut keluaran hasil clustering jika kita pilih 2 sebagai jumlah cluster.
nocluster1cluster1

Contoh kedua kita ambil dataset old faithful geyser (http://www.stat.cmu.edu/~larry/all-of-statistics/=data/faithful.dat).

f = open('faithful.dat.txt', 'r')
lines = f.readlines()
f.close()

datapoints = []
for line in lines:
	tokens = line.split()
	datapoints += [(float(tokens[1]), float(tokens[2]))]

Karena fitur kedua berbeda skalanya dengan fitur pertama (puluhan berbanding dengan satuan), kita lakukan normalisasi z-score pada tiap masing-masing fitur dengan cara mengurangi dengan mean distribusi dan kemudian dibagi dengan standar deviasi.

avg1 = sum([x for (x,y) in datapoints])
avg2 = sum([y for (x,y) in datapoints])
centered_datapoints = map(lambda (x,y): (x-avg1, y-avg2), datapoints)
std1 = math.sqrt(sum(map(lambda x: x*x, [x for (x,y) in centered_datapoints])))
std2 = math.sqrt(sum(map(lambda x: x*x, [y for (x,y) in centered_datapoints])))
normalized_datapoints = map(lambda (x,y): (x/std1, y/std2), centered_datapoints)

Hasil clustering-nya adalah sebagai berikut.

# Before clustering
plt.plot([x for (x,y) in normalized_datapoints], [y for (x,y) in normalized_datapoints], 'k^')
plt.show()

# Cluster the data
nodes = upgma.upgma(normalized_datapoints, 2)
plt.plot([x[0] for x in nodes[0].points], [x[1] for x in nodes[0].points], 'b*')
plt.plot([x[0] for x in nodes[1].points], [x[1] for x in nodes[1].points], 'ro')
plt.show()

nocluster2cluster2

Kode lengkap dapat dilihat di: https://github.com/mitbal/py-upgma

Semoga berguna. Salam.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s