LOGO
THUẬT TOÁN K-MEAN VỚI BÀI
TOÁN PHÂN CỤM DỮ LIỆU

Danh sách nhóm:
1.Nguyễn Thị Ngọc Hà
2.Nguyễn Thị Ngọc Quỳnh
3.Trần Thị Hồng Nhung
4.Nguyễn Hữu Quang
5.Huỳnh Bá thùy Trinh
NỘI DUNG
I. PHÂN CỤM DỮ LIỆU
II. THUẬT TOÁN K-MEAN
III. GIỚI THIỆU WEKA VÀ BÀI TOÁN ỨNG DỤNG
2
I.PHÂN CỤM DỮ LIỆU
1. Định nghĩa:

Phân cụm dữ liệu (PCDL) là các qui trình tìm cách
nhóm các đối tượng đã cho vào các cụm, sao cho các
đối tượng trong cùng 1 cụm tương tự nhau và các đối
tượng khác cụm thì không tương nhau.

PCDL nhằm khám phá cấu trúc của mẫu dữ liệu để
thành lập các nhóm dữ liệu từ tập dữ liệu lớn, nó cho
phép người ta đi sâu vào phân tích và nghiên cứu cho
từng cụm dữ liệu này nhằm khám phá và tìm kiếm các
thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết
định
3
MỤC ĐÍCH

phố
Địa lý
Bảo hiểm
Sinh học
5
3.CÁC YÊU CẦU PCDL TRONG KHAI PHÁ DỮ
LIỆU

Có khả năng mở rộng tập dữ liệu

Khả năng làm việc với các kiểu dữ liệu 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 nhiều chiều.

Dễ hiểu, có thể diễn dịch và khả dụng

Khả năng làm việc với dữ liệu có chứa nhiễu ( outliers)

Ít nhạy cảm với thứ tự các bản ghi nhập vào
6
7
Phân cụm dựa trên mô hình
Phân cụm dựa trên lưới
Phân cụm dựa trên mật độ
Phân cụm phân cấp
Phân cụm phân hoạch
Phân cụm có ràng buộc
4. PHÂN LOẠI

như : CURE, BIRCH
9
Phân cụm phân cấp

Cây phân cụm có thể được xây dưng theo 2 phương
pháp sau:

Phương pháp Bottom up ( từ dưới lên): Thay thế
từng đối tượng trong cụm của nó. Trộn theo từng
bước hai cụm giống nhau nhất cho đến khi chỉ còn
một cụm hay thoả mãn điều kiện thì dừng.

Phương pháp Top- down ( 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.
10
Phân cụm dữ liệu dựa trên mật độ

Phương pháp này nhóm các đối tượng theo hàm mật đ
ộ xác định. Theo phương pháp này các điểm có mật
độ cao hơn sẽ ở cùng một cụm.

Đặc trưng của phương pháp:
- Phát hiện ra các cụm có hình dạng bất kì.
- Phát hiện nhiễu.

Một số thuật toán PCDL dựa trên mật độ điển hình
như: DBSCAN, OPTICS, DENCLUE, …
11


K-Means là thuật toán thuộc phương pháp phân
hoạch dữ liệu, nó rất quan trọng và được sử dụng
phổ biến trong kỹ thuật phân cụm.

Tư tưởng chính của thuật toán :

Tìm cách phân nhóm các đối tượng (objects) đã
cho vào K cụm (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 tâm nhóm (centroid ) là nhỏ nhất.
14
2. Phần tử trung tâm

Với k phần tử trung tâm (k nhóm) ban đầu được chọn ngẫu
nhiên, sau mỗi lần nhóm các đối tượng vào các nhóm, phần tử
trung tâm được tính toán lại.

Clusteri = {a
1
, a
2
a
t
} – Nhóm thứ i
i=1 k, k:số cluster
j= 1 m, m:số thuộc tính
t - số phần tử hiện có của nhóm thứ i

nhóm j , c
j
được tính toán dựa trên công thức:
Trong đó:
∂
ji
- khoảng cách Euclidean từ a
i
đến c
j
x
is
- thuộc tính thứ s của đối tượng a
i
x
js
- thuộc tính thứ s của phần tử trung tâm c
j
16
Thuật toán K-Means thực hiện qua các bước chính sau:

Bước 1: Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster).
Mỗi cụm được đại diện bằng các tâm của cụm.

Bước 2: Tính khoảng cách giữa các đối tượng (objects) đến K
tâm (thường dùng khoảng cách Euclidean)

Bước 3: Nhóm các đối tượng vào nhóm gần nhất

Bước 4: Xác định lại tâm mới cho các nhóm

Điều kiện khởi tạo có ảnh hưởng lớn đến kết quả. Điều
kiện khởi tạo khác nhau có thể cho ra kết quả phân
vùng nhóm khác nhau.

Không xác định được mức độ ảnh hưởng của thuộc tính
đến quá trình tạo nhóm.
5. Ưu, nhược điểm của thuật toán K-mean:
20
III. GIỚI THIỆU WEKA VÀ BÀI TOÁN
ỨNG DỤNG
1. Giới thiệu phần mềm WEKA
2. Bài toán ứng dụng phân cụm dữ liệu trong
WEKA
21
1. Giới thiệu phần mềm WEKA

là một công cụ phần mềm viết bằng Java, phục vụ lĩnh
vực máy học và khai phá dữ liệu.
•
Weka cung cấp nhiều giải thuật khác nhau với nhiều phương
thức cho quá trình xử lý để ước lượng kết quả bằng sơ đồ cho
bất kì một dữ liệu nào.
22
1. Giới thiệu phần mềm WEKA
Trong phần mềm Weka,Explorer có 6 phần:

Preprocess: Tiền xử lý dữ liệu.

Classify: Tạo ra những chương trình để phân loại.


6. hours.hrs [35 40] : number of working hours during week
7. Pension [none, ret_allw, empl_contr] : employer contributions to
pension plan
8. stby_pay[2 25] : standby pay
9. shift_diff [1 25] : shift differencial : supplement for work on II
and III shift

25
THÔNG TIN THUỘC TÍNH