Ví dụ minh hoạ thuật toán

Ví dụ minh hoạ thuật toán Ví dụ như chúng ta có một vài đối tượng (4 kiểu của thuốc) và mỗi đối tượng có hai thuộc tính hoặc đặc tính như biểu diễn theo bảng sau. Mục đích của chúng ta là nhóm các đối tượng đó lại vào trong K = 2 nhóm medicine cơ bản trên hai với hai đặc tính pH và weight index. Feature 1 (X): Object Medicine A Medicine B Medicine C Medicine D weight index 1 2 4 5 1 1 3 4 Feature 2 (Y): pHMỗi loại Medicine diễn một điểm với...
Nội dung trích xuất từ tài liệu:
Ví dụ minh hoạ thuật toán Ví dụ minh hoạ thuật toán Ví dụ như chúng ta có một vài đối tượng (4 kiểu của thuốc) và mỗiđối tượng có hai thuộc tính hoặc đặc tính như biểu diễn theo bảng sau. Mụcđích của chúng ta là nhóm các đối tượng đó lại vào trong K = 2 nhómmedicine cơ bản trên hai với hai đặc tính pH và weight index. Feature 1 (X): Feature 2 (Y): pH Object weight index Medicine A 1 1 Medicine B 2 1 Medicine C 4 3 Medicine D 5 4 Mỗi loại Medicine diễn một điểm với hai đặc trưng (X,Y) như biểu diễntrên toạ độ như sau: 1) Bước 1 Giá trị ban đầu của các trọng tâm: Giả sử chúng ta sử dụng medicine A và medicine B như các trọng tâm ban đầu. Đưa vào C1, C2 biểu diễn toạ độ của các trọng tâm đó là: C1= (1,1), C2= (2,1). 2) Bước 2 Object-Centroid distance: Chúng ta tính toán khoảng cách giữa nhóm trọng tâm đến mỗi đối tượng. Sử dụng cách tính khoảng cách của Euclidean. Sau đó ta đưa ra ma trận: C1 = (1,1) group-1 0 1 3,61 5D0 = C2 = (2,1) group -2 1 0 2.83 4.24 A B C D X 1 2 4 5 1 1 3 4 Y Mỗi cột trong ma trận khoảng cách tượng trưng cho đối tượng. Dòngđầu của ma trận khoảng cách tương ứng với khoảng cách của mỗi đối tượngđến trọng tâm đầu tiên và dòng thứ hai là khoảng cách của mỗi đối tượngđến trọng tâm thứ hai.Ví dụ, khoảng cách từ Medicine C = (4, 3) đến trọng tâm đầu tiên C1 =(1,1) là: (4 − 1)2 + (3 − 1)2 = 3.61 và khoảng cách của nó đến trọng tâm thứhai C2 = (2,1) là (4 − 2)2 + (3 − 1)2 = 2.83 3) Bước 3Objects clustering: Chúng ta gán mỗi đối tượng cơ sở với khoảng cáchnhỏ nhất. Bởi vậy, machine A được gán đến nhóm 1, machine B được gánđến nhóm 2, machine C đến nhóm 2 và machine D đến nhóm 2. Phần tửcủa ma trận nhóm theo là 1 nếu chỉ nếu các đối tượng được gán đến nhómđó. Group -1 1 0 0 0 G0 = 0 1 1 1 Group -1 A B C D 4) Bước 4 Lặp lại 1, determine deteroids: bây giờ chúng ta tính toán cáctrọng tâm mới của mỗi nhóm cơ sở trên những thành viên mới. Nhóm 1 chỉcó một thành viên bởi vậy trọng tâm chính là nó. Nhóm 2 bây giờ có bathành viên, bởi vậy trọng tâm là trung bình toạ độ giữa ba thành viên: C2 =⎛ 2 + 4 + 5 1+ 3 + 4 ⎞⎜ , ⎟⎝ 3 3 ⎠ 5) Bước 5 Lặp lại bước 1, Object-centroids distances: Bước tiếp theo là tínhtoán khoảng cách của tất cả các đối tượng đến các trọng tâm mới. Tương tựbước 2, chúng ta có khoảng cách ma trận lặp lại 1 là: 0 1 3,61 5 C1 = (1,1) group -1 1D = 11 8 3.14 2.36 0.47 1.89 C2 = ( , ) group -2 3 3 A B C D X 1 2 4 5 1 1 3 4 Y 6) Bước 6Lặp lại bước 1, Objects clustering: Tương tự bước 3, chúng ta gán mỗiđối tượng cơ sở trong khoảng cách nhỏ nhất. Cơ sở trong khoảng cáchmatrix mới, chúng ta di chuyển machine B đến Group 1 trong khi tất cả cácđối tượng khác còn lại. Nhóm ma trận được biểu diễn theo: 1 1 0 0G1 = group - 1 0 0 1 1 group -2 A B C D 7) Bước 7Lặp lại bước 2, determine centroids: Bây giờ chúng ta lặp lại bước 3 đểtính toán các trọng tâm cơ sở trên các phân nhóm của bước trước. Nhóm 1và nhóm 2 có hai thành viên bởi vậy các trọng tâm mới là 1+ 2 1+1 C1 = ( , ) = ⎛1 1 ,1⎞ ⎜ ⎟ 2 2 ⎝ 2 ⎠ 4+5 3+ 4 và C2 = ( , ) = ⎛ 4 1 ,3 1 ⎞ ⎜ ⎟ 2 2 ⎝ 2 2⎠ 8) Bước 8 Lặp lại bước 2, Object-centroids distrances: chúng ta có khoảngcách ma trận mới tại bước 2 như: 1 C1= (1 ,1) group -1 0.5 0.5 3,20 4.61 2 1D2 = 4.30 3.54 0.71 0.71 C1= (1 ,1) group -2 2 9) Bước 9 Lặp lại bước 2, Objects clustering: Làm lại, chúng ta gán mỗi đốitượng cơ sở trên khoảng cách nhỏ nhất. group - 1 1 1 0 0 0 0 1 1 group -2 A B C D Chúng ta thu được kết quả là việc so sánh các nhóm của phép lặpcuối cùng và phép lặp này biểu thị rằng các đối tượng không dời chuyểnsang bất cứ nhóm nào. Bởi vậy việc tính toán của k-Mean clustering có thểđược nghiên cứu sự ổn định của nó. Kết quả cuối cùng khi gom nhóm. Feature 1 (X): Feature 2 Grou ...