K-Means Clustering

Understanding K-Means Clustering

• เพื่อเข้าใจการจัดกลุ่มแบบ K-Means Clustering

Theory

• โดยทั่วไปจะใช้เรื่องในเข้ามาจัดการเป็นอย่างปกมาก

T-shirt size problem

• โดยการจะทำเสื้อยืดนั้น บริษัทจะต้องผลิตรูปแบบและขนาดที่แตกต่างกันเพื่อตอบสนองผู้บริโภคโดยจะทำให้เหมาะสมกับผู้คนทุกๆ ไซต์โดยโดยจะยกตัวอย่างกราฟด้านล่างนี้

• และบริษัทนั้นไม่สามารถสร้างเสื้อยืดที่มีขนาดทุกๆขนาดได้ แต่จะแบ่งออกเป็น คนตัวเล็ก คนตัวขนาดกลาง คนตัวใหญ่ และจะสามารถผลิตแค่ 3 Size เพื่อให้พอดีทุกคน ในการจัดกลุ่มแบบนี้สามารถทำผ่าน K-Means Clustering ได้โดยวิธีที่ดีที่สุดคือ 3 Size และหากไม่เป็นเช่นนั้น สามารถแบ่งกลุ่มเพิ่มได้อีก อาจจะ 5 size ดูที่รูปภาพ

หลักการทำงาน

• ขั้นตอนวิธี (algorithm) ของกระบวนการที่เกิดซ้ำแล้วซ้ำอีก นั้นจะสามารถอธิบายโดย step-by-step ในการช่วยงานด้าน image โดยวิิธีคือ

ขั้นตอนที่ 1

• Algorithm จะสุ่มเลือกสอง centroids คือ C1 และ C2

ขั้นตอนที่ 2

• จะคำนวณระยะห่างจากจุดแต่ละจุดของ centroids หากข้อมูลที่ทดสอบนั้น ใกล้ชิด C1 แล้วข้อมูลจะใส่ชื่อกำกับว่า '0' หากข้อมูลที่ทดสอบ ใกล้กับ C2 จะใส่ชื่อกำกับว่า '1' หากมี Centroid มากขึ้นก็จะใส่ชื่อเพิ่มลำดับไปเรื่อยๆ

• ในกรณณีที่จะใส่ให้กับ '0' นั้นเป็นสีแดง และใส่สีให้กับ '1' เป็นสีฟ้า

ขั้นตอนที่ 3

• ต่อไปจะเป็นการคำนวณค่าเฉลี่ยของจุดสีฟ้าและจุดสีแดงที่แยกจากกัน โดย new centroid = C1 และ C2
  • และนำข้อมูลใหม่นี้ไปทำเหมือนกันกับ ขั้นตอนที่สอง

Final Step

• ใน Step นี้ เมื่อทำ ขั้นตอนที่ 2-3 เสร็จแล้วจะวนทำซ้ำจนกว่าทั้ง centroids จะแปรสภาพไปยังจุดคงที่ * โดยจุดเหล่านั้นเป็นผลรวมของระยะทางระหว่างข้อมูลการทดสอบและ centroids ที่สอดคล้องกันขอพวกมันนั้น จะมีขั้นต่ำเท่าไหร่ หรือ เพียงแค่ผลรวมของระยะทางเท่านั้น โดย

C1↔Red_Points and C2↔Blue_Points คือค่าต่ำสุด ดังสูตร

• • โดยผลลัพธ์ คือ

K-Means Clustering in OpenCV

เป้าหมาย

• เรียนรู้ที่จะใช้ฟังก์ชั่น cv2.kmeans() สำหรับใช้ data clustering

ทำความเข้าใจกับ parameters

Input Parameters

samples : โดยใช้งานฟังก์ชั่น np.float32 data type เข้ามาช่วยและควรจะเป็นคอลัมน์เดียว nclusters(K) : จำนวนของ clusters criteria : เป็นเกณฑ์ในการยกเลิกการทำซ้ำ ว่าเมื่อใดที่จะยุติการทำซ้ำ และมี tuple 3 parameter `( type, max_iter, epsilon )`:

• • v2.TERM_CRITERIA_EPS - หยุด algorithm การวนซ้ำโดยจะมีความแม่นยำแบบเฉพาะตัว ต้องระบุ Epsilon
  • cv2.TERM_CRITERIA_MAX_ITER - หยุด algorithm หลังจาก max_iter
  • cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER - หยุดกระทำเมื่อพบเงื่อยไขตามที่กล่าวมาข้างต้น
• max_iter - จำนวนเต็มแบบ Integer specifying maximum ของการวนลูป.
• epsilon - จำเป็นต้องถูกต้อง

attempts : คือ Flag ที่จำเป็นต้องระบุจำนวนครั้งสำหรับ Algorithm ดำเนินโดยใช้ Label (ป้ายชื่อ) ใน algorithm การส่งกลับของป้ายชื่อจะให้สิ่งที่ดีที่สุด เป็น compactness และออกเป็น output flags: : Flag นี้จะใช้ในการระบุว่าจะเริ่มต้นที่ canters ปกติใช้คำสั่ง cv2.KMEANS_PP_CENTERS and cv2.KMEANS_RANDOM_CENTERS.

Output Parameters

• • compactness : คือผลรวมของระยะทางกำลังสอง จากจุดหนึ่งไปอีกจุด
  • labels : คือป้ายชื่อของ Array เช่นเดียวกับ Code ในบทก่อนๆ เช่น '0' , '1' ..... '99'
  • centers : คือศูนย์รวมของกลุ่มอาเรย์

Data With Only One Feature

Code Example

import numpy as np
import cv2
from matplotlib import pyplot as plt
 
x = np.random.randint(25,100,25)
y = np.random.randint(175,255,25)
z = np.hstack((x,y))
z = z.reshape((50,1))
z = np.float32(z)
plt.hist(z,256,[0,256]),plt.show()

• ดังนั้นจึงมี 'z' ซึ่งป็นอาร์เรย์ของขนาด 50 และค่าตั้งแต่ 0 ถึง 255 ได้เปลี่ยน 'z' สำหรับ vector column โดยจะมีประโยชน์มากขึ้นเมื่อมีคุณสมบัตินั้นอยู่ โดยใช้ฟังก์ชั่น np.float32

• ตอนนี้ใช้ฟังก์ชั่น Kmeans ก่อนที่จะระบุเงื่อนไขโดยเงื่อนไขนั้น เมื่อใดก็ตามที่ มีการทำซ้่ำ 10 รอบความถูกต้องจะ = 1.0 และถึงขั้นที่จะหยุดและ return คำตอบ

 # Define criteria = ( type, max_iter = 10 , epsilon = 1.0 )
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
 
 # Set flags (Just to avoid line break in the code)
flags = cv2.KMEANS_RANDOM_CENTERS
 
 # Apply KMeans
compactness,labels,centers = cv2.kmeans(z,2,None,criteria,10,flags)

• ในตอนนี้จะเป็น compactness และ ป้ายชื่อ และ ศูนย์กลาง ในกรณีนี้ ได้ผลลัพธ์ ศูนย์กลาง = 60 และ 207 ป้ายชื่อนั้นจะได้ขนาดเท่ากัน และ ขึ้นอยู่กับ centroid โดยตอนนี้สามารถแยกข้อมูลไปยังกลุ่มแตกต่างกันขึ้นอยู่ป้ายชื่อ (label)

A = z[labels==0]
B = z[labels==1]

• ในตอนนี้ plot A อยู่สีแดง และ B อยู่สีฟ้า โดย centroid จะอยู่ในสีเหลือง

# Now plot 'A' in red, 'B' in blue, 'centers' in yellow
plt.hist(A,256,[0,256],color = 'r')
plt.hist(B,256,[0,256],color = 'b')
plt.hist(centers,32,[0,256],color = 'y')
plt.show()

Data with Multiple Features

• ในตัวอย่างถัดไปนี้ จะเป็นการหา height for t-shirt problem ตอนนี้ เราจะหาค่า height และ weight โดย 2 feature
• โปรดจำไว้ว่าในกรณีที่ก่อนหน้านี้เราทำข้อมูลของเราที่จะเวกเตอร์คอลัมน์เดียว คุณลักษณะแต่ละครั้งจะถูกจัดให้อยู่ในคอลัมน์ในขณะที่แต่ละแถวสอดคล้องกับตัวอย่างการทดสอบการป้อนข้อมูล
• ยกตัวอย่างเช่นในกรณีนี้เราตั้งค่าข้อมูลการทดสอบขนาด 50x2 ซึ่งเป็นความสูงและน้ำหนักของ 50 คน คอลัมน์แรกสอดคล้องกับความสูงของทั้งหมด 50 คนและคอลัมน์ที่สองสอดคล้องกับน้ำหนักของพวกเขา แถวแรกมีสององค์ประกอบที่แรกคือความสูงของคนแรกและคนที่สองน้ำหนักของเขา ในทำนองเดียวกันที่เหลืออยู่แถวสอดคล้องกับความสูงและน้ำหนักของคนอื่น ๆ ตรวจสอบภาพ

Code

import numpy as np
import cv2
from matplotlib import pyplot as plt

X = np.random.randint(25,50,(25,2))
Y = np.random.randint(60,85,(25,2))
Z = np.vstack((X,Y))

# convert to np.float32
Z = np.float32(Z)

# define criteria and apply kmeans()
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
ret,label,center=cv2.kmeans(Z,2,None,criteria,10,cv2.KMEANS_RANDOM_CENTERS)

# Now separate the data, Note the flatten()
A = Z[label.ravel()==0]
B = Z[label.ravel()==1]

# Plot the data
plt.scatter(A[:,0],A[:,1])
plt.scatter(B[:,0],B[:,1],c = 'r')
plt.scatter(center[:,0],center[:,1],s = 80,c = 'y', marker = 's')
plt.xlabel('Height'),plt.ylabel('Weight')
plt.show()

Color Quantization

• Quantization คือ กระบวนการลดตัวเลขของสีออกจากภาพ โดยเหตุผลคือการลดหน่วยความจำ บางครั้งอุปกรณ์บางอย่างอาจมีข้อจำกัด ดังกล่าวว่าสามารถผลิตเท่านั้นตามจำนวนจำกัด ของสี ในกรณีดังกล่าวยัง quantization โดยสีจะดำเนินการ และ ที่นี่เราใช้ K-Meaning ในการจัดกลุ่มสำหรับ quantization สี

Code

import numpy as np
import cv2

img = cv2.imread('lena.jpg')
Z = img.reshape((-1,3))

# convert to np.float32
Z = np.float32(Z)

# define criteria, number of clusters(K) and apply kmeans()
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
K = 8
ret,label,center=cv2.kmeans(Z,K,None,criteria,10,cv2.KMEANS_RANDOM_CENTERS)

# Now convert back into uint8, and make original image
center = np.uint8(center)
res = center[label.flatten()]
res2 = res.reshape((img.shape))

cv2.imshow('res2',res2)
cv2.waitKey(0)
cv2.destroyAllWindows()