Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán phân cụm, phân lớp dữ liệu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN MINH TÂM NGHI N U M T THU T TO N PHÂN M PHÂN P I U V NG NG

U N VĂN THẠ Ĩ KHOA HỌ M Y TÍNH

THÁI NGUYÊN - 2019

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN MINH TÂM NGHI N U M T THU T TO N PHÂN M PHÂN P I U V NG NG Chuyên ngành: Khoa học máy tính Mã số: 84 80 101

U N VĂN THẠ Ĩ KHOA HỌ M Y TÍNH

Người hướng dẫn khoa học: TS. NGUYỄN VĂN NÚI THÁI NGUYÊN - 2019

LỜI CẢM ƠN

Em xin chân thành cảm ơn Trƣờng Đại học Công nghệ Thông tin và

Truyền thông – Đại học Thái Nguyên đã tạo điều kiện cho em thực hiện luận

văn này.

Em xin gửi lời cảm ơn sâu sắc tới thầy giáo TS. Nguyễn Văn Núi, Bộ

môn công nghệ phần mềm - Trƣờng Đại học Công nghệ Thông tin và Truyền

thông - Đại học Thái Nguyên đã trực tiếp hƣớng dẫn em trong quá trình thực

hiện luận văn.

Em cũng xin gửi lời cảm ơn tới các thầy, cô đã có những ý kiến đóng

góp bổ ích và đã tạo mọi điều kiện tốt nhất cho em trong suốt thời gian thực

hiện luận văn. Xin cảm ơn các bạn học đồng khóa đã thƣờng xuyên động

viên, giúp đỡ tôi trong quá trình học tập.

Cuối cùng, em xin gửi lời cảm ơn đến gia đình và đồng nghiệp vì sự ủng

hộ và động viên đã dành cho em trong suốt quá trình học tập cũng nhƣ thực

hiện luận văn này.

Thái Nguyên, tháng 05 năm 2019

Học viên

Nguyễn Minh Tâm

LỜI CAM ĐOAN

Em xin cam đoan về nội dung đồ án tốt nghiệp với tên đề tài “ Nghi

cứu t số thu t t h cụ h dữ i u v ứ g dụ g” không

sao chép nội dung từ các luận văn khác, hay các sản phẩm tƣơng tự mà không

phải do em làm ra. Sản phẩm luận văn là do chính bản thân em tìm hiểu và

xây dựng nên.

Nếu có gì sai em xin chịu mọi hình thức kỷ luật của Trƣờng Đại học

Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên.

Thái Nguyên, tháng 05 năm 2019

Học viên

Nguyễn Minh Tâm

MỤC LỤC

LỜI CẢM ƠN ............................................................................................................... 1

LỜI CAM ĐOAN ......................................................................................................... 2

MỞ ĐẦU ........................................................................................................................ 7

CHƢƠNG 1 TỔNG QUAN.......................................................................................... 9

1.1 Giới thiệu chung ....................................................................................... 9

1.2 Các bƣớc trong khai phá dữ liệu ............................................................ 10

1.3 Các kỹ thuật áp dụng trong khai phá dữ liệu ......................................... 12

1.4 Ứng dụng của khai phá dữ liệu .............................................................. 14

1.5 Những thách thức trong khai phá dữ liệu .............................................. 15

CHƢƠNG 2 PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN .. 17

2.1 Định nghĩa về phân cụm dữ liệu ............................................................ 17

2.2 Mục tiêu của phân cụm dữ liệu .............................................................. 18

2.3 Bài toán phân cụm dữ liệu ..................................................................... 20

2.4 Một số kiểu dữ liệu ................................................................................ 20

2.5 Một số kỹ thuật phân cụm dữ liệu ......................................................... 23

2.5.1 Phương pháp phân cụm dữ liệu dựa trên phân cụm phân cấp ....... 23

2.5.2 Phương pháp phân cụm dữ liệu dựa trên mật độ ............................ 25

2.5.3 Phương pháp phân cụm phân hoạch ............................................... 29

2.6 Kết luận .................................................................................................. 33

CHƢƠNG 3 PHÂN LỚP DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN ........... 34

3.1 Định nghĩa về phân lớp dữ liệu .............................................................. 34

3.2 Các vấn đề quan tâm của phân lớp dữ liệu ............................................ 34

3.2.1 Quá trình phân lớp dữ liệu: ............................................................. 34

3.2.2 So sánh các phương pháp phân lớp ................................................. 36

3.3 Phân lớp bằng cây quyết định ................................................................ 36

3.3.1 Khái niệm về cây quyết định ............................................................ 36

3.3.2 Ưu, nhược điểm của cây quyết định ................................................ 39

3.3.3 Một số thuật toán của cây quyết định .............................................. 40

3.4 Phân lớp bằng Bayesian ......................................................................... 48

3.5 Phân lớp dựa trên sự kết hợp ................................................................. 51

3.5.1 Các khái niệm quan trọng về luật kết hợp ....................................... 51

3.5.2 Một số thuật toán về luật kết hợp .................................................... 52

3.6 Độ chính xác classifier ........................................................................... 57

3.7 Kết luận .................................................................................................. 59

CHƢƠNG 4 MỘT SỐ KẾT QUẢ THỬ NGHIỆM ................................................. 60

4.1. Giới thiệu về công cụ phân cụm, phân lớp dữ liệu Weka ..................... 60

4.2. Ứng dụng phân cụm dữ liệu để phân nhóm khách hàng ...................... 62

4.3. Ứng dụng phân lớp dữ liệu để phân lớp ............................................... 68

4.3.1. Phân lớp dữ liệu với thuật toán Apriori ......................................... 68

4.3.2. Phân lớp dữ liệu với thuật toán Naive Bayes ................................. 71

KẾT LUẬN .................................................................................................................. 75

TÀI LIỆU THAM KHẢO ........................................................................................... 76

Tiếng Việt: ................................................................................................... 76

Tiếng Anh: ................................................................................................... 76

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Các bƣớc trong khai phá dữ liệu ..................................................... 10

Hình 2.1. Mô phỏng vấn đề phân cụm dữ liệu ................................................ 17

Hinh 2.2. Cụm dữ liệu đƣợc khám phá bởi giải thuật DBSCAN ................... 26

Hinh 2.3. Thứ tự phân cụm các đối tƣợng theo OPTICS ............................... 29

Hinh 2. 4. Phân cụm dựa trên phƣơng pháp k-means ..................................... 31

Hình 4. 1. Giao diện chính của phần mềm ...................................................... 61

Hình 4.2. Thông tin dữ liệu cơ bản của file bank-k.arff hiển thị bởi Weka ... 63

Hình 4.3. Lƣu đồ thuật toán K-Means ............................................................ 64

Hình 4.4. Bảng tham số sử dụng cho thuật toán K-Means: Hình (a) K=3; Hình

(b): K=5 ........................................................................................................... 65

Hình 4.5. Kết quả phân cụm với thuật toán K-Means (K=3) ......................... 66

Hình 4.6. Kết quả phân cụm với thuật toán K-Means (K=5) ......................... 67

Hình 4.7. Giao diện Weka chọn thuật toán Apriori ........................................ 68

Hình 4.8. Giao diện Weka thiết lập tham số cho thuật toán Apriori .............. 69

Hình 4.9. Kết quả sinh luật bởi thuật toán Apriori ......................................... 70

Hình 4.10. Giao diện Weka lựa chọn thuật toán Naive Bayes ....................... 71

Hình 4.11. Kết quả sinh luật bởi thuật toán Naive Bayes ............................... 72

Hình 4.12. Giao diện Weka lựa chọn thuật toán C4.5 .................................... 73

Hình 4.13. Kết quả sinh luật bởi thuật toán C4.5 ............................................ 74

DANH MỤC CÁC TỪ VIẾT TẮT

STT Từ viết tắt Viết đầy đủ Ghi chú

1 PLDL Phân lớp dữ liệu

2 CSDL Cơ sở dữ liệu

3 KPDL Khai phá dữ liệu

4 AGNES Agglomerative Nesting Thuật toán tích đống lồng

5 BIRCH Blanced Iterative Reducing and Clustering using Hỉeachies

6 CF Clustering Feature Đặc trƣng của phân cụm

7 DBSCAN

8 OPTICS Density Based Spatial Clustering of Application with Noise Ordering Point to Identify the Clustering Structure

9 PAM Partitioning Around Medoids

10 ID3 Interative Decision 3

11 NBC Native Bayes Classification Phân lớp dữ liệu Naive Bayes

12 FP Frequent Pattern Mẫu thƣờng xuyên

MỞ ĐẦU

Trong thời gian gần đây, sự phát triển mạnh mẽ của công nghệ thông tin,

thƣơng mại điện tử vào nhiều lĩnh vực của đời sống, kinh tế xã hội đã sinh ra

một lƣợng dữ liệu lƣu trữ khổng lồ. Sự bùng nổ này đã dẫn tới một nhu cầu

cấp thiết cần có những kỹ thuật và công cụ để tự động chuyển đổi dữ liệu

thành các tri thức có ích mà các phƣơng pháp quản trị và khai thác cơ sở dữ

liệu truyền thống không còn đáp ứng đƣợc nữa. Trong những khuynh hƣớng

kỹ thuật mới có kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD –

Knowledge Discovery and Data Mining). Nhƣng để có thể khai phá dữ liệu

một cách hiệu quả và chính xác, ta cần có những mô hình toán học, các giải

thuật đáp ứng đƣợc điều đó. Vì vậy, trong luận văn này có trình bày một số

vấn đề về phân cụm, phân lớp dữ liệu một trong những kỹ thuật cơ bản để

khai phá dữ liệu nhƣng lại đƣợc sử dụng rộng rãi và đem lại hiệu quả cao.

Bố cục của lu vă

Nội dung chính của luận văn đƣợc chia thành 4 chƣơng nhƣ sau:

Chương 1. Tổng quan: Chƣơng này giới thiệu một cách tổng quát về quá trình

phát hiện tri thức nói chung và khai phá dữ liệu nói riêng. Đặc biệt, chƣơng

trình còn liệt kê một số điểm chính về ứng dụng cũng nhƣ thách thức của khai

phá dữ liệu và phát hiện tri thức.

Chương 2. Phân cụm dữ liệu và một số thuật toán cơ bản: Chƣơng này trình

bày các nội dung chính liên quan đến phân cụm dữ liệu. Một số thuật toán

phân cụm dữ liệu cơ bản cũng đƣợc trình bày chi tiết trong chƣơng này.

Chương 3. Phân lớp dữ liệu và một số thuật toán cơ bản: Chƣơng này trình

bày các nội dung chính liên quan đến phân lớp dữ liệu và ứng dụng. Một số

thuật toán phân lớp dữ liệu bao gồm: ID3, C.4.5, Naive Bayes, Apriori, …

cũng sẽ đƣợc trình bày chi tiết trong chƣơng này.

Chương 4. Một số kết quả thử nghiệm: Chƣơng này trình bày và phân tích

một số kết quả thử nghiệm các thuật toán phân cụm, phân lớp dữ liệu cơ bản.

Kết quả phân tích chủ yếu đƣợc triển khai thực hiện dựa trên phần mềm

Weka (Waikato Environment for Knowledge Analysis) - một bộ phần

mềm học máy đƣợc trƣờng Đại học Waikato, New Zealand phát triển

bằng Java. Weka là phần mềm tự do phát hành theo Giấy phép Công cộng

GNU, hiện đang đƣợc sử dụng rất rộng rãi bởi cộng đồng những ngƣời làm về

lĩnh vực khai phá dữ liệu và phát hiện tri thức.

CHƢƠNG 1

TỔNG QUAN

1.1 Gi i thi u chung

Sự phát triển của khoa học công nghệ và việc ứng dụng công nghệ thông

tin ở hầu hết các lĩnh vực trong nhiều năm qua cũng đồng nghĩa với lƣợng dữ

liệu đã đƣợc thu thập và lƣu trữ ngày càng lớn. Các hệ quản trị cơ sở dữ liệu

truyền thống cũng chỉ khai thác đƣợc một lƣợng thông tin nhỏ không còn đáp

ứng đầy đủ những yêu cầu, những thách thức mới. Do vậy các phƣơng pháp

quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng

đƣợc thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là kỹ thuật

phát hiện tri thức và khai phá dữ liệu. Tôi xin giới thiệu một cách tổng quan

về phát hiện tri thức và khai phá dữ liệu cùng một số kỹ thuật cơ bản để trong

khai phá dữ liệu để phát hiện tri thức và một số ứng dụng trong thực tế nhằm

hỗ trợ cho tiến trình ra quyết định.

Khai phá dữ liệu (Data Mining) hay có thể hiểu là phát hiện tri thức

(Knowledge Discovery) có rất nhiều khái niệm khác nhau nhƣng về cơ bản

đó là quá trình tự động trích xuất thông tin có giá trị (thông tin dự đoán -

Predictive Information) ẩn chứa trong lƣợng dữ liệu lớn trong thực tế. Nó

bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm

ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, nó liên quan đến

việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có

tính chính quy (regularities) trong tập dữ liệu. Khai phá dữ liệu là một tiến

trình sử dụng các công cụ phân tích dữ liệu khác nhau để khám phá ra các

mẫu dƣới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan hệ giữa các

dữ kiện, đối tƣợng bên trong cơ sở dữ liệu, kết quả của việc khai phá là xác

định các mẫu hay các mô hình đang tồn tại bên trong, nhƣng chúng nằm ẩn

khuất ở các cơ sở dữ liệu. Để từ đó rút trích ra đƣợc các mẫu, các mô hình hay

các thông tin và tri thức từ các cơ sở dữ liệu. Để hình dung rõ hơn Data

Mining là gì có thể hiểu đơn giản nó chính là một phần của quá trình trích

xuất những dữ liệu có giá trị tốt, loại bỏ dữ liệu giá trị xấu trong rất nhiều

thông tin trên Internet và các nguồn dữ liệu đang có.

1.2 C c bƣ c trong khai phá dữ li u

Qúa trình phát hiện tri thức gồm 6 giai đoạn [1] đƣợc thể hiện nhƣ hình

Hình 1.1. C c bƣ c trong khai phá dữ li u

Đầu vào là dữ liệu thô đƣợc lấy từ internet và đầu ra là các thông tin có

giá trị.

(1) Gom dữ liệu: Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai

phá dữ liệu. Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ

liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.

(2) Trích lọc dữ liệu: Ở giai đoạn này những tập dữ liệu cần đƣợc khai

phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định phục vụ mục

đích khai thác.

(3) Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu: Đối với dữ liệu thu

thập đƣợc, cần xác định các vấn đề ảnh hƣởng là cho nó không sạch. Bởi vì,

dữ liệu không sạch (những dữ liệu không đầy đủ, nhiễu, không nhất quán) thì

các tri thức khám phá đƣợc sẽ bị ảnh hƣởng và không đáng tin cậy, dẫn tới

các quyết định thiếu chính xác. Vậy, cần gán các giá trị thuộc tính còn thiếu,

sữa chữa các dữ liệu nhiễu, lỗi, xác định loại bỏ các giá trị ngoại lai, giải

quyết các mâu thuẫn dữ liệu. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ,

đƣợc rút gọn và đƣợc rời rạc hóa. Đây là một quá trình rất quan trọng vì dữ

liệu này nếu không đƣợc “làm sạch - tiền xử lý dữ liệu” thì sẽ gây nên những

kết quả sai lệch nghiêm trọng.

(4) Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu

đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lại nó, tức là dữ

liệu sẽ đƣợc chuyển đổi về dạng thuận lợi nhất nhằm phục vụ quá trình khai

phá ở bƣớc sau.

(5) Khai phá dữ liệu: Ở giai đoạn này nhiều thuật toán khác nhau đã

đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Đây là bƣớc áp dụng những kỹ

thuật phân tích (nhƣ các kỹ thuật của học máy) nhằm để khai thác dữ liệu,

trích chọn đƣợc những mẫu thông tin, những mối liên hệ đặc biệt trong dữ

liệu. Đây đƣợc xem là bƣớc quan trọng và tốn nhiều thời gian nhất của toàn

quá trình khai phá dữ liệu.

(6) Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, những mẫu

thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc

biến đổi và biểu diễn ở một dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây,

bảng biểu, luật,…

Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo

những tiêu chí nhất định.

Trên đây là 6 giai đoạn của quá trình phát hiện tri thức, trong đó giai

đoạn 5 khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn đƣợc

đánh giá là quan trọng nhất.

1.3 Các kỹ thu t áp dụng trong khai phá dữ li u

Đứng trên quan điểm của học máy, thì các kỹ thuật trong KPDL, bao

gồm:

Học có giám sát: Là quá trình gán nhãn cho các phần tử trong CSDL dựa

trên một tập các ví dụ huấn luyện và các thông tin về nhãn đã biết.

Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các

lớp hay cụm dữ liệu tƣơng tự nhau mà chƣa biết trƣớc các thông tin về lớp

hay tập các ví dụ huấn luyện.

Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp

dựa trên một tập nhỏ các ví dụ huấn luyện và các thông tin về một số nhãn lớp

đã biết trƣớc.

Nếu căn cứ vào lớp các bài toán cần giải quyết, thì KPDL bao gồm các

kỹ thuật áp dụng sau:

- Kĩ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất

hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kĩ thuật

này có thể liệt kê: phân cụm (clustering), tóm tắt (summerization), trực quan

hóa (visualization), phân tích sự phát hiện biến đổi và độ lệch, phân tích luật

kết hợp (association rules)...;

- Kĩ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đƣa ra các dự đoán dựa

vào các suy diễn trên dữ liệu hiện thời. Các kĩ thuật này gồm có: phân lớp

(classification), hồi quy (regression)...;

3 phƣơng pháp thông dụng nhất trong khai phá dữ liệu là: phân cụm dữ

liệu, phân lớp dữ liệu và khai phá luật kết hợp. Ta sẽ xem xét từng 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 cụm 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. Phân cụm dữ

liệu là một ví dụ của phƣơng pháp học không giám sát. Không giống nhƣ

phân loại dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trƣớc các

mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học

bằng quan sát (learning by observation), trong khi phân loại dữ liệu là học

bằng ví dụ (learning by example). Trong phƣơng pháp này bạn sẽ không thể

biết kết quả các cụm thu đƣợc sẽ nhƣ thế nào khi bắt đầu quá trình. Vì vậy,

thông thƣờng cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu

đƣợc. Phân cụm dữ liệu đƣợc sử dụng nhiều trong các ứng dụng về phân đoạn

thị trƣờng, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web…

Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ một bƣớc tiền xử lí

cho các thuật toán khai phá dữ liệu khác.

Phân lớp dữ liệu là xếp một đối tƣợng vào một trong những lớp đã biết

trƣớc. Ví dụ nhƣ phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hƣớng

tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định,

mạng nơron nhân tạo,... Phân lớp dữ liệu còn đƣợc gọi là học có giám sát.

Quá trình phân lớp dữ liệu thƣờng gồm 2 bƣớc xây dựng mô hình và sử dụng

mô hình để phân lớp dữ liệu.

Bƣớc 1: Một mô hình sẽ đƣợc xây dựng dựa trên việc phân tích các mẫu

dữ liệu sẵn có. Mỗi mẫu tƣơng ứng với một lớp, đƣợc quyết định bởi một

thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn đƣợc gọi là tập dữ

liệu huấn luyện (training data set). Các nhãn của tập dữ liệu huấn luyện đều

phải đƣợc xác định trƣớc khi xây dựng mô hình, vì vậy phƣơng pháp này còn

đƣợc gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là

học không có thầy (unsupervised learning).

Bƣớc 2: Sử dụng mô hình để phân lớp dữ liệu. Trƣớc hết chúng ta phải

tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận đƣợc, mô hình

sẽ đƣợc sử dụng để dự đoán nhãn cho các mẫu dữ liệu khác trong tƣơng lai.

Khai phá luật kết hợp (Association Rule Mining) là kỹ thuật rất quan

trọng trong lĩnh vực khai phá dữ liệu. Mục đích của việc khai phá luật kết hợp

là tìm ra các mối quan hệ, sự kết hợp hay mối tƣơng quan giữa các đối tƣợng

trong khối lƣợng lớn dữ liệu. Nói cách khác, thuật toán khai phá luật kết hợp

cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thƣờng

xuyên) nhƣ thế nào. Thuật toán này thực hiện thông qua 2 giai đoạn chính:

- Giai đoạn đầu là đi tìm các sự kiện xảy ra thƣờng xuyên.

- Giai đoạn hai là tìm luật.

1.4 Ứng dụng của khai phá dữ li u

Mặc dù còn rất nhiều vấn đề mà KPDL cần phải tiếp tục nghiên cứu để

giải quyết nhƣng tiềm năng của nó đã đƣợc khẳng định bằng sự ra đời của rất

nhiều ứng dụng. Các ứng dụng của KPDL trong khoa học cũng đƣợc phát

triển. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng

tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle tích hợp

các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đã đi tiên phong trong

việc phát triển các ứng dụng khai phá dữ liệu với các ứng dụng nhƣ

Intelligence Miner. Ta có thể đƣa ra một số ứng dụng trong các lĩnh vực nhƣ:

Ngân hàng: Xây dựng mô hình dự báo rủi ro tín dụng, tìm kiếm tri thức,

quy luật của thị trƣờng chứng khoán và đầu tƣ bất động sản.

Thƣơng mại điện tử: Công cụ tìm hiểu, định hƣớng, thúc đẩy, giao tiếp

với khách hàng, phân tích khách hàng duyệt web, phân tích hành vi mua sắm

trên mạng và cho biết thông tin tiếp thị phù hợp với từng loại khách hàng.

Thiên văn học: Hệ thống SKICAT do JPL/Caltech phát triển đƣợc sử

dụng cho các nhà thiên văn để tự động xác định các vì sao và các dải thiên hà

trong một bản khảo sát lớn để có thể phân tích và phân loại.

Sinh học phân tử: Hệ thống tìm kiếm các mẫu trong cấu trúc phân tử và

trong các dữ liệu gen.

Mô hình hóa những thay đổi thời tiết: các mẫu không gian, thời gian nhƣ

lốc, gió xoáy đƣợc tự động tìm thấy trong các tập lớn dữ liệu mô phỏng và

quan sát đƣợc.

1.5 Những thách thức trong khai phá dữ li u

Mặc dù khai phá dữ liệu mang lại nhiều lợi ích và lợi thế, tuy nhiên nó

vẫn gặp phải những thách thức cơ bản đó là những vấn đề sau đây:

- Cơ sở dữ liệu lớn: kích thƣớc của cơ sở dữ liệu đƣợc nhận biết thông

qua số lƣợng các mẫu tin, các thuộc tính (hay các biến) và các bảng, số lƣợng

có thể là hàng trăm thuộc tính và bảng, hàng triệu các mẫu tin. Nhƣ vậy, kích

thƣớc của cơ sở dữ liệu tính bằng terabyte đã bắt đầu xuất hiện. Dữ liệu với số

chiều (tƣơng ứng với thuộc tính khi biểu diễn qua không gian các mẫu dữ

liệu) lớn tạo nên sự gia tăng về kích thƣớc của không gian tìm kiếm trong việc

quy nạp mô hình, một sự bùng nổ về tổ hợp. Khi xây dựng mô hình chỉ một

tập con trong cơ sở dữ liệu tham gia, vì vậy tính may rủi trong các thuật toán

khai phá sẽ tìm đƣợc các mẫu không có giá trị trong trƣờng hợp tổng quát.

Một giải pháp cho vấn đề này là giảm bớt đáng kể số chiều của bài toán và sử

dụng tri thức trƣớc (prior knowledge) để nhận biết các biến ít liên quan và

loại bỏ chúng.

- Vấn đề “quá khớp” (Over-fitting): Khi thuật toán khai phá tìm kiếm với

các tham số tốt nhất cho một mô hình đặc biệt và một giới hạn của tập dữ liệu,

mô hình ấy có thể “quá khớp” trên tập dữ liệu ấy nhƣng lại thi hành không

chính xác trên tập dữ liệu kiểm tra. Một giải pháp thƣờng đƣợc sử dụng là

thẩm định chéo.

- Thay đổi dữ liệu và tri thức: Dữ liệu là không tĩnh, dữ liệu luôn thay

đổi nhanh chóng có thể dẫn đến những mẫu đã khai phá trƣớc đây không còn

hiệu lực. Thêm vào đó, các biến đã đƣợc đo trong cơ sở dữ liệu ứng dụng đã

bị thay đổi, bị xóa hoặc đã tăng lên với một độ đo mới. Điều này có thể đƣợc

thực hiện bằng cách gia tăng các phƣơng thức cập nhật các mẫu và xem xét

các thay đổi nhƣ là một cơ hội cho việc khám phá bằng việc sử dụng nó để xử

lý thích hợp việc tìm kiếm các mẫu chỉ với sự thay đổi.

- Dữ liệu thiếu và nhiễu: Đây là vấn đề rất đƣợc quan tâm trong khai phá

dữ liệu, điều này thƣờng dẫn đến việc dự đoán thiếu chính xác.

- Tích hợp với hệ thống: Hệ thống khai phá dữ liệu thực sự là hữu ích khi

phải đƣợc tích hợp với cơ sở dữ liệu thông qua các giao diện nhƣ truy vấn,

bảng tính và các công cụ trực quan khác. Hơn nữa, phải tạo ra một môi trƣờng

thuận lợi cho việc tƣơng tác với ngƣời dùng.

CHƢƠNG 2

PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN

2.1 Đị h ghĩa về phân cụm dữ li u

Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp

các phƣơng pháp học không giám sát trong Machine Learning. Có rất nhiều

định nghĩa khác nhau về kỹ thuật này, nhƣng về bản chất ta 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 đã cho vào các cụm

(clusters), sao cho các đối tƣợng trong cùng một cụm tƣơng tự (similar) nhau

và các đối tƣợng khác cụm thì không tƣơng tự (dissimilar) nhau.

Chúng ta có thể có thể minh hoạ vấn đề phân cụm nhƣ hình sau:

Hình 2.1. Mô phỏng vấ đề phân cụm dữ li u

Trong trƣờng hợp này, chúng ta dễ dàng xác định đƣợc 3 cụm dựa vào

các dữ liệu đã cho, các tiêu chí “tƣơng tự” để phân cụm trong trƣờng hợp này

là khoảng cách hai hoặc nhiều đối tƣợng thuộc nhóm của chúng đƣợc “đóng

gói” theo một khoảng cách nhất định. Điều này đƣợc gọi là phân cụm dựa trên

khoảng cách.

Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái

niệm hai hay nhiều đối tƣợng thuộc cùng nhóm nếu có một định nghĩa khái

niệm chung cho tất cả các đối tƣợng trong đó. Nói cách khác, đối tƣợng của

nhóm phải phù hợp với nhau theo miêu tả các khái niệm đã đƣợc định nghĩa,

không phải theo những biện pháp đơn giản tƣơng tự.

- Marketing: Xác định các nhóm khách hàng (khách hàng tiềm năng,

Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như:

khách hàng giá trị, phân 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 công ty để giúp công ty có chiến lƣợc kinh doanh hiệu

- Sinh học: Phân nhóm động vật và thực vật dựa vào các thuộc tính của

quả hơn.

- Thƣ viện: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả.

- Bảo hiểm, tài chính: Phân nhóm các đối tƣợng sử dụng bảo hiểm và các

chúng.

dịch vụ tài chính, dự đoán xu hƣớng của khách hàng, phát hiện gian lận tài

- Mạng lƣới toàn cầu: Phân loại tài liệu, phân loại ngƣời dùng web.

chính .

2.2 Mục tiêu của phân cụm dữ li u

Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên

trong một bộ dữ liệu không có nhãn. Nhƣng để có thể quyết định đƣợc cái gì

tạo thành một cụm tốt, làm thế nào để quyết định cái gì đã tạo nên một

phân cụm dữ liệu tốt ? Nó có thể đƣợc hiển thị rằng không có tiêu chuẩn tuyệt

đối “tốt nhất” mà sẽ là độc lập với mục đích cuối cùng của phân cụm dữ liệu.

Do đó, mà ngƣời sử dụng phải cung cấp tiêu chuẩn, theo cách nhƣ vậy mà kết

quả của phân cụm dữ liệu sẽ phù hợp với nhu cầu của họ cần.

Một vấn đề thƣờng gặp trong phân cụm là hầu hết các dữ liệu cần cho

phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác

hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lí dữ

liệu nhằm khắc phục hoặc loại bỏ nhiễu trƣớc khi chuyển sang giai đoạn phân

tích cụm dữ liệu. Nhiễu ở đây đƣợc hiểu là các đối tƣợng dữ liệu không chính

xác, không tƣờng minh hoặc là các đối tƣợng dữ liệu khuyết, thiếu thông tin

về một số thuộc tính... Một trong các kỹ thuật xử lí nhiễu phổ biến là việc

thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính

tƣơng ứng. Ngoài ra, dò tìm đối tƣợng ngoại lai cũng là một trong những

hƣớng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định

một nhóm nhỏ các đối tƣợng dữ liệu khác thƣờng so với các dữ liệu trong cơ

sở dữ liệu, tức là các đối tƣợng dữ liệu không tuân theo các hành vi hoặc mô

hình dữ liệu nhằm tránh sự ảnh hƣởng của chúng tới quá trình và kết quả của

phân cụm.

Theo các nghiên cứu đến thời điểm hiện nay thì chƣa có một phƣơng

pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng

cấu trúc cơ sở dữ liệu. Hơn nữa, đối với các phƣơng pháp phân cụm cần có

cách thức biểu diễn cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn

khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp. Vì vậy phân

cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn

đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau,

đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị

dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá

dữ liệu.

Phân cụm là một lĩnh vực nghiên cứu có nhiều thách thức, tại đó các ứng

dụng tiềm năng của nó đƣa ra các yêu cầu đặc biệt. Sau đây là các yêu cầu

điển hình của phân cụm trong khai phá dữ liệu:

(1) Khả năng mở rộng.

(2) Thích nghi với các kiểu dữ liệu khác nhau.

(3) Khám phá ra các cụm với hình thù bất kỳ.

(4) Tối thiểu lƣợng tri thức cần cho xác định tham số vào.

(5) Ít nhạy cảm với thứ tự của dữ liệu vào.

(6) Thích nghi với dữ liệu nhiễu cao.

(7) Ít nhạy cảm với tham số đầu vào.

(8) Thích nghi với dữ liệu đa chiều.

(9) Dễ hiểu, dễ cài đặt và khả thi.

2.3 Bài toán phân cụm dữ li u

Phân cụm dữ liệu là quá trình học không giám sát trên một tập dữ liệu

đầu vào nhằm phân chia tập dữ liệu ban đầu thành các tập dữ liệu con có tính

chất tƣơng tự nhau.

Đầu vào: Tập dữ liệu D gồm n phần tử trong không gian m chiều.

i, x2

i) mô tả m thuộc tính của phần tử thứ i.

- D = {x1, x2,…,xn} i,…, xm - xi = (x1

Đầu ra: Phân tách các dữ liệu thuộc D thành các cụm sao cho:

- Các phần tử trong cùng một cụm có tính chất tƣơng tự nhau

(gần nhau).

- Các phần tử ở các cụm khác nhau có tính chất khác nhau (xa

nhau).

2.4 M t số kiểu dữ li u

Thuật toán phân cụm dữ liệu có nhất rất nhiều liên kết với các loại dữ

liệu. Vì vậy, sự hiểu biết về quy mô, bình thƣờng hoá, và gần nhau là rất quan

trọng trong việc giải thích các kết quả của thuật toán phân cụm dữ liệu. Kiểu

dữ liệu nói đến mức độ lƣợng tử hóa trong dữ liệu [2] một thuộc tính duy nhất

có thể đƣợc gõ nhƣ nhị phân, rời rạc, hoặc liên tục. Thuộc tính nhị phân có

chính xác hai giá trị, nhƣ là đúng hoặc sai. Thuộc tính rời rạc có một số hữu

hạn các giá trị có thể, vì thế các loại nhị phân là một trƣờng hợp đặc biệt của

các loại rời rạc.

Trong phần này ta phân tích các kiểu dữ liệu thƣờng đƣợc sử dụng trong

phân cụm dữ liệu. Trong phân cụm dữ liệu, các đối tƣợng dữ liệu cần phân

tích có thể là con ngƣời, nhà cửa, tiền lƣơng, các thực thể phần mềm,… Các

đối tƣợng này thƣờng đƣợc diễn tả dƣới dạng các thuộc tính của nó. Các

thuộc tính này là các tham số cần cho giải quyết vấn đề phân cụm dữ liệu và

sự lựa chọn chúng có tác động đáng kể đến các kết quả của phân cụm. Phân

loại các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu

hết các tập dữ liệu nhằm cung cấp các phƣơng tiện thuận lợi để nhận dạng sự

khác nhau của các phần tử dữ liệu. Dƣới đây là cách phân cụm dựa trên hai

đặc trƣng là: kích thƣớc miền và hệ đo.

2.4.1 Phân loại kiểu dữ li u dựa tr kích thƣ c miền

- Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm

đƣợc, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ nhƣ các thuộc

tính về màu, nhiệt độ hoặc cƣờng độ âm thanh.

- Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm

đƣợc. Thí dụ nhƣ các thuộc tính về số của một cuốn sách, số thành viên trong

một gia đình,…

2.4.2 Phân loại kiểu dữ li u dựa trên h đ

Giả sử ta có hai đối tƣợng x, y và các thuộc tính xi , yi tƣơng ứng với

thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu nhƣ sau:

- Thuộc tính định danh: Dạng thuộc tính khái quát hoá của thuộc tính nhị

phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn

hai phần tử - nghĩa là nếu x và y là hai đối tƣợng thuộc tính thì chỉ có thể xác

định là x  y hoặc x = y. Thí dụ nhƣ thuộc tính về nơi sinh.

- Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự,

nhƣng chúng không đƣợc định lƣợng. Nếu x và y là hai thuộc tính thứ tự thì ta

có thể xác định là x  y hoặc x = y hoặc x > y hoặc x < y. Thí dụ nhƣ thuộc

tính Huy chƣơng của vận động viên thể thao.

- Thuộc tính khoảng: Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với

thuộc tính khoảng, ta có thể xác định một thuộc tính là đứng trƣớc hoặc đứng

sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi> yi thì ta nói x cách

y một khoảng |xi – yi| tƣơng ứng với thuộc tính thứ i. Ví dụ: thuộc tính số

Serial của một đầu sách trong thƣ viện hoặc thuộc tính số kênh trên truyền

hình.

- Thuộc tính tỉ lệ: Là thuộc tính khoảng nhƣng đƣợc xác định một cách

tƣơng đối so với điểm mốc, thí dụ nhƣ thuộc tính chiều cao hoặc cân nặng lấy

giá trị 0 làm mốc.

Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và

thuộc tính có thứ tự gọi chung là thuộc tính hạng mục, thuộc tính khoảng và

thuộc tính tỉ lệ đƣợc gọi là thuộc tính số.

Ngƣời ta còn đặc biệt quan tâm đến dữ liệu không gian. Đây là loại dữ

liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu

không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối

tƣợng, thí dụ nhƣ thông tin về hình học,… Dữ liệu không gian có thể là dữ

liệu liên tục hoặc rời rạc.

Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều

chiều và cho phép ta xác định đƣợc khoảng cách giữa các đối tƣợng dữ liệu

trong không gian.

Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian.

Thông thƣờng, các thuộc tính số đƣợc đo bằng các đơn vị xác định nhƣ

là Kilogams hoặc Centimeter. Tuy nhiên, các đơn vị đo có ảnh hƣởng đến các

kết quả phân cụm. Thí dụ nhƣ thay đổi độ đo cho thuộc tính cân nặng từ

Kilogams sang Pound có thể mang lại các kết quả khác nhau trong phân cụm.

Để khắc phục điều này ngƣời ta phải chuẩn hoá dữ liệu, tức là sử dụng các

thuộc tính dữ liệu không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hoá phụ

thuộc vào ứng dụng và ngƣời dùng, thông thƣờng chuẩn hoá dữ liệu đƣợc

thực hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm

các trọng số cho các thuộc tính.

2.5 M t số kỹ thu t phân cụm dữ li u

Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng

trong thực tế, nó đều hƣớng tới hai mục tiêu chung đó là chất lƣợng của các

cụm khám phá đƣợc và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật

phân cụm có thể phân loại theo các phƣơng pháp tiếp cận chính nhƣ sau: phân

cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm

dựa trên lƣới, phân cụm dựa trên mô hình phân cụm và phân cụm có dữ liệu

ràng buộc.

2.5.1 Phƣơ g h h cụm dữ li u dựa trên phân cụm phân cấp

Phƣơng pháp phân cụm phân cấp làm việc bằng cách nhóm các đối

tƣợng vào trong một cây các cụm.

- Phân cụm phân cấ tích đống: bắt đầu bằng cách đặt mỗi đối tƣợng

vào trong cụm của bản thân nó, sau đó kết nhập các cụm nguyên tử này vào

trong các cụm ngày càng lớn hơn cho tới khi tất cả các đối tƣợng nằm trong

một cụm đơn hay cho tới khi thỏa mãn điều kiện dừng cho trƣớc.

- Phân cụm phân cấp phân ly: phƣơng pháp này ngƣợc lại bằng cách

bắt đầu với tất cả các đối tƣợng trong một cụm, chia nhỏ nó vào trong các

phần ngày càng nhỏ hơn cho tới khi mỗi đối tƣợng hình thành nên một cụm

hay thỏa mãn một điều kiện dừng cho trƣớc.

2.5.1.1 Thuật toán AGNES

Thuật toán AGNES (Agglomerative Nesting) - tích đống lồng [3].

Phƣơng pháp này sử dụng phƣơng pháp kết nối đơn, tại đó mỗi cụm đƣợc đại

diện bởi tất cả các điểm dữ liệu trong cụm, và độ tƣơng đồng giữa hai cụm

đƣợc đo bởi độ tƣơng đồng của cặp điểm dữ liệu gần nhất thuộc về các cụm

khác nhau. AGNES hoà nhập các nút (tức là các đối tƣợng hay các cụm riêng

lẻ) có độ không tƣơng đồng ít nhất, cứ thể cho tới khi hoà nhập thành một

cụm duy nhất.

Thu t toán AGNES bao gồ c c bƣ c cơ bản sau :

Bước 1: Mỗi đối tượng là một nhóm

Bước 2: Hợp nhất các nhóm có khoảng cách giữa các nhóm là nhỏ nhất.

Bước 3: Nếu thu được nhóm “toàn bộ” tức là dữ liệu đã nằm toàn bộ

trong một nhóm thì dừng, ngược lại quay lại bước 2

2.5.1.2 Thuật toán BIRCH

Một phƣơng pháp phân cụm phân cấp đƣợc tích hợp thú vị gọi là BIRCH

(Balanced Iterative Reducing and Clustering using Hierachies) đƣợc đề xuất

năm 1996 bởi Zhang, Ramakrishnan và Livny.

Nó đƣa ra hai khái niệm: đặc trƣng phân cụm (CF - Clustering Feature)

và cây CF (Clustering Feature tree), sử dụng cây CF đại diện một cụm tóm tắt

để có đƣợc tốc độ và khả năng mở rộng phân cụm tốt trong các cơ sở dữ liệu

lớn. Nó cũng tốt đối với phân cụm tăng trƣởng động của các điểm dữ liệu đầu

vào. Đối với mỗi cụm dữ liệu, BIRCH chỉ lƣu bộ ba (N, LS, SS), Trong đó N

là số đối tƣợng trong cụm, LS là tổng các giá trị thuộc tính của các đối tƣợng

trong cụm, và SS là tổng bình phƣơng của các giá trị thuộc tính của các đối

tƣợng trong cụm. Khi đó, các cụm trong tập dữ liệu ban đầu sẽ đƣợc cho dƣới

dạng một cây CF. Ngƣời ta đã chứng minh đƣợc rằng các đại lƣợng thống kê

nhƣ độ đo có thể xác định từ cây CF.

Một cây CF là một cây cân bằng chiều cao, nó lƣu trữ các đặc trƣng

phân cụm. Nó có hai tham số: hệ số phân nhánh B và ngƣỡng T. Hệ số phân

nhánh chỉ rõ số lƣợng tối đa các con. Tham số ngƣỡng chỉ rõ đƣờng kính tối

đa của các cụm con đƣợc lƣu trữ tại các nút lá. Bằng cách thay đổi giá trị

ngƣỡng, nó có thể thay đổi kích thƣớc của cây. Các nút không phải là lá lƣu

trữ tổng các CF của các nút con, do vậy tóm tắt thông tin về các con của

chúng.

Thu t t BIRCH đƣợc thực hi qua hai giai đ ạn sau:

Giai đoạn 1: Duyệt tất cả các đối tƣợng trong tập dữ liệu và xây dựng

một cây CF ban đầu. Ở giai đoạn này các đối tƣợng lần lƣợt đƣợc chèn vào

nút lá gần nhất của cây CF (nút lá của cây đóng vai trò cụm con), sau khi chèn

xong thì mọi nút trên cây CF đƣợc cập nhật thông tin. Nếu đƣờng kính của

cụm con sau khi chèn lớn hơn ngƣỡng T thì nút đƣợc tách ra. Quá trình này

đƣợc lặp lại cho đến khi tất cả các đối tƣợng đều đƣợc chèn vào cây

CF. Để lƣu thông toàn bộ cây CF trong bộ nhớ điều chỉnh kích thƣớc của cây

CF thông qua điều chỉnh ngƣỡng T.

Giai đoạn 2: BIRCH chọn một giải thuật toán phân cụm bất kỳ (nhƣ

thuật toán phân hoạch) để thực hiện phân cụm cho tất các các nút lá CF.

2.5.2 Phƣơ g h h cụm dữ li u dựa trên m t đ

Phƣơng pháp này nhóm các đối tƣợng dữ liệu dựa trên hàm mật độ xác

định, mật độ là số các đối tƣợng lân cận của một đối tƣợng dữ liệu theo một

nghĩa nào đó. Trong cách tiếp cận này, khi một dữ liệu đã xác định thì nó tiếp

tục đƣợc phát triển thêm các đối tƣợng dữ liệu mới miễn là số các đối tƣợng

lân cận này phải lớn hơn một ngƣỡng đã đƣợc xác định trƣớc. Phƣơng pháp

phân cụm dựa trên mật độ của các đối tƣợng để xác định các cụm dữ liệu có

thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật này có thể khắc

phục đƣợc các phần tử ngoại lai hoặc giá trị nhiễu rất tốt, tuy nhiên việc xác

định các tham số mật độ của thuật toán là rất khó khăn, trong khi các tham số

này lại có tác động rất lớn đến kết quả phân cụm.

2.5.2.1 Thuật toán DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

là một giải thuật phân cụm dựa trên mật độ, đƣợc phát triển bởi Ester,

Kriegel, Sander và Xu (1996). Thuật toán thích nghi với mật độ dầy để phân

cụm và khám phá ra các cụm có hình dạng bất kỳ trong không gian CSDL có

nhiễu. Nó có định nghĩa cụm là tập tối đa các điểm liên thông mật độ.

Hinh 2.2. Cụm dữ li u đƣợc khám phá bởi giải thu t DBSCAN

Quan sát 3 tập dữ liệu điểm mẫu ở hình 2.2, chúng ta dễ dàng nhận ra

các cụm điểm và các điểm nhiễu. Ý tƣởng chính để phát hiện ra các cụm của

giải thuật DBSCAN là bên trong mỗi cụm luôn tồn tại một mật độ cao hơn

bên ngoài cụm. Hơn nữa, mật độ ở những vùng nhiễu thì thấp hơn mật độ bên

trong của bất kỳ cụm nào. Trong mỗi cụm phải xác định bán kính vùng lân

cận (Eps) và số lƣợng điểm tối thiểu trong vùng lân cận của một điểm trong

cụm (MinPts). Hình dạng vùng lân cận của một điểm đƣợc xác định dựa vào

việc chọn hàm khoảng cách giữa hai điểm p và q, ký hiệu là dist(p,q). Ví dụ,

nếu dùng khoảng cách Mahattan trong không gian 2D thì hình dạng vùng lân

cận là hình chữ nhật.

Các bƣớc của thuật toán DBSCAN nhƣ sau:

Bước 1: Chọn một đối tượng p tuỳ ý

Bước 2: Lấy tất cả các đối tượng mật độ - đến được từ p với Eps và

MinPts.

Bước 3: Nếu p là điểm nhân thì tạo ra một cụm theo Eps và MinPts.

Bước 4: Nếu p là một điểm biên, không có điểm nào là mật độ - đến

được mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu.

Bước 5: Quá trình tiếp tục cho đến khi tất cả các đối tượng được xử lý.

Nếu ta chọn sử dụng giá trị trị toàn cục Eps và MinPts, DBSCAN có thể

hoà nhập hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả

sử khoảng cách giữa hai tập dữ liệu S1 và S2 đƣợc định nghĩa là Dist(S1,S2) =

S2}. S1 và qmin{dist(p,q)| p  S1 và qS2 }.

Thuật toán DBSCAN có thể tìm ra các cụm với hình thù bất kỳ, trong

khi đó tại cùng một thời điểm ít bị ảnh hƣởng bởi thứ tự của các đối tƣợng dữ

liệu nhập vào. Khi có một đối tƣợng đƣợc chèn vào chỉ tác động đến một láng

giềng xác định. Mặt khác, DBSCAN yêu cầu ngƣời dùng xác định bán kính

Eps của các láng giềng và số các láng giềng tối thiểu MinPts, thông thƣờng

các tham số này đƣợc xác định bằng phép chọn ngẫu nhiên hoặc theo kinh

nghiệm.

Độ phức tạp của thuật toán DBSCAN là O ( n×thời gian tìm các đối

tƣợng Eps ). Trong đó n là số đối tƣợng cần phân cụm. Trong trƣờng hợp xấu nhất thì độ phức tạp sẽ là O ( n2).

2.5.2.2 Thuật toán OPTICS

Thuật toán OPTICS (Ordering Points To Identify the Clustering

Structure) do Ankerst, Breunig, Kriegel và Sander đề xuất năm 1999, là thuật

toán mở rộng cho thuật toán DBSCAN, bằng cách giảm bớt các tham số đầu

vào. Thuật toán thực hiện tính toán và sắp xếp các đối tƣợng theo thứ tự tăng

dần nhằm tự động phân cụm và phân tích cụm tƣơng tác hơn là đƣa ra phân

cụm một tập dữ liệu rõ ràng. Thứ tự này diễn tả cấu trúc dữ liệu phân cụm

dựa trên mật độ chứa thông tin tƣơng đƣơng với phân cụm dựa trên mật độ

với một dãy các tham số đầu vào. OPTICS xem xét bán kính tối thiểu nhằm

xác định các láng giềng phù hợp với thuật toán.

Bằng cách khảo sát giải thuật phân cụm dựa trên mật độ, OPTICS có thể

dễ dàng thấy rằng đối với một giá trị hằng số MinPts, các cụm dựa trên mật

độ đối với mật độ cao hơn (tức là một giá trị ε thấp hơn) đƣợc chứa hoàn toàn

trong các tập mật độ liên kết đối với một mật độ thấp hơn. Bởi vậy, để đƣa ra

các cụm dựa trên mật độ với một tập các tham số khoảng cách, giải thuật cần

lựa chọn các đối tƣợng để xử lý theo một trật tự cụ thể để đối tƣợng là mật độ

đối với giá trị ε thấp nhất đƣợc kết thúc trƣớc tiên. Dựa trên ý tƣởng này, hai

giá trị cần đƣợc lƣu trữ đối với mỗi đối tƣợng: khoảng cách nòng cốt (core-

distance) và khoảng cách tiến (reachability distance).

Khoảng cách nòng cốt của một đối tƣợng p là khoảng cách nhỏ nhất ε'

giữa p và một đối tƣợng trong ε - láng giềng của nó để p sẽ là một đối tƣợng

nòng cốt đối với ε' nếu nhƣ láng giềng này đƣợc chứa trong ε - láng giềng của

p. Nếu không thì khoảng cách nòng cốt là không xác định. Khoảng cách tiến

của một đối tƣợng p đối với một đối tƣợng o khác là khoảng cách nhỏ nhất để

p là mật độ trực tiếp tiến từ o nếu o là một đối tƣợng nòng cốt. Nếu o không

phải là một đối tƣợng nòng cốt, ngay cả tại khoảng cách phát sinh ε, khoảng

cách tiến của một đối tƣợng p đối với o là không xác định.

Giải thuật OPTICS tạo lập trật tự của một cơ sở dữ liệu, thêm vào đó là

lƣu trữ khoảng cách nòng cốt và một khoảng cách tiến phù hợp với mỗi đối

tƣợng. Thông tin nhƣ vậy là đủ cho sự rút trích của tất cả các phân cụm dựa

trên mật độ đối với bất kỳ một khoảng cách ε' nhỏ hơn khoảng cách phát sinh

ε từ trật tự này.

Thuật toán DBSCAN và OPTICS tƣơng tự với nhau về cấu trúc và có

cùng độ phức tạp: O(nLogn) (n là kích thƣớc của tập dữ liệu). Hình sau thể

hiện về một thí dụ trong PCDL của thuật toán OPTICS:

Hinh 2.3. Thứ tự phân cụ c c đối tƣợng theo OPTICS

2.5.3 Phƣơ g h h cụm phân hoạch

Ý tƣởng chính của kỹ thuật này là phân hoạch một tập hợp dữ liệu có n

phần tử cho trƣớc thành k nhóm dữ liệu sao mỗi phần tử dữ liệu chỉ thuộc về

một nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Số các cụm đƣợc

thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc.

Phƣơng pháp này là tốt cho việc tìm các cụm hình cầu trong không gian

Euclidean. Ngoài ra, phƣơng pháp này cũng phụ thuộc vào khoảng cách cơ

bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau

với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ

là xa nhau so với mỗi điểm khác.

2.5.3.1 Thuật toán K-means

Ý tƣởng của thuật toán K-Means đƣợc đề xuất bởi MacQueen trong lĩnh

vực thống kê năm 1967, là một trong những thuật toán học không giám sát

thông dụng nhất trong phân nhóm dữ liệu. Với mục tiêu chia tập gồm n đối

tƣợng của cơ sở dữ liệu thành k cụm ( k ≤ n, k là số nguyên, dƣơng) sao cho

các đối tƣợng trong cùng một vùng có khoảng cách bé còn các đối tƣợng khác

vùng thì có khoảng cách lớn hơn nhiều.

Thuật toán: Đầu tiên, xác định K tâm cụm, trong đó K là một tham số mà

ngƣời dùng đƣa vào.

Với x = {x1, x2 ,..., xN} là tập dữ liệu đầu vào và C = {C1,C2 ,...,CK } là tập

K tâm cụm.

Đầu vào: X = {x1, x2 ,..., xN} (Tập dữ liệu đầu vào)

K (Số lƣợng tâm cụm)

MaxIters (Số vòng lặp tối đa)

Đầu ra: C = { c1,c2,...,cK } (Tập các cụm)

Thuật toán K-Means thực hiện qua các bước chính sau:

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.

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)

3. Nhóm các đối tƣợng vào nhóm gần nhất

4. Xác định lại tâm mới cho các nhóm

5. Thực hiện lại bƣớc 2 cho đến khi không có sự thay đổi nhóm nào của

các đối tƣợng

Thuật toán k-means đƣợc chứng minh là hội tụ và có độ phức tạp tính

toán là: O((nk d)Tflop). Trong đó: n là số đối tƣợng dữ liệu, k là số cụm dữ

liệu, d là số chiều,  là số vòng lặp, Tflop là thời gian để thực hiện một phép

tính cơ sở nhƣ phép tính nhân, chia, …Nhƣ vậy, do k-means phân tích phân

cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy nhiên, nhƣợc

điểm của k-means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra

các cụm có dạng hình cầu, k-means còn rất nhạy cảm với nhiễu và các phần

tử ngoại lai trong dữ liệu. Hình sau diễn tả mô phỏng về một số hình dạng

cụm dữ liệu khám phá đƣợc bởi k-means:

Hinh 2. 4. Phân cụm dựa tr hƣơ g h p k-means

Tuy nhiên, phƣơng pháp k-means chỉ áp dụng khi trung bình của một

cụm đƣợc xác định. Không phải ứng dụng nào cũng có thể áp dụng kỹ thuật

này, ví dụ những dữ liệu bao hàm các thuộc tính xác thực. Về phía các ngƣời

dùng, họ phải chỉ rõ k - số cụm, cần sớm phát hiện ra sự bất lợi. Phƣơng pháp

k-means không thích hợp với việc tìm các cụm có hình dáng không lồi hay

các cụm có kích thƣớc khác xa nhau. Hơn nữa, nó nhạy cảm với các điểm dữ

liệu nhiễu, một số lƣợng nhỏ dữ liệu nhƣ vậy về căn bản có ảnh hƣởng tới giá

trị trung bình. Trên thực tế ngƣời ta chƣa có một giải pháp tối ƣu nào để chọn

các tham số đầu vào, giải pháp thƣờng đƣợc sử dụng nhất là thử nghiệm với

các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất.

Đến nay, đã có rất nhiều thuật toán kế thừa tƣ tƣởng của thuật toán k-

means áp dụng trong khai phá dữ liệu để giải quyết tập dữ liệu có kích thƣớc

rất lớn đang đƣợc áp dụng rất hiệu quả và phổ biến nhƣ thuật toán k-medoid,

PAM, CLARA, CLARANS, k- prototypes, …

2.5.3.2 Thuật toán PAM

Thuật toán PAM (Partitioning Around Medoids) đƣợc Kaufman và

Rousseeuw đề xuất 1987, là thuật toán mở rộng của thuật toán k-means, nhằm

có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc các phần tử ngoại lai.

Ý tƣởng của k-medodis thay vì lấy giá trị trung bình của các đối tƣợng

trong cụm nhƣ một điểm tham khảo, k-medoids lấy một đối tƣợng đại diện

trong cụm, gọi là medoid, nó là điểm đại diện đƣợc định vị trung tâm nhất

trong cụm. Do vậy, phƣơng pháp phân chia vẫn đƣợc thực hiện dựa trên

nguyên tắc tối thiểu hoá tổng các độ không tƣơng đồng giữa mỗi đối tƣợng

với điểm tham khảo tƣơng ứng của nó, điểm này thiết lập nên cơ sở của

phƣơng pháp k-mediods.

Giải thuật PAM, đây là giải thuật phân cụm kiểu k-mediods. Để xác định

các medoid, PAM bắt đầu bằng cách lựa chọn k đối tƣợng medoid bất kỳ. Sau

mỗi bƣớc thực hiện, PAM cố gắng hoán chuyển giữa đối tƣợng medoid Om và

một đối tƣợng Op không phải là medoid, miễn là sự hoán chuyển này nhằm

cải tiến chất lƣợng của phân cụm, quá trình này kết thúc khi chất lƣợng phân

cụm không thay đổi. Chất lƣợng phân cụm đƣợc đánh giá thông qua hàm tiêu

chuẩn, chất lƣợng phân cụm tốt nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu.

PAM tính giá trị Cjmp cho tất cả các đối tƣợng Oj để làm căn cứ cho việc

hoán chuyển giữa Om và Op.

Om : là đối tƣợng medoid hiện thời cần đƣợc thay thế;

Op : là đối tƣợng medoid mới thay thế cho Om;

Oj : Là đối tƣợng dữ liệu (Không phải medoid) có thể đƣợc di

chuyển sang cụm khác;

Oj,2 : Là đối tƣợng medoid hiện thời gần đối tƣợng Oj nhất;

Các bƣớc thực hiện thuật toán PAM

Đầu vào : Số cụm k và một cơ sở dữ liệu chứa n đối tượng

Đầu ra : Một tập k cụm đã tối thiểu hoá tổng các độ đo không tương

đồng của tất cả các đối tượng tới medoid gần nhất của chúng.

Bắt đầu

1. Chọn tuỳ ý k đối tượng giữ vai trò là các medoid ban đầu;

2. Repeat

3. Ấn định mỗi đối tượng vào cụm có medoid gần nó nhất;

4. Tính hàm mục tiêu (tổng các độ đo tương đồng của tất cả các đối

tượng tới medoid gần nhất cùa chúng);

5. Đổi medoid x bằng một đối tượng y nếu như việc thay đổi này làm

giảm hàm mục tiêu;

6. Until : không có sự thay đổi nào

Kết thúc

Khi có sự hiện diện của nhiễu và các outlier, phƣơng pháp k-medoids

mạnh hơn k-means bởi so với giá trị trung bình (mean), medoid ít bị ảnh

hƣởng hơn bởi các outlier hay các giá trị ở rất xa khác nữa. Tuy nhiên, chi phí

xử lý của nó tốn kém hơn phƣơng pháp k-means và nó cũng cần ngƣời dùng

chỉ ra k - số cụm.

2.6 Kết lu n

Chƣơng này trình bày một số phƣơng pháp phân cụm dữ liệu phổ biến

nhƣ phân cụm dựa trên mật độ, phân cụm phân hoạch, phân cụm dựa vào cụm

phân cấp. Qua đó ta có thể thấy đƣợc khả năng phân cụm của từng phƣơng

pháp, các ƣu nhƣợc điểm của từng phƣơng pháp đối với từng loại dữ liệu, khả

năng áp dụng vào các bài toán thực tiễn.

CHƢƠNG 3

PHÂN LỚP DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN

3.1 Đị h ghĩa về phân l p dữ li u

Phân lớp dữ liệu là một nhánh nhỏ của học có giám sát (Supervised

Learning) với việc sử dụng dữ liệu đầu vào là một tập các mẫu dữ liệu huấn

luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu. Đầu ra là mô hình (bộ

phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp, chúng đƣợc

dùng để dự đoán những nhãn phân lớp cho các bộ dữ liệu hay mẫu mới. Một

số thuật toán dùng trong bài toán phân lớp nhƣ: cây quyết định, mạng nơron,

Naive Bayes.

3.2 Các vấ đề quan tâm của phân l p dữ li u

3.2.1 Quá trình phân lớp dữ liệu:

Các bƣớc tiền xử lý dữ liệu sau đây giúp cải thiện độ chính xác, hiệu suất

và khả năng mở rộng của phân lớp.

- Làm sạch dữ liệu: Đây là quá trình thuộc về tiền xử lý dữ liệu để gỡ bỏ

hoặc làm giảm nhiễu và cách xử lý các giá trị khuyết. Các bƣớc này giúp làm

giảm sự mập mờ khi học:

 Bỏ qua các bộ: Điều này thƣờng đƣợc thực hiện khi thông tin nhãn

dữ liệu bị mất. Phƣơng pháp này không phải lúc nào cũng hiệu quả trừ khi

các bộ có chứa một số thuộc tính không thực sự quan trọng.

 Điền vào các giá trị thiếu bằng tay: Phƣơng pháp này thƣờng tốn

thời gian và có thể không khả thi cho một tập dữ liệu nguồn lớn với nhiều

giá trị bị thiếu.

 Sử dụng các giá trị quy ƣớc để điền vào cho giá trị thiếu: Thay thế

các giá trị thuộc tính thiếu bởi cùng một hằng số quy ƣớc, chẳng hạn nhƣ

một nhãn ghi giá trị “Không biết” hoặc “∞”. Tuy vậy điều này cũng có thể

khiến cho chƣơng trình khai phá dữ liệu hiểu nhầm trong một số trƣờng hợp

và đƣa ra các kết luận không hợp lý.

 Sử dụng các thuộc tính có nghĩa để điền vào cho giá trị thiếu.

- Phân tích sự thích hợp: Nhiều thuộc tính trong dữ liệu có thể không

thích hợp hay không cần thiết để phân lớp. Vì vậy, chúng ta phải biết chọn ra

những đặt trƣng tốt (good feature) của dữ liệu, lƣợc bỏ những đặc trƣng

không tốt của dữ liệu, gây nhiễu (noise). Uớc lƣợng số chiều của dữ liệu bao

nhiêu là tốt hay nói cách khác là chọn bao nhiêu thuộc tính. Nếu số chiều quá

lớn gây khó khăn cho việc tính toán thì phải giảm số chiều của dữ liệu nhƣng

vẫn giữ đƣợc độ chính xác của dữ liệu . Trong học máy, bƣớc này gọi là trích

chọn đặc trƣng. Phép phân tích này giúp phân loại hiệu quả và nâng cao khả

năng mở rộng.

- Biến đổi dữ liệu: Dữ liệu có thể đƣợc tổng quát hoá tới các mức khái

niệm cao hơn. Điều này rất hữu ích cho các thuộc tính có giá trị liên tục. Ví

dụ, các giá trị số của thuộc tính thu nhập đƣợc tổng quát hoá sang các phạm

vi rời rạc nhƣ thấp, trung bình và cao. Tƣơng tự, các thuộc tính giá trị tên nhƣ

đường phố đƣợc tổng quát hoá tới khái niệm mức cao hơn nhƣ thành phố.

Nhờ đó các thao tác vào/ra trong quá trình học sẽ ít đi.

Dữ liệu cũng có thể đƣợc tiêu chuẩn hoá, đặc biệt khi các mạng nơron

hay các phƣơng pháp dùng phép đo khoảng cách trong bƣớc học. Tiêu chuẩn

hoá biến đổi theo tỷ lệ tất cả các giá trị của một thuộc tính cho trƣớc để chúng

rơi vào phạm vi chỉ định nhỏ nhƣ [-1.0,1.0] hay [0,1.0]. Chuẩn hóa là một

phần hữu ích của thuật toán phân lớp trong mạng noron, hoặc thuật toán tính

toán độ lệch sử dụng trong việc phân lớp hay nhóm cụm các phần tử liền kề.

Một số phƣơng pháp chuẩn hóa min-max, z-score, và thay đổi số chữ số phần

thập phân. Tuy nhiên điều này sẽ cản trở các thuộc tính có phạm vi ban đầu

lớn (nhƣ thu nhập) có nhiều ảnh hƣởng hơn đối với các thuộc tính có phạm vi

nhỏ hơn ban đầu (nhƣ các thuộc tính nhị phân).

3.2.2 So sánh các phương pháp phân lớp

Các phƣơng pháp phân lớp có thể đƣợc so sánh và đánh giá theo các tiêu

chí sau:

- Độ chính xác dự đoán: Dựa trên khả năng mô hình dự đoán đúng nhãn

lớp của dữ liệu mới.

- Tốc độ: Dựa trên các chi phí tính toán. Chi phí này bao gồm sinh và sử

dụng mô hình.

- Khả năng mở rộng: Dựa trên khả năng trình diễn hiệu quả của mô hình

đối với dữ liệu lớn.

- Khả năng diễn dịch: Dựa trên mức khả năng mà mô hình cung cấp để

hiểu thấu đáo dữ liệu.

3.3 Phân l p bằng cây quyết định

3.3.1 Khái niệm về cây quyết định

Cây quyết định (decision tree) là một phƣơng pháp rất mạnh và phổ biến

cho cả hai nhiệm vụ của khai phá dữ liệu là phân lớp và dự báo. Mặt khác,

cây quyết định còn có thể chuyển sang dạng biểu diễn tƣơng đƣơng dƣới dạng

tri thức là các luật If-Then.

Cây quyết định là cấu trúc biễu diễn dƣới dạng cây. Trong đó, mỗi nút

trong (internal node) biễu diễn một thuộc tính, nhánh (branch) biễu diễn giá

trị có thể có của thuộc tính, mỗi lá (leaf node) biểu diễn các lớp quyết định và

đỉnh trên cùng của cây gọi là gốc (root). Cây quyết định có thể đƣợc dùng để

phân lớp bằng cách xuất phát từ gốc của cây và di chuyển theo các nhánh cho

đến khi gặp nút lá. Trên cơ sở phân lớp này chúng ta có thể chuyển đổi về các

luật quyết định.

Cây quyết định đƣợc sử dụng để xây dựng một kế hoạch nhằm đạt đƣợc

mục tiêu mong muốn. Các cây quyết định đƣợc dùng để hỗ trợ quá trình ra

quyết định. Cây quyết định là một dạng đặc biệt của cấu trúc cây.

Tạo cây quyết định chính là quá trình phân tích cơ sở dữ liệu, phân lớp

và đƣa ra dự đoán. Cây quyết định đƣợc tạo thành bằng cách lần lƣợt chia (đệ

quy) một tập dữ liệu thành các tập dữ liệu con, mỗi tập con đƣợc tạo thành

chủ yếu từ các phần tử của cùng một lớp. Lựa chọn thuộc tính để tạo nhánh

thông qua Entropy và Gain.

Hầu hết các thuật toán sinh cây quyết định đều dựa trên tiếp cận top-

down trình bày sau đây, trong đó nó bắt đầu từ một tập các bộ huấn luyện và

các nhãn phân lớp của chúng. Tập huấn luyện đƣợc chia nhỏ một các đệ quy

thành các tập con trong quá trình cây đƣợc xây dựng.

Generate_decision_tree: Thuật toán sinh cây quyết định từ các bộ dữ

liệu huấn luyện của nguồn dữ liệu D.

Đầu vào:

- Nguồn dữ liệu D, trong đó có chứa các bộ dữ liệu huấn luyện và các

nhãn phân lớp.

- Attribute_list là danh sách các thuộc tính.

- Attribute_selection_method, một thủ tục để xác định tiêu chí phân chia

các bộ dữ liệu một các tốt nhất thành các lớp. Tiêu chí này bao gồm một

thuộc tính phân chia splitting_attribute, điểm chia split_point và tập phân chia

splitting_subset.

Đầu ra: Một cây quyết định

N i dung thu t toán:

1. Tạo nút N

2. If các bộ trong D đều có nhãn lớp C then

3. Trả về N thành một nút lá với nhãn lớp C

4. If danh sách thuộc tính attribute_list là rỗng then

5. Trả về N thành một nút là với nhãn là lớp chiếm đa số trong D

(Việc này thực hiện qua gọi hàm Attribute_selection_method(D,

attribute_list) để tìm ra tiêu chí phân chia tốt nhất splitting_criterion

và gán nhãn cho N tiêu chí đó)

6. If splitting_attribute là một giá trị rời rạc và có nhiều cách

chia then

7. Attribute_list = attribute_list – splitting_attribute // Loại bỏ

thuộc tính splitting_attribute

8. Foreach j insplitting_criterion

// Phân chia các bộ xây dựng cây cho các phân chia đó

9. Đặt Dj là tập các bộ trong D phù hợp với tiêu chí j

10. If Dj là rỗng then

11. Gắn nhãn cho nút N với nhãn phổ biến trong D

12. Else Gắn nút được trả về bởi hàm

Generate_decision_tree(Dj, attribute_list) cho nút N

13. Endfor

Return N

Học bằng cây quyết định cũng là một phƣơng pháp thông dụng trong

khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các

lá đại diện cho các phân lớp còn cành đại diện cho các kết hợp của các thuộc

tính dẫn tới phân lớp đó. Một cây quyết định có thể đƣợc học bằng cách chia

tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính. Quá

trình này đƣợc lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ

qui hoàn thành khi không thể tiếp tục thực hiện việc chia tách đƣợc nữa, hay

khi một phân lớp đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất.

Cây quyết định có thể đƣợc mô tả nhƣ là sự kết hợp của các kỹ thuật

toán học và tính toán nhằm hỗ trợ việc mô tả, phân lớp và tổng quát hóa một

tập dữ liệu cho trƣớc.

Dữ liệu đƣợc cho dƣới dạng các bản ghi có dạng: .

Biến phụ thuộc (dependant variable) y là biến mà chúng ta cần tìm hiểu, phân

loại hay tổng quát hóa. là các biến sẽ giúp ta thực hiện công việc đó.

3.3.2 Ưu, nhược điểm của cây quyết định

So với các phƣơng pháp, cách thức khai phá dữ liệu khác, cây quyết định

là phƣơng pháp có nhiều ƣu điểm:

- Cây quyết định dễ hiểu. Khi nhìn vào mô hình cây quyết định có thể

hiểu đƣợc ngay và có thể nắm đƣợc cách xây dựng cây quyết định sau khi

đƣợc giải thích ngắn gọn.

- Việc chuẩn bị dữ liệu cho một cây quyết định là tƣơng đối đơn giản.

Các kỹ thuật khác thƣờng đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ

(dummy variable) và loại bỏ các giá trị rỗng.

- Cây quyết định có thể xử lý dữ liệu thuộc nhiều kiểu dữ liệu khác nhau,

có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thƣờng

chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật

quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể

dùng cho các biến có giá trị bằng số.

- Cây quyết định là mô hình hộp trắng. Nó quan sát một tình huống cho

trƣớc và có thể dễ dàng giải thích các điều kiện của tình huống đó bằng logic

Boolean. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho

kết quả quá phức tạp để có thể hiểu đƣợc.

- Có thể thẩm định, kiểm tra mô hình bằng các phƣơng pháp thống kê.

Nó làm cho ta có thể tin tƣởng vào mô hình, tin tƣởng và kết quả dự đoán của

mô hình.

Cây quyết định có khả năng xử lý tốt lƣợng dữ liệu lớn trong thời gian

ngắn, không đòi hỏi phần cứng máy tính quá mạnh. Phần lớn máy tính cá

nhân hiện nay đều có thể phân tích các lƣợng dữ liệu lớn trong một thời gian

đủ ngắn để giúp các nhà quản lý đƣa ra quyết định dựa trên phân tích từ cây

quyết định.

Nhƣợc điể :

- Đối với các tập dữ liệu có nhiều thuộc tính thì cây quyết định sẽ lớn

(về chiều sâu cả chiều ngang), vì vậy làm giảm độ dễ hiểu.

- Việc xếp hạng các thuộc tính để phân nhánh dựa vào lần phân nhánh

trƣớc đó và bỏ qua sự phụ thuộc lẫn nhau giữa các thuộc tính.

- Khi dùng độ lợi thông tin (Information Gain) để xác định thuộc tính

rẽ nhánh, các thuộc tính có nhiều giá trị thƣờng đƣợc ƣu tiên chọn.

3.3.3 M t số thu t t của c y quyết đị h

3.3.3.1 Thuật toán ID3.

Thuật toán ID3 (Interative Decision 3) đƣợc đề xuất bởi Quinlan trƣờng

đại học Syney năm 1979. Giải thuật quy nạp cây ID3 là một giải thuật học

đơn giản nhƣng tỏ ra thành công trong nhiều lĩnh vực.

ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết định

(decision tree). Biểu diễn này cho phép chúng ta xác định phân lớp của một

đối tƣợng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó.

Nhƣ vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập

các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện

(training data). Hay nói khác hơn, giải thuật có:

- Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả

một tình huống, hay một đối tƣợng nào đó, và một giá trị phân lớp của nó.

- Đầu ra: Cây quyết định có khả năng phân lớp đúng đắn các ví dụ trong

tập dữ liệu rèn luyện, và hy vọng là phân lớp đúng cho cả các ví dụ chƣa gặp

trong tƣơng lai.

Giải thu t ID3 xây dựng cây quyết định theo giải thu t sau:

Function induce_tree (tập ví dụ, tập thuộc tính)

begin

if mọi ví dụ trong tập ví dụ đều nằm trong cùng một lớp then

return một nút lá được gán nhãn bởi lớp đó

elseif tập thuộc tính là rỗng then

return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong

tập ví dụ

else

begin

chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại;

xóa P ra khỏi tập thuộc tính;

với mỗi giá trị V của P

begin

tạo một nhánh của cây gán nhãn V;

Đặt vào phân vùng V các ví dụ trong tập ví dụ có giá trị V tại

thuộc tính P;

Gọi induce_tree(phân vùng V, tập thuộc tính), gắn kết quả

vào nhánh V

end

ID3 xây dựng cây quyết định theo cách từ trên xuống. Lƣu ý rằng đối

với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ

rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân

vùng (partition) có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc

tính để kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để phân vùng

tập hợp các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy một cây con

cho từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân

vùng đều nằm trong cùng một lớp, lớp đó trở thành nút lá của cây.

Vì thứ tự của các trắc nghiệm là rất quan trọng đối với việc xây dựng

một cây quyết định đơn giản, ID3 phụ thuộc rất nhiều vào tiêu chuẩn chọn lựa

trắc nghiệm để làm gốc của cây.

Tìm kiếm không gian giả thuyết trong ID3

Giống nhƣ các phƣơng pháp học quy nạp khác, thuật toán ID3 cũng tìm

kiếm trong một không gian các giả thuyết một giả thuyết phù hợp với tập dữ

liệu huấn luyện. Không gian giả thuyết mà thuật toán ID3 tìm kiếm là một tập

hợp các cây quyết định có thể có. Thuật toán ID3 thực hiện một phép tìm

kiếm bắt đầu từ đơn giản đến phức tạp, theo giải thuật leo núi (hill climbing),

đi từ cây rỗng, sau đó dần dần xem xét các giả thuyết phức tạp hơn mà có thể

phân lớp đúng các ví dụ huấn luyện. Đại lƣợng đánh giá đƣợc dùng để hƣớng

dẫn tìm kiếm theo giải thuật leo núi ở đây là phép đo lƣợng thông tin thu

đƣợc.

Từ cách hình dung thuật toán ID3 nhƣ là một giải thuật tìm kiếm trong

không gian các giả thuyết, ta có một số nhận xét nhƣ sau:

- Không gian giả thuyết các cây quyết định của ID3 là một không gian

đầy đủ các cây quyết định trên các thuộc tính đã cho trong tập rèn luyện. Điều

này có nghĩa là không gian mà ID3 tìm kiếm chắc chắn có chứa cây quyết

định cần tìm.

- Trong khi tìm kiếm, ID3 chỉ duy trì một giả thuyết hiện tại. Vì vậy, giải

thuật này không có khả năng biểu diễn đƣợc tất cả các cây quyết định khác

nhau có khả năng phân lớp đúng dữ liệu hiện có.

- Giải thuật thuần ID3 không có khả năng quay lui trong khi tìm kiếm.

Vì vậy, nó có thể có những hạn chế giống nhƣ giải thuật leo núi, đó là hội tụ

về cực tiểu địa phƣơng.

- Vì ID3 sử dụng tất cả các ví dụ ở mỗi bƣớc để đƣa ra các quyết định

dựa trên thống kê, nên kết quả tìm kiếm của ID3 rất ít bị ảnh hƣởng bởi một

vài dữ liệu sai (hay dữ liệu nhiễu).

- Trong quá trình tìm kiếm, giải thuật ID3 có xu hƣớng chọn cây quyết định

ngắn hơn là những cây quyết định dài. Đây là tính chất thiên lệch quy nạp của

ID3.

Đ h gi hi u suất

Một cây quyết định tạo ra bởi ID3 đƣợc đánh giá là tốt khi nó có khả năng phân

lớp đúng đƣợc các trƣờng hợp hay ví dụ sẽ xảy ra trong tƣơng lai, hay cụ thể hơn là

có khả năng phân lớp đúng các khả năng không nằm trong tập dữ liệu rèn luyện.

Để đánh giá hiệu suất của một cây quyết định ngƣời ta thƣờng sử dụng một

tập ví dụ độc lập, tập này khác với tập dữ liệu rèn luyện, để đánh giá khả năng

phân lớp của cây trên các khả năng của tập này. Tập dữ liệu nhƣ thế gọi là tập

kiểm tra (validation set). Trong thực tế, tập dữ liệu sẵn có sẽ đƣợc chia thành hai

tập dữ liệu: tập huấn luyện thƣờng chiếm 2/3 số trƣờng hợp và tập kiểm tra

chiếm 1/3.

3.3.3.2 Thuật toán C4.5

C4.5[4] là sự kế thừa của của thuật toán học máy bằng cây quyết định

dựa trên nền tảng là kết quả nghiên cứu của Hunt và các cộng sự của ông

trong nửa cuối thập kỷ 50 và nửa đầu những năm 60 (Hunt 1962). Phiên bản

đầu tiên ra đời là ID3 (Quinlan, 1979)- 1 hệ thống đơn giản ban đầu chứa

khoảng 600 dòng lệnh Pascal, và tiếp theo là C4 (Quinlan 1987). Năm 1993,

J. Ross Quinlan đã kế thừa các kết quả đó phát triển thành C4.5 với 9000

dòng lệnh C chứa trong một đĩa mềm. Mặc dù đã có phiên bản phát triển từ

C4.5 là C5.0 - một hệ thống tạo ra lợi nhuận từ Rule Quest Research, nhƣng

nhiều tranh luận, nghiên cứu vẫn tập trung vào C4.5 vì mã nguồn của nó là

sẵn dùng.

Với những đặc điểm C4.5 là thuật toán phân lớp dữ liệu dựa trên cây

quyết định hiệu quả và phổ biến trong những ứng dụng khai phá cơ sở dữ liệu

có kích thƣớc nhỏ. C4.5 sử dụng cơ chế lƣu trữ dữ liệu thƣờng trú trong bộ

nhớ, chính đặc điểm này làm C4.5 chỉ thích hợp với những cơ sở dữ liệu nhỏ,

và cơ chế sắp xếp lại dữ liệu tại mỗi node trong quá trình phát triển cây quyết

định. C4.5 còn chứa một kỹ thuật cho phép biểu diễn lại cây quyết định dƣới

dạng một danh sách sắp xếp thứ tự các luật if-then (một dạng quy tắc phân

lớp dễ hiểu). Kỹ thuật này cho phép làm giảm bớt kích thƣớc tập luật và đơn

giản hóa các luật mà độ chính xác so với nhánh tƣơng ứng cây quyết định là

tƣơng đƣơng.

N i dung thu t toán:

Function C4.5(Tree)

1. ;

2. If< Kiểm tra các mẫu, nếu thuộc cùng một lớp hoặc có rất ít

mẫu khác lớp>then else ;

3. For Do ;

giá trị Gain tốt nhất. Gọi N.test là thuộc tính có Gain lớn nhất>;

5. If Then

phép tách của N.test>;

6. For Do

(Tree’ được tách ra theo quy tắc:

- Nếu N.test là thuộc tính liên tục tách theo ngưỡng ở bước 5

- Nếu N.test là thuộc tính phân loại rời rạc tách theo các giá trị

của thuộc tính này);

7. If< Kiểm tra, nếu Tree’ rỗng>Then

N là nút lá>; Else

đối với hàm C4.5(Tree’), với tập Tree’>;

9. ;

;

C4.5 dùng Gain - E tr y đ đ ựa chọ thu c tí h “tốt hất”.

Phần lớn các hệ thống đều cố gắng để tạo ra một cây càng nhỏ càng tốt,

vì những cây nhỏ hơn thì dễ hiểu hơn và dễ đạt đƣợc độ chính xác dự đoán

cao hơn. Do không thể đảm bảo đƣợc sự cực tiểu của cây quyết định, C4.5

dựa vào nghiên cứu tối ƣu hóa, và sự lựa chọn cách phân chia mà có độ đo

lựa chọn thuộc tính đạt giá trị cực đại.

Hai độ đo đƣợc sử dụng trong C4.5 là information gain và gain ratio.

RF(Cj,S) biểu diễn tần xuất (Relative Frequency) các case trong S thuộc về

lớp Cj.

Với |Sj|là kích thƣớc tập các case có giá trị phân lớp là Cj. |S| là kích

thƣớc tập dữ liệu huấn luyện.

Chỉ số thông tin cần thiết cho sự phân lớp: I(S) với S là tập cần xét sự

phân phối lớp đƣợc tính bằng:

Sau khi S đƣợc phân chia thành các tập con S1,S2,... ,St bởi Test B thì

information gain đƣợc tính bằng:

Test B sẽ đƣợc chọn nếu có G(S, B) đạt giá trị lớn nhất.

Tuy nhiên có một vấn đề khi sử dụng G(S, B) ƣu tiên test có số lƣợng

lớn kết quả, ví dụ G(S,B) đạt cực đại với test mà từng Si chỉ chứa một case

đơn. Tiêu chuẩn gain ratio giải quyết đƣợc vấn đề này bằng việc đƣa vào

thông tin tiềm năng (potential information) của bản thân mỗi phân hoạch.

Test B sẽ đƣợc chọn nếu tỉ số giá trị gain ratio = lớn nhất.

Trong mô hình phân lớp C4.5, có thể dùng một trong hai loại chỉ số

Information Gain hay Gain ratio để xác định thuộc tính tốt nhất. Trong đó

Gain ratio là lựa chọn mặc định.

C4.5 có cơ chế ri g tr g xử ý hữ g gi trị thiếu.

Giá trị thiếu của thuộc tính là hiện tƣợng phổ biến trong dữ liệu, có thể

do lỗi khi nhập các bản ghi vào cơ sở dữ liệu, cũng có thể do giá trị thuộc tính

đó đƣợc đánh giá là không cần thiết đối với case cụ thể.

Trong quá trình xây dựng cây từ tập dữ liệu huấn luyện S, B là test dựa

trên thuộc tính A với các giá trị đầu ra là b1, b2,..., bt . Tập S0 là tập con các

case trong S mà có giá trị thuộc tính A không biết và Si biểu diễn các case với

đầu ra là bi trong test B.

Khi đó độ đo information gain của test B giảm vì chúng ta không phân

đƣợc lớp nào từ các case trong S0.

Tƣơng ứng với G(S, B), P(S,B) cũng thay đổi:

Hai thay đổi này làm giảm giá trị của test liên quan đến thuộc tính có tỉ

lệ giá trị thiếu cao.

Nếu test B đƣợc chọn, C4.5 không tạo một nhánh riêng trên cây quyết

định cho S0. Thay vào đó, thuật toán có cơ chế phân chia các case trong S0 về

các tập con Sj là tập con mà có giá trị thuộc tính Test xác định theo trọng số

Chuyể đổi từ c y quyết đị h sa g u t.

Việc chuyển đổi từ cây quyết định sang luật dạng if-then tạo ra những

quy tắc phân lớp dễ hiểu, dễ áp dụng. Các mô hình phân lớp biểu diễn các

khái niệm dƣới dạng các luật đã đƣợc chứng minh là hữu ích trong nhiều lĩnh

vực khác nhau, với các đòi hỏi cả về độ chính xác và tính hiểu đƣợc của mô

hình phân lớp. Tuy nhiên, tài nguyên tính toán dùng cho việc tạo ra tập luật từ

dữ liệu huấn luyện có kích thƣớc lớn và nhiều giá trị sai là vô cùng lớn.

Giai đoạn chuyển đổi từ cây quyết định sang luật gồm 4 bƣớc:

- Cắt tỉa: Luật khởi tạo ban đầu là đƣờng đi từ gốc đến lá của cây quyết

định. Một quyết định có L lá thì tƣơng ứng tập luật sản xuất sẽ có L luật khởi

tạo. Từng điều kiện trong luật đƣợc xem xét và loại bỏ nếu không ảnh hƣởng

tới độ chính xác của luật đó. Sau đó, các luật đã đƣợc cắt tỉa đƣợc thêm vào

tập luật trùng với những luật đã có.

- Lựa chọ : Các luật đã cắt tỉa đƣợc nhóm lại theo giá trị phân lớp, tạo

nên các tập con chứa các luật theo lớp. Sẽ có k tập luật con nếu tập training có

k giá trị phân lớp. Từng tập con trên đƣợc xem xét để chọn ra một tập con các

luật mà tối ƣu hóa độ chính xác dự đoán của lớp gắn với tập luật đó.

- Sắ xế : Sắp xếp K tập luật đã tạo ra từ trên bƣớc theo tần số lỗi. Lớp

mặc định đƣợc tạo ra bằng cách xác định các case trong tập dữ liệu huấn

luyện không chứa tổng các luật hiện tại và chọn lớp phổ biến nhất trong các

case đó làm lớp mặc định.

- Ƣ c ƣợ g đ h gi : Tập luật đƣợc đem ƣớc lƣợng lại trên toàn bộ

dữ liệu huấn luyện nhằm mục đính xác định xem có luật nào làm giảm độ

chính xác của sự phân lớp. Nếu có, luật đó bị loại bỏ và quá trình ƣớc lƣợng

đƣợc lặp cho đến khi không thể cải tiến thêm.

Nh xét về thu t t C4.5

C4.5 là một thuật toán hiệu quả cho những tập dữ liệu vừa và nhỏ.

C4.5 có cơ chế sinh cây quyết định hiệu quả và chặt chẽ bằng việc sử

dụng độ đo lựa chọn thuộc tính tốt nhất là information gain. Các cơ chế xử

lý với giá trị lỗi, thiếu và chống “quá vừa” dữ liệu của C4.5 cùng với cơ chế

cắt tỉa cây đã tạo nên sức mạnh của C4.5. Thêm vào đó, mô hình phân lớp

C4.5 còn có phần chuyển đổi từ cây quyết định sang luật if- then, làm tăng

độ chính xác và tính dễ hiểu của kết quả phân lớp. Đây là tiện ích rất có ý

nghĩa đối với ngƣời sử dụng.

3.4 Phân l p bằng Bayesian

Bộ phân lớp Bayes có thể dự báo các xác suất là thành viên của lớp,

chẳng hạn xác suất mẫu cho trƣớc thuộc về một lớp xác định.

Định lý bayes

- X là mẫu dữ liệu chƣa biết nhãn lớp.

- H là giả thuyết sao cho X thuộc về lớp C.

- Ấn định xác suất hậu nghiệm posterior probability P(H|X) sao cho H

đúng khi cho trƣớc quan sát X (H conditioned on X).

- Giả sử thế giới các mẫu dữ liệu gồm trái cây, đƣợc mô tả bằng màu sắc

và hình dáng.

 Giả sử X là màu đỏ và tròn

 H là giả thuyết mà X là quả táo

 Thì P(H|X) phản ánh độ tin cậy X là quả táo khi biết trƣớc X có màu

đỏ và tròn

- P(X|H) là xác suất tiên nghiệm của X có điều kiện trên H.

- Khi có n giả thuyết

Phân l p Naive Bayesian

Naive Bayes Classification (NBC) là một thuật toán dựa trên định lý

Bayes về lý thuyết xác suất để đƣa ra các phán đoán cũng nhƣ phân lớp dữ

liệu dựa trên các dữ liệu đƣợc quan sát và thống kê. Naive Bayes

Classification là một trong những thuật toán đƣợc ứng dụng rất nhiều trong

các lĩnh vực Machine learning dùng để đƣa ra các dự đoán chính xác nhất dựa

trên một tập dữ liệu đã đƣợc thu thập, vì nó khá dễ hiểu và độ chính xác cao.

- Mỗi mẫu dữ liệu đƣợc biểu diễn bằng X= (x1, x2,…, xn) với các thuộc

tính A1, A2,…, An

- Các lớp C1, C2, …, Cm. Cho trƣớc mẫu chƣa biết X. NBC gán X vào Ci

nếu P(Ci|X) > P(Cj|X) với 1  j  m, j  i. Do vậy, chúng ta cực đại

P(Ci|X). Lớp Ci sao cho P(Ci|X) là cực đại đƣợc gọi là giả thuyết hậu

nghiệm cực đại (maximum posterior hypothesis).

Theo định lý Bayes ta có công thức sau :

- Để phân lớp mẫu chƣa biết X, ta tính P(X|Ci) P(Ci) cho từng Ci. Sau đó

mẫu X đƣợc gán vào Ci nếu P(Ci|X) > P(Cj|X) for 1  j  m, j  i

- Nói cách khác, NBC gán X vào lớp Ci sao cho P(X|Ci) P(Ci) là cực đại.

Thu t t Naive Bayes C assificati đƣợc áp dụng vào các loại

ứng dụng sau:

- Real time Prediction: NBC chạy khá nhanh nên nó thích hợp áp

dụng ứng dụng nhiều vào các ứng dụng chạy thời gian thực, nhƣ hệ thống

cảnh báo, các hệ thống trading.

- Multi class Prediction: Nhờ vào định lý Bayes mở rộng ta có thể ứng

dụng vào các loại ứng dụng đa dự đoán, tức là ứng dụng có thể dự đoán nhiều

giả thuyết mục tiêu.

- Text classification/ Spam Filtering/ Sentiment Analysis: NBC cũng rất

thích hợp cho các hệ thống phân loại văn bản hay ngôn ngữ tự nhiên vì tính

chính xác của nó lớn hơn các thuật toán khác. Ngoài ra các hệ thống chống

thƣ rác cũng rất ƣu chuộng thuật toán này. Và các hệ thống phân tích tâm lý

thị trƣờng cũng áp dụng NBC để tiến hành phân tích tâm lý ngƣời dùng ƣu

chuộng hay không ƣu chuộng các loại sản phẩm nào từ việc phân tích các thói

quen và hành động của khách hàng.

- Recommendation System: Naive Bayes Classifier và Collaborative

Filtering đƣợc sử dụng rất nhiều để xây dựng cả hệ thống gợi ý, ví dụ nhƣ

xuất hiện các quảng cáo mà ngƣời dùng đang quan tâm nhiều nhất từ việc học

hỏi thói quen sử dụng internet của ngƣời dùng, hoặc nhƣ ví dụ đƣa ra gợi ý

các bài hát tiếp theo mà có vẻ ngƣời dùng sẽ thích trong một ứng dụng nghe

nhạc.

3.5 Phân l p dựa trên sự kết hợp

3.5.1 Các khái ni m quan trọng về lu t kết hợp

Khái niệm luật kết hợp đƣợc phát biểu lần đầu tiên bởi R. Agrawal [5]

đã đƣa ra một định nghĩa về luật kết hợp nhƣ sau:

Định nghĩa: Cho tập I = {i1,i2, … ,in} là tập n thuộc tính nhị phân gọi là

các phần tử (item). Cho D = {t1,t2, … ,tm} là tập các giao tác gọi là cơ sở dữ

liệu. Mỗi giao tác trong D có một ID duy nhất và chứa tập các mục trong I.

Một luật được định nghĩa sự kéo theo có dạng X  Y trong đó X,Y  I và X 

Y = . Tập các mục gọi là tập mục (itemset) X gọi là phần mệnh đề điều kiện

và Y gọi là mệnh đề kết quả của luật tương ứng.

Để chọn ra các luật có ích từ tập các luật có thể có, ta cần ràng buộc

những số đo đảm bảo ý nghĩa. Hai ràng buộc đƣợc xem là quan trọng nhất, đó

là giá trị độ hỗ trợ và độ tin cậy tối thiểu.

Độ hỗ trợ của một luật kết hợp XY là tỷ lệ giữa số lƣợng các bản ghi

chứa tập hợp XY, so với tổng số các bản ghi trong D. Ký hiệu supp (XY).

Ví dụ, độ hỗ trợ của luật X =>Y là 5% có nghĩa là 5% các giao dịch X và Y

đƣợc mua cùng nhau.

Công thức để tính độ hỗ trợ của luật X =>Y nhƣ sau:

Độ tin cậy (minimum confident) đƣợc định nghĩa nhƣ sau: Độ tin cậy

của luật X  Y là xác suất xuất hiện Y với điều kiện X trong tất cả các giao

tác. Ví dụ độ tin cậy của luật kết hợp {Quả bóng } => Giày} là 90% có nghĩa

là 90% khách hàng mua Quả bóng cũng mua Giày

Để thu đƣợc các luật kết hợp ta có 2 bƣớc sau:

- Bước 1: giá trị độ hỗ trợ tối thiệu đƣợc áp dụng để tìm ra các tập mục

xuất hiện thƣờng xuyên trong cơ sở dữ liệu.

- Bước 2: là từ những tập này, áp dụng giá trị độ tin cậy tối thiệu để

tạo ra luật.

3.5.2 M t số thu t toán về lu t kết hợp

3.5.2.1. Thuật toán Apriori

Thuật toán do Agrawal đƣa ra năm 1994, là một thuật toán điển hình áp

dụng trong khai phá luật kết hợp. Thuật toán dựa trên nguyên lý Apriori “tập

con bất kỳ của một tập phổ biến cũng là một tập phổ biến”. Mục đích của thuật

toán Apriori là tìm ra đƣợc tất cả các tập phổ biến có thể có trong cơ sở dữ liệu

giao dịch D. Thuật toán hoạt động theo nguyên tắc quy hoạch động, nghĩa là từ

các tập Fi = { ci | ci là tập phổ biến, |ci| = 1} gồm mọi tập mục phổ biến có độ

dài i (1 ≤ i ≤ k), đi tìm tập Fk+1 gồm mọi tập mục phổ biến có độ dài k+1. Các

mục i1, i2,…, in trong thuật toán đƣợc sắp xếp theo một thứ tự cố định.

Nội dung thuật toán:

Input: Cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}.

Ngƣỡng tối thiểu minsup > 0.

Output: Tập hợp tất cả các tập phổ biến.

L1 = { tập 1 mục thƣờng xuyên }

for (k=2; Lk-1 <> Ø; k++)

begin

Ck = apriori-gen(Lk-1); // Sinh ra các ứng viên mới Ck từ tập Lk-1

for all tất cả giao tác t  D

begin

Ct = subset (Ck, t)//Chỉ lấy các ứng viên thuộc t

for all ứng viên c  Ct c.count++

end;

Lk = {c  Ct | c.count  minSup}

//chỉ lấy những ứng viên đủ điều kiện để xét cho bƣớc sau

End.

Tr g đó:

Hàm apriori-gen(Lk-1)

Trả kết quả là tập cha của tất cả các tập có k mục

Bƣớc 1: chọn 2 tập mục p, q từ tập Lk-1 mục.

- Nếu (k-2) mục của p và q giống nhau, thì ta tạo một ứng viên c mới từ p

và q,

- Ứng viên c này sẽ gồm (k-2) mục giống nhau và 2 mục khác nhau từ p

và q.

Bƣớc 2: bỏ bớt một số tập con ck-1 nếu c không nằm trong Lk-1.

Hàm Subset (Ck, t)

Các bƣớc thực hiện nhƣ sau:

Bƣớc 1: tạo ra một cây băm cho Ck

- Thêm tập mục c

 Đi từ gốc đế khi gặp nút lá

 Tại các nút trong không gian với độ sâu d, chọn nhánh để đi tiếp,

áp dụng hàm băm cho mục thứ d của c.

- Tất cả các nút băm đƣợc tạo ban đầu đƣợc xem nhƣ một cây.

- Một lá có thể chuyển thành nút trung gian khi số lƣợng nút tăng lên.

Bƣớc 2: Sau khi xây dựng cây băm Ck, hàm subset sẽ tìm các ứng viên

thuộc t nhƣ sau:

- Tại nút lá, tìm tập mục mà giao tác t chứa.

- Tại nút trung gian, khi sắp đến nút I, ta sẽ xem I có thuộc t hay không,

và đi theo nhánh tƣơng ứng.

- Tại nút gốc, tìm tất cả các mục thuộc t.

Ứng dụng của thu t toán Apriori

Sau khi đã biết thuật toán Apriori hoạt động thế nào, giờ chúng ta sẽ tìm

hiểu nó dùng để làm gì và dùng nó nhƣ thế nào :3

Dù g để làm gì?

Việc thuật toán Apriori có thể làm là nhìn vào quá khứ và khẳng định

rằng nếu một việc gì đó xảy ra thì sẽ có tỉ lệ bao nhiêu phần trăm sự việc tiếp

theo sẽ xảy ra. Nó giống nhƣ nhìn vào quá khứ để dự đoán tƣơng lại vậy, và

việc này rất có ít cho các nhà kinh doanh. Ví dụ một siêu thị muốn nghĩ cách

sắp xếp các gian hàng một cách hợp lí nhất, họ có thể nhìn vào lịch sử mua

hàng và sắp sếp các tập sản phẩm thƣờng đƣợc mua cùng nhau vào một chỗ.

Hoặc một trang web tin tức muốn giới thiệu cho ngƣời dùng các bài viết liên

quan đến nhau nhất, cũng có thể áp dụng quy luật tƣơng tự.

Đ h gi thu t toán:

Apriori là thuật toán đơn giản, dễ hiểu và dễ cài đặt.

Tuy nhiên hạn chế của thuật toán là:

˗ Phải duyệt cơ sở dữ liệu nhiều lần

˗ Số lƣợng lớn tập phổ biến đƣợc tạo ra làm gia tăng sự phức tạp không

gian.

˗ Thực hiện việc tính độ phổ biến nhiều, đơn điệu.

3.5.2.2. Thuật toán FP Growth

Thuật toán FP Growth (Frequent Pattern) ra đời vào tháng 5/2000 bởi

Jiawei Han, Jian pei và Yiwen Yin để tìm tập mục thƣờng xuyên bằng cách

không sinh các tập mục ứng viên từ các tập mục thƣờng xuyên trƣớc mà vẫn

hiệu quả bằng cách sử dụng ba kỹ thuật sau:

˗ Nén tập dữ liệu vào cấu trúc cây nhờ đó giảm chi phí cho toàn tập dữ

liệu dùng trong quá trình khai phá. Các mục không phổ biến đƣợc loại

bỏ sớm những vẫn đảm bảo kết quả khai phá không bị ảnh hƣởng.

˗ Khai thác phát triển tập các mẫu dựa trên FP-Tree, bắt đầu từ mẫu phổ

biến có kích thƣớc 1 và chỉ kiểm tra trên cơ sở mẫu ƣớc định, khởi tạo

FP-Tree của mẫu phụ thuộc, thực hiện khai phá đệ quy trên cây này.

Mẫu kết quả nhận đƣợc qua việc kết nối mẫu hậu tố với mẫu mới đƣợc

sinh ra từ FP-Tree ƣớc định.

˗ Tránh tạo ra các tập dự tuyển. Mỗi lần, giải thuật chỉ kiểm tra một

phần của tập dữ liệu.

Cây FP (còn gọi là FP-Tree) là cấu trúc dữ liệu dạng cây đƣợc tổ chức nhƣ

˗ Nút gốc đƣợc gán nhãn “null”

˗ Mỗi nút còn lại chứa các thông tin: item-name, count, node-link. Trong

đó:

 Item-name: Tên của mục mà nút đó đại diện.

 Count: Số giao dịch có chứa mẫu bao gồm các mục duyệt từ nút

gốc đến nút đang xét.

 Node-link: Chỉ đến nút kế tiếp trong cây (hoặc trỏ đến null nếu

nút đang xét là nút lá).

˗ Bảng Header có số dòng bằng số mục. Mỗi dòng chứa 3 thuộc tính:

item-name, item-count, node-link. Trong đó:

 Item-name: Tên của mục.

 Item-count: Tổng số biến count của tất cả các nút chứa mục đó.

 Node-link: Trỏ đến nút sau cùng đƣợc tạo ra để chứa mục đó

trong cây.

Thu t toán Xây dựng cây FP.

Input:

Cơ sở dữ liệu giao tác D

Giá trị .

Output: Cây FP của cơ sở dữ liệu giao tác.

Cách thực hiện:

Bƣớc 1: Duyệt D lần đầu để thu đƣợc tập F gồm các frequent item và

support count của chúng. Sắp xếp các item trong F theo trật tự giảm dần của

supprort count ta đƣợc danh sách FList.

Bƣớc 2: Tạo gốc của cây FP (kí hiệu T), gán nhãn là null. Tạo bảng

Header có |F| dòng và đặt tất cả các node –link chỉ đến null

Bƣớc 3: Quét từng giao tác Trans trong cơ sở dữ liệu, với mỗi giao tác t:

Chọn các items phổ biến trong t, sắp xếp dựa theo Flist. Gọi danh sách

này là [p|P], với p là item đầu tiên và P là các item còn lại.

Để khám phá các các mẫu phổ biến từ cây FP-Tree, ta sử dụng thủ tục

FP-Growth:

Input:

Cơ sở dữ liệu DB biểu diễn bằng cây FP, và Giá trị ngƣỡng support tối

thiểu ξ .

Output:

Tập hoàn chỉnh các mẫu phổ biến

Giải thuật: gọi FP-growth (FP-tree,null)

Procedure FP-Growth(Tree, α)

{

F = ϕ;

if Tree chỉ chứa một đường dẫn đơn P then

{

for each tổ hợp β của các nút trong P do

{

Phát sinh mẫu p = β ∪ α;

support_count(p) = min_sup các nút trong β;

F = F ∪ p;

}

else

for each ai in the header of Tree

{

Phát sinh mẫu β = ai∪ α;

support_count(β)=ai.support_count;

F = F ∪ β;

Xây dựng cơ sở có điều kiện của β;

Xây dựng FP-Tree có điều kiện Treeβ của β;

if (Treeβ != ϕ) thenCall FP_Growth(Treeβ, β);

}

Đ h gi thu t toán:

Nhƣợc điểm lớn nhất của giải thuật FP-Growth chính là việc xây dựng

cây FP khá phức tạp, đòi hỏi chi phí lớn về mặt thời gian và bộ nhớ. Tuy

nhiên một khi đã xây dựng xong cây FP thì việc khai phá các mẫu phổ biến lại

trở nên vô cùng hiệu quả.

3.6 Đ chính xác classifier

Đánh giá độ chính xác của bộ phân lớp rất quan trọng, bởi vì nó cho

phép dự đoán đƣợc độ chính xác của các kết quả phân lớp những dữ liệu

tƣơng lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau.

Holdout và hợp lệ chéo k-fold là hai kỹ thuật phổ biến để đánh giá độ chính

xác classifier dựa trên các phân chia lấy mẫu ngẫu nhiên từ dữ liệu cho trƣớc.

Trong phƣơng pháp holdout, dữ liệu dƣa ra đƣợc phân chia ngẫu nhiên

thành 2 phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thƣờng 2/3

dữ liệu cấp cho tập dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm định.

Việc đánh giá này là lạc quan bởi chỉ một phần dữ liệu ban đầu đƣợc

dùng để thu classifier. Lấy mẫu con ngẫu nhiên là một sự thay đổi của phƣơng

pháp holdout trong đó phƣơng pháp holdout đƣợc lặp lại k lần. Độ chính xác

classifier bằng giá trị trung bình của các độ chính xác có đƣợc từ mỗi lần lặp.

- Toàn bộ tập ví dụ D đƣợc chia thành 2 tập con không giao nhau

+ Tập huấn luyện D_train – để huấn luyện hệ thống.

+ Tập kiểm thử D_test – để đánh giá hiệu năng của hệ thống đã học

→ D = D_train ∪ D_test, và thƣờng là |D_train| >> |D_test| .

- Các yêu cầu:

+ Bất kỳ ví dụ nào thuộc vào tập kiểm thử D_test đều không đƣợc sử

dụng trong quá trình huấn luyện hệ thống.

+ Bất kỳ ví dụ nào đƣợc sử dụng trong giai đoạn huấn luyện hệ thống

đều không đƣợc sử dụng trong giai đoạn đánh giá hệ thống.

Các ví dụ kiểm thử trong D_test cho phép một đánh giá không thiên vị đối

với hiệu năng của hệ thống.

- Các lựa chọn thƣờng gặp: |D_train|=(2/3).|D|, |D_test|=(1/3).|D|

- Phù hợp khi ta có tập ví dụ D có kích thƣớc lớn.

Trong phƣơng pháp hợp lệ chéo K-fold dữ liệu ban đầu đƣợc phân chia

ngẫu nhiên vào trong k tập con riêng biệt ("các fold") S1,S2,...,Sk, chúng có

kích thƣớc xấp xỉ bằng nhau. Mỗi lần (trong số k lần) lặp, một tập con đƣợc

sử dụng làm tập kiểm thử, và (k-1) tập con còn lại đƣợc dùng để làm tập huấn

luyện. Tức là classifier của lần lặp đầu tiên đƣợc huấn luyện trên các tập con

S2,S3,...,Sk và đƣợc kiểm định trên S1; classifier của lần lặp thứ 2 đƣợc huấn

luyện trên các tập con S1,S3,...,Sk và đƣợc kiểm định trên S2, v.v... Các lựa

chọn thông thƣờng của k là 10 hoặc 5, phù hợp khi có tập ví dụ D vừa và nhỏ.

Độ chính xác classifier là toàn bộ số lƣợng các phân loại chính xác từ k

lần lặp chia cho tổng số lƣợng các mẫu trong dữ liệu ban đầu. Trong hợp lệ

chéo phân tầng, các fold đƣợc phân tầng để sự phân bố lớp của các mẫu trong

mỗi fold xấp xỉ nhƣ sự phân bố lớp trong dữ liệu ban đầu.

3.7 Kết lu n

Chƣơng này trình bày một số phƣơng pháp phân lớp dữ liệu phổ biến nhƣ

phân lớp bằng cây quyết định, phân lớp Bayesian, phân lớp dựa trên sự kết hợp

và độ chính xác classifier. Qua đó, ta có thể thấy đƣợc khả năng phân lớp của

từng phƣơng pháp cũng nhƣ khả năng áp dụng vào các bài toán thực tiễn.

CHƢƠNG 4

MỘT SỐ KẾT QUẢ THỬ NGHIỆM

4.1. Gi i thi u về công cụ phân cụm, phân l p dữ li u Weka

Weka là môi trƣờng thử nghiệm khai phá dữ liệu do các nhà khoa học

thuộc trƣờng Đại học Waitako, khởi xƣớng và đƣợc sự đóng góp của rất nhiều

nhà nghiên cứu khoa học trên thế giới. Weka là một bộ phần mềm mã nguồn

mở miễn phí, cung cấp công cụ để chuyển đổi các bộ dữ liệu nhƣ các thuật

toán để phân loại và lấy mẫu một cách trực quan cùng với các giao diện ngƣời

dùng đồ hoạ để dễ dàng thao tác các chức năng này. Weka còn cho phép các

giải thuật học mới phát triển có thể tích hợp vào môi trƣờng của nó. Hệ thống

đƣợc xây dựng bằng ngôn ngữ lập trình java, đƣợc tổ chức thành những thƣ

viện phục vụ cho khai phá dữ liệu và lĩnh vực học máy.

Weka cung cấp những tính năng chính sau:

- Bao gồm nhiều công cụ hữu ích để thay đổi tập dữ liệu, xử lý dữ liệu,

mô hình hoá dữ liệu.

- Đƣợc tổ chức theo dạng mã nguồn mở để ngƣời dùng dễ dowload và sử dụng.

- Kiến trúc dạng thƣ viện với hơn 600 lớp và đƣợc tổ chức thành 10 gói

(package) dễ dàng cho việc xây dựng các ứng dụng thực nghiệm.

- Độc lập với môi trƣờng do sử dụng máy ảo Java(JVM –Java virtual

machine).

- Giao diện đồ hoạ giúp ngƣời dùng dễ sử dụng.

- Môi trƣờng cho phép so sánh các giải thuật học máy và khai phá dữ liệu.

Weka cung cấp 5 môi trƣờng làm việc để hỗ trợ ngƣời dùng hai chức

năng chính là khai phá dữ liệu và thực nghiệm, đánh giá các mô hình học máy.

Hình 4. 1. Gia di chí h của hầ ề

- Explorer: Môi trƣờng cho phép tiến hành khai phá dữ liệu với nhiều

tính năng nhƣ tiền xử lý dữ liệu (Preprocess), phân lớp (Classify), phân cụm

(Cluster), khai thác luật kết hợp (Associate). Ngoài ra, phần mềm còn có thể

hỗ trợ lựa chọn thuộc tính (Select attributes) và mô hình hoá dữ liệu

(Visualize).

- Experimenter: Môi trƣờng cho phép thực nghiệm, so sánh, phân tích

các mô hình học máy.

- KnowledgeFlow: Môi trƣờng này hỗ trợ các tính năng tƣơng tự nhƣ

Explorer nhƣng với một giao diện kéo thả tƣợng trƣng cho các giải thuật và

dữ liệu để kết nối chúng lại với nhau và đƣa ra cấu trúc.

- Simple CLI: Với việc cung cấp giao diện dòng đơn giản cho phép trực

tiếp thực hiện các lệnh của phần mềm Weka cho các hệ điều hành không cung

cấp giao diện dòng lệnh riêng.

- Workbench: Đây là môi trƣờng với sự kết hợp của tất cả các môi

trƣờng nêu trên, ngƣời dùng không cần quay lại cửa sổ chính mà có thể

chuyển đổi qua lại giữa chúng với nhau.

4.2. Ứng dụng phân cụm dữ li u để phân nhóm khách hàng

Trong khuôn khổ luận văn, dữ liệu đƣợc lấy từ địa chỉ website:

https://github.com/bluenex/WekaLearningDataset

Dữ liệu dùng để phân cụm trong ví dụ này là dữ liệu dùng để phân loại

khách hàng của ngân hàng (file dữ liệu bank-k.aff), gồm có 11 thuộc tính và

600 khách hàng dƣới đây là cấu trúc và phân bố dữ liệu của bank-k.arff.

Bảng 4.1. Bảng thông tin cấu trúc của file dữ li u bank-k.arff

Thu c Kiểu dữ STT Giá trị Mô tả tính li u

Nominal 0_34,35_51,52_max Tuổi khách hàng 1.

Nominal FEMALE,MALE Giới tính 2. age sex

INER_CITY,TOWN, Nominal Khu vực cƣ trú 3. region RURAL, SUBURBAN

0_24386,24387_43758, income Nominal Thu nhập 4. 43759_max

Tình trạng hôn nhân 5.

Số con 6.

Nominal NO, YES Có xe hơi không? 7. married Nominal NO, YES children Nominal 0,1,2,3 car

KH có tài khoản tiết kiệm

8. save_act Nominal NO, YES không (saving account)

current_a Hiện tại có tài khoản Nominal NO, YES 9. ct không?

Có vay thế chấp không? 10. mortgage Nominal NO, YES

KH có kế hoạch trả nợ

Nominal NO, YES không (Personal Equity 11. pep

Plan)

Hình 4.2. Thông tin dữ li u cơ bản của file bank-k.arff hiển thị bởi Weka

Phần này tôi sẽ triển khai kỹ thuật phân cụm dựa trên thuật toán K-

means trên phần mềm Weka.

K-means là thuật toán đƣợc sử dụng phổ biến trong kỹ thuật phân cụm,

thuật toán với ý tƣởng là tìm cách nhóm các đối tƣợng đã cho vào K cụm (K

là số các cụm đƣợc xác định trƣớc, K nguyên dƣơng), phƣơng thức phân cụm

nhóm dữ liệu thực hiện dựa trên khoảng cách Euclidean nhỏ nhất giữa đối

tƣợng đến phần tử trung tâm của các cụm.

Thuật toán K-means bao gồm các bước cơ bản sau:

 B1: Chọn K tâm (centroid) cho K cụm (cluster), việc chọn giá trị

K có thể là ngẫu nhiên hoặc theo kinh nghiệm.

 B2: Tính khoảng cách giữa các đối tƣợng đến K tâm (dùng khoảng

cách Euclidean).

 B3: Nhóm các đối tƣợng vào nhóm gần nhất.

 B4: Cập nhật lại tâm mới cho các nhóm.

 B5: Lặp lại bƣớc 2 cho đến khi không còn sự thay đổi của các

Bắt đầu

Số cụm K

sai

Trọng tâm

đúng

Không có

Kết thúc

Tính khoảng cách các đối

đối tƣợng

tƣợng đến các tâm

Nhóm các đối tƣợng vào

các cụm

trọng tâm cụm.

Hình 4.3. Lƣu đồ thu t toán K-Means

Ở đây em sẽ dùng thuật toán K-means để phân nhóm các khách hàng vào

K nhóm (trong lần mô phỏng này thử K= 3 và K=5) dựa vào sự tƣơng tự

(similar) trên 11 thuộc tính của bảng dữ liệu, cách tính khoảng cách dùng

khoảng cách Euclidean.

Hình 4.4. Bảng tham số sử dụng cho thu t toán K-Means: Hình (a) K=3;

Hình (b): K=5

Kết quả thu đƣợc khi phân cụm bằng thuật toán K-means nhƣ sau:

V i K=3

Hình 4.5. Kết quả phân cụm v i thu t toán K-Means (K=3)

Nhƣ hiển thị ở Hình 4.5, thuật toán phân dữ liệu khách ở trên thành 3

cụm: cụm 0 chứa 287 bản ghi, tƣơng đƣơng 47,83%; cụm 1 chứa 177 bản ghi,

tƣơng đƣơng 29,50%; cụm 2 chứa 136 bản ghi, tƣơng đƣơng 22,67%.

V i K=5

Hình 4.6. Kết quả phân cụm v i thu t toán K-Means (K=5)

Giống như các thuật toán khác, K-means cũng có những hạn chế nhất định:

- Số nhóm K luôn phải xác định trƣớc.

- Việc khởi tạo phần tử trung tâm của nhóm ban đầu ảnh hƣởng đến sự

phân chia đối tƣợng vào nhóm trong trƣờng hợp dữ liệu không lớn.

- Đ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 rõ ràng vùng của nhóm, cùng một đối tƣợng, nó

có thể đƣợc đƣa vào nhóm này hoặc nhóm khác khi dung lƣợng dữ liệu thay đổi.

- 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.

4.3. Ứng dụng phân l p dữ li u để phân l p

Trong lĩnh vực khai phá dữ liệu, mục đích của luật kết hợp là tìm ra các

mối kết hợp hay tƣơng quan giữa các đối tƣợng trong khối lƣợng lớn dữ liệu.

Ứng dụng của luật kết hợp rất phổ biến ở nhiều lĩnh vực nhất là trong kinh

doanh nhƣ Market Basket Analysis.

4.3.1. Phân lớp dữ liệu với thuật toán Apriori

Thuật toán Apriori đƣợc dùng để phát hiện các luật kết hợp dạng khẳng

định (Positive Rule X=Y) nhị phân (Binary Association) chứ không thể phát

hiện các luật kết hợp ở dạng phủ định (Negative Association Rule) chẳng hạn

nhƣ các kết hợp dạng “Khách hàng mua mặt hàng X thƣờng không mua mặt

hàng Y”.

Vẫn sử dụng dữ liệu bank-k.aff sau đây em sẽ sử dụng thuật toán Apriori

để phát hiện các luật kết hợp trên phần mềm Weka.

Chọn tab Association và chọn thuật toán Apriori.

Hình 4.7. Giao di n Weka chọn thu t toán Apriori

Thiết lập các tham số (numRules, support, confidence,…)

Hình 4.8. Giao di n Weka thiết l p tham số cho thu t toán Apriori

Giải thích các tham số chính đối với thuật toán Apriori.

LowerBoundMinSupport: Cận dƣới của minimum support

MetricType: Có 4 loại metricType là Confidence, Lift, Leverage,

Conviction.

Minium metric score: Chỉ quan tâm đến các luật có metric score cao hơn

giá trị này.

NumRuler: Số luật muốn tìm (Các luật sẽ sắp xếp theo thứ tự giảm dần

của metric score).

Hình 4.9. Kết quả sinh lu t bởi thu t toán Apriori

Nhƣ thể hiện ở Hình 4.9, 10 luật tốt nhất đƣợc sinh ra bởi thuật toán

Apriori trên dữ liệu nhƣ trên. Thông qua thuật toán, ta có thể dự đoán và biết

đƣợc độ tin cậy của khách hàng tham gia vào hệ thống ngân hàng. Ví dụ:

Luật số 1 cho biết rằng nếu thu nhập (income) lớn hơn hoặc bằng 43759

thì khách hàng có tài khoản tiết kiệm (save_act = YES) với độ tin cậy bằng 1.

Luật số 2 cho biết rằng nếu tuổi (age) lớn hơn hoặc bằng 52 và thu nhập

lớn hơn 43759 thì khách hàng có tài khoản tiết kiệm với độ tin cậy bằng 1.

Hạn chế của thuật toán Apriori.

- Số lƣợng lớn tập phổ biến đƣợc tạo ra làm gia tăng sự phức

tạp không gian.

- Để xác định độ Support của các tập ứng viên, thuật toán luôn

luôn phải quét lại toàn bộ cơ sở dữ liệu. Do vậy sẽ tiêu tốn rất nhiều

thời gian khi số k-iteams tăng.

- Khi số lần duyệt cơ sở dữ liệu nhiều làm gia tăng sự phức tạp

thời gian khi cơ sở dữ liệu gia tăng.

Do những hạn chế đó, một điều cần thiết phải đƣa ra một số thay đổi

trong thuật toán Apriori .

4.3.2. Phân lớp dữ liệu với thuật toán Naive Bayes

Tiếp tục sử dụng dữ liệu bank-k.aff, sau đây em sẽ sử dụng thuật toán

là Naive Bayes để phân lớp và dự đoán khả năng trả nợ của khách hàng

(pep=Yes: Có kế hoạch trả nợ; pep=NO: Chƣa có kế hoạch trả nợ).

Đầu tiên, tiến hành chọn thuật toán phân lớp dữ liệu Naive Bayes theo

nhƣ hình bên dƣới:

Hình 4.10. Giao di n Weka lựa chọn thu t toán Naive Bayes

Tiếp theo, tiến hành xây dựng mô hình phân lớp và đánh giá chéo 10-

fold với thuật toán Naive Bayes để dự đoán, ta thu đƣợc kết quả nhƣ hình

dƣới:

Hình 4.11. Kết quả sinh lu t bởi thu t toán Naive Bayes

Nhƣ kết quả thể hiện ở Hình 4.11 mô hình đạt độ chính xác 70,3%.

Thông qua mô hình này, ta có thể xây dựng đƣợc mô hình phân lớp dữ liệu

khách hàng để dự đoán cho một/hoặc 1 nhóm đối tƣợng khách hàng về tình

trạng/kế hoạch trả nợ, với tỷ lệ chính xác 70,3%. Đây cũng đƣợc coi là một cơ

sở quan trọng, có độ tin cậy chấp nhận đƣợc để giúp cho ngân hàng xây dựng

kế hoạch triển khai cung cấp/giải quyết các dịch vụ ngân hàng đối với khách

hàng.

4.3.3. Phân lớp dữ liệu với thuật toán C4.5

Vẫn sử dụng dữ liệu bank-k.arff, sau đây em sẽ sử dụng thuật toán

là C4.5 để phân lớp và dự đoán khả năng trả nợ của khách hàng (pep=Yes:

Có kế hoạch trả nợ; pep=NO: Chƣa có kế hoạch trả nợ), thuật toán C4.5 đƣợc

gọi là thuật toán j48 trong WEKA. C4.5 là một thuật toán đƣợc sử dụng để tạo

cây quyết định đƣợc phát triển bởi Ross Quinlan. C4.5 là phần mở rộng của

thuật toán ID3 trƣớc đó của Quinlan. Các cây quyết định đƣợc tạo bởi C4.5 có

thể đƣợc sử dụng để phân loại và vì lý do này, C4.5 thƣờng đƣợc gọi là phân

loại thống kê. Nó trở nên khá phổ biến sau khi xếp hạng là 1 trong 10 thuật

toán hàng đầu về khai thác dữ liệu.

Đầu tiên, tiến hành chọn thuật toán phân lớp dữ liệu C4.5 theo nhƣ hình

bên dƣới:

Hình 4.12. Giao di n Weka lựa chọn thu t toán C4.5

Tiếp theo, tiến hành xây dựng mô hình phân lớp và đánh giá chéo 10-

fold với thuật toán C4.5 để dự đoán, ta thu đƣợc kết quả nhƣ hình dƣới:

Hình 4.13. Kết quả sinh lu t bởi thu t toán C4.5

Nhƣ thể hiện Hình 4.13, mô hình đạt độ chính xác 85%. Có thể thấy thấy

đối với bộ dữ liệu bank-k.arff thuật toán C4.5 cho hiệu quả tốt hơn so với

thuật toán Naive Bayes.

KẾT LUẬN

Sau một thời gian làm việc, nghiên cứu dƣới sự hƣớng dẫn tận tình của

thầy giáo TS. Nguyễn Văn Núi, tôi đã đạt đƣợc các kết quả sau đây:

1. Trình bày đầy đủ và chi tiết các vấn đề liên quan đến khai phá dữ

liệu và phát hiện tri thức; các thuật toán phân cụm, phân lớp dữ liệu và ứng

dụng.

2. Giới thiệu và trình bày công cụ phần mềm Weka (Waikato

Environment for Knowledge Analysis) - một bộ phần mềm học

máy đƣợc Đại học Waikato, New Zealand phát triển bằng Java, ứng dụng

trong phân lớp, phân cụm dữ liệu.

3. Cài đặt, cấu hình phần mềm Weka và tiến hành phân cụm, phân lớp

dữ liệu thực hiện trong phân cụm, phân lớp dữ liệu khách hàng bank-k.arff.

Hƣ g h t triể của u vă :

Trong thời gian tới, tôi sẽ tiếp tục nghiên cứu sâu hơn về các vấn đề

của phân cụm, phân lớp dữ liệu, đặc biệt sẽ nghiên cứu tìm hiểu sâu hơn việc

ứng dụng phần mềm Weka để tiến hành phân tích dữ liệu ứng dụng trong các

lĩnh vực cụ thể nhƣ phân lớp, dự đoán dữ liệu khách hàng.

Tiến hành nghiên cứu thu thập bộ dữ liệu trong thực tế với số lƣợng lớn

hơn, tiến hành cài đặt module mã lệnh để tự động hóa quá trình khai phá dữ

liệu, phát hiện tri thức.

TÀI LIỆU THAM KHẢO

Tiếng Vi t:

[1]. Lê Văn Phùng, Quách Xuân Trƣởng (2012), Khai phá dữ

liệu, NXB Thông tin và truyền thông.

Tiếng Anh:

[2]. Anil K. Jain, Richard C. Dubes (1988), “Algorithms for

clustering data”, Published by Prentice Hall, Lebanon, Indiana, U.S.A.

[3]. Leonard Kaufman, Peter J. Rousseeuw (1990), “Finding

Groups in Data An Introduction to Cluster Analysis”, Publisher

by Wiley-Interscience.

[4]. J.Ross Quinlan (1993), “Programs for machine learning”,

Morgan Kaufmann Publishers Inc. San Francisco, CA, USA.

[5]. Rakesh Agrawal (1993),“Mining Association Rules Between

Sets of Items in Large Databases”, Publishers IBM Almaden Research

Center 650 Harry Road, San Jose.

Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán phân cụm, phân lớp dữ liệu và ứng dụng

THÁI NGUYÊN - 2019

U N VĂN THẠ Ĩ KHOA HỌ M Y TÍNH

Người hướng dẫn khoa học: TS. NGUYỄN VĂN NÚI THÁI NGUYÊN - 2019

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok