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

Nguyễn Nhƣ Thế

Nguyễn Nhƣ Thế
NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU
NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU
VÀ ỨNG DỤNG TRONG BÀI TOÁN DỰ BÁO THUÊ BAO
VÀ ỨNG DỤNG TRONG BÀI TOÁNDỰ BÁOTHUÊ BAO
RỜI MẠNG VIỄN THÔNG
RỜI MẠNG VIỄN THÔNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên -2016
Thái Nguyên - 2016


ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC
THÁI
NGUYÊN

TRONG
BÀI
TOÁNDỰ
BÁOTHUÊ
BAO
RỜI MẠNG
MẠNG VIỄN
VIỄN THÔNG
THÔNG
RỜI
Chuyên ngành: Khoa học máy tính
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 0101
Mã số: 60 48 0101
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC:TS.NGUYỄN LONG GIANG
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS NGUYỄN LONG GIANG

Thái Nguyên -2016
Thái Nguyên - 2016


i

LỜI CAM ĐOAN

Tên tôi là: Nguyễn Nhƣ Thế
Sinh ngày: 12/12/1989
Học viên lớp cao học: CHK13E - Trƣờng Đại học Công nghệ thông tin

Tôi xin cảm ơn Chi nhánh Mobifone Phú Thọ đã nhiệt tình giúp đỡ, cung
cấp thông tin trong quá trình nghiên cứu, thực nghiệm chƣơng trình luận văn.
Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động
viên, khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện
và hoàn thành luận văn này.
Thái Nguyên, ngày 28 tháng 6 năm 2016
HỌC VIÊN

Nguyễn Nhƣ Thế


iii

MỤC LỤC
LỜI CAM ĐOAN ............................................................................................................. i
LỜI CẢM ƠN .................................................................................................................. ii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................... v
DANH MỤC HÌNH ẢNH .............................................................................................. vi
DANH MỤC BẢNG BIỂU........................................................................................... vii
MỞ ĐẦU .......................................................................................................................... 1
Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .................................................. 3
1.1. Tổng quan về khai phá dữ liệu ....................................................................... 3
1.1.1. Tại sao cần khai phá dữ liệu .................................................................... 3
1.1.2. Các khái niệm cơ bản .............................................................................. 3
1.1.3. Quy trình khai phá dữ liệu ....................................................................... 5
1.1.4. Các bài toán cơ bản trong khai phá dữ liệu .............................................. 6
1.1.5. Các ứng dụng của khai phá dữ liệu .......................................................... 7
1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu .......................................... 8
1.2.Bài toán phân lớp và dự báo ......................................................................... 10
1.2.1. Giới thiệu bài toán ................................................................................. 10

3.3.1. Phân lớp dữ liệu sử dụng cây quyết định C4.5 ....................................... 51
3.3.2. Phân lớp dữ liệu sử dụng phƣơng pháp Naive Bayes ............................. 53
3.3.3. Phân lớp dữ liệu bằng Support Vector Machines .................................. 55
3.3. Đánh giá kết quả.......................................................................................... 56
KẾT LUẬN .................................................................................................................... 58
TÀI LIỆU THAM KHẢO ............................................................................................. 60


v

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

TT

Thuật ngữ

Định nghĩa

1. KPDL

Khai phá dữ liệu

2. KDD

Knowledge Discovery and Data Mining

3. NB

Naïve Bayes


Hình 3.10 – Hiệu năng các thuật toán với lớp thuê bao rời mạng ............................ 57


vii

DANH MỤC BẢNG BIỂU

Bảng 1 - Ma trận nhầm lẫn ..................................................................................... 49
Bảng 2 – Kết quả mô hình phân lớp sử dụng C 4.5 ................................................. 53
Bảng 3 – Độ đo hiệu năng thuật toán Cây quyết định ............................................. 53
Bảng 4 – Kết quả mô hình phân lớp sử dụng NB .................................................... 54
Bảng 5. – Độ đo hiệu năng thuật toán NB ............................................................... 54
Bảng 6 – Kết quả mô hình phân lớp sử dụng SVM ................................................ 55
Bảng 7. – Độ đo hiệu năng thuật toán SVM ............................................................ 56
Bảng 8. – Tổng hợp đánh giá hiệu năng các phƣơng pháp phân lớp ........................ 56


1

MỞ ĐẦU
Sự bùng nổ và phát triển của ngành công nghệ thông tin đã làm lƣợng dữ
liệu đƣợc thu thập và lƣu trữ ở các hệ thống thông tin tăng lên một cách nhanh
chóng. Trƣớc tình hình đó, việc khai thác và chọn lọc những dữ liệu có ích,
tiền ẩn từ lƣợng dữ liệu khổng lồ này là rất cần thiết. Các tri thức trích lọc từ
dữ liệu sẽ giúp các cơ quan, tổ chức đƣa ra những dự báo và điều hành hiệu
quả.
Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge
discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin với
mục tiêu là tìm kiếm các tri thức có ích, cần thiết, tiềm ẩn và chƣa đƣợc biết
trƣớc trong cơ sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đông đảo các

1.1. Tổng quan về khai phá dữ liệu
1.1.1. Tại sao cần khai phá dữ liệu
Khoảng hơn một thập kỷ trở lại đây, lƣợng thông tin đƣợc lƣu trữ trên
các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên.
Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Ngƣời ta ƣớc đoán
rằng lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo
đó số lƣợng cũng nhƣ kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên
một cách nhanh chóng. Nói một cách hình ảnh là chúng ta đang “ngập” trong
dữ liệu nhƣng lại “đói” tri thức. Câu hỏi đặt ra là liệu chúng ta có thể khai
thác đƣợc gì từ những “núi” dữ liệu tƣởng chừng nhƣ “bỏ đi” ấy không? [3]
“Necessity is the mother of invention” - Data Mining ra đời nhƣ một
hƣớng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên. Khá nhiều định nghĩa
về Data Mining, tuy nhiên có thể tạm hiểu rằng Data Mining nhƣ là một công
nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu
đƣợc tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.
1.1.2. Các khái niệm cơ bản
Khai phá dữ liệu (datamining) [4] đƣợc định nghĩa nhƣ là một quá trình
chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Một ví dụ hay đƣợc sử
dụng là là việc khai thác vàng từ đá và cát, Dataming đƣợc ví nhƣ công việc
"Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trƣớc. Thuật ngữ
Dataming ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lƣợng
lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng
tự với từ Datamining nhƣ Knowledge Mining (khai phá tri thức), knowledge


4

extraction (chắt lọc tri thức), data/patern analysis(phân tích dữ liệu/mẫu), data
archaeoloogy (khảo cổ dữ liệu), datadredging(nạo vét dữ liệu),...
Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng

2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành
những kho dữ liệu (data warehouses & data marts) sau khi đã làm
sạch và tiền xử lý (data cleaning & preprocessing).
3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho
dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai
thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu
(noisy data), dữ liệu không đầy đủ (incomplete data), .v.v.
4. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù
hợp cho quá trình xử lý.
5. Khai phá dữ liệu (data mining): Là một trong các bƣớc quan trọng
nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra
những mẫu dữ liệu.
6. Ƣớc lƣợng mẫu (knowledge evaluation): Quá trình đánh giá các kết
quả tìm đƣợc thông qua các độ đo nào đó.
7. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng
các kỹ thuật để biểu diễn và thể hiện trực quan cho ngƣời dùng.


6

Hình 1.1- Các bước trong khai phá dữ liệu [1]
1.1.4. Các bài toán cơ bản trong khai phá dữ liệu
Mô tả khái niệm (concept description): là bài toán tìm đặc trƣng và tính
chất của khái niệm. Bài toán thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví
dụ: tóm tắt văn bản.
Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng
khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80%
trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp đƣợc ứng dụng nhiều
trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trƣờng chứng
khoán, .v.v.

mẫu, luật ... Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích


8

trực tuyến (OLAP- On Line Analytical Processing) cũng liên quan rất chặt
chẽ với phát hiện tri thức và khai phá dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng trong thực tế,[3] ví dụ nhƣ:
 Bảo hiểm, tài chính và thị trƣờng chứng khoán: phân tích tình hình tài
chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng
khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện
gian lận, ...
 Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.
 Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh
lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa
các triệu chứng bệnh, chuẩn đoán và phƣơng pháp điều trị (chế độ
dinh dƣỡng, thuốc, ...)
 Sản xuất và chế biến: Quy trình, phƣơng pháp chế biến và xử lý sự cố.
 Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm
tắt văn bản,...
 Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật
học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ
gene và một số bệnh di truyền, ...
 Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám
sát lỗi, sự cố, chất lƣợng dịch vụ, dự báo thuê bao rời mạng ...
1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu
Việc thực hiện một DMM với đầy đủ 4 bƣớc công việc chính của quá
trình khai phá dữ liệu là:



Tiến trình phân lớp dựa trên 4 thành phần cơ bản:
- Lớp (class)
- Dự đoán (predictors)
- Tập dữ liệu được đào tạo (Training dataset)
- Tập dữ liệu kiểm thử (Testing dataset)
Đặc trƣng của tiến trình phân lớp gồm những điểm sau:
Input: tập dữ liệu đào tạo chứa những đối tƣợng với thuộc tính của
nó,với một số thuộc tính đã đƣợc gán nhãn;
Output: mô hình (classifier) đƣợc gán bởi những nhãn cụ thể cho mỗi đối
tƣợng phân lớp các đối tƣợng từng các thƣ mục), dựa trên những thuộc tính
khác;
Dự báo: là một quá trình gồm hai bƣớc, nó gần giống với quá trình phân
lớp. Tuy nhiên để dự báo, chúng ta bỏ qua khái niệm nhãn phân lớp bởi vì các
giá trị đƣợc dự báo là liên tục (đƣợc sắp xếp) hơn là các giá trị phân loại. Ví
dụ thay vì phân loại xem một khoản vay có là an toàn hay rủi do thì chúng ta
sẽ dự đoán xem tổng số tiền cho vay của một khoản vay là bao nhiêu thì
khoản vay đó là an toàn.
Có thể xem xét việc dự báo cũng là một hàm y = f(X), trong đó X là dữ
liệu đầu vào, và đầu ra là một giá trị y liên tục hoặc sắp xếp đƣợc. Việc dự
báo và phân lớp có một vài điểm khác nhau khi sử dụng các phƣơng pháp xây


11

dựng mô hình. Giống với phân lớp, tập dữ liệu huấn luyện sử dụng để xây
dựng mô hình dự báo không đƣợc dùng để đánh giá tính chính xác. Tính
chính xác của mô hình dự báo đƣợc đánh giá dựa trên việc tính độ lệch giá
các giá trị dự báo với các giá trị thực sự nhận đƣợc của mỗi bộ kiểm tra X.
1.2.2 Các bƣớc giải quyết bài toán
Các bƣớc giải quyết bài toán gồm:

- Node trong: Mỗi node trong của cây cũng tƣơng ứng với một thuộc tính
điều kiện. Một node trong của cây có thể coi nhƣ là node gốc của một cây
con.Mỗi node trong chỉ bao hàm những đối tƣợng dữ liệu thuộc một nhánh cụ
thể của node cha.


13

- Node lá: node cuối trong nhánh mà tất cả các đối tƣợng đều thuộc một
lớp hoặc không còn thuộc tính điều kiện nào để phân chia hoặc không còn đối
tƣợng dữ liệu nào để phân chia.
Điều quan trọng của thuật toán cây quyết định là tiêu chí đánh giá để tìm
điểm chia. Ý tƣởng chính trong việc đƣa ra các tiêu chí này là làm sao cho các
tập con đƣợc phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng
một nhãn) càng tốt. Quinlan đã phát triển thuật toán ID3 dùng độ đo thông tin
thu thêm (Information Gain - Gain) để xác định điểm chia tốt nhất. Độ đo này
dựa trên cơ sở lý thuyết thông tin của Claude Shannon (1948) để đo tính
thuần nhất (hay ngƣợc lại là pha trộn) của một tập hợp. Độ đo này đƣợc xác
nhƣ sau:
Entropy (S) =

m
i=1 Pi

log 2 Pi (1.1)

Trong đó m là số lƣợng các lớp khác nhau và Pi là tỉ lệ các đối tƣợng
mang nhãn i.
Để xác định điểm chia, ID3 so sánh entropy của một node cha với tổng tỉ
lệ entropy của các node con sau khi phân chia, Gain(S, A) của thuộc tính A,

Thuật toán C4.5, một cải tiến của ID3, mở rộng cách tính Information
Gain thành Gain Ratio để chọn thuộc tính phân chia trong quá trình xây dựng
cây.
Gain Ratio đƣợc xác định bởi công thức sau:
GainRatio =

Gain(S, A)
(1.3)
SplitInformation(S, A)

Trong đó: SplitInformation(S, A) chính là thông tin do phân tách của A
trên cơ sở giá trị của thuộc tính phân loại S. Công thức tính nhƣ sau:
m

SplitInformation S, A = −

|Si |
|Si |
log 2
(1.4)
|S|
i=1 |S|


15

2.2. Phân lớp bằng phƣơng pháp Bayesian
Thuật toán phân lớp Naïve Bayes (NB) là một trong những thuật toán
phân lớp điển hình nhất trong học máy và khai thác dữ liệu. Naïve Bayes là
phƣơng pháp phân lớp dựa vào xác suất đƣợc sử dụng rộng rãi trong lĩnh vực


n
k=1 P

𝑋𝑘 𝐶𝑗

Trong đó:
- P(Ci|X) là xác suất thuộc phân lớp i khi biết trƣớc mẫu X.

(2.2)


16

- P(Ci) xác suất là phân lớp i.
- P(xk|Ci) xác suất thuộc tính thứ k mang giá trị xk khi biết X thuộc
phân lớp i.
Các bƣớc thực hiện thuật toán Naive Bayes:
Bước 1: Huấn luyện Naive Bayes (dựa vào tập dữ liệu), tính P(Ci ) và
P(Xk|Ci)
Bước 2: Phân lớp Xnew= (x1,x2,...,xn), tính xác suất từng lớp khi đã
biết trƣớc đƣợc gán vào lớp có xác suất lớn nhất theo công thức
𝑚𝑎𝑥𝐶𝑖 ∈ 𝐶 𝑃 𝐶𝑖

𝑛
𝑘=1 𝑃

𝑋𝑘 Ci

(2.3)