Clustering : K-Means

ปรับปรุง : 2561-07-04 (clustering)

Clustering : K-Means

K-Means เป็นวิธีที่นิยมใช้ในการแบ่งกลุ่มข้อมูล โดยเปรียบเทียบความคล้ายคลึงของข้อมูล กับจุดศูนย์กลางของแต่ละคลัสเตอร์ (Cluster) หรือค่าเฉลี่ย (Mean) เป็นการแบ่งแบบ Partitional clustering ด้วยการแบ่งข้อมูลออกเป็นส่วน ตามจำนวนกลุ่มที่ระบุ มี 4 ขั้นตอน #
1. mark - กำหนดจำนวนกลุ่ม K กลุ่ม และกำหนดจุดศูนย์กลางเริ่มต้นจำนวน K จุด ด้วยการสุ่ม
2. distance - นำวัตถุทั้งหมดจัดเข้ากลุ่มที่มีจุดศูนย์กลางที่อยู่ใกล้วัตถุนั้นมากที่สุด โดยคำนวณจากการวัดระยะห่างระหว่างจุดที่น้อยที่สุด
3. center - คำนวณจุดศูนย์กลาง K จุดใหม่ โดยหาจากค่าเฉลี่ยทุกวัตถุที่อยู่ในกลุ่ม
4. repeat - ทำซ้ำในข้อ 2. จนกระทั่งจุดศูนย์กลางไม่เปลี่ยนแปลง
เทคนิคการแบ่งกลุ่มข้อมูล (Clustering) ด้วยวิธี K-Means หาอ่านได้จากหนังสือ An Introduction to Data Mining Techniques โดย Ph.D. Eakasit Pacharawongsakda

K-Mean โดย ดร.เอกสิทธิ์ พัชรวงศ์ศักดา

ลำดับที่	รหัสลูกค้า	จำนวนส่ง SMS(ครั้ง)	จำนวนใช้โทรศัพท์(ครั้ง)
1	101	27	144
2	102	32	44
3	103	41	30
4	104	125	21
5	105	105	23
6	106	20	121

ขั้นตอนทั้ง 4 ตาม K-Means มีดังนี้
1. แบ่งข้อมูล 6 รายการเป็น 3 กลุ่ม กำหนดให้ข้อมูลลำดับ 1, 3, 5 เป็นศูนย์กลางของคลัสเตอร์
2. คำนวณระยะห่างระหว่างข้อมูลด้วย การวัดระยะห่าง Euclidean
Distance = รากที่สอง [(x1 - y1)^2 + (x2 - y2)^2 + .. + (x.. - y..)^2]
D(2,1) = รากที่สอง[ (32-27)^2 + (44-144)^2 ] = 100.12
D(4,1) = รากที่สอง[ (125-27)^2 + (21-144)^2 ] = 157.27
D(6,1) = รากที่สอง[ (20-27)^2 + (121-144)^2 ] = 24.04
D(2,3) = รากที่สอง[ (32-41)^2 + (44-30)^2 ] = 16.64
D(4,3) = รากที่สอง[ (125-41)^2 + (21-30)^2 ] = 84.48
D(6,3) = รากที่สอง[ (20-41)^2 + (121-30)^2 ] = 93.39
D(2,5) = รากที่สอง[ (32-105)^2 + (44-23)^2 ] = 75.96
D(4,5) = รากที่สอง[ (125-105)^2 + (21-23)^2 ] = 20.10
D(6,5) = รากที่สอง[ (20-105)^2 + (121-23)^2 ] = 129.73
คลัสเตอร์แรก พบว่าระยะห่าง 6 กับ 1 น้อยที่สุด คือ 24.04
คลัสเตอร์สอง พบว่าระยะห่าง 2 กับ 3 น้อยที่สุด คือ 16.64
คลัสเตอร์สาม พบว่าระยะห่าง 4 กับ 5 น้อยที่สุด คือ 20.10
3. จุดกึ่งกลางของแต่ละคลัสเตอร์
คลัสเตอร์แรก (C1) พบว่าระยะห่าง 6 กับ 1
- SMS = (27 + 20) / 2 = 23.5
- Call = (144 + 121) / 2 = 132.5
คลัสเตอร์สอง (C2) พบว่าระยะห่าง 2 กับ 3
- SMS = ( 32 + 41 ) / 2 = 36.5
- Call = ( 44 + 30 ) / 2 = 37
คลัสเตอร์สาม (C3) พบว่าระยะห่าง 4 กับ 5
- SMS = ( 125 + 105 ) / 2 = 115
- Call = ( 21 + 23 ) / 2 = 22

K-Mean ขั้นตอนที่ 4
4. ทำซ้ำข้อ 2 คำนวณระยะห่าง นำทุกจุดไปหาระยะห่างจากคลัสเตอร์ที่ได้
D(1,C1) = รากที่สอง[ (27-23.5)^2 + (144-132.5)^2 ] = 12.02
D(2,C1) = รากที่สอง[ (32-23.5)^2 + (44-132.5)^2 ] = 88.91
D(3,C1) = รากที่สอง[ (41-23.5)^2 + (30-132.5)^2 ] = 103.98*
D(4,C1) = รากที่สอง[ (125-23.5)^2 + (21-132.5)^2 ] = 103.98*
D(5,C1) = รากที่สอง[ (105-23.5)^2 + (23-132.5)^2 ] = 136.50
D(6,C1) = รากที่สอง[ (20-23.5)^2 + (101-132.5)^2 ] = 12.02
D(1,C2) = รากที่สอง[ (27-36.5)^2 + (144-37)^2 ] = 107.42
D(2,C2) = รากที่สอง[ (32-36.5)^2 + (44-37)^2 ] = 8.32
D(3,C2) = รากที่สอง[ (41-36.5)^2 + (30-37)^2 ] = 8.32
D(4,C2) = รากที่สอง[ (125-36.5)^2 + (21-37)^2 ] = 89.93
D(5,C2) = รากที่สอง[ (105-36.5)^2 + (23-37)^2 ] = 69.92
D(6,C2) = รากที่สอง[ (20-36.5)^2 + (101-37)^2 ] = 85.61
D(1,C3) = รากที่สอง[ (27-115)^2 + (144-22)^2 ] = 150.43
D(2,C3) = รากที่สอง[ (32-115)^2 + (44-22)^2 ] = 85..87
D(3,C3) = รากที่สอง[ (41-115)^2 + (30-22)^2 ] = 74.43
D(4,C3) = รากที่สอง[ (125-115)^2 + (21-22)^2 ] = 10..05
D(5,C3) = รากที่สอง[ (105-115)^2 + (23-22)^2 ] = 10.05
D(6,C3) = รากที่สอง[ (20-115)^2 + (101-22)^2 ] = 137.21

ลำดับที่	คลัสเตอร์	จำนวนส่ง SMS(ครั้ง)	จำนวนใช้โทรศัพท์(ครั้ง)
1	คลัสเตอร์ 1	27	144
6	คลัสเตอร์ 1	20	121
2	คลัสเตอร์ 2	32	44
3	คลัสเตอร์ 2	41	30
4	คลัสเตอร์ 3	125	21
5	คลัสเตอร์ 3	105	23

"Imagination is more important than knowledge" - Albert Einstein

http://goo.gl/72BPC