ĐẠ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
UM T
PHÂN
M PHÂN
P

U N VĂN THẠ

THU T TO N
I UV
NG

Ĩ KHOA HỌ M Y TÍNH

THÁI NGUYÊN - 2019

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
UM T

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


2

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

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


4

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

STT Từ viết tắt

Viết đầy đủ

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

5


OPTICS

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

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ố


8

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.


9

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

(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.


11

(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.

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)...;


13

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

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.


15

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

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


18

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ự.
Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như:
-

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


19

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.



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


21

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ự

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.


23

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