BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRẦN THỊ LƢƠNG
TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI
LUẬN VĂN THẠC SỸ
CÔNG NGHỆ THÔNG TIN
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN
NGHİÊN CỨU PHƢƠNG PHÁP HỌC MÁY CHO PHÂN LỚP
DỮ LİỆU HỌC VİÊN TẠO NGUỒN PHÁT TRİỂN ĐẢNG
TRẦN THỊ LƢƠNG
2016-2018
HÀ NỘI - 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI
LUẬN VĂN THẠC SỸ
NGHİÊN CỨU PHƢƠNG PHÁP HỌC MÁY CHO PHÂN LỚP
DỮ LİỆU HỌC VİÊN TẠO NGUỒN PHÁT TRİỂN ĐẢNG
TRẦN THỊ LƢƠNG
CHUYÊN NGÀNH : CÔNG NGHỆ THÔNG TIN
MÃ SỐ: 8.48.02.01
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN QUANG HOAN
HÀ NỘI - 2018
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả
nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công
trình nào khác.
Hà Nội, ngày
tháng
năm 2018
HỌC VIÊN
Trần Thị Lƣơng
i
LỜI CẢM ƠN
Em xin chân thành cảm ơn Trƣờng Đại học Kỹ thuật - Hậu cần CAND, Khoa
Công nghệ thông tin - Trƣờng Đại học Mở Hà Nội đã tạo điều kiện thuận lợi giúp
em hoàn thành luận văn này.
Em xin chân thành cảm ơn sự hƣớng dẫn, chỉ bảo tận tình của PGS.TS.
Nguyễn Quang Hoan trong suốt thời gian thực hiện đề tài, cảm ơn thầy đã luôn
dành thời gian giúp đỡ em để có thể hoàn thành đƣợc luận văn này.
Em xin cảm các thầy cô giáo khoa Công nghệ thông tin - Trƣờng Đại học
Mở Hà Nội đã truyền thụ kiến thức, hỗ trợ em trong suốt quá trình học tập vừa qua;
Cảm ơn bạn bè, đồng nghiệp, gia đình và những ngƣời thân yêu đã luôn đồng hành,
tạo mọi điều kiện, động viên giúp đỡ em trong quá trình học tập, công tác để hoàn
thành khóa học và luận văn này.
ii
MỤC LỤC
LỜI CAM ĐOAN ............................................................................................. i
LỜI CẢM ƠN .................................................................................................. ii
MỤC LỤC ....................................................................................................... iii
DANH SÁCH CHỮ VIẾT TẮT TIẾNG VIỆT ........................................... vi
DANH SÁCH BẢNG .................................................................................... vii
DANH SÁCH HÌNH VẼ.............................................................................. viii
LỜI MỞ ĐẦU ................................................................................................. ix
CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU .............................. 1
1.1. Phân lớp dữ liệu. ..............................................................................................1
1.2. Một số vấn đề liên quan đến giải quyết bài toán phân lớp dữ liệu ..................5
1.2.1. Chuẩn bị dữ liệu cho việc phân lớp ..........................................................5
1.2.2. So sánh các mô hình phân lớp ..................................................................6
1.2.3. Một số phƣơng pháp đánh giá độ chính xác mô hình phân lớp ...............7
1.3. Phƣơng pháp cây quyết định............................................................................8
1.3.1. Định nghĩa ................................................................................................8
1.3.2. Xây dựng cây quyết định ..........................................................................9
1.3.3. Các đặc trƣng trong phân lớp dữ liệu sử dụng cây quyết định ...............10
1.3.4. Các nghiên cứu giải thuật hiện nay ........................................................11
1.4. Kết luận chƣơng 1 ..........................................................................................12
CHƢƠNG 2. GIẢI THUẬT C4.5 VÀ MẠNG NƠRON NHÂN TẠO ..... 13
2.1. Giải thuật C4.5 ...............................................................................................13
2.1.1. Giới thiệu chung .....................................................................................13
2.1.2. Giải thuật C4.5 ........................................................................................13
2.1.3. C4.5 chọn thuộc tính phân loại tốt nhất ..................................................15
2.1.4. Ví dụ minh họa cho giải thuật C4.5 ........................................................16
2.2. Đánh giá cây quyết định trong phân lớp dữ liệu ............................................26
2.2.1. Ƣu điểm của cây quyết định ...................................................................26
2.2.2. Nhƣợc điểm của cây quyết định .............................................................28
2.3. Mạng nơron nhân tạo .....................................................................................28
2.3.1. Nơron sinh học: ......................................................................................28
iii
2.3.2. Nơron nhân tạo .......................................................................................30
2.3.3. Mạng nơron nhân tạo ..............................................................................32
2.3.4 Huấn luyện mạng nơron ..........................................................................35
2.4. Phƣơng pháp học lan truyền ngƣợc và sai số ................................................37
2.5. Kết luận chƣơng 2 ..........................................................................................49
CHƢƠNG 3. PHÂN LỚP DỮ LIỆU HỌC VIÊN TẠO NGUỒN ............ 50
PHÁT TRIỂN ĐẢNG ................................................................................... 50
3.1. Khảo sát và thu thập dữ liệu ..........................................................................50
3.2. Xử lý dữ liệu ..................................................................................................50
3. 3. Phân lớp dữ liệu học viên sử dụng thuật toán C4.5 ......................................53
3.3.1. Áp dụng giải thuật ..................................................................................53
3.3.2. Xây dựng cây quyết định ........................................................................53
3.4. Phân lớp cán bộ sử dụng mạng nơron nhân tạo .............................................53
3.5. Giới thiệu một số ngôn ngữ trong khai phá dữ liệu .......................................53
3.5.1. Giới thiệu về ngôn ngữ R .......................................................................53
3.5.2. Giới thiệu về phần mềm Weka ...............................................................54
3.6. Kết quả thực nghiệm ......................................................................................55
3.6.1. Chạy giải thuật J48 trên ngôn ngữ Weka ...............................................55
3.6.2. Chạy giải thuật mạng nơron trên ngôn ngữ Weka .................................58
3.7. Kết luận chƣơng 3 ..........................................................................................60
KẾT LUẬN .................................................................................................... 61
TÀI LIỆU THAM KHẢO ............................................................................ 62
PHỤ LỤC ....................................................................................................... 63
iv
DANH SÁCH THUẬT NGỮ VIẾT TẮT TIẾNG ANH
Viết tắt
Tiếng Anh
Tiếng Việt
Evolutionary Programming
Lập trình tiến hóa
Genetic Algorithm
Thuật toán GAs
Negative
Số mẫu âm
Negative Predictive Value
Giá trị tiên đoán âm
Positive
Số mẫu dƣơng
PPV
Positive Predictive Value
Giá trị tiên đoán dƣơng
TN
True Nagative
Thực âm
True Nagative Rate
Tỷ lệ thực âm
True Positive
Thực dƣơng
TPR
True Positive Rate
Tỷ lệ thực dƣơng
GR
Gain Ratio
Tỉ số độ lợi
IG
Information Gain
Độ lợi thông tin
Accuracy
Độ chính xác
EP
GAs
N
NPV
P
TNR
TP
ACC
v
DANH SÁCH CHỮ VIẾT TẮT TIẾNG VIỆT
Chữ gốc
Chữ viết tắt
Công an nhân dân
CAND
Công nhận đối tƣợng
CNDT
Phân loại học viên
PLHV
Trung bình
TB
Có giấy khen
CGK
Cán bộ đi học
CBDH
Học sinh phổ thông
HSPT
Đoàn viên ƣu tú
DVUT
Công nhận đối tƣợng
CNDT
Xuất sắc
XS
Công an trung ƣơng
CATW
Quyết định
QD
Phân loại rèn luyện
PLRL
Kết nạp đảng
KND
Có
C
Không
K
Cơ sở dữ liệu
CSDL
Ngôn ngữ truy vấn mang tính cấu trúc
SQL
vi
DANH SÁCH BẢNG
Bảng 2.1: Bảng cơ sở dữ liệu dự đoán đối tƣợng kết nạp đảng có DVUT = C ........17
Bảng 2.2: Một số hàm H(s) thƣờng dùng cho mô hình nơron nhân tạo ...................31
Bảng 2.3: Một số hàm phi tuyến thƣờng đƣợc sử dụng trong các mô hình nơron ...32
Bảng 2.4: Ma trận nhầm lẫn ......................................................................................47
Bảng 3.1: Bảng cơ sở tri thức....................................................................................52
vii
DANH SÁCH HÌNH VẼ
Hình 1.1: Quá trình phân lớp dữ liệu - Bƣớc xây dựng mô hình phân lớp .................2
Hình 1.2: Quá trình phân lớp dữ liệu - Ƣớc lƣợng độ chính xác của mô hình ...........3
Hình 1.3: Quá trình phân lớp dữ liệu - Phân lớp dữ liệu mới .....................................4
Hình 1.4: Ƣớc lƣợng độ chính xác của mô hình phân lớp với phƣơng pháp holdout 7
Hình 1.5: Ví dụ về cây quyết định ..............................................................................8
Hình 2.1: Ví dụ Cây quyết định hoàn chỉnh .............................................................23
Hình 2.2: Mô hình nơron sinh học ............................................................................29
Hình 2.3: Mô hình nơron nhân tạo ............................................................................30
Hình 2.4: Sơ đồ đơn giản về một mạng nơron nhân tạo ...........................................33
Hình 2.5: Mạng truyền thẳng một lớp .......................................................................34
Hình 2.6: Mạng truyền thẳng nhiều lớp. ...................................................................34
Hình 2.7: Các dạng học .............................................................................................36
Hình 2.8: Mạng truyền thẳng nhiều lớp ....................................................................38
Hình 2.9: Cấu trúc mạng lan truyền ngƣợc ...............................................................40
Hình 3.1: Kết quả Classifer Output .........................................................................566
Hình 3.2: Cây quyết định sử dụng giải thuật C4.5 trong Weka ................................57
Hình 3.3: Kết quả Classifer Output ...........................................................................58
Hình 3.4: Mạng nơron trong Weka .......................................................................5959
viii
LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Công tác phát triển Đảng của trƣờng Đại học Kỹ thuật - Hậu cần CAND
trong những năm gần đây rất đƣợc Đảng ủy quan tâm chú trọng cả về chất lƣợng và
số lƣợng. Số lƣợng đảng viên đƣợc kết nạp sau mỗi năm học ngày càng tăng lên;
tuy nhiên, quá trình xét kết nạp, công nhận đối tƣơng phát triển đảng còn nhiều bất
cập, chƣa đáp ứng đƣợc nhu cầu thực tế: Chƣa có công cụ hỗ trợ quản lý đánh giá
các tiêu chí kết nạp đảng một cách chính xác, minh bạch; việc xem xét kết nạp đảng
nhiều khi còn bỏ sót những quần chúng ƣu tú, có nguyện vọng đƣợc đứng trong
hàng ngũ của Đảng.
Xuất phát từ thực tế công tác, tôi đã tìm hiểu, nghiên cứu về phƣơng pháp
phân lớp dữ liệu mà cụ thể ở đây là giải thuật cây quyết định J48 và mạng nơron để
phân lớp dữ liệu theo phƣơng pháp học máy với hy vọng tìm ra quy luật, các đặc
trƣng tác động đến việc xem xét kết nạp Đảng để có thể giới thiệu nguồn phát triển
Đảng cho Đảng ủy Nhà trƣờng đƣợc nhanh nhất và chính xác nhất
Với những lý do trên, tôi chọn đề tài “Nghiên cứu phương pháp học máy cho
phân lớp dữ liệu học viên tạo nguồn phát triển đảng”.
2. Mục tiêu, đối tƣợng và phạm vi nghiên cứu
- Mục tiêu: Phân lớp dữ liệu học viên trƣờng Đại học Kỹ thuật - Hậu cần
CAND dựa trên giải thuật C4.5 và Mạng nơron.
- Đối tƣợng nghiên cứu: Đối tƣợng nghiên cứu của luận văn là dữ liệu về học
viên trƣờng Đại học Kỹ thuật - Hậu cần CAND.
- Phạm vi nghiên cứu: Giới hạn thử nghiệm phân lớp theo 6 đặc trƣng và 164
bản ghi đầu vào đƣợc cho là cơ bản nhất; sau đó có thể mở rộng thêm các đặc trƣng
cũng nhƣ các bản ghi khác.
ix
3. Bố cục luận văn
Luận văn đƣợc chia thành ba chƣơng có nội dung nhƣ sau:
Luận văn gồm các phần chính sau:
- Phần mở đầu
- Chƣơng 1: Phƣơng pháp phân lớp dữ liệu
- Chƣơng 2: Giải thuật C4.5 và Mạng nơron nhân tạo
- Chƣơng 3: Phân lớp dữ liệu học viên tạo nguồn phát triển đảng trƣờng Đại
học Kỹ thuật - Hậu cần CAND
- Kết luận: Tổng kết các kết quả đã đạt đƣợc của luận văn và hƣớng nghiên
cứu tiếp theo.
x
CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU
1.1. Phân lớp dữ liệu.
Phân lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị hay là
nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ
liệu mới. Phân lớp dữ liệu cũng là tiên đoán loại lớp của nhãn. Bên cạnh kỹ thuật
phân lớp có một hình thức tƣơng tự là kỹ thuật tiên đoán, kỹ thuật tiên đoán khác
với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kỹ
thuật tiên đoán mô hình là những hàm đánh giá liên tục.
Ví dụ: Nhờ các quy luật về xu hƣớng mua hàng của khách hàng
trong siêu thị mà nhân viên kinh doanh có thể đƣa ra những quyết sách đúng đắn về
số lƣợngmặt hàng, chủng loại bày bán
Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm của các nhà
nghiên cứu trong nhiều lĩnh vực khác nhau nhƣ học máy (Machine Learning), hệ
chuyên gia (Expert System), thống kê (Statistics),... Công nghệ này cũng đƣợc ứng
dụng trong nhiều lĩnh vực khác nhau nhƣ: Thƣơng mại, maketing, nhà băng, nghiên
cứu thị trƣờng, bảo hiểm, y tế, giáo dục,... Phần lớn các giải thuật ra đời đều sử
dụng cơ chế dữ liệu cƣ trú trong bộ nhớ (Memory Resident), thƣờng thao tác với
lƣợng dữ liệu nhỏ. Một số giải thuật ra đời sau này đã sử dụng kỹ thuật cƣ trú trên
đĩa cải thiện đáng kể khả năng mở rộng của giải thuật với những tập dữ liệu lớn lên
tới hàng tỷ bản ghi.
Quá trình phân lớp dữ liệu gồm hai bƣớc [9]:
Bước thứ nhất
Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay
các khái niệm định trƣớc. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc
đƣợc mô tả bằng các thuộc tính và đƣợc tạo ra từ tập các bộ giá trị của các thuộc
tính đó. Mỗi bộ giá trị đƣợc gọi chung là một phần tử dữ liệu (Data Tuple), có thể là
các mẫu (Sample), hay ví dụ (Example), đối tượng (Objiect), bản ghi (Record) hay
trường hợp (Case).Lớp ở đây là giá trị của một thuộc tính đƣợc chọn làm thuộc tính
gán nhãn lớp hay thuộc tính phân lớp (Class lable attribute). Đầu ra của bƣớc này
1
thƣờng là các quy tắc phân lớp dƣới dạng luật if - then, cây quyết định, công thức
logic hay mạng nơron. Quá trình này đƣợc mô tả nhƣ trong Hình 1.1
Giải thuật phân lớp
Dữ liệu huấn luyện
Bộ phân lớp
Tuoi
NN
Chon
25
Anh
Yes
35
Anh
Yes
IF Tuoi <= 35 or NN = Anh
THEN Chon = Yes
40
Anh
No
27
Pháp
No
32
Trung
No
30
Anh
Yes
32
Anh
Yes
40
Pháp
No
Hình 1.1: Quá trình phân lớp dữ liệu - Bước xây dựng mô hình phân lớp
Xây dựng mô hình là mô tả một tập những lớp đƣợc định nghĩa trƣớc, trong
đó: mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định nghĩa trƣớc nhƣ là đƣợc
xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ đƣợc sử dụng trong việc sử
dụng mô hình đƣợc gọi là tập huấn luyện. Mô hình đƣợc biểu diễn là những luật
phân lớp, cây quyết định và những công thức toán học.
Bước thứ hai
Trong bƣớc này dùng mô hình đã xây dựng ở bƣớc trƣớc để phân lớp dữ liệu
mới. Trƣớc tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo
ra đƣợc ƣớc lƣợng. Holdout là một kỹ thuật đơn giản để ƣớc lƣợng độ chính xác.
Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã đƣợc gán nhãn lớp.
Các mẫu này đƣợc chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu huấn
luyện. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đƣa là tỉ lệ phần trăm
2
các mẫu trong tập dữ liệu kiểm tra đƣợc mô hình phân lớp đúng (so với thực tế).
Nếu độ chính xác của mô hình đƣợc ƣớc lƣợng dựa trên tập dữ liệu huấn luyện thì
kết quả thu đƣợc là rất khả quan vì mô hình luôn có xu hƣớng “quá vừa” dữ liệu.
Quá vừa dữ liệu là hiện tƣợng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá
trình xây dựng mô hình phân lớp từ tập dữ liệu huấn luyện tạo có thể đã kết hợp
những đặc điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu
kiểm tra độc lập với tập dữ liệu huấn luyện. Nếu độ chính xác của mô hình là chấp
nhận đƣợc, thì mô hình đƣợc sử dụng để phân lớp những dữ liệu tƣơng lai, hoặc
những dữ liệu mà giá trị của thuộc tính phân lớp là chƣa biết.
Bộ phân lớp
Tập dữ liệu kiểm tra
Tuoi
27
34
36
44
NN
Anh
Phap
Trung
Anh
Chon
Yes
No
No
Yes
Chon
Yes
No
No
No
Hình 1.2: Quá trình phân lớp dữ liệu - Ước lượng độ chính xác của mô hình
3
Bộ phân lớp (Mô hình)
Tập dữ liệu mới
Tuoi
27
34
36
34
NN
Anh
Phap
Trung
Anh
Chon
Yes
No
No
Yes
Chon
Yes
No
No
No
Hình 1.3: Quá trình phân lớp dữ liệu - Phân lớp dữ liệu mới
Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tƣơng lai
hoặc phân lớp cho những đối tƣợng chƣa biết đến. Trƣớc khi sử dụng mô hình
ngƣời ta thƣờng phải đánh giá tính chính xác của mô hình.
Trong đó: nhãn đƣợc biết của mẫu kiểm tra đƣợc so sánh với kết quả phân
lớp của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại
đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện.
Phân lớp là một hình thức học đƣợc giám sát tức là: tập dữ liệu huấn luyện
(quan sát, thẩm định v.v.) đi đôi với những nhãn chỉ định lớp quan sát, những dữ
liệu mới đƣợc phân lớp dựa trên tập huấn luyện .
Ngƣợc lại với hình thức học đƣợc giám sát là hình thức học không đƣợc
giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không đƣợc biết đến.
Trong mô hình phân lớp, giải thuật phân lớp dữ vai trò trung tâm, quyết định
tới sự thành công của mô hình phân lớp. Do vậy, chìa khóa của vấn đề phân lớp dữ
liệu là tìm ra đƣợc một giải thuật phân lớp nhanh, hiệu quả, có độ chính xác cao và
có khả năng mở rộng đƣợc. Trong đó, khả năng mở rộng đƣợc của giải thuật đƣợc
đặc biệt trú trọng và phát triển [9].
* Các phƣơng pháp ứng dụng trong phân lớp dữ liệu:
- Phân lớp cây quyết định
- Mạng nơron
4
- Các giải thuật di truyền
- Bộ phân lớp Bayesian (Bayesian Classifier)
- Mô hình phân lớp K-hàng xóm gần nhất
- Phân tích thống kê
- Phƣơng pháp tập thô (Rough Set Approach)
* Phát biểu bài toán của luận văn
- Cho Cơ sở dữ liệu là danh sách học viên của trƣờng Đại học Kỹ thuật - Hậu
cần CAND. Gồm 6 đặc trƣng đầu vào (Kết quả phân loại học viên; kết quả rèn
luyện; cảm tình đảng; đoàn viên ƣu tú; học lớp đối tƣợng; đối tƣợng) và 3 đầu ra
(Kết nạp đảng; công nhận đối tƣợng và không).
- Sử dụng giải thuật học toán C4.5 và mạng Nơron để phân lớp dữ liệu học
viên; So sánh kết quả của hai giải thuật và đánh giá độ chính xác phân lớp của hai
giải thuật trên.
1.2. Một số vấn đề liên quan đến giải quyết bài toán phân lớp dữ liệu
1.2.1. Chuẩn bị dữ liệu cho việc phân lớp
Công việc đầu tiên là tiền xử lý dữ liệu cho quá trình phân lớp là một việc
làm không thể thiếu và có vai trò quan trọng quyết định tới việc có áp dụng đƣợc
mô hình phân lớp hay không. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính
xác, tính hiệu quả và khả năng mở rộng đƣợc của mô hình phân lớp.
Quá trình tiền xử lý dữ liệu gồm các công việc sau:
-Làm sạch dữ liệu: Làm sạch dữ liệu liên quan đến việc xử lý lỗi và giá trị
thiếu trong tập dữ liệu ban đầu. Trong đó lỗi là các lỗi ngẫu nhiên hay các giá trị
không hợp lệ của các biến trong tập dữ liệu. Để xử lý với tập lỗi này có thể dùng kỹ
thuật làm trơn. Giá trị thiếu là những ô không có giá trị của các thuộc tính. Giá trị
lỗi có thể do lỗi chủ quan trong quá trình nhập liệu hoặc trong trƣờng hợp cụ thể giá
trị của các thuộc tính đó không có, hay không quan trọng. Kỹ thuật xử lý ở đây có
thể thay giá trị thiếu bằng giá trị phổ biến nhất của thuộc tính đó hoặc bằng giá trị
có thể xảy ra nhất dựa trên thống kê. Mặc dù phần lớn giải thuật phân lớp đều có cơ
chế xử lý với những giá trị thiếu và lỗi trong tập dữ liệu, nhƣng bƣớc tiền xử lý này
có thể làm giảm sự hỗn độn trong quá trình học (xây dựng mô hình phân lớp).
5
- Phân tích sự cần thiết của dữ liệu: Có rất nhiều thuộc tính trong tập dữ liệu
có thể hoàn toàn không cần thiết hay liên quan đến một bài toán phân lớp cụ thể. Ví
dụ dữ liệu về ngày trong tuần hoàn toàn không cần thiết đối với ứng dụng phân tích
độ rủi ro của các khoản tiền cho vay của ngân hàng, nên thuộc tính này là dƣ thừa.
Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ những thuộc tính không cần
thiết, dƣ thừa khỏi quá trình học vì những thuộc tính đó sẽ làm chậm, phức tạp và gây
ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng đƣợc.
- Chuyển đổi dữ liệu: Việc khái quát hóa dữ liệu lên mức khái niệm cao
hơn đôi khi là cần thiết trong quá trình tiền xử lý. Việc này đặc biệt hữu ích với
những thuộc tính liên tục. Với những thuộc tính rời rạc nhƣ địa chỉ phố có thể
đƣợc khái quát hóa lên thành phố. Việc khái quát hóa làm cô đọng dữ liệu học
nguyên thủy, vì vậy các thao tác vào, ra liên quan đến quá trình học sẽ giảm.
1.2.2. So sánh các mô hình phân lớp
Trong từng trƣờng hợp cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc
lựa chọn đó căn cứ vào sự so sánh các mô hình phân lớp khác nhau, dựa trên các
tiêu chuẩn sau:
- Độ chính xác dự đoán (Predictive Accuracy): Độ chính xác là khả năng
của mô hình để dự đoán chính xác nhãn lớp của dữ liệu mới hay dữ liệu chƣa biết.
- Tốc độ (Speed): Tốc độ là chi phí tính toán liên quan đến quá trình tạo ra
và sử dụng mô hình.
- Sức mạnh (Robustness): Sức mạnh là khả năng mô hình tạo ra những dự
đoán đúng từ những dữ liệu lỗi hay dữ liệu với những giá trị thiếu.
- Khả năng mở rộng (Scalability): là khả năng thực thi hiệu quả trên lƣợng
lớn dữ liệu của mô hình đã học.
- Tính hiểu được (interpretability): Tính hiểu đƣợc là mức độ hiểu và hiểu
rõ những kết quả sinh ra bởi mô hình đã học.
- Tính đơn giản (Simplicity): Tính đơn giản liên quan đến kích thƣớc của
cây quyết định hay độ cô đọng của các luật, càng đơn giản càng hiệu quả.
Trong các tiêu chuẩn trên, khả năng mở rộng của mô hình phân lớp đƣợc
nhấn mạnh và chú trọng phát triển, đặc biệt với cây quyết định [9].
6
1.2.3. Một số phương pháp đánh giá độ chính xác mô hình phân lớp
Độ chính xác của bộ phân lớp là quan trọng ở chỗ 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. Dƣới đây là hai phƣơng pháp đánh giá phổ biến
là holdout và k-fold cross-validation. Cả hai phƣơng pháp này đều dựa trên các phân
hoạch ngẫu nhiên tập dữ liệu ban đầu.
Phương pháp holdout
Dữ liệu đƣ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 dữ liệu đào tạo, phần
còn lại cho tập dữ liệu kiểm tra [9].
Lấy từ bộ
Tập dữ liệu
đào tạo
phân lớp
Dữ liệu
Ƣớc lƣợng
độ chính xác
Tập dữ liệu
kiểm tra
Hình 1.4: Ước lượng độ chính xác của mô hình phân lớp với phương pháp holdout
Phương pháp k-fold cross-validation
Tập dữ liệu ban đầu đƣợc chia ngẫu nhiên thành k tập con có kích thƣớc xấp
xỉ nhau S1,S2,…,Sk. Quá trình phân lớp và test đƣợc thực hiện k lần. Tại lần lặp thứ
i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Có nghĩa
là đầu tiên việc phân lớp đƣợc thực hiện trên các tập S2, S3,…Sk sau đó test trên tập
S1, tiếp tục quá trình phân lớp đƣợc thực hiện trên tập S2,S3,S4,…,Sk sau đó test trên
7
tập S2 và cứ tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia cho
tổng số mẫu của tập dữ liệu ban đầu.
1.3. Phƣơng pháp cây quyết định
1.3.1. Định nghĩa
Những năm qua, nhiều mô hình phân lớp dữ liệu đã đƣợc các nhà khoa học
trong nhiều lĩnh vực khác nhau đề xuất nhƣ mạng nơ ron, mô hình thống kê tuyến
tính trên bậc 2, cây quyết định, mô hình di truyền. Trong số những mô hình đó, cây
quyết định với những ƣu điểm của mình đƣợc đánh giá là một công cụ mạnh, phổ
biến và đặc biệt thích hợp cho data mining nói chung và phân lớp dữ liệu nói riêng [3].
Những ƣu điểm của cây quyết định nhƣ:
- Xây dựng tƣơng đối nhanh, đơn giản, dễ hiểu.
- Các cây có thể dễ dàng đƣợc chuyển đổi sang các câu lệnh SQL để có thể
đƣợc sử dụng để truy nhập dữ liệu một cách hiệu quả.
Việc phân lớp dựa trên cây quyết định đạt đƣợc sự tƣơng tự và đôi khi là
chính xác hơn so với các phƣơng pháp phân lớp khác [6].
Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây nhƣ trong hình sau:
Tuổi
Tuổi>18
Tuổi< 18
CNV
KNĐ = No
CNV = C
CNV = K
KNĐ = No
KNĐ = Yes
Hình 1.5: Ví dụ về cây quyết định
Trong cây quyết định:
- Gốc: là node trên cùng của cây
- Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật).
8
- Xem thêm -