K-Means Là Gì

     

1. Trình làng về chuyên môn phân cụm trong khai thác dữ liệu (Clustering Techniques in Data Mining)

Phân cụm là kỹ thuật rất đặc biệt trong khai thác dữ liệu, nó nằm trong lớp các phương pháp Unsupervised Learning trong Machine Learning. Có khá nhiều định nghĩa khác nhau về kỹ thuật này, dẫu vậy về bản chất ta rất có thể hiểu phân nhiều là các qui trình tìm biện pháp nhóm các đối tượng người sử dụng đã mang đến vào các cụm (clusters), làm thế nào để cho các đối tượng trong cùng 1 cụm tương tự như (similar) nhau và các đối tượng người sử dụng khác nhiều thì không giống như (Dissimilar) nhau.

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

Mục đích của phân cụm là tìm kiếm ra thực chất bên trong số nhóm của dữ liệu. Những thuật toán phân các (Clustering Algorithms) các sinh ra các cụm (clusters). Tuy nhiên, không có tiêu chí như thế nào là được coi là tốt độc nhất vô nhị để đánh hiệu của của phân tích phân cụm, điều này dựa vào vào mục đích của phân cụm như: data reduction, “natural clusters”, “useful” clusters, outlier detection

Kỹ thuật phân cụm có thể áp dụng trong không hề ít lĩnh vực như:

Marketing: Xác định các nhóm người sử dụng (khách sản phẩm tiềm năng, khách hàng giá trị, phân nhiều loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của doanh nghiệp để giúp doanh nghiệp có kế hoạch kinh doanh tác dụng hơn;Biology: Phận nhóm động vật và thực vật phụ thuộc các ở trong tính của chúng;Libraries: theo dõi độc giả, sách, dự đoán yêu cầu của độc giả…;Insurance, Finance: Phân team các đối tượng người dùng sử dụng bảo hiểm và những dịch vụ tài chính, dự đoán xu thế (trend) của khách hàng hàng, phát hiện gian lận tài bao gồm (identifying frauds);WWW: Phân một số loại tài liệu (document classification); phân loại người tiêu dùng web (clustering weblog);… 

Các chuyên môn phân nhiều được phân nhiều loại như sau (xem hình)

*

2. Thuật Toán K-Means

K-Means là thuật toán rất quan trọng đặc biệt và được sử dụng phổ cập trong kỹ thuật phân cụm. Tư tưởng chính của thuật toán K-Means là tìm biện pháp phân đội các đối tượng người tiêu dùng (objects) đã cho vô K các (K là số những cụm được xác đinh trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng người dùng đến trọng điểm nhóm (centroid ) là nhỏ nhất.

Thuật toán K-Means được biểu hiện như sau

 

*
 Thuật toán K-Means thực hiện qua quá trình chính sau:

1. Chọn hốt nhiên K trọng điểm (centroid) đến K cụm (cluster). Mỗi cụm được đại diện thay mặt bằng các tâm của cụm.

2. Tính khoảng cách giữa các đối tượng người sử dụng (objects) cho K trung khu (thường dùng khoảng cách Euclidean)

3. Team các đối tượng người tiêu dùng vào nhóm gần nhất

4. Xác định lại chổ chính giữa mới cho các nhóm

5. Thực hiện lại cách 2 cho đến khi không tồn tại sự biến hóa nhóm nào của các đối tượng

 Ví dụ minh họa thuật toán K-Mean:

Giả sử ta có 4 phương thuốc A,B,C,D, mỗi một số loại thuộc được biểu diễn bởi 2 đặc trưng X với Y như sau. Mục đích của ta là nhóm những thuốc đã cho vô 2 nhóm (K=2) dựa vào các đặc thù của chúng.

*
*

Bước 1. Khởi sinh sản tâm (centroid) cho 2 nhóm. đưa sử ta lựa chọn A là tâm của nhóm thứ độc nhất vô nhị (tọa độ trung ương nhóm trước tiên c1(1,1)) và B là tâm của group thứ 2 (tạo độ trọng điểm nhóm sản phẩm hai c2 (2,1)).

*

Bước 2. Tính khoảng cách từ các đối tượng người tiêu dùng đến tâm của những nhóm (Khoảng biện pháp Euclidean)

*

Mỗi cột vào ma trận khoảng cách (D) là một đối tượng người sử dụng (cột đầu tiên tương ứng với đối tượng người tiêu dùng A, cột sản phẩm công nghệ 2 khớp ứng với đối tượng người tiêu dùng B,…). Hàng trước tiên trong ma trận khoảng cách biểu diễn khoảng cách giữa các đối tượng người sử dụng đến tâm của tập thể nhóm thứ nhất (c1) với hàng thứ 2 trong ma trận khoảng cách biểu diễn khoảng cách của các đối tượng người sử dụng đến tâm của tập thể nhóm thứ 2 (c2).

Ví dụ, khoảng cách từ bài thuốc C=(4,3) đến trọng tâm c1(1,1) là 3.61 và đến trung ương c2(2,1) là 2.83 được tính như sau:

*

*

Bước 3.

Xem thêm: Cách Làm Bánh Cay Chiên Từ Bột Mì Giòn Ngon, 2 Cách Làm Bánh Cay Chiên Từ Khoai Mì Thơm Ngon

 Nhóm các đối tượng người tiêu dùng vào nhóm gần nhất

*

Ta thấy rằng đội 1 sau vòng lặp trước tiên gồm có một đối tượng A với nhóm 2 có các đối tượng người sử dụng còn lại B,C,D.

Bước 5. Tính lại tọa độ các tâm cho các nhóm mới phụ thuộc tọa độ của các đối tượng trong nhóm. Nhóm 1 chỉ có 1 đối tượng A bắt buộc tâm team 1 vẫn không đổi, c1(1,1). Trung tâm nhóm 2 được xem như sau:

*

*

Bước 6. Tính lại khoảng cách từ các đối tượng người tiêu dùng đến trung ương mới

*

Bước 7. Nhóm các đối tượng người tiêu dùng vào nhóm

*

Bước 8. Tính lại trọng điểm cho nhóm mới

*
*

*

 

Bước 8. Tính lại khoảng cách từ các đối tượng người dùng đến trung khu mới

*

Bước 9. Nhóm các đối tượng người tiêu dùng vào nhóm

*

Ta thấy G2 = G1 (Không có sự biến đổi nhóm nào của các đối tượng) cần thuật toán giới hạn và hiệu quả phân đội như sau:

*

Thuật toán K-Means có ưu điểm là đối kháng giản, dễ dàng nắm bắt và mua đặt. Tuy nhiên, một trong những hạn chế của K-Means là hiệu quả của thuật toán dựa vào vào bài toán chọn số nhóm K (phải xác minh trước) và chi tiêu cho thực hiện vòng lặp thống kê giám sát khoảng cách phệ khi số các K và dữ liệu phân các lớn.

3. Thực thi ứng dụng phân các với phần mềm WeKa

Trong lấy ví dụ như này, tôi sẽ giới thiệu cách tạo ra một KnowledgeFlow để thực hiện kỹ thuật phân cụm dựa trên thuật toán K-Means trên Data Mining Software WeKa.

Xem thêm: Phương Pháp Chiếu Đèn Hồng Ngoại Có Tác Hại Gì, Đèn Hồng Ngoại

Dữ liệu dùng để phân cụm trong lấy một ví dụ này là dữ liệu dùng làm phân loại người tiêu dùng của bank (file dữ liệu bank.arff). Bank.arff gồm tất cả 11 ở trong tính cùng 600 người tiêu dùng (instances). Dưới trên đây là kết cấu và phân bố dữ liệu của bank.arff

*

Nhiệm vụ của họ là sử dụng thuật toán K-Means để phân team các khách hàng vào K team (trong ví dụ này K=5) dựa vào sự tựa như (similar) trên11 thuộc tính của họ.

 Ta gây ra một KnowledgeFlow vào WeKa như sau:

*

Thiết lập các tham số cho thuật toán K-Means như số cụm (trong lấy ví dụ như này K=5), giải pháp tính khoảng cách (trong ví dụ này dùng khoảng cách Euclidean),…