1. Trang Chủ
  2. Khoa học tự nhiên
  3. Bài tập chuyên đề Datamining - Gom cụm

Bài tập chuyên đề Datamining - Gom cụm

 Gom cụm: Gom các đối tượng dữ liệu o Tương tự với một đối tượng khác trong cùng cụm o Không tương tự với các đối tượng trong các cụm khác (Tức là thực hiện gom các đối tượng có cùng tính chất hay có các tính chất gần giống nhau thành nhóm) o Ví dụ: Phân loại học sinh trong một lớp theo điểm số thành 5 nhóm giỏi, khá, trung bình khá, trung bình, yếu. Những học sinh có điểm từ 8-10 phân vào nhóm giỏi, từ 7-8 phân vào nhóm khá, 6-7 phân vào nhóm trung bình khá, 5-6... Bài tập chuyên đề Datamining

Thể loại Tài liệu miễn phí Khoa học tự nhiên

Số trang 24

Ngày tạo 8/30/2018 1:36:17 AM +00:00

Loại tệp DOC

Kích thước 0.40 M

Tên tệp

Tải Bài tập chuyên đề Datamining - Gom cụm (.docx) Tải Bài tập chuyên đề Datamining - Gom cụm (.pdf)

Xem mẫu

  1. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Gom cụm (clustering) Phân tích bằng gom cụm  Phân tích bằng gom cụm là gì ?  Đối tượng tương tự và không tương tự  Các loại dữ liệu trong phân tích bằng gom cụm  Các phương pháp gom cụm chính  Các phương pháp phân cấp  Các phương pháp phân hoạch  Tóm tắt I)Phân tích bằng gom cụm là gì ? Gom cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thường mà chúng ta vẫn làm và thực hiện hàng ngày ví dụ như phân loại học sinh khá, giỏi trong lớp, phân loại đất đai, phân loại tài sản, phân loại sách trong thư viện…  Gom cụm: Gom các đối tượng dữ liệu o Tương tự với một đối tượng khác trong cùng cụm o Không tương tự với các đối tượng trong các cụm khác (Tức là thực hiện gom các đối tượng có cùng tính chất hay có các tính chất gần giống nhau thành nhóm) o Ví dụ: Phân loại học sinh trong một lớp theo điểm số thành 5 nhóm giỏi, khá, trung bình khá, trung bình, yếu. Những học sinh có điểm từ 8-10 phân vào nhóm giỏi, từ 7-8 phân vào nhóm khá, 6-7 phân vào nhóm trung bình khá, 5-6 nhóm TB, 5 trở xuống vào nhóm yếu.  Mục tiêu của gom cụm: Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.  Ứng dụng của gom cụm: o Kinh doanh: phát hiện ra nhóm khách hàng. Ví dụ Trong tiếp thị mỹ phẩm có thể phân nhóm khách hang ưa chuộng mỹ phẩm Hàn Quốc, nhóm khách hang ưa chuộng Mỹ phẩm pháp… o Sinh học: phân loại động, thực vật, phân loại gen. o Địa lí: nhận ra các vùng đất giống nhau dựa vào CSDL quan sát trên trái đất, phân nhóm nhà,…
  2. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang o Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với chi phí đền bù trung bình cao o Hoạch định thành phố: nhận dạng các nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý. o Một công cụ độc lập để xem xét phân bố dữ liệu o Làm bước tiền xử lý cho các thuật toán khác  Thế nào là gom cụm tốt − Một phương pháp tốt sẽ tạo ra các cụm có chất lượng cao với: o Tương tự cao cho trong lớp (intra-class) o Tương tự thấp giữa các lớp (inter-class) o Tức là những đối tượng cùng một nhóm có sự giống nhau hoặc gần giống nhau càng nhiều thì chất lượng gom cụm sẽ càng cao − Chất lượng của kết quả gom cụm phụ thuộc vào: o Độ đo tương tự sử dụng o Cài đặt độ đo tương tự  Các yêu cầu của gom cụm trong khai phá dữ liệu.  Scalability: Có thể thay đổi kích cỡ.  Khả năng làm việc với các loại thuộc tính khác nhau.  Khám phá ra các cụm có hình dạng bất kì. Khả năng làm việc với dữ liệu có chứa nhiễu ( outliers)   Tương tự và bất tương tự giữa hai đối tượng (1) − Không có định nghĩa duy nhất về sự tương tự và bất tương tự giữa các đối tượng dữ liệu − Định nghĩa về tương tự và bất tượng tự giữa các đối tượng tùy thuộc vào o Loại dữ liệu khảo sát o Loại tương tự cần thiết − Tương tự /Bất tượng tự giữa đối tượng thường được biểu diễn qua độ đo khoảng cách d(x,y) − Lý tưởng, mọi độ đo khoảng cách phải là một và phải thỏa các điều kiện sau: 1. d ( x, y ) ≥ 0 2. d ( x, y ) = 0 iff x = y 3. d ( x, y ) = d ( y, x ) 4. d ( x, z ) ≤ d ( x, y ) + d ( y, z )
  3. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang II)Loại dữ liệu trong phân tích cụm  Các biến khoảng tỉ lệ  Biến nhị phân  Các biến định danh, thứ tự, tỉ lệ  Các biến có kiểu hổn hợp  Các kiểu dữ liệu phức tạp Các biến trị khoảng (1) Định nghĩa: Biến trị khoảng là các phép đo liên tục của các thang đo tuyến tính, thô. Ví dụ: trọng lượng, chiều cao, chiều ngang, chiều dọc, tuổi, nhiệt độ thời tiết.  Một nhóm các độ đo khoảng cách phổ biến cho biến tỉ lệ theo khoảng là khoảng cách Minkowski. d (i, j ) = q (| xi1 − x j1 | q + | xi 2 − x j 2 | q +...+ | xip − x jp | q ) + Với i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là các đối tượng dữ liệu p-chiều và q là số nguên dương  Nếu q = 1, độ đo khoảng cách là Manhattan d (i, j) = x −x | +| x −x | +...+| x −x | | i1 j1 i2 j2 ip jp  Nếu q = 2, độ đo khoảng cách là khoảng cách Euclidean d (i, j) = (| x − x |2 + | x − x |2 +...+ | x − x |2 ) i1 j1 i2 j 2 ip jp Các biến nhị phân (1)  Biến nhị phân chỉ có hai trạng thái là 0 hay 1  Bảng contingency table cho dữ liệu nhị phân: Subject j
  4. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang 1 0 sum a +b 1 a b c +d Subject i 0 c d a +c b +d sum p  Hệ số Jaccard coefficient (tương tự không bất biến, nếu biến nhị phân là bất đối xứng): − Biến nhị phân đối xứng và bất đối xứng Một biến nhị phân là đối xứng nếu đồng thời các trạng thái của nó có tầm quan o trọng như nhau và mang cùng một trọng số. Do đó, không có sự ưu tiên khi kết quả đưa ra phải được mã hoá là 0 hoặc 1. Ví dụ thuộc tính giới tính có 2 tr ạng thái là male và female. Tính tương tự giữa các biến nhị phân đối xứng được gọi là tính tương tự bất biến, trong đó kết quả không thay đổi khi 1 hoặc tất cả các biến nhị phân được mã hoá khác nhau. Với các tính giống nhau bất biến, một hệ số được biết đến nhiều nhất để xác định sự khác nhau giữa đối tượng i và j là hệ số đối sánh đơn giản, được định nghĩa như sau: b+c d (i, j ) = a +b+c +d Một biến nhị phân là - không đối xứng nếu các kết quả của các trạng thái không có tầm quan trọng như nhau. Chẳng hạn kết quả âm tính và dương tính khi khám bệnh. Theo thói quen, chúng ta sẽ mã hoá kết quả quan trọng nhất, thường là kết quả ít xẩy ra bằng 1 (HIV dương tính) và bằng 0 cho kết quả khác (HIV âm tính). Tính tương tự giữa các biến này được gọi là tương tự không bất biến. Với sự tương tự không bất biến, hệ số được biết đến nhiều nhất là hệ số Jaccard trong đó số phép so sánh phủ định coi như không quan trọng và do đó được bỏ qua khi tính toán. b+c d (i , j ) = a+b+c Ví dụ: Bảng hồ sơ bệnh nhân
  5. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Name(tên) Gender(giới Fever(ho) Cough(sốt Test-1 Test-2 Test-3 Test-4 tính) ) Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N Có 8 thuộc tính Name, Gender, Fever, Cough, Test-1, Test-2, Test-3, Test-4 trong đó: Gender là thuộc tính nhị phân đối xứng  Các thuộc tính còn lại là nhị phân bất đối xứng  Ta gán các trị Y và P bằng 1 và trị N được gán bằng 0. Tính khoảng cách giữa các bệnh nhân dựa vào các bất đối xứng dùng hệ số Jacard ta có bảng giá trị như sau: name Fever Cough Test-1 Test-2 Test-3 Test-4 Jack 1 0 1 0 0 0 Marry 1 0 1 0 1 0 Jim 1 1 0 0 0 0 + Tính d(Jack,Marry): • Bảng dữ liệu dạng nhị phân:
  6. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Marry sum 1 0 Jack 1 2 0 2 0 1 3 4 sum 3 3 6 Từ bảng ta có:a=2, b=0, c=1, d=3 0 +1 D(Jack,Marry): 2 + 0 + 1 =0.33 + Tính:d(Jack,Jim): Bảng dữ liệu nhị phân: Jim 1 0 sum Jack 1 1 1 2 0 1 3 4 sum 2 4 6
  7. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Từ bảng ta có : a=2, b=1, c=2, c=3 1+1 D(jack,jim)= 1 + 1 + 1 =0.67 + Tính d(jim,marry): Bảng dữ liệu nhị phân: mary 1 0 sum Jim 1 1 1 2 0 2 2 4 sum 3 3 6 từ bảng: a=1, b=1, c=2 1+ 2 d(jim,marry)= =0,75 1+1+ 2 Như vậy, theo tính toán trên Jim và Marry có khả năng mắc bệnh giống nhau nhiều nhất vì d(jim, marry)=0.75 là lớn nhất. Các biến định danh ( nominal variables) Định nghĩa: Biến định danh là mở rộng của biến nhị phân với nhiều hơn hai trạng thái. Ví dụ: thuộc tính màu sắc: đỏ, vàng, xanh, lục. Có hai phương pháp để tính toán sự tương tự giữa hai đối tượng: • Phương pháp 1: Đối sánh đơn giản với m là số lần đối sáng, p là tổng số các biến p−m d (i , j ) = p
  8. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang • Phương pháp 2: Dùng một số lượng lớn các biến nhị phân. Tạo biến nhị phân mới cho từng trạng thái định danh.  Các biến thứ tự :có thể là liên tục hay rời rạc Thứ tự của các trị là quan trọng, ví dụ hạng.  Có thể xử lý như tỉ lệ khoảng như sau:  - Thay thế xif bởi hạng của chúng - ánh xạ phạm vi của từng biến vào đoạn [0,1] bằng cách thay thế đối tượng i trong biến thứ f bởi rif ∈ {1,..., M f } - Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo khoảng rif − 1 z if = M f −1 Các biến thang đo tỉ lệ Định nghĩa: Là các biến có độ đo dương trên thang phi tuyến, xấp xỉ thang đo mũ. Ví dụ: AeBt hay Ae-Bt. Các phương pháp tính độ tương tự: Xử lý chúng như các biến thang đo khoảng  áp dụng các biến đổi logarithmic  Xử lý chúng như dữ liệu thứ tự liên tục  Xử lý chúng theo hạng như thang đo khoảng.  Các biến có kiểu hỗn hợp Một cơ sở dữ liệu có thể chứa đồng thời cả sáu loại biến. Khi đó có thể dùng công thức được gán trọng để kết hợp các hiệu quả:
  9. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang ∑δd p (f) (f) ij ij f =1 với δ ij = 0 nếu xif hoặc xjf missing d (i , j ) = f ∑δ p (f) ij f =1 hoặc xif =xjf =0 trường hợp khác δ ij = 1 f Đóng góp của biến f vào khoảng cách d(i,j):  Nếu f là biến nhị phân hay định danh: - d ij f ) = 0 nếu xif =xjf ( các trường hợp khác d ij = 1 (f) Nếu f là dựa trên khoảng cách: dùng khoảng cách được chuẩn hoá. - Nếu f là thứ tự thang đo tỉ số tính các hạng r if và xử lý zif như thang đo khoảng - rif − 1 z if = M f −1 Các biến tỉ lệ o Độ đo dương trên thang phi tuyến, xấp xỉ thang đo mũ o Ví dụ AeBt hay Ae-Bt o Các phương pháp: xử lý chúng như các biến thang đo khoảng không phải là lựa chọn tốt ! áp dụng biến đổi logarithmic yif = log(xif) xử lý chúng như dữ liệu thứ tự liên tục và xử lý chúng theo hạng như thang đo khoảng Các biến có kiểu hỗn hợp o CSDL Có thể chứa cả sáu loại biến o Có thể dùng công thức được gán trọng để kết hợp các hiệu quả: Σ p = 1δ ij f )dij f ) ( ( d (i, j) = f δ Σp o ( f ) δ (f) = 0 if xfif = 1 rij xjf is missing, ij or xif = xjf = 0; (f) otherwise δ ij = 1
  10. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Đóng góp của biến f vào khoảng cách d(i,j): Nếu f là biến nhị phân hay định danh: - d ij f ) = 0 nếu xif =xjf ( các trường hợp khác d ij = 1 (f) Nếu f là dựa trên khoảng cách: dùng khoảng cách được chuẩn hoá. - Nếu f là thứ tự thang đo tỉ số tính các hạng r if và xử lý zif như thang đo khoảng - rif − 1 z if = M f −1 Các kiểu dữ liệu phức tạp Tất cả các đối tượng được xem xét a trong KPDL là không quan hệ => Loại dữ liệu phức tạp Ví dụ về loại dữ liệu như vậy là dữ liệu không gian, dữ liệu đa phương tiện, dữ liệu di truyền, dữ liệu văn bản, dữ liệu chuỗi thời gian, dữ liệu văn bản và dữ liệu được thu gom từ World-Wide Web Các độ đo tương tự và bất tương tự thường hoàn toàn khác nhau ứng với các loại dữ liệu trên III. Các phương pháp gom cụm (clustering) chính yếu  Các phương pháp phân cấp  Các phương pháp dựa trên phân hoạch III.1 Phương pháp phân cấp ( Hierachical methods): Phân cấp: Tạo phân cấp cụm chứ không phải phân hoạch các đối tượng. Khác với phân hoạch, phân cấp không cần số cụm k ở đầu vào và dùng ma trận khoảng cách làm tiêu chuẩn gom cụm. Trong phương pháp phân cấp có thể dùng điều kiện dừng. Ví dụ: số cụm.
  11. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Cây các cụm Phân cấp cụm thường được biểu diễn dưới dạng cây của các cụm. Trong đó: Các lá của cây biểu diễn từng đối tượng - Các nút trong biểu diễn các cụm - Có hai phương pháp tạo cây phân cấp: từ trên xuống và tù dưới lên: Phương pháp phân cấp từ trên xuống: Bắt đầu từ cụm lớn nhất chứa tất cả các đối tượng. Chia cụm phân biệt nhất thành các cụm nhỏ hơn và tiếp diễn cho đến khi có n cụm thoả mãn điều kiện dừng. a ab b abcde c cde d de e Phân chia- divisive ân divisive Step 3 Step 2 Step 1 Step 0 Step 4 Phương pháp từ dưới lên: Các bước thực hiện: B1: Tạo n nhóm, mỗi nhóm gồm một đối tượng và lập ma trận khoảng cách cấp n. B2:Tìm 2 nhóm u,v có khoảng cách nhỏ nhất (duv) B3: Gộp nhóm u với nhóm v. Ký hiệu nhóm mới là (uv). Lập ma trận khoảng cách mới bằng cách: + Loại các hàng và cột tương ứng với các nhóm u,v
  12. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang +Thêm một hàng và một cột để lưu khoảng cách của nhóm uv với các nhóm còn lại B4: Lặp lại các bước 2 và bước 3 cho đến khi chọn được k nhóm thích hợp nhất cho bài toán hoặc chỉ có một nhóm duy nhất. Phương pháp này đưa tới bài toán nhỏ hơn : Tìm khoảng cách giữa hai nhóm  Các phương pháp tính khoảng cách giữa hai nhóm là: 1. Phương pháp kết nối đơn: Trong phương pháp kết nối đơn điều kiện ở đây là khoảng cách giữa hai cụm là khoảng cách ngắn nhất từ một thành viên của nhóm tới thành viên của nhóm khác. d(C1,C2) = min(drs), với r thuộc C1; s thuộc C2 (*) Ví dụ: Cho 5 đối tượng.Với khoảng cách giữa các đối tượng được cho như sau: d(1,2) =2, d(1,3)=6, d(1,4)=10, d(1,5)=9, d(2,3)=5, d(2,4)=9, d(2,5)=8, d(3,4)=4, d(3,5)=5, d(4,5)=3. ma trận khoảng cách của 5 đối tưọng là D như sau: 0 2 6 10 9 D= 20598 65045 10 9 4 0 3 98530 B1: Ta xây dựng 5 nhóm và lập ma trận khoảng cách giữa 5 nhóm này là D=D1 B2: Khoảng cách giữa 2 nhóm 1 và 2 nhỏ nhất là 2. B3: Ta sẽ gộp nhóm 1 và 2 thành một nhóm.. Khi đó ta sẽ cập nhật l ại ma tr ận khoảng cách mới là D1 + xoá cột 1 và dòng 1 của nhóm 1. Xoá cột 2 và dòng 2 của nhóm 2. + Để thêm một cột và một dòng đẻ lưư khoảng cách của nhom (12) đến các nhóm còn lại ta tính theo công thức (*) .
  13. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang D(12,3)= min(drs) với r thuộc nhóm (12), và s thuộc nhóm 3. D(1,3)=6, d(2,3)=5. vậy nên d(12,3)=5. Hoàn toàn tương tự ta tính được d(12,5)=8, d(12,4)=9. Khi đó ta thu được ma trận khoảng cách mới D1 là 0598 D1= 5045 9 403 8 530 B4: Lặp lại bước 2, khoảng cách của nhóm 5 và nhóm 4 là nhỏ nhất d(5,4)=3 - - Lặp lại bước 3, Ta sẽ gộp nhóm 4 và 5 thành một nhóm.. Khi đó ta sẽ cập nhật lại ma trận khoảng cách mới là D2 + xoá cột 4 và dòng 4 của nhóm 4. Xoá cột 5 và dòng 5 của nhóm 5 + Thêm một dòng và một cột để lưư khoảng cách c ủa nhóm (45) t ớ các nhóm khác. Ta tính theo công thức (*) D(45, 12)=min(drs) với r thuộc (45), s thuộc (12) D(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8. vậy d(45,12)=8. Hoàn toàn tương tự ta tính đựoc d(45,3)=4. Khi đó ta thu được ma trận khoảng cách mới D2 là: 058 D2 = 504 84 0 - Lặp lại bước 2: d (45,3)= 4 là nhỏ nhất
  14. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang - Lặp lại bước 3: ta gộp nhóm (45) và nhóm 3 thành một nhóm. Cập nhật ma tr ận khoảng cách mới là D3. + Xoá dòng và cột của nhóm (45), xoá dòng và cột của nhóm 3 + Thêm một dong f và một cột đẻ lưư khoảng cách của nhóm mơid này đến các nhóm khác ta sẽ tính khoảng cách theo công thức (*) D(345,12)= min( drs) với r thuộc (345) và s thuộc(12). D(3,1)=6, d(3,2)=5, d(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8. vậy d(345,12)=5. Ta thu được khoảng cách mới là D3 là: 05 D3= 50 Cuối cùng nhóm thu đựoc sẽ là nhóm (12543) Sơ đồ mô tả các bước: B0 B1 B2 B3 B4 1 1 12345 2 2 3 345 4 4 5 5
  15. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang 2.Phương pháp kết nối đầy đủ: d(C1,C2) = max(drs), với r thuộc C1; s thuộc C2. 3.Phương pháp kết nối trung bình: Khoảng cách giữa một cluster này và một cluster khác là tương đ ương khoảng cách trung bình từ một vài thành viên của một nhóm này đến một vài thành viên của nhóm khác. n1 n2 1 ∑∑( drs ) Với r thuộc C1, s thuộc C2. D (C1, C 2) = n1n 2 r= s= 1 1 Đánh giá: Các phương pháp phân cấp có ưu điểm lớn là: khái niệm đơn giản, lý thuyết tốt. - Khi cụm được trộn tách, quyết định là vĩnh cửu, vì vậy số các phương án khác cần xem xét bị rút giảm. - Điểm yếu của phương pháp phân cấp: Do việc trộn tách các cụm là vĩnh cửu nên quyết định sai là không thể khắc phục được. Các phương pháp phân chia cần thời gian tính toán và không thể scalable cho tập dữ liệu lớn III.2 Các phương pháp dựa trên phân hoạch a. Mô tả phương pháp Cho một cơ sở dữ liệu D chứa n đối tượng, tạo phân hoạch thành tập có k cụm sao cho: - Mỗi cụm chứa ít nhất một đối tượng - Mỗi đối tượng thuộc về một cụm duy nhất
  16. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang - Cho trị k, tìm phân hoạch có k cụm sao cho tối ưu hoá tiêu chuẩn phân hoạch được chọn. b. Các phương pháp b.1.Phương pháp gom cụm k-mean Input: Số các cụm k cần gom và cơ sở dữ liệu chứa n đối tượng. Output: k cụm đã được gom. Thuật giải: gồm 4 bước - Bước1: Phân hoạch đối tượng thành k tập con ( cụm) ngẫu nhiên. - Bước 2: Tính các tâm ( trung bình của các đối tượng trong cụm) cho từng c ụm trong phân hoạch hiện hành. - Bước 3: Gán mỗi đối tượng cho cụm tâm gần nhất - Bước 4: Nếu cụm không có sự thay đổi thì dừng, ngược lại quay lại bước 2..
  17. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Ví dụ về thuật toán k-mean, n=10, k=2 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 10 9 10 8 9 7 8 6 7 5 6 4 5 3 4 2 3 2 1 1 0 0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 Bước 2: Để xác định các điểm hạt giống ta đi tìm toạ độ của nó bằng cách tính hoành độ và tung độ trung bình. Gọi ( x1 , y1 ), ( x 2 , y 2 ) là toạ độ của 2 điểm hạt giống. Ta có: 3+3+3+ 4+ 4+5 x1 = = 3.67 6 1+ 4 + 5 + 6 + 7 + 8 y1 = =5.17 6 5+7+7+8 x2 = = 6.75 4 3+ 4+5+5 y2 = = 4.25 4
  18. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Bước 3: Tính khoảng cách từ các centroid đến các điểm Toạ độ các Khoảng cách đến Khoảng cách đến Thuộc Thuộc STT điểm cụm 1 cụm 2 centroid 1 (3.67, 5.17) centroid 2 (6.75, 4.25) 1 (5,1) 4.2 3.62 x 2 (7,3) 3.86 1.24 x 3 (3,4) 1.22 3.71 x 4 (7,4) 3.45 0.36 x 5 (4,5) 0.30 2.82 x 6 (5,5) 1.30 1.88 x 7 (8,5) 4.30 1.52 x 8 (3,6) 1.22 4.12 x 9 (4,7) 2.02 3.89 x (3,8) 3,08 5.3 x Bước 4: Các đối tượng trong các cụm có sự thay đổi nên quay lại bước 2. Bước 2: Tính toạ độ các điểm centroid mới 3+3+3+ 4+ 4+5 x1 = = 3.67 6 4+5+5+6+7+8 y1 = =5.83 6 5+7+7+8 x2 = = 6.75 4 1+ 3 + 4 + 5 y2 = = 3.25 4 Bước 3: Tính khoảng cách từ các centroid đến các điểm Toạ độ Khoảng cách đến Khoảng cách đến Thuộc Thuộc STT các điểm cụm 1 cụm 2 centroid 1 (3.67, 5.17) centroid 2 (6.75, 4.25) 1 (5,1) 5.00 2.85 x 2 (7,3) 4.37 0.35 x 3 (3,4) 1.95 3.82 x 4 (7,4) 3.80 0.79 x 5 (4,5) 0.44 2.82 x 6 (5,5) 1.57 2.47 x 7 (8,5) 4.4 2.15 x 8 (3,6) 0.69 4.65 x 9 (4,7) 1.21 4.65 x 10 (3,8) 2.17 6.05 x
  19. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang Nhận xét: Sau khi thực hiện bước 3 các cụm không có sự thay đổi nên dừng tại đây. Điểm mạnh của phương pháp gom cụm k- means  Hiệu suất tương đối: O(nkt) với n là số đối tượng, k là số cụm, t là số lần l ặp. - Thông thường k, t
  20. Bài tập chuyên đề Datamining_nhóm 2 GVHD: Nguyễn Hương Giang
nguon tai.lieu . vn
Thạc sĩ - Tiến sĩ - Cao học Công nghệ thông tin Kinh tế - Thương mại Tài chính - Ngân hàng Kiến trúc - Xây dựng Điện-Điện tử-Viễn thông Cơ khí - Chế tạo máy Công nghệ - Môi trường Báo cáo khoa học Quản trị kinh doanh Khoa học xã hội Khoa học tự nhiên Nông - Lâm - Ngư Y khoa - Dược