trong Data Mining & Business Intelligence...Data Mining và Business Intelligence...(Entire Site)
kiếm tìm kiếm

movingthenationforward.com » Data Mining và Business Intelligence » Data Mining & Business Intelligence » Thuật toán K-Means với việc phân nhiều dữ liệu
*
*
*
gmail.com

1.Giới thiệu về nghệ thuật phân các trong khai thác dữ liệu (Clustering Techniques in Data Mining)

Phân cụm là kỹ thuậtrất đặc biệt quan trọng trong khai phá dữ liệu, nó trực thuộc lớp các phương pháp Unsupervised Learning trong Machine Learning. Có khá nhiều định nghĩa không giống nhau về kỹ thuật này, tuy thế về bản chất ta hoàn toàn có thể hiểu phân cụm là các qui trình tìm cách nhóm các đối tượng người tiêu dùng đã cho vào các cụm (clusters), làm sao cho các đối tượng trong cùng 1 cụm tương tự (similar) nhau cùng các đối tượng người tiêu 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 nhiều là tra cứu ra thực chất bên trong các nhóm của dữ liệu. Các thuật toán phân cụm (Clustering Algorithms) hầu như sinh ra các cụm (clusters). Mặc dù nhiên, không tồn tại tiêu chí nào là được xem như là tốt duy nhất để đá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ác như: data reduction, “natural clusters”, “useful” clusters, outlier detection

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

Marketing:Xác định những nhóm người sử dụng (khách sản phẩm tiềm năng, quý khách giá trị, phân một số loại và dự kiến hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của người tiêu dùng để giúp doanh nghiệp có chiến lược kinh doanh hiệu quả hơn; Biology: Phận nhóm động vật và thực vật nhờ vào các nằm trong tính của chúng; Libraries: quan sát và theo dõi độc giả, sách, dự đoán nhu yếu của độc giả…; Insurance, Finance: Phân team các đối tượng người sử dụng sử dụng bảo đảm và các dịch vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phân phát hiện gian lận tài bao gồm (identifying frauds); WWW: Phân 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 các loại như sau (xem hình)


*

2. Thuật Toán K-Means

K-Means là thuật toán rất đặc biệt quan trọng và được sử dụng thông dụng trong nghệ thuật phân cụm. Tứ tưởng bao gồm của thuật toán K-Means là tìm bí quyết phân nhóm các đối tượng người dùng (objects) đã cho vào K nhiều (K là số các 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 đến vai trung phong nhóm (centroid ) là bé dại nhất.

Thuật toán K-Means được bộc lộ như sau

*

Thuật toán K-Means thực hiện qua công việc chính sau:

1. Chọn bỗng dưng K chổ chính giữa (centroid) mang lại K nhiều (cluster). Mỗi các được 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 (objects) đến K trung ương (thường dùng khoảng cách Euclidean)

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

4. Xác minh lại tâm mới cho những nhóm

5. Tiến hành lại cách 2 cho tới khi không có sự thay đổi nhóm nào của những đối tượng

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

Giả sử ta gồm 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 thù X và Y như sau. Mục tiêu của ta là nhóm các thuốc đã bỏ vào 2 team (K=2) dựa vào các đặc trưng của chúng.

*

Bước 1.Khởi chế tạo tâm (centroid) cho 2 nhóm. Trả sử ta lựa chọn A là tâm của group thứ độc nhất vô nhị (tọa độ trung khu nhóm thứ nhất c1(1,1)) với B là tâm của tập thể nhóm thứ 2 (tạo độ trọng điểm nhóm trang bị hai c2 (2,1)).

*

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

*

Mỗi cột trong ma trận khoảng cách (D) là một đối tượng người dùng (cột thứ nhất tương ứng với đối tượng A, cột trang bị 2 tương ứng với đối tượng người sử dụng B,…). Hàng thứ nhất 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 nhóm thứ nhất (c1) cùng hàng thứ hai trong ma trận khoảng cách biểu diễn khoảng cách của các đối tượng đến tâm của group thứ 2 (c2).

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

*

*

Bước 3. team các đối tượng người tiêu dùng vào đội gần nhất

*

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

Bước 5. Tính lại tọa độ các tâm cho những nhóm mới dựa vào tọa độ của các đối tượng người tiêu dùng trong nhóm. Nhóm 1 chỉ có một đối tượng A đề nghị tâm nhóm 1 vẫn ko đổi, c1(1,1). Trọng điểm nhóm 2 được tính như sau:

*

*

Bước 6. Tính lại khoảng cách từ các đối tượng người sử dụng đến tâm mới

*

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

*

Bước 8. Tính lại trung khu cho đội mới

*
*

*

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

*

Bước 9. nhóm các đối tượng người sử dụng vào nhóm

*

Ta thấy G2 = G1 (Không bao gồm sự biến đổi nhóm nào của những đối tượng) bắt buộc thuật toán dừng và kết quả phân đội như sau:

*

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

3. Tiến hành ứng dụng phân cụm với phần mềm WeKa

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

Xem thêm: To Run In The Family Là Gì, Nghĩa Của Từ To Run In The Family

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

Các chúng ta có thể Down file bank.arff trên đây:


*

Nhiệm vụ của họ là sử dụng thuật toán K-Means để phân đội các người tiêu dùng vào K nhóm (trong lấy một ví dụ này K=5) dựa vàosự tương tự (similar) trên11 nằm trong tính của họ.

Ta xây dừng một KnowledgeFlow vào WeKa như sau:


*

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

*

Kết trái phân cụm chi tiết như sau:

*

PS.The next topic is SOM (Self Organizing Maps) in Clustering Techniques. All comments please send lớn chucnv