K-MEANS LÀ GÌ

admin 03/07/2022

Trong bài bác trước, bọn họ học thuật toán Hồi qui con đường tính Linear Regression. Đây là thuật toán đơn giản dễ dàng nhất vào Supervised learning. Nội dung bài viết này chúng ta chuyển sang học tập về một thuật toán cơ phiên bản trong Unsupervised learning - thuật toán K-means clustering (phân team K-means). Đây là là một thuật toán khá gần cận với tôi vị trong quá trình làm nghiên cứu ở đại học, tôi đã làm khá sâu về graph và đường đi ngắn độc nhất với bài toàn tra cứu k Nearest Neighbor.

Bạn đang xem: K-means là gì

Hiểu về K-Means Clustering

Trước hết bọn họ sẽ mày mò về thuật toán K-means clustering trước bởi ví dụ :

Bài toán form size áo T-shirt

Giả sử có một doanh nghiệp định ra mắt một mẫu mã sản phẩn mới T-shirt vào thị trường. Tất nhiên họ sẽ đề xuất sản xuất rất nhiều size để tương xứng với sự đa dạng mẫu mã của thị trường người dùng. Với triết lý đo, doanh nghiệp đã thực hiện khảo sát dữ liệu chiều cao và cân nặng của fan dùng, với vẽ nó thành 1 trang bị thị như sau :

Công ty này ko thể đầy đủ nguồn lực để rất có thể sản xuất áo với tất cả mọi size. Thực tiễn này trong kinh doanh bạn cũng dễ ợt hiểu được. THay bởi vì đó, họ sẽ phân chia số lượng người dùng thành các kích cỡ như là Small, Medium, Large và sản xuất chỉ 3 chủng loại như thế. 3 mẫu này là đủ khớp với tất cả mọi bạn và thị trường. Ở đây việc phân chia các người tiêu dùng vào 3 team trên sẽ được xử lý bởi kĩ thuật phân đội K-means. Thuật toán này sẽ mang lại ta 3 kích thước áo tối ưu độc nhất vô nhị - thoã mãn toàn bộ mọi người. Tất nhiên, giả dụ như ko thể tìm kiếm được 3 kích cỡ áo vừa vặn vẹo thoả mãn mọi fan trong nhóm, công ty sẽ chia nhỏ nhóm thêm thành nhiều nhóm khác, rất có thể là 5, có thể là nhiều hơn nữa nữa ....

bạn nhìn hình sẽ rõ nhé

Làm ráng nào nhưng chia nhỏ được thế

Thuật toán này sẽ là 1 vòng lặp. Để dễ dàng mình sẽ biểu hiện từng step của thuật toán và môt chút hình minh hoạ.

Hãy coi nhóm tài liệu như đồ thị dưới ( nhằm dễ hình dung thì các bạn hãy xem đây như thể đồ thị về độ cao - cân nặng của nhóm người dùng ). Chúng ta sẽ nhóm những dữ liệu thành 2 nhóm.

STEP 1 : Thuật toán này chọn tự dưng 2 trọng tâm. C1 với C2 ( thỉnh thoảng, bất kì 2 cặp điểm nào cũng trở thành được xem như là 2 cặp giữa trung tâm ).

STEP 2 : đo lường và thống kê khoảng phương pháp từ mỗi điểm đến chọn lựa 2 trung tâm đó. Giả dụ một dữ liệu thử nghiệm là gần với C1 hơn nữa thì nó sẽ được gán nhãn "0". Nếu đó là gần với C2 hơn, nó sẽ được dán nhãn là "1" (nếu bạn dùng nhiều trung tâm hơn thì các bạn sẽ có các label hơn ví như "2", "3" v.v... ).

Trong hình, bọn họ sẽ tô màu cho những nhãn 0 là đỏ cùng xanh cho những nhãn 1. Bọn họ có hình như dưới :

STEP 3 : Tiếp theo bọn họ tính toán vừa đủ của tất cả các điểm greed color và đỏ riêng biệt biệt. Hiệu quả này sẽ được cho phép quyết định được giữa trung tâm mới. C1 cùng C2 sẽ được tái thiết lập cấu hình vị trí bắt đầu với các điểm tài liệu mới ( chú ý, những hình ảnh dưới ko cần là quý giá thật đây chỉ là ví dụ thôi nhé ).

Tiếp, bọn họ lại tái diễn bước 2. Họ có kết quả như sau :

Bây giờ, cách 2 và cách 2 sẽ được lặp đi lặp lại cho tới khi giữa trung tâm được quy tụ về 1 điểm cố định. Hoặc đơn giản là nó sẽ dừng lại ở trong một phạm vi - toại nguyện một chuẩn mà họ đã giới thiệu từ trước. Ví du như là đã đạt được đến chu kỳ vòng lặp về tối đa đã tư tưởng trước, hoặc là đã đạt được một chuẩn đúng chuẩn nào đó .v... Các điểm đó sẽ vừa lòng tổng khoảng cách giữa dữ liệu test và giữa trung tâm tương ứng là bé dại nhất. Hoặc cũng rất có thể là tổng khoảng cách giữa C1 cho tới điểm đỏ và C2 cho tới điểm xanh là nhỏ nhất.

Cuối cùng họ có giữa trung tâm như sau :

K-Means Clustering thực hiện trong OpenCV

Mục tiêu của phần nay là sẽ giúp bạn sử dụng công nuốm OpenCV - rõ ràng là cv2.kmeans() để triển khai thuật toán k-means.

Xem thêm: Đúng, Cổ Loa Là Kinh Đô Của Nước Âu Lạc Được Đặt Ở Đâu? Kinh Đô Của Nước Âu Lạc Đóng Ở

Tìm gọi về Parameterssamples : Mẫu thì nên là kiểu dữ liệu của np.float32, cùng mỗi đối tượng cần được đặt trọng một cột duy nhất.nclusters (K): Số nhóm yêu cầu tại thời điểm cuối cùngcriteria : Đây là tiêu chí dứt vòng lặp. Khi tiêu chuẩn này được thỏa mãn, thuật toán đã dừng vòng lặp. Trên thực tế, nó phải là một trong những nhóm 3 thông số (type, max_iter, epsilon):3.a - loại tiêu chuẩn chấm dứt: Nó gồm 3 lá cờ như sau:cv2.TERM_CRITERIA_EPS - phòng sự lặp lại thuật toán nếu đạt được độ đúng đắn nhất định - epsilon đạt được.cv2.TERM_CRITERIA_MAX_ITER - giới hạn thuật toán sau khi số lượng khăng khăng được lặp đi lặp lạicv2.TERM_CRITERIA_EPS max_iter + cv2.TERM_CRITERIA_MAX_ITER - ngăn ngừa sự lặp đi tái diễn khi một trong các điều kiện trên nó được đáp ứng3.b - max_iter - một vài nguyên xác định số lượng buổi tối đa vòng lặp.3.c - Độ đúng mực - epsilonattempts: Cờ để xác định số lần các thuật toán được thực hiện bằng cách sử dụng bài toán đánh nhãn khởi tạo thành khác nhau.flags : Cờ này được thực hiện để khẳng định trung tầm thuở đầu được chọn như thế nào. Về cơ phiên bản có 2 cờ được áp dụng là : cv2.KMEANS_PP_CENTERS cùng cv2.KMEANS_RANDOM_CENTERS.Output parameterscompactness : Đây là tổng của bình phương khoảng cách từ mỗi điểm đến lựa chọn trọng tâm tương tự của họ.labels : Đây là mảng những label trong những số đó mỗi thành phần của mảng được đánh dấu "0", "1" .....centers : Đây là mảng trọng tâm của các nhóm.

Bây giờ họ sẽ thấy làm vậy nào để vận dụng thuật toán K-Means với ví dụ.

Dữ liệu với có một biến

Hãy xem xét, bạn có một bộ dữ liệu chỉ với một tính năng, có nghĩa là một chiều. Ví dụ như bài toán áo T-shirt sinh sống trên nhưng bọn họ chỉ thực hiện mỗi độ cao của người dùng để làm quyết định size áo .

Chúng ta sẽ bước đầu bằng cách tạo thành dữ liệu với vẽ nó trên thiết bị thị trong Matplotlib :

import numpy as npimport cv2from matplotlib import pyplot as pltx = 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()Chúng ta tất cả z là 1 mảng có form size 50, và những giá trị khác biệt từ 0 cho 255. Mang đến z thành một vector cột. Sau đó, họ tạo tài liệu của loại np.float32.

Chúng ta sẽ có được hình ảnh sau:

Bây giờ bọn họ áp dụng thuật toán K-Means. Trước đó họ cần khẳng định các tiêu chí. Tiêu chuẩn của tôi là, bất cứ khi nào 10 lần lặp của thuật toán được chạy, hoặc đạt được độ chính xác của epsilon = 1.0, thuật toán vẫn dừng cùng trả về công dụng :

# Define criteria = ( type, max_iter = 10 , epsilon = 1.0 )criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)# phối flags (Just to avoid line break in the code)flags = cv2.KMEANS_RANDOM_CENTERS# Apply KMeanscompactness,labels,centers = cv2.kmeans(z,2,None,criteria,10,flags)Việc này sẽ mang đến ta các giá trị về compactness, label với trọng tâm. Vào trường vừa lòng này, ta có những trung chổ chính giữa là 60 với 207. Nhãn sẽ sở hữu được cùng kích thước với dữ liệu test, ở chỗ này mỗi dữ liệu sẽ tiến hành gắn nhãn là "0", "1", "2" v.v... Tùy nằm trong vào giữa trung tâm của chúng. Hiện giờ ta chia dữ liệu vào các nhóm khác biệt tùy nằm trong vào nhãn của chúng.

A = zB = zBây giờ chúng ta sẽ vẽ A red color và B màu xanh lá cây và giữa trung tâm của chúng bằng màu vàng.

# Now plot "A" in red, "B" in blue, "centers" in yellowplt.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()Chúng ta vẫn có kết quả như sau :

Dữ liệu với chỉ những biến

Trong ví dụ sinh sống trên, họ chỉ có chiều cao để quyêt định bài xích toán. Bây giơ, hãy quan tâm đến luôn cả khối lượng nhé . Bài toán sẽ đổi mới phân team tập các chiều cao - cân nặng. Chăm chú rằng sinh sống ví dụ trước, chúng ta lưu dữ liệu vào một trong những vector đơn. Mỗi biến sẽ tiến hành sắp xếp vào một cột, từng cột sẽ tương xứng với một giá bán trị test được đẩy vào. Trong trường hòa hợp này, trả sử bọn họ có tập dữ liệu 50x2, tức là sẽ tất cả cặp độ cao - trọng lượng của 50 người. Cột đầu tiên sẽ tương ứng với độ cao của 50 người và cột thứ hai là khối lượng của họ. Dòng dầu tiên khớp ứng với 2 nhân tố ( chiều cao - trọng lượng ) của bạn thứ nhất. V.v... Tương tự như như vậy cho đến dòng số 50.

Giải thích có vẻ như hơi dài chiếc nhưng nếu bạn nào còn nhớ kỹ năng toán về ma trận hẳn sẽ định hình được ngay lập tức ý niệm này vào đầu :

Tiếp, bọn họ sẽ code như sau :

import numpy as npimport cv2from matplotlib import pyplot as pltX = np.random.randint(25,50,(25,2))Y = np.random.randint(60,85,(25,2))Z = np.vstack((X,Y))# convert to np.float32Z = np.float32(Z)# define criteria & 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, cảnh báo the flatten()A = ZB = Z# Plot the dataplt.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()Kết quả bọn họ có được :

Color Quantization

Color Quantization là một trong process giảm con số màu vào một hình ảnh.

Xem thêm: Phát Biểu Thức Định Luật 2 Newton Là, Phát Biểu Và Viết Hệ Thức Của Định Luật Ii Newton

Lý vì chưng để giảm chất lượng ảnh là để bớt thiểu dung lượng nhớ và tải server or dễ dàng và đơn giản là nhiều khi trên một số thiết bị có thể có giới hạn làm sao để cho nó hoàn toàn có thể sản xuất chỉ số lượng màu giới hạn. Trong số những trường hợp đó, lượng tử hóa color được thực hiện. Ở đây chúng ta sử dụng k-means clustering để "trung bình hoá màu".

Hẳn là bạn đã nhận được ra sự liên quan rồi nhỉ. Màu sẽ có được 3 biến chuyển là R, G, B. Vày vậy, chúng ta cần định hình lại image vào trong 1 mảng có kích cỡ Mx3 (M là số px trong images). Sau khi phân nhóm, chúng ta thay giá chỉ trị giữa trung tâm ( R, G, B ) cho toàn bộ các điểm hình ảnh sao mang đến hình ảnh mới sẽ chỉ có một số trong những lượng màu xác định. Tiếp tục, họ lại reshape nó trở lại dạng hình hình ảnh bình thường :

Code đang như sau :

import numpy as npimport cv2img = cv2.imread("home.jpg")Z = img.reshape((-1,3))# convert to np.float32Z = np.float32(Z)# define criteria, number of clusters(K) & apply kmeans()criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)K = 8ret,label,center=cv2.kmeans(Z,K,None,criteria,10,cv2.KMEANS_RANDOM_CENTERS)# Now convert back into uint8, and make original imagecenter = np.uint8(center)res = centerres2 = res.reshape((img.shape))cv2.imshow("res2",res2)cv2.waitKey(0)cv2.destroyAllWindows()Kết trái với K = 8 :