Thuật toán phân cụm K-Means*

Cao Ngpc Anh vd Dig Tap chi KHOA HOC & CONG NGHE 169(09). 159-164

THUAT TOAN PHAN CVM K-MEANS*

Cao Ngpc AnhS Vu Viet VfiS Phiing Thi Thu Hien^

^Trudng Dgi hpc Kmh ti - Kp thudt Cong nghiep

^Viin Cong nghe Thdng tin - Dgi hpc Quoc gia Hd npi

^Trudng Dgi hoc Ky thugt Cong nghifp - Dgi hpc Thdi Nguyen

TOM TAT

Thuat toan phan cum niia giam sat thu hiit duoc nhieu nghi6n ciru trong thdi gian gan day, Dua

tren mgt so thong tin cung cap bdi ngudi sd dyng nhu mdt sd diem dfl lieu da duac gan nhSn sSn

hogc mpt so rang budc gitta cac cap dit lieu (must-link, cannot-link) duoc tich hop vao cac thuat

toan phan cum nua giam sat sS lam cho chat luong ciia qua trinh phan cum dupc cai tien Bai bao

nay de xuat mot phuong phap phan cum niia giam sat trong tnrdng hop dff lieu tro gnip la khdng

diy dli cho tiiufit toan phan cym K-Means, thu^t toan mdi duoc djt ten la K-Means*, Thugt toan

K-Means* dugc lai gitta hai phuong phap gdm phucmg phap phan cum niia giam sat va phuang

phdp udc lucmg cdc trpng tam ciia cac cum cho K-Means, Ket qua thuc nghigm tir UCl chi ra hieu

qua ciia phuong phap de xuat.

Tir khoa: thugt todn phdn cum K-Means, phdn cum nua gidm sdt. du hiu gdn nhdn, phuang phdp

min-max, du lieu UCI

GIOITHIEU

Phan cum dir lieu (clustering) la mpt trong

nhung van de ca ban cua ITnh vyc hpc may va

khai pha du lieu. Bai toan phan cym nham

phan tach mpt tgp dii lieu gom n phan tu

thanh k cum sao cho cac phan tu trong moi

cym la tuang tu nhau va cac phan tii nam

khac cym thi se khdng tuong tu nhau theo

mot nghia nao dd. Phan cym dir lieu thuoc Idp

bai toan hoc khdng giam sat khac logi vdi cac

thuat toan hpc cd giam sat chang han nhu

mgng Naron hay phuang phap Support

Vector Machine [14]. Ket qua ciia qua trinh

phan cym se cho chung ta biet cau tnic an

chira ben trong cua toan bo tgp dir lipu va moi

lien hp giiia cac phan tu trong dir lieu. Pha

phan cym cd the ddng vai trd lam cdng dogn

chinh trong mpt irng dyng chSng hgn nhu

phan cym ngudi dung website, phan cym cac

trang thai cam xuc khudn mgt,,., hoac trong

cdng dogn tien xir ly dir lieu nhu phan dogn

anh, lara sgch dir lipu.

Bai toan phan cym da dugc nghien cuu va de

xuat tir each day hem nua the ky [14]: Thugt

toan K-Means 1957, thugt toan phan cum kieu

phan tang nam 1967, thugt toan phan cym dya

Email-pthientng@gmail.com

tren do thi nam 1973, thuat toan phan cym md

I98I, thugt toan phan cym dya tren md hinh

mat do (DBSCAN) nam 1996 [6]. Vdi raoi

logi thugt toan da de xuat ludn ton tai nhung

uu diem va nhuac diem rieng Vdi K-Means

dd la ket qua phan cym phy thupe vao cac

diem trong tara khdi tao ban dau, vdi thuat

toan DBSCAN va phuong phap phan cum thii

bac la do phuc tap cua thuat toan cao, doi vdi

phuang phap sir dyng dd thi la khd xac dinh

tham so,., Trong so nhirng thuat toan ca ban

neu tren, thugt toan K-Means la thugt toan

dupc su dyng nhieu nhat [12],

Mpt trong nhirng nghien ciiu thu hut cac nha

nghien ciiu trong nhiing nam gan day la

hudng nghien ciiu ve thugt toan phan cym

nua giam sat [1], [2], [3], [4], [8], [10], [II],

[13], Xuat phat tii nhiing thugt toan ca ban ke

tren, gia thiet ring chiing ta cd them mpt so

thdng tin chang han nhu cd mot so rang budc

giiia cac phan hi trong tap dir lipu hay da cd

trudc mpt so phan tir dupc gan nhgn sin xac

dinh chung d cum nao Y tudng ca ban la

phat trien cac thuat toan cd the tich hpp cac

thdng tin bo trg nham tang chat Iuang cua qua

trinh phan cym. Hang logt cac cong trinh

nghien ciiu da duac cdng bo nhu da nhac den

d tren.

159