Đ I H C QU C GIA HÀ N I
TR
NG Đ I H C CÔNG NGH
Nguy n Th Thùy Linh
NGHIÊN C U CÁC THU T TOÁN PHÂN L P D
D A TRÊN CÂY QUY T Đ NH
KHÓA LU N T T NGHI P Đ I H C H CHÍNH QUY
Ngành: Công ngh thông tin
HÀ N I - 2005
LI U
Đ I H C QU C GIA HÀ N I
TR
NG Đ I H C CÔNG NGH
Nguy n Th Thùy Linh
NGHIÊN C U CÁC THU T TOÁN PHÂN L P D
LI U
D A TRÊN CÂY QUY T Đ NH
KHÓA LU N T T NGHI P Đ I H C H CHÍNH QUY
Ngành: Công ngh thông tin
Cán b h
ng d n: TS. Nguy n H i Châu
HÀ N I - 2005
TÓM T T N I DUNG
Phân lớp dữ liệu là một trong những h ớng nghiên cứu chính của khai phá dữ
liệu. Công nghệ này đã, đang và sẽ có nhiều ứng dụng trong các lĩnh vực th ơng mại,
ngân hàng, y tế, giáo dục…Trong các mô hình phân lớp đã đ ợc đề xuất, cây quyết
định đ ợc coi là công cụ mạnh, phổ biến và đặc biệt thích hợp với các ứng dụng khai
phá dữ liệu. Thuật toán phân lớp là nhân tố trung tâm trong một mô hình phân lớp.
Khóa luận đã nghiên cứu vấn đề phân lớp dữ liệu dựa trên cây quyết định. Từ
đó tập trung vào phân tích, đánh giá, so sánh hai thuật toán tiêu biểu cho hai phạm vi
ứng dụng khác nhau là C4.5 và SPRINT. Với các chiến l ợc riêng về lựa chọn thuộc
tính phát triển, cách thức l u trữ phân chia dữ liệu, và một số đặc điểm khác, C4.5 là
thuật toán phổ biến nhất khi phân lớp tập dữ liệu vừa và nhỏ, SPRINT là thuật toán
tiêu biểu áp dụng cho những tập dữ liệu có kích th ớc cực lớn. Khóa luận đã chạy thử
nghiệm mô hình phân lớp C4.5 với tập dữ liệu thực và thu đ ợc một số kết quả phân
lớp có ý nghĩa thực tiễn cao, đồng thời đánh giá đ ợc hiệu năng của mô hình phân lớp
C4.5. Trên cơ sở nghiên cứu lý thuyết và quá trình thực nghiệm, khóa luận đã đề xuất
một số cải tiến mô hình phân lớp C4.5 và tiến tới cài đặt SPRINT.
- i-
L IC M
N
Trong suốt thời gian học tập, hoàn thành khóa luận em đã may mắn đ ợc các
thầy cô chỉ bảo, dìu dắt và đ ợc gia đình, bạn bè quan tâm, động viên.
Em xin đ ợc bày tỏ lòng biết ơn chân thành tới các thầy cô tr ờng Đại học
Công Nghệ đã truyền đạt cho em nguồn kiến thức vô cùng quý báu cũng nh cách học
tập và nghiên cứu khoa học.
Cho phép em đ ợc gửi lời cảm ơn sâu sắc nhất tới TS. Nguyễn Hải Châu,
ng ời thầy đã rất nhiệt tình chỉ bảo và h ớng dẫn em trong suốt quá trình thực hiện
khóa luận.
Với tất cả tấm lòng mình, em xin bày tỏ lòng biết ơn sâu sắc đến TS. Hà
Quang Thụy đã tạo điều kiện thuận lợi và cho em những định h ớng nghiên cứu. Em
xin lời cảm ơn tới Nghiên cứu sinh Đoàn Sơn (JAIST) đã cung cấp tài liệu và cho em
những lời khuyên quý báu. Em cũng xin gửi lời cảm ơn tới các thầy cô trong Bộ môn
Các hệ thống thông tin, Khoa Công nghệ thông tin đã giúp em có đ ợc môi thực
nghiệm thuận lợi.
Em cũng xin gửi tới các bạn trong nhóm Seminar “Khai phá dữ liệu và Tính
toán song song” lời cảm ơn chân thành vì những đóng góp và những kiến thức quý báu
em đã tiếp thu đ ợc trong suốt thời gian tham gia nghiên cứu khoa học.
Cuối cùng, em xin cảm ơn gia đình, bạn bè và tập thể lớp K46CA, những
ng ời đã luôn ở bên khích lệ và động viên em rất nhiều.
Hà Nội, tháng 6 năm 2005
Sinh viên
Nguyễn Thị Thùy Linh
- ii-
M CL C
TÓM T T N I DUNG ..................................................................................................i
L I C M N ............................................................................................................... ii
M C L C .................................................................................................................... iii
DANH M C BI U Đ HÌNH VẼ...............................................................................v
DANH M C THU T NG ...................................................................................... vii
ĐẶT V N Đ .................................................................................................................1
Ch ng 1. T NG QUAN V PHÂN L P D LI U D A TRÊN CÂY QUY T
Đ NH...............................................................................................................................3
1.1. Tổng quan về phân lớp dữ liệu trong data mining................................................3
1.1.1. Phân lớp dữ liệu........................................................................................................ 3
1.1.2. Các vấn đề liên quan đến phân lớp dữ liệu............................................................... 6
1.1.3. Các ph ơng pháp đánh giá độ chính xác của mô hình phân lớp .............................. 8
1.2. Cây quyết định ứng dụng trong phân lớp dữ liệu .................................................9
1.2.1. Định nghĩa ................................................................................................................ 9
1.2.2. Các vấn đề trong khai phá dữ liệu sử dụng cây quyết định.................................... 10
1.2.3. Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu....................................... 11
1.2.4. Xây dựng cây quyết định........................................................................................ 13
1.3. Thuật toán xây dựng cây quyết định...................................................................14
1.3.1. T t ởng chung ...................................................................................................... 14
1.3.2. Tình hình nghiên cứu các thuật toán hiện nay........................................................ 15
1.3.3. Song song hóa thuật toán phân lớp dựa trên cây quyết định tuần tự...................... 17
Ch ng 2. C4.5 VÀ SPRINT......................................................................................21
2.1. Giới thiệu chung .................................................................................................21
2.2. Thuật toán C4.5...................................................................................................21
2.2.1. C4.5 dùng Gain-entropy làm độ đo lựa chọn thuộc tính “tốt nhất”........................ 22
2.2.2. C4.5 có cơ chế riêng trong xử lý những giá trị thiếu.............................................. 25
2.2.3. Tránh “quá vừa” dữ liệu ......................................................................................... 26
2.2.4. Chuyển đổi từ cây quyết định sang luật ................................................................. 26
2.2.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ỏ ....................... 27
2.3. Thuật toán SPRINT ............................................................................................28
2.3.1. Cấu trúc dữ liệu trong SPRINT .............................................................................. 29
2.3.2. SPRINT sử dụng Gini-index làm độ đo tìm điểm phân chia tập dữ liệu “tốt nhất”
.......................................................................................................................................... 31
2.3.3. Thực thi sự phân chia ............................................................................................. 34
2.3.4. SPRINT là thuật toán hiệu quả với những tập dữ liệu quá lớn so với các thuật toán
khác................................................................................................................................... 35
- iii-
2.4. So sánh C4.5 và SPRINT....................................................................................37
Ch ng 3. CÁC K T QU TH C NGHI M .........................................................38
3.1. Môi tr ờng thực nghiệm .....................................................................................38
3.2. Cấu trúc mô hình phân lớp C4.5 release8:..........................................................38
3.2.1. Mô hình phân lớp C4.5 có 4 ch ơng trình chính: .................................................. 38
3.2.2. Cấu trúc dữ liệu sử dụng trong C4.5 ...................................................................... 39
3.3. Kết quả thực nghiệm...........................................................................................40
3.3.1. `7Một số kết quả phân lớp tiêu biểu: ...................................................................... 40
3.3.2. Các biểu đồ hiệu năng ............................................................................................ 47
3.4. Một số đề xuất cải tiến mô hình phân lớp C4.5..................................................54
K T LU N ..................................................................................................................56
TÀI LI U THAM KH O...........................................................................................57
- iv-
DANH M C BI U Đ
HÌNH VẼ
Hình 1 - Quá trình phân lớp dữ liệu - (a) B ớc xây dựng mô hình phân lớp .................4
Hình 2 - Quá trình phân lớp dữ liệu - (b1) ớc l ợng độ chính xác của mô hình...........5
Hình 3 - Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ...................................5
Hình 4 - ớc l ợng độ chính xác của mô hình phân lớp với ph ơng pháp holdout ......8
Hình 5- Ví dụ về cây quyết định .....................................................................................9
Hình 6 - Mã giả của thuật toán phân lớp dữ liệu dựa trên cây quyết định ....................14
Hình 7 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp đồng bộ...........................18
Hình 8 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp phân hoạch .....................19
Hình 9 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp lai....................................20
Hình 10 - Mã giả thuật toán C4.5 ..................................................................................22
Hình 11 - Mã giả thuật toán SPRINT............................................................................28
Hình 12 - Cấu trúc dữ liệu trong SLIQ..........................................................................29
Hình 13 - Cấu trúc danh sách thuộc tính trong SPRINT – Danh sách thuộc tính liên tục
đ ợc sắp xếp theo thứ tự ngay đ ợc tạo ra ............................................................30
Hình 14 - ớc l ợng các điểm phân chia với thuộc tính liên tục .................................32
Hình 15 - ớc l ợng điểm phân chia với thuộc tính rời rạc .........................................33
Hình 16 - Phân chia danh sách thuộc tính của một node ..............................................34
Hình 17 - Cấu trúc của bảng băm phân chia dữ liệu trong SPRINT (theo ví dụ các hình
tr ớc) ......................................................................................................................35
Hình 18 - File định nghĩa cấu trúc dữ liệu sử dụng trong thực nghiệm ........................39
Hình 19 - File chứa dữ liệu cần phân lớp ......................................................................40
Hình 20 - Dạng cây quyết định tạo ra từ tập dữ liệu thử nghiệm..................................41
Hình 21 - ớc l ợng trên cây quyết định vừa tạo ra trên tập dữ liệu training và tập dữ
liệu test ...................................................................................................................42
Hình 22 - Một số luật rút ra từ bộ dữ liệu 19 thuộc tính, phân lớp loại thiết lập chế độ
giao diện của ng ời sử dụng (WEB_SETTING_ID).............................................43
Hình 23 - Một số luật rút ra từ bộ dữ liệu 8 thuộc tính, phân lớp theo số hiệu nhà sản
xuất điện thoại (PRODUCTER_ID) ......................................................................44
Hình 24 - Một số luật sinh ra từ tập dữ liệu 8 thuộc tính, phân lớp theo dịch vụ
điệnthoại mà khách hàng sử dụng (MOBILE_SERVICE_ID)..............................45
Hình 25 - ớc l ợng tập luật trên tập dữ liệu đào tạo ..................................................46
- v-
Bảng 1 - Bảng dữ liệu tập training với thuộc tính phân lớp là buys_computer ............24
Bảng 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 2 thuộc tính....................................................................49
Bảng 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 7 thuộc tính....................................................................50
Bảng 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo18 thuộc tính...................................................................51
Bảng 5 - Thời gian sinh cây quyết định phụ thuộc vào số l ợng thuộc tính .................52
Bảng 6 - Thời gian xây dựng cây quyết định với thuộc tính rời rạc và thuộc tính liên
tục ...........................................................................................................................53
Bảng 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp...................54
Biểu đồ 1- So sánh thời gian thực thi của mô hình phân lớp SPRINT và SLIQ theo
kích th ớc tập dữ liệu đào tạo................................................................................36
Biểu đồ 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 2 thuộc tính....................................................................49
Biểu đồ 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 7 thuộc tính....................................................................50
Biểu đồ 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo18 thuộc tính...................................................................51
Biểu đồ 5 - Sự phụ thuộc thời gian sinh cây quyết định vào số l ợng thuộc tính.........52
Biểu đồ 6 - So sánh thời gian xây dựng cây quyết định từ tập thuộc tính liên tục và từ
tập thuộc tính rời rạc ..............................................................................................53
Biểu đồ 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp...............54
- vi-
DANH M C THU T NG
STT
Ti ng Anh
Ti ng Vi t
1
training data
dữ liệu đào tạo
2
test data
dữ liệu kiểm tra
3
Pruning decision tree
Cắt, tỉa cây quyết định
4
Over fitting data
Quá vừa dữ liệu
5
Noise
Dữ liệu lỗi
6
Missing value
Giá trị thiếu
7
Data tuple
Phần tử dữ liệu
Case
Case (đ ợc hiểu nh một data
tuple, chứa một bộ giá trị của
các thuộc tính trong tập dữ liệu)
8
- vii-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
ĐẶT V N Đ
Trong quá trình hoạt động, con ng ời tạo ra nhiều dữ liệu nghiệp vụ. Các tập
dữ liệu đ ợc tích lũy có kích th ớc ngày càng lớn, và có thể chứa nhiều thông tin ẩn
dạng những quy luật ch a đ ợc khám phá. Chính vì vậy, một nhu cầu đặt ra là cần tìm
cách trích rút từ tập dữ liệu đó các luật về phân lớp dữ liệu hay dự đoán những xu
h ớng dữ liệu t ơng lai. Những quy tắc nghiệp vụ thông minh đ ợc tạo ra sẽ phục vụ
đắc lực cho các hoạt động thực tiễn, cũng nh phục vụ đắc lực cho quá trình nghiên
cứu khoa học. Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng mong muốn
đó.
Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ tr ớc những
khao khát tri thức của con ng ời. Trong những năm qua, phân lớp dữ liệu đã thu hút sự
quan tâm 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
ứng dụng trong nhiều lĩnh vực thực tế nh : th ơng mại, nhà băng, maketing, nghiên
cứu thị tr ờng, bảo hiểm, y tế, giáo dục...
Nhiều kỹ thuật phân lớp đã đ ợc đề xuất nh : Phân lớp cây quyết định
(Decision tree classification), phân lớp Bayesian (Bayesian classifier), phân lớp Khàng xóm gần nhất (K-nearest neighbor classifier), mạng nơron, phân tích thống kê,…
Trong các kỹ thuật đó, cây quyết định đ ợc coi là công cụ mạnh, phổ biến và đặc biệt
thích hợp cho data mining [5][7]. Trong các mô hình phân lớp, thuật toán phân lớp là
nhân tố chủ đạo. Do vậy cần xây dựng những thuật toán có độ chính xác cao, thực thi
nhanh, đi kèm với khả năng mở rộng đ ợc để có thể thao tác với những tập dữ liệu
ngày càng lớn.
Khóa luận đã nghiên cứu tổng quan về công nghệ phân lớp dữ liệu nói chung
và phân lớp dữ liệu dựa trên cây quyết định nói riêng. Từ đó tập trung hai thuật toán
tiêu biểu cho hai phạm vi ứng dụng khác nhau là C4.5 và SPRINT. Việc phân tích,
đánh giá các thuật toán có giá trị khoa học và ý nghĩa thực tiễn. Tìm hiểu các thuật
toán giúp chúng ta tiếp thu và có thể phát triển về mặt t t ởng, cũng nh kỹ thuật của
một công nghệ tiên tiến đã và đang là thách thức đối với các nhà khoa học trong lĩnh
vực data mining. Từ đó có thể triển khai cài đặt và thử nghiệm các mô hình phân lớp
dữ liệu trên thực tế. Tiến tới ứng dụng vào trong các hoạt động thực tiễn tại Việt Nam,
mà tr ớc tiên là các hoạt động phân tích, nghiên cứu thị tr ờng khách hàng.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 1-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Khóa luận cũng đã chạy thử nghiệm mô hình phân lớp C4.5 trên tập dữ liệu
thực tế từ Tổng công ty b u chính viễn thông. Qua đó tiếp thu đ ợc các kỹ thuật triển
khai, áp dụng một mô hình phân lớp dữ liệu vào hoạt động thực tiễn. Quá trình chạy
thử nghiệm đã thu đ ợc các kết quả phân lớp khả quan với độ tin cậy cao và nhiều
tiềm năng ứng dụng. Các đánh giá hiệu năng của mô hình phân lớp cũng đã đ ợc tiến
hành. Trên cơ sở đó, khóa luận đề xuất những cải tiến nhằm tăng hiệu năng của mô
hình phân lớp C4.5 đồng thời thêm tiện ích cho ng ời dùng.
Khóa luận gồm có 3 ch ơng chính:
Ch ng 1 đi từ tổng quan công nghệ phân lớp dữ liệu tới kỹ thuật phân lớp dữ
liệu dựa trên cây quyết định. Các đánh giá về công cụ cây quyết định cũng đ ợc trình
bày. Ch ơng này cũng cung cấp một cái nhìn tổng quan về lĩnh vực nghiên cứu các
thuật toán phân lớp dữ liệu dựa trên cây quyết định với nền tảng t t ởng, tình hình
nghiên cứu và ph ơng h ớng phát triển hiện nay.
Ch ng 2 tập trung vào hai thuật toán tiêu biểu cho hai phạm vi ứng dụng
khác nhau là C4.5 và SPRINT. Hai thuật toán này có những chiến l ợc riêng trong lựa
chọn tiêu chuẩn phân chia dữ liệu cũng nh cách thức l u trữ phân chia dữ
liệu…Chính những đặc điểm riêng đó mà C4.5 là thuật toán tiêu biểu phổ biến nhất
với tập dữ liệu vừa và nhỏ, trong khi đó SPRINT lại là sự lựa chọn đối với những tập
dữ liệu cực lớn.
Ch ng 3 trình bày quá trình thực nghiệm với mô hình phân lớp C4.5 trên tập
dữ liệu thực từ tổng công ty b u chính viễn thông Việt Nam. Các kết quả thực nghiệm
đã đ ợc trình bày. Từ đó khóa luận đề xuất các cải tiến mô hình phân lớp C4.5
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 2-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Chư ng 1. T NG QUAN V PHÂN L P D
TRÊN CÂY QUY T Đ NH
LI U D A
1.1. Tổng quan về phân lớp dữ liệu trong data mining
1.1.1. Phân l p d
li u
Ngày nay phân lớp dữ liệu (classification) là một trong những h ớng nghiên
cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu với
nhiều thông tin ẩn con ng ời có thể trích rút ra các quyết định nghiệp vụ thông minh.
Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra một mô hình
mô tả các lớp dữ liệu quan trọng hay dự đoán xu h ớng dữ liệu t ơng lai. Phân lớp dự
đoán giá trị của những nhãn xác định (categorical label) hay những giá trị rời rạc
(discrete value), có nghĩa là phân lớp thao tác với những đối t ợng dữ liệu mà có bộ
giá trị là biết tr ớc. Trong khi đó, dự đoán lại xây dựng mô hình với các hàm nhận giá
trị liên tục. Ví dụ mô hình phân lớp dự báo thời tiết có thể cho biết thời tiết ngày mai là
m a, hay nắng dựa vào những thông số về độ ẩm, sức gió, nhiệt độ,… của ngày hôm
nay và các ngày tr ớc đó. Hay nhờ các luật về xu h ớng mua hàng của khách hàng
trong siêu thị, các nhân viên kinh doanh có thể ra những quyết sách đúng đắn về l ợng
mặt hàng cũng nh chủng loại bày bán… Một mô hình dự đoán có thể dự đoán đ ợc
l ợng tiền tiêu dùng của các khách hàng tiềm năng dựa trên những thông tin về thu
nhập và nghề nghiệp của khách hàng. Trong những năm qua, phân lớp dữ liệu đã thu
hút sự quan tâm 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 ứng dụng trong nhiều lĩnh vực khác nhau nh : th ơng mại, nhà băng,
maketing, nghiên cứu thị tr ờng, bảo hiểm, y tế, giáo dục... Phần lớn các thuật toán ra
đời tr ớc đề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ố thuật toán 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 thuật toán 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 [14]:
• B ớc thứ nhất (learning)
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
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 3-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyế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), ví dụ (example), đối t ợng (object), bản ghi (record) hay tr ờng hợp
(case). Khoá luận sử dụng các thuật ngữ này với nghĩa t ơng đ ơng. Trong tập dữ liệu
này, mỗi phần tử dữ liệu đ ợc giả sử thuộc về một lớp định tr ớc, 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 label attribute). Đầu ra của b ớc này th ờng là các quy tắc phân lớp d ới dạng
luật dạng 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
a)
Classification
algorithm
Training data
Age
20
18
40
50
35
30
32
40
C a r T yp e
C o mbi
S po rts
S po rts
F a mily
M iniv a n
C o mbi
F a mily
C o mbi
R is k
High
High
High
Low
Low
High
Low
Low
Classifier (model)
if age < 31
or Car Type =Sports
then Risk = High
Hình 1 - Quá trình phân lớp dữ liệu - (a) B ớc xây dựng mô hình phân lớp
• B ớc thứ hai (classification)
B ớc thứ hai 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 đào tạo. Độ
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 các 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 đào tạo 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 đào tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 4-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
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 đào tạo.
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.
b1)
Classifier (model)
Test data
Age
27
34
66
44
Car Type
Sports
Family
Family
Sports
Risk
High
Low
High
High
Risk
High
Low
Low
High
Hình 2 - Quá trình phân lớp dữ liệu - (b1) ớc l ợng độ chính xác của mô hình
b2)
Classifier (model)
New data
Age
27
34
55
34
C a r T yp e
S po rts
M iniv a n
F a m ily
S po rts
R is k
R is k
H ig h
Low
Low
H ig h
Hình 3 - Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới
Trong mô hình phân lớp, thuật toán phân lớp giữ 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 thuật toán 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 thuật toán đ ợc đặc biệt trú
trọng và phát triển [14].
Có thể liệt kê ra đây các kỹ thuật phân lớp đã đ ợc sử dụng trong những năm qua:
• Phân lớp cây quyết định (Decision tree classification)
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 5-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
• Bộ phân lớp Bayesian (Bayesian classifier)
• Mô hình phân lớp K-hàng xóm gần nhất (K-nearest neighbor classifier)
• Mạng nơron
• Phân tích thống kê
• Các thuật toán di truyền
• Ph ơng pháp tập thô (Rough set Approach)
1.1.2. Các v n đ liên quan đ n phân l p d
li u
1.1.2.1. Chuẩn b d li u cho vi c phân l p
Việc 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 sự áp dụng đ ợc hay không của mô hình phân
lớp. 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 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ý với lỗi (noise) và giá trị thiếu
(missing value) trong tập dữ liệu ban đầu. Noise 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 loại lỗi này có
thể dùng kỹ thuật làm trơn. Missing value là những ô không có giá trị của các
thuộc tính. Giá trị thiếu 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 thuộc tính đó không có, hay không quan
trọng. Kỹ thuật xử lý ở đây có thể bằng cách 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 thuật toán 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).
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
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 6-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
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
(continuous attribute hay numeric attribute). Ví dụ các giá trị số của thuộc tính
thu nhập của khách hàng có thể đ ợc khái quát hóa thành các dãy giá trị rời rạc:
thấp, trung bình, cao. T ơng tự với những thuộc tính rời rạc (categorical
attribute) nh địa chỉ phố có thể đ ợc khái quát hóa lên thành 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.1.2.2. So sánh các mô hình phân l p
Trong từng ứng dụng 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 với 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à những 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 ta những dự đoán đúng từ những dữ liệu
noise hay dữ liệu với những giá trị thiếu.
• Khả năng mở rộng (scalability)
Khả năng mở rộng 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.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 7-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
• 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.
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à trú trọng phát triển, đặc biệt với cây quyết định. [14]
1.1.3. Các phư ng pháp đánh giá đ chính xác của mô hình phân l p
ớc l ợng độ 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. Khóa luận này đề cập đến 2
ph ơng pháp đánh giá phổ biến là holdout và k-fold cross-validation. Cả 2 kỹ thuật
này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu.
• 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 tra [14].
Derive
classifier
Training set
Esitmate
accuracy
Data
Test set
Hình 4 -
ớc l ợng độ chính xác của mô hình phân lớp với ph ơng pháp holdout
• Trong 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 (fold) có kích th ớc xấp xỉ nhau S1, S2, …, Sk. Quá trình học
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 dạy đ ợ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 dạy đ ợc thực hiện
trên tập S1, S3, S4,…, Sk, sau đó test trên tập S2; và cứ thế 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.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 8-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
1.2. Cây quyết định ứng dụng trong phân lớp dữ liệu
1.2.1. Đ nh nghĩa
Trong 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 notron, mô hình thông kê tuyến
tính /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 [7]. Có thể
kể ra 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. Hơn nữa 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 cơ sở dữ liệu một cách hiệu quả. Cuối cùng, 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 [10].
Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây, nh mô tả trong
hình vẽ sau:
Age
Age≤27.5
Age>27.5
Car type
Risk = High
Car type ∈ {sport}
Car type ∈ {family, truck}
Risk = Low
Risk = High
Hình 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)
• Nhánh: biểu diễn các kết quả của kiểm tra trên node trong (mũi tên)
• Node lá: biểu diễn lớp hay sự phân phối lớp (hình tròn)
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 9-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Để phân lớp mẫu dữ liệu ch a biết, giá trị các thuộc tính của mẫu đ ợc đ a
vào kiểm tra trên cây quyết định. Mỗi mẫu t ơng ứng có một đ ờng đi từ gốc đến lá
và lá biểu diễn dự đoán giá trị phân lớp mẫu đó.
1.2.2. Các v n đ trong khai phá d
li u s d ng cây quy t đ nh
Các vấn đề đặc thù trong khi học hay phân lớp dữ liệu bằng cây quyết định
gồm: xác định độ sâu để phát triển cây quyết định, xử lý với những thuộc tính liên tục,
chọn phép đo lựa chọn thuộc tính thích hợp, sử dụng tập dữ liệu đào tạo với những giá
trị thuộc tính bị thiếu, sử dụng các thuộc tính với những chi phí khác nhau, và cải thiện
hiệu năng tính toán. Sau đây khóa luận sẽ đề cập đến những vấn đề chính đã đ ợc giải
quyết trong các thuật toán phân lớp dựa trên cây quyết định.
1.2.2.1. Tránh “quá vừa” d li u
Thế nào là “quá vừa” dữ liệu? Có thể hiểu đây là hiện t ợng cây quyết định
chứa một số đặc tr ng riêng của tập dữ liệu đào tạo, nếu lấy chính tập traning data để
test lại mô hình phân lớp thì độ chính xác sẽ rất cao, trong khi đối với những dữ liệu
t ơng lai khác nếu sử dụng cây đó lại không đạt đ ợc độ chính xác nh vậy.
Quá vừa dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định và
những ph ơng pháp học khác. Đặc biệt khi số l ợng ví dụ trong tập dữ liệu đào tạo
quá ít, hay có noise trong dữ liệu.
Có hai ph ơng pháp tránh “quá vừa” dữ liệu trong cây quyết định:
• Dừng phát triển cây sớm hơn bình th ờng, tr ớc khi đạt tới điểm phân lớp hoàn
hảo tập dữ liệu đào tạo. Với ph ơng pháp này, một thách thức đặt ra là phải ớc
l ợng chính xác thời điểm dừng phát triển cây.
• Cho phép cây có thể “quá vừa” dữ liệu, sau đó sẽ cắt, tỉa cây.
Mặc dù ph ơng pháp thứ nhất có vẻ trực tiếp hơn, nh ng với ph ơng pháp thứ
hai thì cây quyết định đ ợc sinh ra đ ợc thực nghiệm chứng minh là thành công hơn
trong thực tế. Hơn nữa việc cắt tỉa cây quyết định còn giúp tổng quát hóa, và cải thiện
độ chính xác của mô hình phân lớp. Dù thực hiện ph ơng pháp nào thì vấn đề mấu
chốt ở đây là tiêu chuẩn nào đ ợc sử dụng để xác định kích th ớc hợp lý của cây cuối
cùng.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 10-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
1.2.2.2. Thao tác v i thu c tính liên t c
Việc thao tác với thuộc tính liên tục trên cây quyết định hoàn toàn không đơn
giản nh với thuộc tính rời rạc.
Thuộc tính rời rạc có tập giá trị (domain) xác định từ tr ớc và là tập hợp các
giá trị rời rạc. Ví dụ loại ô tô là một thuộc tính rời rạc với tập giá trị là: {xe tải, xe
khách, xe con, taxi}.Việc phân chia dữ liệu dựa vào phép kiểm tra giá trị của thuộc
tính rời rạc đ ợc chọn tại một ví dụ cụ thể có thuộc tập giá trị của thuộc tính đó hay
không: value(A) ∈ X với X ⊂ domain (A). Đây là phép kiểm tra logic đơn giản, không
tốn nhiều tài nguyên tính toán. Trong khi đó, với thuộc tính liên tục (thuộc tính dạng
số) thì tập giá trị là không xác định tr ớc. Chính vì vậy, trong quá trình phát triển cây,
cần sử dụng kiểm tra dạng nhị phân: value(A) ≤ θ. Với θ là hằng số ng ỡng
(threshold) đ ợc lần l ợt xác định dựa trên từng giá trị riêng biệt hay từng cặp giá trị
liền nhau (theo thứ tự đã sắp xếp) của thuộc tính liên tục đang xem xét trong tập dữ
liệu đào tạo. Điều đó có nghĩa là nếu thuộc tính liên tục A trong tập dữ liệu đào tạo có
d giá trị phân biệt thì cần thực hiện d-1 lần kiểm tra value(A) ≤ θi với i = 1..d-1 để tìm
ra ng ỡng θbest tốt nhất t ơng ứng với thuộc tính đó. Việc xác định giá trị của θ và tiêu
chuẩn tìm θ tốt nhất tùy vào chiến l ợc của từng thuật toán [13][1]. Trong thuật toán
C4.5, θi đ ợc chọn là giá trị trung bình của hai giá trị liền kề nhau trong dãy giá trị đã
sắp xếp.
Ngoài ra còn một số vấn đề liên quan đến sinh tập luật, xử lý với giá trị thiếu
sẽ đ ợc trình bày cụ thể trong phần thuật toán C4.5.
1.2.3. Đánh giá cây quy t đ nh trong lĩnh v c khai phá d li u
1.2.3.1. S c m nh c a cây quy t đ nh
Cây quyết định có 5 sức mạnh chính sau [5]:
Khả năng sinh ra các quy tắc hiểu đ ợc
Cây quyết định có khả năng sinh ra các quy tắc có thể chuyển đổi đ ợc sang
dạng tiếng Anh, hoặc các câu lệnh SQL. Đây là u điểm nổi bật của kỹ thuật này.
Thậm chí với những tập dữ liệu lớn khiến cho hình dáng cây quyết định lớn và phức
tạp, việc đi theo bất cứ đ ờng nào trên cây là dễ dàng theo nghĩa phổ biến và rõ ràng.
Do vậy sự giải thích cho bất cứ một sự phân lớp hay dự đoán nào đều t ơng đối minh
bạch.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 11-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Khả năng thực thi trong những lĩnh vực h ớng quy tắc
Điều này có nghe có vẻ hiển nhiên, nh ng quy tắc quy nạp nói chung và cây
quyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh vực thực sự là các quy tắc.
Rất nhiều lĩnh vực từ di truyền tới các quá trình công nghiệp thực sự chứa các quy tắc
ẩn, không rõ ràng (underlying rules) do khá phức tạp và tối nghĩa bởi những dữ liệu lỗi
(noisy). Cây quyết định là một sự lựa chọn tự nhiên khi chúng ta nghi ngờ sự tồn tại
của các quy tắc ẩn, không rõ ràng.
Dễ dàng tính toán trong khi phân lớp
Mặc dù nh chúng ta đã biết, cây quyết định có thể chứa nhiều định dạng,
nh ng trong thực tế, các thuật toán sử dụng để tạo ra cây quyết định th ờng tạo ra
những cây với số phân nhánh thấp và các test đơn giản tại từng node. Những test điển
hình là: so sánh số, xem xét phần tử của một tập hợp, và các phép nối đơn giản. Khi
thực thi trên máy tính, những test này chuyển thành các toán hàm logic và số nguyên
là những toán hạng thực thi nhanh và không đắt. Đây là một u điểm quan trọng bởi
trong môi tr ờng th ơng mại, các mô hình dự đoán th ờng đ ợc sử dụng để phân lớp
hàng triệu thậm trí hàng tỉ bản ghi.
Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc
Cây quyết định xử lý “tốt” nh nhau với thuộc tính liên tục và thuộc tính rời
rạc. Tuy rằng với thuộc tính liên tục cần nhiều tài nguyên tính toán hơn. Những thuộc
tính rời rạc đã từng gây ra những vấn đề với mạng neural và các kỹ thuật thống kê lại
thực sự dễ dàng thao tác với các tiêu chuẩn phân chia (splitting criteria) trên cây quyết
định: mỗi nhánh t ơng ứng với từng phân tách tập dữ liệu theo giá trị của thuộc tính
đ ợc chọn để phát triển tại node đó. Các thuộc tính liên tục cũng dễ dàng phân chia
bằng việc chọn ra một số gọi là ng ỡng trong tập các giá trị đã sắp xếp của thuộc tính
đó. Sau khi chọn đ ợc ng ỡng tốt nhất, tập dữ liệu phân chia theo test nhị phân của
ng ỡng đó.
Thể hiện rõ ràng những thuộc tính tốt nhất
Các thuật toán xây dựng cây quyết định đ a ra thuộc tính mà phân chia tốt
nhất tập dữ liệu đào tạo bắt đầu từ node gốc của cây. Từ đó có thể thấy những thuộc
tính nào là quan trọng nhất cho việc dự đoán hay phân lớp.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 12-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
1.2.3.2. Đi m y u c a cây quy t đ nh
Dù có những sức mạnh nổi bật trên, cây quyết định vẫn không tránh khỏi có
những điểm yếu. Đó là cây quyết định không thích hợp lắm với những bài toán với
mục tiêu là dự đoán giá trị của thuộc tính liên tục nh thu nhập, huyết áp hay lãi xuất
ngân hàng,… Cây quyết định cũng khó giải quyết với những dữ liệu thời gian liên tục
nếu không bỏ ra nhiều công sức cho việc đặt ra sự biểu diễn dữ liệu theo các mẫu liên
tục.
Dễ xẩy ra lỗi khi có quá nhiều lớp
Một số cây quyết định chỉ thao tác với những lớp giá trị nhị phân dạng yes/no
hay accept/reject. Số khác lại có thể chỉ định các bản ghi vào một số lớp bất kỳ, nh ng
dễ xảy ra lỗi khi số ví dụ đào tạo ứng với một lớp là nhỏ. Điều này xẩy ra càng nhanh
hơn với cây mà có nhiều tầng hay có nhiều nhánh trên một node.
Chi phí tính toán đắt để đào tạo
Điều này nghe có vẻ mâu thuẫn với khẳng định u điểm của cây quyết định ở
trên. Nh ng quá trình phát triển cây quyết định đắt về mặt tính toán. Vì cây quyết định
có rất nhiều node trong tr ớc khi đi đến lá cuối cùng. Tại từng node, cần tính một độ
đo (hay tiêu chuẩn phân chia) trên từng thuộc tính, với thuộc tính liên tục phải thêm
thao tác xắp xếp lại tập dữ liệu theo thứ tự giá trị của thuộc tính đó. Sau đó mới có thể
chọn đ ợc một thuộc tính phát triển và t ơng ứng là một phân chia tốt nhất. Một vài
thuật toán sử dụng tổ hợp các thuộc tính kết hợp với nhau có trọng số để phát triển cây
quyết định. Quá trình cắt cụt cây cũng “đắt” vì nhiều cây con ứng cử phải đ ợc tạo ra
và so sánh.
1.2.4. Xây d ng cây quy t đ nh
Quá trình xây dựng cây quyết định gồm hai giai đoạn:
• Giai đoạn thứ nhất phát triển cây quyết định:
Giai đoạn này phát triển bắt đầu từ gốc, đến từng nhánh và phát triển quy nạp
theo cách thức chia để trị cho tới khi đạt đ ợc cây quyết định với tất cả các lá đ ợc
gán nhãn lớp.
• Giai đoạn thứ hai cắt, tỉa bớt các cành nhánh trên cây quyết định.
Giai đoạn này nhằm mục đích đơn giản hóa và khái quát hóa từ đó làm tăng độ
chính xác của cây quyết định bằng cách loại bỏ sự phụ thuộc vào mức độ lỗi (noise)
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 13-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
của dữ liệu đào tạo mang tính chất thống kê, hay những sự biến đổi mà có thể là đặc
tính riêng biệt của dữ liệu đào tạo. Giai đoạn này chỉ truy cập dữ liệu trên cây quyết
định đã đ ợc phát triển trong giai đoạn tr ớc và quá trình thực nghiệm cho thấy giai
đoạn này không tốn nhiều tài nguyên tính toán, nh với phần lớn các thuật toán, giai
đoạn này chiếm khoảng d ới 1% tổng thời gian xây dựng mô hình phân lớp [7][1].
Do vậy, ở đây chúng ta chỉ tập trung vào nghiên cứu giai đoạn phát triển cây
quyết định. D ới đây là khung công việc của giai đoạn này:
1) Chọn thuộc tính “tốt” nhất bằng một độ đo đã định tr ớc
2) Phát triển cây bằng việc thêm các nhánh t ơng ứng với từng giá trị của thuộc
tính đã chọn
3) Sắp xếp, phân chia tập dữ liệu đào tạo tới node con
4) Nếu các ví dụ đ ợc phân lớp rõ ràng thì dừng.
Ng ợc lại: lặp lại b ớc 1 tới b ớc 4 cho từng node con
1.3. Thuật toán xây dựng cây quyết định
1.3.1. Tư tưởng chung
Phần lớn các thuật toán phân lớp dữ liệu dựa trên cây quyết định có mã giả nh sau:
Make Tree (Training Data T)
{
Partition(T)
}
Partition(Data S)
{
if (all points in S are in the same class) then
return
for each attribute A do
evaluate splits on attribute A;
use best split found to partition S into S1, S2,..., Sk
Partition(S1)
Partition(S2)
...
Partition(Sk)
}
Hình 6 - Mã giả của thuật toán phân lớp dữ liệu dựa trên cây quyết định
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 14-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Các thuật toán phân lớp nh C4.5 (Quinlan, 1993), CDP (Agrawal và các tác
giả khác, 1993), SLIQ (Mehta và các tác giả khác, 1996) và SPRINT (Shafer và các
tác giả khác, 1996) đều sử dụng ph ơng pháp của Hunt làm t t ởng chủ đạo.
Ph ơng pháp này đ ợc Hunt và các đồng sự nghĩ ra vào những năm cuối thập kỷ 50
đầu thập kỷ 60.
Mô tả quy nạp ph ơng pháp Hunt [1]:
Giả sử xây dựng cây quyết định từ T là tập training data và các lớp được biểu
diễn dưới dạng tập C = {C1, C2, …,Ck }
Trường hợp 1: T chứa các case thuộc về một lớp đơn Cj, cây quyết định ứng
với T là một lá tương ứng với lớp Cj
Trường hợp 2: T chứa các case thuộc về nhiều lớp khác nhau trong tập C. Một
kiểm tra được chọn trên một thuộc tính có nhiều giá trị {O1, O2, ….,On }. Trong nhiều ứng
dụng n thường được chọn là 2, khi đó tạo ra cây quyết định nhị phân. Tập T được chia
thành các tập con T1, T2, …, Tn, với Ti chứa tất cả các case trong T mà có kết quả là Oi
trong kiểm tra đã chọn. Cây quyết định ứng với T bao gồm một node biểu diễn kiểm tra
được chọn, và mỗi nhánh tương ứng với mỗi kết quả có thể của kiểm tra đó. Cách thức
xây dựng cây tương tự được áp dụng đệ quy cho từng tập con của tập training data.
Trường hợp 3: T không chứa case nào. Cây quyết định ứng với T là một lá,
nhưng lớp gắn với lá đó phải được xác định từ những thông tin khác ngoài T. Ví dụ
C4.5 chọn giá trị phân lớp là lớp phổ biến nhất tại cha của node này.
1.3.2. Tình hình nghiên cứu các thu t toán hi n nay
Các thuật toán phân lớp dữ liệu dựa trên cây quyết định đều có t t ởng chủ
đạo là ph ơng pháp Hunt đã trình bày ở trên. Luôn có 2 câu hỏi lớn cần phải đ ợc trả
lời trong các thuật toán phân lớp dữ liệu dựa trên cây quyết định là:
1. Làm cách nào để xác định đ ợc thuộc tính tốt nhất để phát triển tại mỗi
node?
2. L u trữ dữ liệu nh thế nào và làm cách nào để phân chia dữ liệu theo các
test t ơng ứng?
Các thuật toán khác nhau có các cách trả lời khác nhau cho hai câu hỏi trên.
Điều này làm nên sự khác biệt của từng thuật toán.
Có 3 loại tiêu chuẩn hay chỉ số để xác định thuộc tính tốt nhất phát triển tại mỗi
node
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 15-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
• Gini-index (Breiman và các đồng sự, 1984 [1]): Loại tiêu chuẩn này lựa chọn
thuộc tính mà làm cực tiểu hóa độ không tinh khiết của mỗi phân chia. Các
thuật toán sử dụng này là CART, SLIQ, SPRINT.
• Information–gain (Quinlan, 1993 [1]): Khác với Gini-index, tiểu chuẩn này sử
dụng entropy để đo độ không tinh khiết của một phân chia và lựa chọn thuộc
tính theo mức độ cực đại hóa chỉ số entropy. Các thuật toán sử dụng tiêu chuẩn
này là ID3, C4.5.
•
χ2 -bảng thống kê các sự kiện xảy ra ngẫu nhiên: χ2 đo độ t ơng quan giữa từng
thuộc tính và nhãn lớp. Sau đó lựa chọn thuộc tính có độ t ơng quan lớn nhất.
CHAID là thuật toán sử dụng tiêu chuẩn này.
Chi tiết về cách tính các tiêu chuẩn Gini-index và Information-gain sẽ đ ợc
trình bày trong hai thuật toán C4.5 và SPRINT, ch ơng 2.
Việc tính toán các chỉ số trên đôi khi đòi hỏi phải duyệt toàn bộ hay một phần
của tập dữ liệu đào tạo. Do vậy các thuật toán ra đời tr ớc yêu cầu toàn bộ tập dữ liệu
đào tạo phải nằm th ờng trú trong bộ nhớ (memory- resident) trong quá trình phát
triển cây quyết định. Điều này đã làm hạn chế khả năng mở rộng của các thuật toán đó,
vì kích th ớc bộ nhớ là có hạn, mà kích th ớc của tập dữ liệu đào tạo thì tăng không
ngừng, đôi khi là triệu là tỉ bản ghi trong lĩnh vực th ơng mại. Rõ ràng cần tìm ra giải
pháp mới để thay đổi cơ chế l u trữ và truy cập dữ liệu, năm 1996 SLIQ (Mehta) và
SPRINT (Shafer) ra đời đã giải quyết đ ợc hạn chế đó. Hai thuật toán này đã sử dụng
cơ chế l u trữ dữ liệu th ờng trú trên đĩa (disk- resident) và cơ chế sắp xếp tr ớc một
lần (pre- sorting) tập dữ liệu đào tạo. Những đặc điểm mới này làm cải thiện đáng kể
hiệu năng và tính mở rộng so với các thuật toán khác. Tiếp theo là một số thuật toán
khác phát triển trên nền tảng SPRINT với một số bổ xung cải tiến nh PUBLIC (1998)
[11] với ý t ởng kết hợp hai quá trình xây dựng và cắt tỉa với nhau, hay ScalParC
(1998) cải thiện quá trình phân chia dữ liệu của SPRINT với cách dùng bảng băm
khác, hay thuật toán do các nhà khoa học tr ờng đại học Minesota (Mỹ ) kết hợp với
IBM đề xuất đã làm giảm chi phí vào ra cũng nh chi phí giao tiếp toàn cục khi song
song hóa so với SPRINT [2]. Trong các thuật toán đó SPRINT đ ợc coi là sáng tạo đột
biến, đáng để chúng ta tìm hiểu và phát triển.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 16-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
1.3.3. Song song hóa thu t toán phân l p d a trên cây quy t đ nh tuần
t
Song song hóa xu h ớng nghiên cứu hiện nay của các thuật toán phân lớp dữ liệu dựa
trên cây quyết định. Nhu cầu song song hóa các thuật toán tuần tự là một nhu cầu tất
yếu của thực tiễn phát triển khi mà các đòi hỏi về hiệu năng, độ chính xác ngày càng
cao. Thêm vào đó là sự gia tăng nhanh chóng về kích th ớc của dữ liệu cần khai phá.
Một mô hình phân lớp chạy trên hệ thống tính toán song song có hiệu năng cao, có khả
năng khai phá đ ợc những tập dữ liệu lớn hơn từ đó gia tăng độ tin cậy của các quy tắc
phân lớp. Hiện nay, các thuật toán tuần tự yêu cầu dữ liệu th ờng trú trong bộ nhớ đã
không đáp ứng đ ợc yêu cầu của các tập dữ liệu có kích th ớc TetaByte với hàng tỉ
bản ghi. Do vậy xây dựng thuật toán song song hiệu quả dựa trên những thuật toán
tuần tự sẵn có là một thách thức đặt ra cho các nhà nghiên cứu.
Có 3 chiến l ợc song song hóa các thuật toán tuần tự:
Ph
ng pháp xây d ng cây đ ng b
Trong ph ơng pháp này, tất cả các bộ vi xử lý đồng thời tham gia xây dựng
cây quyết định bằng việc gửi và nhận các thông tin phân lớp của dữ liệu địa ph ơng.
Hình 7 mô tả cơ chế làm việc của các bộ vi xử lý trong ph ơng pháp này
u điểm của ph ơng pháp này là không yêu cầu việc di chuyển các dữ liệu
trong tập dữ liệu đào tạo. Tuy nhiên, thuật toán này phải chấp nhận chi phí giao tiếp
cao, và tải bất cân bằng. Với từng node trong cây quyết định, sau khi tập hợp đ ợc các
thông tin phân lớp, tất cả các bộ vi xử lý cần phải đồng bộ và cập nhật các thông tin
phân lớp. Với những node ở độ sâu thấp, chi phí giao tiếp t ơng đối nhỏ, bởi vì số
l ợng các mục training data đ ợc xử lý là t ơng đối nhỏ. Nh ng khi cây càng sâu thì
chi phí cho giao tiếp chiếm phần lớn thời gian xử lý. Một vấn đề nữa của ph ơng pháp
này là tải bất cân bằng do cơ chế l u trữ và phân chia dữ liệu ban đầu tới từng bộ vi xử
lý.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 17-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 7 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp đồng bộ
Ph
ng pháp xây d ng cây phân ho ch
Khi xây dựng cây quyết định bằng ph ơng pháp phân hoạch các bộ vi xử lý
khác nhau làm việc với các phần khác nhau của cây quyết định. Nếu nhiều hơn 1 bộ vi
xử lý cùng kết hợp để phát triển 1 node, thì các bộ vi xử lý đ ợc phân hoạch để phát
triển các con của node đó. Ph ơng pháp này tập trung vào tr ờng hợp 1 nhóm các bộ
vi xử lý Pn cùng hợp tác để phát triển node n. Khi bắt đầu, tất cả các bộ vi xử lý cùng
đồng thời kết hợp để phát triển node gốc của cây phân lớp. Khi kết thúc, toàn bộ cây
phân lớp đ ợc tạo ra bằng cách kết hợp tất cả các cây con của từng bộ vi xử lý. Hình 8
mô tả cơ chế làm việc của các bộ vi xử lý trong ph ơng pháp này.
u điểm của ph ơng pháp này là khi một bộ vi xử lý một mình chịu trách
nhiệm phát triển một node, thì nó có thể phát triển thành một cây con của cây toàn cục
một cách độc lập mà không cần bất cứ chi phí giao tiếp nào.
Tuy nhiên cũng có một vài nh ợc điểm trong ph ơng pháp này, đó là: Thứ
nhất yêu cầu di chuyển dữ liệu sau mỗi lần phát triển một node cho tới khi mỗi bộ vi
xử lý chứa toàn bộ dữ liệu để có thể phát triển toàn bộ một cây con. Do vậy dẫn đến
tốn kém chi phí giao tiếp khi ở phần trên của cây phân lớp. Thứ hai là khó đạt đ ợc tải
cân bằng. Việc gán các node cho các bộ vi xử lý đ ợc thực hiện dựa trên số l ợng các
case trong các node con. Tuy nhiên số l ợng các case gắn với một node không nhất
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 18-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
thiết phải t ơng ứng với số l ợng công việc cần phải xử lý để phát triển cây con tại
node đó.
Hình 8 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp phân hoạch
Ph
ng pháp lai
Ph ơng pháp lai có tận dụng u điểm của cả 2 ph ơng pháp trên. Ph ơng
pháp xây dựng cây đồng bộ chấp nhận chi phí giao tiếp cao khi biên giới của cây càng
rộng. Trong khi đó, ph ơng pháp xây dựng cây quyết định phân hoạch thì phải chấp
nhận chi phí cho việc tải cân bằng sau mỗi b ớc. Trên cơ sở đó, ph ơng pháp lai tiếp
tục duy trì cách thức thứ nhất miễn là chi phí giao tiếp phải chịu do tuân theo cách
thức thứ nhất không quá lớn. Khi mà chi phí này v ợt quá một ng ỡng quy định, thì
các bộ vi xử lý đang xử lý các node tại đ ờng biên hiện tại của cây phân lớp đ ợc
phân chia thành 2 phần (với giả thiết số l ợng các bộ vi xử lý là lũy thừa của 2).
Ph ơng pháp này cần sử dụng tiêu chuẩn để khởi tạo sự phân hoạch tập các bộ
vi xử lý hiện tại, đó là:
∑ (Chi phí giao tiếp) ≥ Chi phí di chuyển + Tải cân bằng
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 19-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Mô hình hoạt động của ph ơng pháp lai đ ợc mô tả trong hình 9.
Hình 9 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp lai
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 20-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Chư ng 2.
C4.5 VÀ SPRINT
2.1. Giới thiệu chung
Sau đây là những giới thiệu chung nhất về lịch sử ra đời của hai thuật toán
C4.5 và SPRINT.
C4.5 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 [13].
Năm 1996, 3 tác giả John Shafer, Rakesh Agrawal, Manish Mehta thuộc IBM
Almaden Research Center đã đề xuất một thuật toán mới với tên gọi SPRINT
(Scalable PaRallelization INduction of decision Trees). SPRINT ra đời đã loại bỏ tất
cả các giới hạn về bộ nhớ, thực thi nhanh và có khả năng mở rộng. Thuật toán này
đ ợc thiết kế để dễ dàng song song hóa, cho phép nhiều bộ vi xử lý cùng làm việc
đồng thời để xây dựng một mô hình phân lớp đơn, đồng nhất [7]. Hiện nay SPRINT đã
đ ợc th ơng mại hóa, thuật toán này đ ợc tích hợp vào trong các công cụ khai phá dữ
liệu của IBM.
Trong các thuật toán phân lớp dữ liệu dựa trên cây quyết định, C4.5 và
SPRINT là hai thuật toán tiêu biểu cho hai phạm vi ứng dụng khác nhau. C4.5 là thuật
toán hiệu quả và đ ợc dùng rộng rãi nhất trong các ứng dụng phân lớp với l ợng dữ
liệu nhỏ cỡ vài trăm nghìn bản ghi. SPRINT một thuật toán tuyệt vời cho những ứng
dụng với l ợng dữ liệu khổng lồ cỡ vài triệu đến hàng tỉ bản ghi.
2.2. Thuật toán C4.5
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
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 21-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
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 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.
T t ởng phát triển cây quyết định của C4.5 là ph ơng pháp HUNT đã nghiên
cứu ở trên. Chiến l ợc phát triển theo đ sâu (depth-first strategy) đ ợc áp dụng cho
C4.5.
Mã giả của thuật toán C4.5:
( 1)
ComputerClassFrequency(T);
(2)
if OneClass or FewCases
return a leaf;
Create a decision node N;
(3)
ForEach Attribute A
ComputeGain(A);
(4)
N.test= AttributeWithBestGain;
(5)
if N.test is continuous
find Threshold;
(6)
ForEach T' in the splitting of T
(7)
if T' is Empty
Child of N is a leaf
else
(8)
(9)
Child of N= FormTree(T');
ComputeErrors of N;
return N
Hình 10 - Mã giả thuật toán C4.5
Trong báo cáo này, chúng tôi tập trung phân tích những điểm khác biệt của
C4.5 so với các thuật toán khác. Đó là cơ chế chọn thuộc tính để kiểm tra tại mỗi node,
cơ chế xử lý với những giá trị thiếu, tránh việc “quá vừa” dữ liệu, ớc l ợng độ chính
xác và cơ chế cắt tỉa cây.
2.2.1. C4.5 dùng Gain-entropy làm đ đo l a chọn thu c tính “t t nh t”
Phần lớn các hệ thống học máy đều cố gắng để tạo ra 1 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.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 22-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
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.
RF (Cj, S) = |Sj| / |S|
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 đào tạo.
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 có tỉ số giá trị gain ratio = G(S, B) / P(S, B) l n
nh t.
Trong mô hình phân lớp C4.5 release8, 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.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 23-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Ví d mô t cách tính information gain
• Với thuộc tính rời rạc
Bảng 1 - Bảng dữ liệu tập training với thuộc tính phân lớp là buys_computer
Trong tập dữ liệu trên: s1 là tập những bản ghi có giá trị phân lớp là yes, s2 là tập
những bản ghi có giá trị phân lớp là no. Khi đó:
• I(S) = I(s1,s2) = I(9, 5) = -9/14*log29/14 – 5/14* log25/14 = 0.940
• Tính G(S, A) với A lần l ợt là từng thuộc tính:
– A = age. Thuộc tính age đã đ ợc rời rạc hóa thành các giá trị <30,
30-40, và >40.
– Với age= “<30”: I (S1) = (s11,s21) = -2/5log22/5 –3/5log23/5 =
0,971
– Với age =“ 30-40”: I (S2) = I(s12,s22) = 0
– Với age =“ >40”: I (S3) = I(s13,s23) = 0.971
Σ |Si| / |S|* I(Si) = 5/14* I(S1) + 4/14 * I(S2) + 5/14 * I(S3) =
0.694
Gain (S, age) = I(s1,s2) – Σ |Si| / |S|* I(Si) = 0.246
Tính t ơng tự với các thuộc tính khác ta đ ợc:
– A = income: Gain (S, income) = 0.029
– A = student: Gain (S, student) = 0.151
– A = credit_rating: Gain (S, credit_rating) = 0.048
Thuộc tính age là thuộc tính có độ đo Information Gain lớn nhất. Do
vậy age đ ợc chọn làm thuộc tính phát triển tại node đang xét.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 24-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
• Với thuộc tính liên tục
Xử lý thuộc tính liên tục đòi hỏi nhiều tài nguyên tính toán hơn thuộc tính rời
rạc. Gồm các b ớc sau:
1. Kỹ thuật Quick sort đ ợc sử dụng để sắp xếp các case trong tập dữ liệu
đào tạo theo thứ tự tăng dần hoặc giảm dần các giá trị của thuộc tính
liên tục V đang xét. Đ ợc tập giá trị V = {v1, v2, …, vm}
2. Chia tập dữ liệu thành hai tập con theo ng ỡng θi = (vi + vi+1)/2 nằm
giữa hai giá trị liền kề nhau vi và vi+1. Test để phân chia dữ liệu là test
nhị phân dạng V <= θi hay V > θi. Thực thi test đó ta đ ợc hai tập dữ
liệu con: V1 = {v1, v2, …, vi} và V2 = {vi+1, vi+2, …, vm}.
3. Xét (m-1) ng ỡng θi có thể có ứng với m giá trị của thuộc tính V bằng
cách tính Information gain hay Gain ratio với từng ng ỡng đó. Ng ỡng
có giá trị của Information gain hay Gain ratio lớn nhất sẽ đ ợc chọn
làm ng ỡng phân chia của thuộc tính đó.
Việc tìm ng ỡng (theo cách tuyến tính nh trên) và sắp xếp tập training
theo thuộc tính liên tục đang xem xét đôi khi gây ra thắt cổ chai vì tốn
nhiều tài nguyên tính toán.
2.2.2. C4.5 có c ch riêng trong x
lý nh ng 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 đào tạo S, B là test dựa trên thuộc
tính Aa 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 Aa 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 học đ ợc gì từ các
case trong S0.
T ơng ứng với G(S, B), P(S, B) cũng thay đổi,
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 25-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
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ề vác tập con Si
là tập con mà có giá trị thuộc tính test xác định theo trong số |Si|/ |S – S0|.
2.2.3. Tránh “quá vừa” d
li u
“Quá vừa” dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định
và những ph ơng pháp học khác. Quá vừa dữ liệu là hiện t ợng: nếu không có các
case xung đột (là những case mà giá trị cho mọi thuộc tính là giống nhau nh ng giá trị
của lớp lại khác nhau) thì cây quyết định sẽ phân lớp chính xác toàn bộ các case trong
tập dữ liệu đào tạo. Đôi khi dữ liệu đào tạo lại chứa những đặc tính cụ thể, nên khi áp
dụng cây quyết định đó cho những tập dữ liệu khác thì độ chính xác không còn cao
nh tr ớc.
Có một số ph ơng pháp tránh “quá vừa” dữ liệu trong cây quyết định:
• Dừng phát triển cây sớm hơn bình th ờng, tr ớc khi đạt tới điểm phân lớp
hoàn hảo tập dữ liệu đào tạo. Với ph ơng pháp này, một thách thức đặt ra là
phải ớc l ợng chính xác thời điểm dừng phát triển cây.
• Cho phép cây có thể “quá vừa” dữ liệu, sau đó sẽ cắt, tỉa cây
Mặc dù ph ơng pháp thứ nhất có vẻ trực quan hơn, nh ng với ph ơng pháp
thứ hai thì cây quyết định đ ợc sinh ra đ ợc thử nghiệm chứng minh là thành công
hơn trong thực tế, vì nó cho phép các t ơng tác tiềm năng giữa các thuộc tính đ ợc
khám phá tr ớc khi quyết định xem kết quả nào đáng giữ lại. C4.5 sử dụng kỹ thuật
thứ hai để tránh “quá vừa” dữ liệu.
2.2.4. Chuy n đ i từ cây quy t đ nh sang lu t
Việc chuyển đổi từ cây quyết định sang lu t s n xu t (production rules) 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 sản xuấ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 về cả độ chính xác và tính hiểu đ ợc của mô
hình phân lớp. Dạng output tập luật sản xuất là sự lựa chọn “khôn ngoan”. Tuy nhiên,
tài nguyên tính toán dùng cho việc tạo ra tập luật từ tập dữ liệu đào tạo có kích th ớc
lớn và nhiều giá trị sai là vô cùng lớn [12]. Khẳng định này sẽ đ ợc chứng minh qua
kết quả thực nghiệm trên mô hình phân lớp C4.5
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 26-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Giai đoạn chuyển dổi từ cây quyết định sang luật bao 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 cây
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ắt tỉa đ ợc thêm vào tập luật trung gian nếu nó không trùng với
những luật đã có.
• Lựa chọn
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ắp xếp
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 training không chứa trong 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 l ợng, đánh giá:
Tập luật đ ợc đem ớc l ợng lại trên toàn bộ tập training, nhằm mục đích xác
định xem liệu 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.
2.2.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 dạng 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.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 27-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
2.3. Thuật toán SPRINT
Ngày nay dữ liệu cần khai phá có thể có tới hàng triệu bản ghi và khoảng 10
đến 10000 thuộc tính. Hàng Tetabyte (100 M bản ghi * 2000 tr ờng * 5 bytes) dữ liệu
cần đ ợc khai phá. Những thuật toán ra đời tr ớc không thể đáp ứng đ ợc nhu cầu đó.
Tr ớc tình hình đó, SPRINT là sự cải tiến của thuật toán SLIQ (Mehta, 1996) ra đời.
Các thuật toán SLIQ và SPRINT đều có những cải tiến để tăng khả năng mở rộng của
thuật toán nh :
• Khả năng xử lý tốt với những thuộc tính liên tục và thuộc tính rời rạc.
• Cả hai thuật toán này đều sử dụng kỹ thuật s p x p tr c m t lần dữ liệu, và
l u tr th ng trú trên đĩa (disk – resident data) những dữ liệu quá lớn không
thể chứa vừa trong bộ nhớ trong. Vì sắp xếp những dữ liệu l u trữ trên đĩa là
đắt [3], nên với cơ chế sắp xếp tr ớc, dữ liệu phục vụ cho quá trình phát triển
cây chỉ cần đ ợc sắp xếp một lần. Sau mỗi b ớc phân chia dữ liệu tại từng
node, thứ tự của các bản ghi trong từng danh sách đ ợc duy trì, không cần phải
sắp xếp lại nh các thuật toán CART, và C4.5 [13][12]. Từ đó làm giảm tài
nguyên tính toán khi sử dụng giải pháp l u trữ dữ liệu th ờng trú trên đĩa.
• Cả 2 thuật toán sử dụng những cấu trúc dữ liệu giúp cho việc xây dựng cây
quyết định dễ dàng hơn. Tuy nhiên cấu trúc dữ liệu l u trữ của SLIQ và
SPRINT khác nhau, dẫn đến những khả năng mở rộng, và song song hóa khác
nhau giữa hai thuật toán này.
Mã giả của thuật toán SPRINT nh sau:
SPRI NT algorithm:
Partition(Data S) {
if (all points in S are of the same class) then
return;
for each attribute A do
evaluate splits on attribute A;
Use best split found to partition S into S1& S2
Partition(S1);
Partition(S2);
}
Initial call: Partition(Training Data)
Hình 11 - Mã giả thuật toán SPRINT
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 28-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
2.3.1. C u trúc d
li u trong SPRINT
Kỹ thuật phân chia dữ liệu thành các danh sách thuộc tính riêng biệt lần đầu
tiên đ ợc SLIQ (Supervised Learning In Quest) đề xuất. Dữ liệu sử dụng trong SLIQ
gồm: nhiều danh sách thuộc tính l u trữ th ờng trú trên đĩa (mỗi thuộc tính t ơng ứng
với một danh sách), và một danh sách đơn chứa giá trị của class l u trữ th ờng trú
trong bộ nhớ chính. Các danh sách này liên kết với nhau bởi giá trị của thuộc tính rid
(chỉ số bản ghi đ ợc đánh thứ tự trong cơ sở dữ liệu) có trong mỗi danh sách.
SLIQ phân chia d li u thành hai lo i c u trúc:[14][9]
Hình 12 - Cấu trúc dữ liệu trong SLIQ
• Danh sách thuộc tính (Attribute List) th ờng trú trên đĩa. Danh sách này gồm
tr ờng thuộc tính và rid (a record identifier).
• Danh sách lớp (Class List) chứa các giá trị của thuộc tính phân lớp t ơng ứng với
từng bản ghi trong cơ sở dữ liệu. Danh sách này gồm các tr ờng rid, thuộc tính
phân lớp và node (liên kết với node có giá trị t ơng ứng trên cây quyết định). Việc
tạo ra tr ờng con trỏ trỏ tới node t ơng ứng trên cây quyết định giúp cho quá trình
phân chia dữ liệu chỉ cần thay đổi giá trị của tr ờng con trỏ, mà không cần thực sự
phân chia dữ liệu giữa các node. Danh sách lớp đ ợc l u trữ th ờng trú trong bộ
nhớ trong vì nó th ờng xuyên đ ợc truy cập, sửa đổi cả trong giai đoạn xây dựng
cây, và cả trong giai đoạn cắt, tỉa cây. Kích th ớc của danh sách lớp tỉ lệ thuận với
số l ợng các bản ghi đầu vào. Khi danh sách lớp không vừa trong bộ nhớ, hiệu
năng của SLIQ sẽ giảm. Đó là hạn chế của thuật toán SLIQ. Việc sử dụng cấu trúc
dữ liệu th ờng trú trong bộ nhớ làm giới hạn tính mở rộng đ ợc của thuật toán
SLIQ.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 29-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
SPRINT s d ng danh sách thu c tính c trú trên đĩa
SPRINT khắc phục đ ợc hạn chế của SLIQ bằng cách không sử dụng danh
sách lớp c trú trong bộ nhớ, SPRINT chỉ sử dụng một loại danh sách là danh sách
thuộc tính có cấu trúc nh sau:
RID
0
1
2
3
4
5
Age
23
17
43
68
32
20
Car Type
family
sport
sport
family
truck
family
Car Type Risk
family
high
sport
high
sport
high
family
low
truck
low
family
high
RID
0
1
2
3
4
5
Age
17
20
23
32
43
68
Risk
high
high
high
low
low
high
RID
1
5
0
4
2
3
Risk
high
high
high
low
high
low
Hình 13 - Cấu trúc danh sách thuộc tính trong SPRINT – Danh sách thuộc tính liên
tục đ ợc sắp xếp theo thứ tự ngay đ ợc tạo ra
Danh sách thuộc tính
SPRINT tạo danh sách thuộc tính cho từng thuộc tính trong tập dữ liệu. Danh
sách này bao gồm thuộc tính, nhãn lớp (Class label hay thuộc tính phân lớp), và chỉ số
của bản ghi rid (đ ợc đánh từ tập dữ liệu ban đầu). Danh sách thuộc tính liên tục đ ợc
sắp xếp thứ tự theo giá trị của thuộc tính đó ngay khi đ ợc tạo ra. Nếu toàn bộ dữ liệu
không chứa đủ trong bộ nhớ thì tất cả các danh sách thuộc tính đ ợc l u trữ trên đĩa.
Chính do đặc điểm l u trữ này mà SPRINT đã loại bỏ mọi giới hạn về bộ nhớ, và có
khả năng ứng dụng với những cơ sở dữ liệu thực tế với số l ợng bản ghi có khi lên tới
hàng tỉ.
Các danh sách thuộc tính ban đầu tạo ra từ tập dữ liệu đào tạo đ ợc gắn với
gốc của cây quyết định. Khi cây phát triển, các node đ ợc phân chia thành các node
con mới thì các dánh sách thuộc tính thuộc về node đó cũng đ ợc phân chia t ơng ứng
và gắn vào các node con. Khi danh sách bị phân chia thì thứ tự của các bản ghi trong
danh sách đó đ ợc giữ nguyên, vì thế các danh sách con đ ợc tạo ra không bao giờ
phải sắp xếp lại. Đó là một u điểm của SPRINT so với các thuật toán tr ớc đó.
Biểu đồ (Histogram)
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 30-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
SPRINT sử dụng biểu đồ để lập bảng thống kê sự phân phối lớp của các bản
ghi trong mỗi danh sách thuộc tính, từ đó dùng vào việc ớc l ợng điểm phân chia cho
danh sách đó. Thuộc tính liên tục và thuộc tính rời rạc có hai dạng biểu đồ khác nhau.
•
Bi u đ c a thu c tính liên t c
SPRINT sử dụng 2 biểu đồ: Cbelow và Cabove. Cbelow chứa sự phân phối
của những bản ghi đã đ ợc xử lý, Cabove chứa sự phân phối của những bản ghi
ch a đ ợc xử lý trong danh sách thuộc tính. Hình II-3 minh họa việc sử dụng
biểu đồ cho thuộc tính liên tục
•
Bi u đ c a thu c tính r i r c
Thuộc tính rời rạc cũng có một biểu đồ gắn với từng node. Tuy nhiển
SPRINT chỉ sử dụng một biểu đồ là count matrix chứa sự phân phối lớp ứng
với từng giá trị của thuộc tính đ ợc xem xét.
Các danh sách thuộc tính đ ợc xử lý cùng một lúc, do vậy thay vì đòi hỏi các
danh sách thuộc tính trong bộ nhớ, với SPRINT bộ nhớ chỉ cần chứa tập các biểu đồ
nh trên trong quá trình phát triển cây.
2.3.2. SPRINT s
li u “t t nh t”
d ng Gini-index làm đ đo tìm đi m phân chia t p d
SPRINT là một trong những thuật toán sử dụng độ đo Gini-index để tìm thuộc
tính tốt nhất làm thuộc tính test tại mỗi node trên cây. Chỉ số này đ ợc Breiman nghĩ
ra từ năm 1984, cách tính nh sau:
•
Tr ớc tiên cần định nghĩa: gini (S) = 1- ∑pj2
Trong đó: S là tập dữ liệu đào tạo có n lớp; pj là tần xuất của lớp j
trong S (là th ơng của số bản ghi có giá trị của thuộc tính phân lớp là pj với
tổng số bản ghi trong S)
• Nếu phân chia dạng nhị phân, tức là S đ ợc chia thành S1, S2 (SPRINT chỉ
sử dụng phân chia nhị phân này) thì chỉ số tính độ phân chia đ ợc cho bởi
công thức sau:
ginisplit(S) = n1/n*gini(S1) + n2/n*gini(S2)
Với n, n1, n2 lần l ợt là kích th ớc của S, S1, S2.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 31-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
u điểm của loại chỉ số này là các tính toán trên nó chỉ dựa vào thông tin về
sự phân phối các giá trị lớp trong từng phần phân chia mà không tính toán trên các giá
trị của thuộc tính đang xem xét.
Để tìm đ ợc điểm phân chia cho mỗi node, cần quét từng danh sách thuộc tính
của node đó và ớc l ợng các phân chia dựa trên mỗi thuộc tính gắn với node đó.
Thuộc tính đ ợc chọn để phân chia là thuộc tính có chỉ số ginisplit(S) nh nh t.
Điểm cần nhấn mạnh ở đây là khác với Information Gain chỉ số này đ ợc tính
mà không cần đọc nội dung dữ liệu, chỉ cần biểu đồ biểu diễn sự phân phối các bản ghi
theo các giá trị phân lớp. Đó là tiền đề cho cơ chế l u trữ dữ liệu th ờng trú trên đĩa.
Các biểu đồ của danh sách thuộc tính liên tục, hay rời rạc đ ợc mô tả d ới đây.
V i thu c tính liên t c
Với thuộc tính liên tục, các giá trị kiểm tra là các giá trị nằm giữa mọi cặp 2
giá trị liền kề của thuộc tính đó. Để tìm điểm phân chia cho thuộc tính đó tại một node
nhất định, biểu đồ đ ợc khởi tạo với Cbelow bằng 0 và Cabove là phân phối lớp của tất cả
các bản ghi tại node đó. Hai biểu đồ trên đ ợc cập nhật lần l ợt mỗi khi từng bản ghi
đ ợc đọc. Mỗi khi con trỏ chạy gini-index đ ợc tính trên từng điểm phân chia nằm
giữa giá trị vừa đọc và giá trị sắp đọc. Khi đọc hết danh sách thuộc tính (Cabove bằng 0
ở tất cả các cột) thì cũng là lúc tính đ ợc toàn bộ các gini-index của các điểm phân
chia cần xem xét. Căn cứ vào kết quả đó có thể chọn ra gini-index thấp nhất và t ơng
ứng là điểm phân chia của thuộc tính liên tục đang xem xét tại node đó. Việc tính giniindex hoàn toàn dựa vào biểu đồ. Nếu tìm ra điểm phân chia tốt nhất thì kết quả đó
đ ợc l u lại và biểu đồ vừa gắn danh sách thuộc tính đó đ ợc khởi tạo lại tr ớc khi xử
lý với thuộc tính tiếp theo.
Hình 14 -
ớc l ợng các điểm phân chia với thuộc tính liên tục
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 32-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
V i thu c tính r i r c
Với thuộc tính rời rạc, quá trình tìm điểm phân chia tốt nhất cũng đ ợc tính
toán dựa trên biểu đồ của danh sách thuộc tính đó. Tr ớc tiên cần quét toàn bộ danh
sách thuộc tính để thu đ ợc số l ợng phân lớp ứng với từng giá trị của thuộc tính rời
rạc, kết quả này đ ợc l u trong biểu đồ count matrix. Sau đó, cần tìm tất cả các tập
con có thể có từ các giá trị của thuộc tính đang xét, coi đó là điểm phân chia và tính
gini-index t ơng ứng. Các thông tin cần cho việc tính toán chỉ số gini-index của bất cứ
tập con nào đều có trong count matrix. Bộ nhớ cung cấp cho count matrix đ ợc thu hồi
sau khi tìm ra đ ợc điểm phân chia tốt nhất của thuộc tính đó.
Hình 15 -
ớc l ợng điểm phân chia với thuộc tính rời rạc
Ví d mô t cách tính ch s Gini–index
Với tập dữ liệu đào tạo đ ợc mô tả trong hình 13, việc tính chỉ số Gini-index để tìm ra
điểm phân chia tốt nhất đ ợc thực hiện nh sau:
1. Với Thuộc tính liên tục Age cần tính điểm phân chia trên lần l ợt các so sánh
sau Age<=17, Age<=20, Age<=23, Age<=32, Age<=43, Age<=68
Tuple count
Age<=17
Age>17
High
1
3
Low
0
2
G(Age<=17) = 1- (12+02) = 0
G(Age>17) = 1- ((3/5)2+(2/5)2) = 1 - (13/25)2 = 12/25
GSPLIT = (1/6) * 0 + (5/6) * (12/25) = 2/5
Khóa luận tốt
Tuple count
High
Low
Age<=20
2
0
2
nghiệpAge>20
– Nguyễn Thị2 Thùy Linh
– K46CA
- 33G(Age<=20) = 1- (12+02) = 0
G(Age>20) = 1- ((1/2)2+(1/2)2) = 1/2
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Tuple count
Age<=23
Age>23
High
3
1
Low
0
2
G(Age≤23) = 1- (12+02) = 0
G(Age>23) = 1- ((1/3)2+(2/3)2) = 1 - (1/9) - (4/9) = 4/9
GSPLIT = (3/6) * 0 + (3/6) * (4/9) = 2/9
Tính toán t ơng tự với các test còn lại Age<=32, Age<=43, Age<=68
So sánh các GSPILT tìm đ ợc ứng với từng phân chia của các thuộc tính, GSPLIT
ứng với Age <=23 có giá tr nh nh t. Do vậy điểm phân chia là tại thuộc tính Age
với giá trị phân chia = (23+32) / 2 = 27.5.
Kết quả ta có cây quyết định nh hình 5 phần 1.2.1
2.3.3. Th c thi s phân chia
Sau khi tìm ra điểm phân chia tốt nhất của node dựa trên so sánh gini-index
của các thuộc tính có trên node đó, cần thực thi sự phân chia bằng cách tạo ra các node
con và phân chia danh sách thuộc tính của node cha cho các node con.
Hình 16 - Phân chia danh sách thuộc tính của một node
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 34-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Với thuộc tính đ ợc chọn (Age nh trên hình vẽ) làm thuộc tính phân chia tại
node đó, việc phân chia danh sách thuộc tính này về các node con khá đơn giản. Nếu
đó là thuộc tính liên tục, chỉ cần cắt danh sách thuộc tính theo điểm phân chia thành 2
phần và gán cho 2 node con t ơng ứng. Nếu đó là thuộc tính rời rạc thì cần quét toàn
bộ danh sách và áp dụng test đã xác định để chuyển các bản ghi về 2 danh sách mới
ứng với 2 node con.
Nh ng vấn đề không đơn giản nh vậy với những thuộc tính còn lại tại node
đó (Car Type chẳng hạn), không có test trên thuộc tính này, nên không thể áp dụng các
kiểm tra trên giá trị của thuộc tính để phân chia các bản ghi. Lúc này cần dùng đến một
tr ờng đặc biệt trong các danh sách thuộc tính đó là rids. Đây chính là tr ờng kết nối
các bản ghi trong các danh sách thuộc tính. Cụ thể nh sau: trong khi phân chia danh
sách của thuộc tính phân chia (Age) cần chèn giá trị tr ờng rids của mỗi bản ghi vào
một b ng băm (hash table) để đánh đấu node con mà các bản ghi t ơng ứng (có cùng
rids) trong các danh sách thuộc tính khác đ ợc phân chia tới. Cấu trúc của bảng băm
nh sau:
Hash table
Rids
Child node
1
L
2
R
3
R
4
R
5
L
6
L
Hình 17 - Cấu trúc của bảng băm phân chia dữ liệu trong SPRINT (theo ví dụ các
hình tr ớc)
Phân chia xong danh sách của thuộc tính phân chia thì cũng là lúc xây dựng
xong bảng băm. Danh sách các thuộc tính còn lại đ ợc phân chia tới các node con theo
thông tin trên bảng băm bằng cách đọc tr ờng rids trên từng bản ghi và tr ờng Child
node t ơng ứng trên bảng băm.
Nếu bảng băm quá lớn so với bộ nhớ, quá trình phân chia đ ợc chia thành
nhiều b ớc. Bảng băm đ ợc tách thành nhiều phần sao cho vừa với bộ nhớ, và các
danh sách thuộc tính phân chia theo từng phần bảng băm. Quá trình lặp lại cho đến khi
bảng băm nằm trong bộ nhớ.
2.3.4. SPRINT là thu t toán hi u qu v i nh ng t p d
v i các thu t toán khác
li u quá l n so
SPRINT ra đời không nhằm mục đích làm tốt hơn SLIQ [9] với những tập dữ
liệu mà danh sách lớp nằm vừa trong bộ nhớ. Mục tiêu của thuật toán này là nhằm vào
những tập dữ liệu quá lớn so với các thuật toán khác và có khả năng tạo ra một mô
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 35-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
hình phân lớp hiệu quả từ đó. Hơn nữa, SPRINT còn đ ợc thiết kế để dễ dàng song
song hóa. Quả vậy, việc song song hóa SPRINT khá tự nhiên và hiệu quả với cơ chế
xử lý dữ liệu song song. SPRINT đạt đ ợc chuẩn cho việc sắp xếp dữ liệu và tải cân
bằng khối l ợng công việc bằng cách phân phối đều danh sách thuộc tính thuộc tính
cho N bộ vi xử lý của một máy theo kiến trúc shared-nothing [7]. Việc song song hóa
SPRINT nói riêng cũng nh song song hóa các mô hình phân lớp dữ liệu dựa trên cây
quyết định nói chung trên hệ thống Shared-memory multiprocessor (SMPs) hay còn
đ ợc gọi là hệ thống shared-everthing đ ợc nghiên cứu trong [10].
Bên cạnh những mặt mạnh, SPRINT cũng có những mặt yếu. Tr ớc hết đó là
b ng băm sử dụng cho việc phân chia dữ liệu, có kích cỡ tỉ lệ thuận với số l ợng đối
t ợng dữ liệu gắn với node hiện tại (số bản ghi của một danh sách thuộc tính). Đồng
thời bảng băm cần đ ợc đặt trong bộ nhớ khi thi hành phân chia dữ liệu, khi kích cỡ
bảng băm quá lớn, việc phân chia dữ liệu phải tách thành nhiều b ớc. Mặt khác, thuật
toán này phải chịu chi phí vào-ra “trầm trọng”. Việc song song hóa thuật toán này
cũng đòi hỏi chi phí giao tiếp toàn cục cao do cần đồng bộ hóa các thông tin về các chỉ
số Gini-index của từng danh sách thuộc tính.
Ba tác giả của SPRINT đã đ a ra một số kết quả thực nghiệm trên mô hình
phân lớp SPRINT so sánh với SLIQ [7] đ ợc thể hiện bằng biểu đồ d ới đây.
Biểu đồ 1- So sánh thời gian thực thi của mô hình phân lớp SPRINT và SLIQ theo kích
th ớc tập dữ liệu đào tạo
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 36-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Từ biểu đồ trên có thể thấy: với những tập dữ liệu nhỏ (<1 triệu cases) thì thời
gian thực thi của SPRINT lớn hơn so với thời gian thực thi SLIQ. Điều này có thể giải
thích do khi đó danh sách lớp khi dùng thuật toán SLIQ vẫn nằm vừa trong bộ nhớ.
Nh ng với những tập dữ liệu lớn (>1 triệu cases) thì SLIQ không thể thao tác, trong
khi với những tập dữ liệu khoảng hơn 2,5 triệu cases SPRINT vẫn thao tác dễ dàng. Lý
do là SPRINT sử dụng cơ chế l u trữ liệu th ờng trú hoàn toàn trên đĩa.
2.4. So sánh C4.5 và SPRINT
N i dung so
sánh
C4.5
SPRINT
Tiêu chuẩn Gain-entropy
l a
ch n Có khuynh h ớng làm cô lập lớp
thu c tính lớn nhất khỏi các lớp khác
phân chia
Gini-index
Có khuynh h ớng chia thành các
nhóm lớp với l ợng dữ liệu
t ơng đ ơng
class A 40
class B 30
class C 20
class D 10
class A 40
class B 30
class C 20
class D 10
if age < 40
if age < 65
yes
class A 40
no
class B 30
class C 20
class D 10
C ch l u L u trú trong bộ nhớ (memoryresident)
tr d li u
-> Áp dụng cho những ứng dụng
khai phá cơ sở dữ liệu nhỏ (hàng
trăm nghìn bản ghi)
yes
class A 40
class D
no
class B 30
class C 20
L u trú trên đĩa (disk-resdient)
-> Áp dụng cho những ứng dụng
khai phá dữ liệu cực lớn mà các
thuật toán khác không làm đ ợc
(hàng trăm triệu - hàng tỉ bản
ghi)
C ch s p Sắp xếp lại tập dữ liệu t ơng Sắp xếp tr ớc một lần. Trong
ứng với mỗi node
quá trình phát triển cây, danh
x p d li u
sách thuộc tính đ ợc phân chia
nh ng thứ tự ban đầuvẫn đ ợc
duy trì, do đó không cần phải
sắp xếp lại.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 37-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Chư ng 3.
CÁC K T QU
TH C NGHI M
Tác giả sử dụng mô hình phân lớp C4.5 release8 mã nguồn mở do J. Ross
Quinlan viết, tại địa chỉ:http://www.cse.unsw.edu.au/~quinlan/ để phân tích, đánh giá
mô hình phân lớp C4.5 về kết quả phân lớp và các nhân tố ảnh h ởng đến hiệu năng
của mô hình.
3.1. Môi trường thực nghiệm
Mã nguồn C.45 đ ợc cài đặt và chạy thử nghiệm trên Server 10.10.0.10 của
Đại học Công Nghệ.
C u hình c a Server nh sau: bộ vi xử lý Intel ® Xeon™ 2.4GHz, có 2 bộ
xử lý vật lý có thể hoạt động nh 4 bộ xử lý logic theo công nghệ hyper-threading,
cache size: 512KB, dung l ợng bộ nhớ trong 1GB.
T p d li u th nghi m là tập dữ liệu chứa các thông tin về khách hàng sử
dụng điện thoại di động đã đăng ký sử dụng web portal. Các tr ờng trong tập dữ liệu
gồm có: Các thông tin cá nhân nh : Tên tuổi, giới tính, ngày sinh, vùng đăng ký sử
dụng điện thoại, loại điện thoại sử dụng, version của loại điện thoại đó, số lần và thời
gian truy cập web portal để sử dụng các dịch vụ nh gửi tin nhắn, gửi logo hay
ringtone... Tập dữ liệu có kích th ớc khoảng 120000 bản ghi dùng để training và
khoảng 60000 bản ghi đ ợc sử dụng để làm tập dữ liệu test.
3.2. Cấu trúc mô hình phân lớp C4.5 release8:
3.2.1. Mô hình phân l p C4.5 có 4 chư ng trình chính:
• Ch ơng trình sinh cây quyết định (c4.5)
• Ch ơng trình sinh luật sản xuất (c4.5rules)
• Ch ơng trình ứng dụng cây quyết định vào phân lớp những dữ liệu mới
(consult)
• Ch ơng trình ứng dụng bộ luật sản xuất vào phân lớp những dữ liệu mới
(consultr)
Ngoài ra C4.5 còn có 2 tiện ích đi kèm phục vụ cho quá trình chạy thực nghiệm là:
• csh shell script cho kỹ thuật ớc l ợng độ chính xác của mô hình phân lớp
cross-validation ('xval.sh')
•
Hai ch ơng trình phụ thuộc đi kèm là ('xval-prep' và 'average').
Chi tiết hơn về mô hình phân lớp C4.5 có thể tham khảo tại địa chỉ:
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 38-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/c4.5/tutorial.html
3.2.2. C u trúc d
li u s d ng trong C4.5
Mỗi bộ dữ liệu dùng trong C4.5 gồm có 3 file:
3.2.2.1. Filestem.names: đ nh nghĩa b d li u
Hình 18 - File định nghĩa cấu trúc dữ liệu sử dụng trong thực nghiệm
Mô t :
• Dòng trên cùng định nghĩa các giá trị phân lớp theo thuộc tính đ ợc chọn (ví
dụ trên hình 18 là thuộc tính MOBILE_PRODUCTER_ID)
• Các dòng tiếp theo là danh sách các thuộc tính cùng với tập giá trị của nó
trong tập dữ liệu. Các thuộc tính liên tục đ ợc định nghĩa bằng từ khóa
“continuous”
• Chú thích đ ợc định nghĩa sau dấu “|”
3.2.2.2. Filestem.data: ch a d li u training
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 39-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 19 - File chứa dữ liệu cần phân lớp
Filestem.data có cấu trúc nh sau: mỗi dòng t ơng ứng với một bản ghi
(cases) trong cơ sở dữ liệu. Mỗi dòng một bộ giá trị theo thứ đã định của các thuộc
tính định nghĩa trong filestem.names. Các giá trị ngăn cách nhau bởi dấu phảy. Giá trị
thiếu (missing value) đ ợc biểu diễn bằng dấu “?”.
3.2.2.3. Filestem.test: ch a d li u test
File này chứa dữ liệu test trên mô hình phân lớp đã đ ợc tạo ra từ tập dữ liệu
training, và có cấu trúc giống filestem.data
3.3. Kết quả thực nghiệm
3.3.1. `7M t s k t qu phân l p tiêu bi u:
3.3.1.1. Cây quy t đ nh
Lệnh tạo cây quyết định
$ ./C4.5 -f ../Data/Classes/10-5/class –u >> ../Data/Classes/10-5/class.dt
Tham số tùy chọn:
-f: xác định bộ dữ liệu cần phân lớp
-u: tùy chọn cây được tạo ra được đánh giá trên tập dữ liệu test.
-v verb: mức độ chi tiết của output [0..3], mặc định là 0
-t trials: thiết lập chế độ iteractive với trials là số cây thử
nghiệm. Iteractive là chế độ cho phép tạo ra nhiều cây thử nghiệm bắt
đầu với một tập con dữ liệu được chọn ngẫu nhiên. Mặc định là chế độ
batch với toàn bộ tập dữ liệu được sử dụng để tạo một cây quyết định
duy nhất.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 40-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Cây quyết định có các node trong là các kiểm tra giá trị của thuộc tính đ ợc
chọn để phát triển tại node đó. Lá của cây quyết định có định dạng: Giá_trị_phân_lớp
(N/E) hoặc (N). Với N/E là tỉ lệ giữa tổng các case đạt tới lá đó với số case đạt tới lá
đó nh ng thuộc về lớp khác (trong tập dữ liệu đào tạo).
Hình 20 - Dạng cây quyết định tạo ra từ tập dữ liệu thử nghiệm
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 41-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 21 -
ớc l ợng trên cây quyết định vừa tạo ra trên tập dữ liệu training và tập
dữ liệu test
Sau khi cây quyết định đ ợc tạo ra, nó sẽ đ ợc ớc l ợng lại độ chính xác trên
chính tập dữ liệu đào tạo vừa học đ ợc, và có thể đ ợc ớc l ợng trên tập dữ liệu test
độc lập với dữ liệu training nếu có tùy chọn từ phía ng ời dùng.
Các ớc l ợng đ ợc thực hiện trên cây khi ch a cắt tỉa và sau khi đã cắt tỉa.
Mô hình C4.5 cũng cho phép truyền các tham số về mức độ cắt tỉa của cây, mặc định
là cắt tỉa 25%.
3.3.1.2. Các lu t s n xu t tiêu bi u
Lệnh tạo luật sản xuất khi đã có cây quyết định:
$ ./C4.5rules
5/class.r
-f
../Data/Classes/10-5/class
-u
>>
../Data/Classes/10-
Các tham số tùy chọn –f, -v, -u giống như với lệnh tạo cây quyết định.
Mỗi luật sinh ra gồm có 3 phần:
• Điều kiện phân lớp
• Giá trị phân lớp ( ->class …)
• []: dự đoán độ chính xác của luật. Giá trị này đ ợc ớc l ợng trên tập
training và test (nếu có tùy chọn –u khi sinh luật)
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 42-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 22 - Một số luật rút ra từ bộ dữ liệu 19 thuộc tính, phân lớp loại thiết lập chế độ
giao diện của ng ời sử dụng (WEB_SETTING_ID)
Việc đ a ra đ ợc các luật liên quan đến sở thích giao diện sử dụng của khách
hàng giúp ích cho công việc thiết kế, cũng nh tạo các loại giao diện phù hợp cho từng
loại đối t ợng khách hàng khác nhau. Ví dụ, Rule 233 trong hình 22 cho thấy, nếu
khách hàng đăng ký sử dụng dịch vụ tại Hà Nội, nghề nghiệp thuộc nhóm Other và
sinh năm 1982 thì chế độ giao diện mà ng ời đó sử dụng có mã số là 1. Kết luận này
có độ chính xác là 96,6%.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 43-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 23 - Một số luật rút ra từ bộ dữ liệu 8 thuộc tính, phân lớp theo số hiệu nhà sản
xuất điện thoại (PRODUCTER_ID)
Từ kết quả thực tế hình 23, từ Rule 1021, chúng ta có thể kết luận: nếu khách hàng
làm công việc Supervisory và sinh trong khoảng từ năm 1969 đến 1973 thì loại điện
thoại mà khách hàng dùng có số hiệu là 1 (là điện thoại SAMSUNG). Độ chính xác
của kết luận này là 91,7%.
Những luật nh trên giúp cho các nhân viên maketing có thể tìm ra đ ợc thị tr ờng
điện thoại di động đối với từng loại đối t ợng khách hàng khác nhau, từ đó có các
chiến l ợc phát triển sản phẩm hợp lý.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 44-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 24 - Một số luật sinh ra từ tập dữ liệu 8 thuộc tính, phân lớp theo dịch vụ điện
thoại mà khách hàng sử dụng (MOBILE_SERVICE_ID)
Ví dụ từ Rule 661: nếu khách hàng là nam (F), nghề nghiệp Engineering, điện
thoại sử dụng là Erricsion (MOBILE_PRODUCTER_ID = 4) và đăng ký năm 2004,
thì dịch vụ mà khách hàng đó sử dụng là gửi logo (MOBILE_SERVICE_ID = 2). Độ
chính xác của luật này là 79,4%.
Từ những luật nh vậy, ta có thể thống kê cũng nh dự đoán đ ợc xu h ớng
sử dụng các loại dịch vụ của từng đối t ợng khách hàng khác nhau. Từ đó có chiến
l ợc phát triển dịch vụ khách hàng hiệu quả.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 45-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Hình 25 -
ớc l ợng tập luật trên tập dữ liệu đào tạo
Sau khi đ ợc tạo ra, tập luật đ ợc ớc l ợng lại trên tập training data, hay tập
dữ liệu test (tùy chọn).
Mô tả các một số tr ờng tiêu biểu:
• Rule: số hiệu của luật
• Zize: Kích th ớc của luật (số các điều kiện so sánh trong phần điều kiện phân
lớp)
• Used: số l ợng cases trong tập training áp dụng luật đó. Tr ờng này quy định
tính phổ biến của luật.
• Wrong: số l ợng case phân lớp sai -> tỉ lệ phần trăm lỗi
Kết luận
Từ quá trình thực nghiệm, chúng tôi nhận thấy vai trò của quá trình tiền xử lý
dữ liệu là rất quan trọng. Trong quá trình này, cần xác định chính xác những thông tin
gì cần rút ra từ cơ sở dữ liệu đó, từ đó chọn thuộc tính phân lớp phù hợp. Sau đó việc
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 46-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
lựa chọn những thuộc tính liên quan là rất quan trọng, nó quyết định mô hình phân lớp
có đúng đắn không, có ý nghĩa thực tế không và có thể áp dụng cho những dữ liệu
t ơng lai hay không.
3.3.2. Các bi u đ hi u năng
Các tham số ảnh h ởng đến hiệu năng của mô hình phân lớp là [6]:
• Số các bản ghi trong tập dữ liệu đào tạo (N)
• Số l ợng thuộc tính (A)
• Số các giá trị rời rạc của mỗi thuộc tính (nhân tố nhánh) (V)
• Số các lớp (C)
Chi phí xây dựng cây quyết định là tổng chi phí xây dựng từng node:
T = Σ tnode(i)
Chi phí tốn cho node i đ ợc tính bằng tổng các khoản chi phí riêng cho từng công
việc:
tnode(i) = tsingle(i) + tfreq(i) + tinfo(i) + tdiv(i)
Với:
• tsingle(i) là chi phí thực thi việc kiểm tra xem liệu tất cả các case trong tập
dữ liệu đào tạo có thuộc về cùng một lớp không?
• tdiv(i) là chi phí phân chia tập dữ liệu theo thuộc tính đã chọn
• Việc lựa chọn thuộc tính có Information gain lớn nhất trong tập dữ liệu
hiện tại là kết quả của việc tính Information gain của từng thuộc tính. Chi
phí cho quá trình này bao gồm thời gian tính toán tần xuất phân phối theo
các giá trị phân lớp của từng thuộc tính (tfreq(i)) và thời gian để tính
Information gain từ các thông tin phân phối đó (tinfo(i)).
Có thể biểu diễn sự phụ thuộc của các khoản chi phí trên vào các tham số hiệu năng đã
mô tả ở trên nh sau:
tfreq = k1 *AiNi
tinfo = k2 * CAiV
tdiv = k3 * Ai
tsingle = k4*Ni
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 47-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Với kj là hằng số có giá trị tùy theo từng ứng dụng cụ thể. Số l ợng bản ghi (Ni) và số
l ợng thuộc tính (Ai) t ơng ứng với từng node phụ thuộc vào độ sâu của node đó và
bản thân tập dữ liệu.
Việc xác định chính xác chi phí cho quá trình xây dựng cây quyết định (T) là rất khó
và cần phải biết chính xác hình dáng của cây quyết định, điều này không thể xác định
trong thời gian chạy. Chính vì vậy mà T đ ợc đơn giản hóa bằng cách dùng giá trị
trung bình đi kèm với những giả sử về hình dáng của cây và giải các ph ơng trình lặp
cho từng thành phân riêng lẻ của mô hình [6].
Sau đây là các kết quả thực nghiệm đánh giá ảnh h ởng của các tham số hiệu
năng nh kích th ớc tập dữ liệu đào tạo, số l ợng thuộc tính, thuộc tính liên tục, và số
giá trị phân lớp tới mô hình phân lớp C4.5:
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 48-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
3.3.2.1. Th i gian th c thi ph thu c vào kích th
c t p d li u đào t o
Các thử nghiệm đã đ ợc tiến hành trên nhiều tập dữ liệu với kích th ớc, số l ợng
thuộc tính và thuộc tính phân lớp khác nhau. Sau đây là các bảng kết quả và biểu đồ
thể hiện sự phụ thuộc đang xét.
Thử nghiệm với tập dữ liệu 2 thuộc tính
Bảng 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 2 thuộc tính
Kích th ớc 29000
Thời gian
tập dữ liệu
xây dựng (giây)
60000
66000
131000
262000
Decision Tree
Production Rules
0.46
6.82
0.47
8.85
1.17
20.51
2.2
37.94
(s)
0.15
3.21
40
Decision
Tree
35
30
25
Productio
n Rules
20
15
Trend line
of
Productio
n rules
10
5
0
29000
60000
66000
131000
262000 (cases)
Biểu đồ 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 2 thuộc tính
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 49-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Thử nghiệm với tập dữ liệu 7 thuộc tính
Bảng 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 7 thuộc tính
Kích th ớc 1000
Thời gian
tập dữ liệu
xây dựng (giây)
10000 15000 20000
25000
30000
36000
Decision Tree
Production Rules
0.46
107.1
5.70
1211.0
8.31
2504.8
13.34
5999.5
0.03
0.13
1.90
276.2
2.79
709.9
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
Decision
Tree
Productio
n Rules
Trend line
of
Productio
n rules
1000
10000 15000 20000 25000 30000 36000
Biểu đồ 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo 7 thuộc tính
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 50-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Thử nghiệm với tập dữ liệu 18 thuộc tính
Bảng 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo18 thuộc tính
6000
8500
10000 12000 15000 17500 20000 25000
Decision Tree
0.45
0.64
1.32
1.77
2.37
1.8
2.68
2.98
5.24
Production Rules
43.6
90.77
304.0
7
531.3
4
838.8
8
968.2
4
1584.
63
2927.
56
4617.
23
5000
(s)
Kích th ớc 4000
Thời gian tập dữ liệu
xây dựng (giây)
4500
Decision
Tree
4000
3500
Productio
n Rules
3000
2500
2000
Trend Line
of
Productio
n Rules
1500
1000
500
(case)
0
4000 6000 8500 10000 12000 15000 17500 20000 25000
Biểu đồ 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích
th ớc tập dữ liệu đào tạo18 thuộc tính
Các đánh giá sự phụ thuộc của thời gian thực thi vào kích th ớc tập dữ liệu
đào tạo đã đ ợc tiến hành trên các tập dữ liệu với số l ợng thuộc tính khác nhau. Có
thể rút ra các kết luận sau:
• Kích th ớc tập dữ liệu càng lớn thì thời gian sinh cây quyết định cũng nh thời
gian sinh tập luật sản xuất càng lớn. Căn cứ vào các đ ờng trendline của đ ờng
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 51-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
biểu diễn thời gian sinh tập luật sản xuất đ ợc vẽ thêm trên các biểu đồ, chúng
tôi dự đoán sự phụ thuộc trên đ ợc diễn đạt bằng hàm đa thức.
• Các biểu đồ trên cho thấy quá trình sinh luật sản xuất sau từ cây quyết định đã
tạo ra tốn tài nguyên tính toán gấp nhiều lần so với quá trình sinh cây quyết
định. Thực nghiệm cho thấy với những tập dữ liệu cỡ trăm nghìn bản ghi, thời
gian sinh luật sản xuất là khá lâu ( thông th ờng > 5 giờ). Đó cũng là một trong
những lý do khiến C4.5 không thể áp dụng với những tập dữ liệu lớn. Tập dữ
liệu đào tạo có càng nhiều thuộc tính thì sự chênh lệch về thời gian thực thi giữa
2 quá trình trên càng lớn.
3.3.2.2. Hi u năng c a C4.5 ph thu c vào s l
ng thu c tính
Để đánh giá sự phụ thuộc trên, các thử nghiệm đã tiến hành với 3 tập dữ liệu
có 2, 4, và 8 thuộc tính rời rạc, với cùng thuộc tính phân lớp.
Bảng 5 - Thời gian sinh cây quyết định phụ thuộc vào số l ợng thuộc tính
3000
0.01
0.12
0.14
16000
0.05
0.82
3.56
23000
0.1
2.18
9.99
32000
0.18
3.32
23.40
40500
0.25
5.58
33.36
55500
0.39
11.83
47.62
65500
0.47
16.79
80
96600
0.89
33.49
106.61
(s)
2 attributes
4 attributes
8 attributes
6000
0.02
0.18
0.3
200
180
160
140
2
attributes
4
attributes
8
attributes
120
100
80
60
40
20
00
10
(cases)
13
60
0
0
96
50
0
65
50
55
50
0
0
40
00
32
00
0
0
23
00
16
00
60
30
00
0
Biểu đồ 5 - Sự phụ thuộc thời gian sinh cây quyết định vào số l ợng thuộc tính
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 52-
131000
1.17
71.52
185
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
Thời gian C4.5 xây dựng cây quyết định phụ thuộc vào số l ợng thuộc tính
qua các khoảng thời gian tfreq, tinfo, tdiv. Số thuộc tính càng nhiều thời gian tính toán để
lựa chọn thuộc tính tốt nhất test tại mỗi node càng lớn, vì vậy thời gian sinh cây quyết
định càng tăng. Do vậy C4.5 bị hạn chế về số l ợng thuộc tính trong tập dữ liệu đào
tạo [2]. Đây là một điểm khác biệt so với SPRINT
3.3.2.3. Hi u năng c a C4.5 khi thao tác v i thu c tính liên t c
Bảng 6 - Thời gian xây dựng cây quyết định với thuộc tính rời rạc và thuộc tính liên
tục
140
6000
0.18
16000 22000 31000 40000 55000 65000 96000 131000
0.92
2.18
3.32
5.74
11.83 16.79 33.47 61.52
0.24
0.66
3.02
5.01
11.56
16.99
30.37
38.16
70.38
125.21
(s)
3 thuộc tính rời rạc+
1 thuộc tính liên tục
4 thuộc tính liên tục
3000
0.12
120
100
3 categorical
attributes + 1
continuous
attribute
4 continuous
attributes
80
60
40
20
13
10
00
96
00
0
65
00
0
55
00
0
40
00
0
31
00
0
22
00
0
(cases)
60
00
16
00
0
30
00
0
Biểu đồ 6 - So sánh thời gian xây dựng cây quyết định từ tập thuộc tính liên tục và từ
tập thuộc tính rời rạc
Nh đã phân tích trong thuật toán C4.5 cũng nh trong thuật toán phân lớp dữ
liệu dựa trên cây quyết định nói chung, việc thao tác với thuộc tính liên tục chiếm
nhiều tài nguyên tính toán hơn với thuộc tính rời rạc. Do vậy tập dữ liệu có nhiều
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 53-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
thuộc tính liên tục ảnh h ởng đáng kể đến thời gian sinh cây quyết định so với tập dữ
liệu có nhiều thuộc tính rời rạc.
3.3.2.4. Hi u năng c a C4.5 khi thao tác v i nhi u giá tr phân l p
Bảng 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp
6000
0.07
0.18
16000 23000 31000 40000 55000
0.22
0.35
0.61
0.97
1.8
0.82
2.18
3.32
5.74
11.83
65500
2.36
16.79
96600
3.68
33.49
131000
4.72
61.51
(s)
3000
4 classes
0.04
28 classes 0.12
4
classes
28
classes
16
00
0
23
00
0
31
00
0
40
00
0
55
00
0
65
50
0
96
60
13 0
10
00
60
00
30
00
70
60
50
40
30
20
10
0
(cases)
Biểu đồ 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp
Càng nhiều giá trị phân lớp thì thời gian tính Information gain cho từng thuộc
tính (tinfo) càng nhiều. Do vậy thời gian sinh cây quyết định càng lâu.
3.4. Một số đề xuất cải tiến mô hình phân lớp C4.5
Từ quá trình nghiên cứu mô hình phân lớp C4.5 cũng nh những so sánh với SPRINT
để thấy đ ợc u nh ợc điểm của thuật toán. Và từ quá trình thực nghiệm chúng tôi
đ a ra một số đề xuất cải tiến thuật toán C4.5
1. Sinh luật sản xuất là một tính năng mới của C4.5 so với các thuật toán khác.
Hiện nay với cơ sở dữ liệu lớn, tập luật sinh ra là rất dài, ví dụ với tập training
cỡ 30000 cases với 8 thuộc tính, tập luật có thể lên tới 3000 luật. Do đó việc
xem và trích rút thông tin có ích trên tập luật là khó khăn. Trên thực tế đó,
chúng tôi đề xuất tích hợp thêm vào C4.5 module trích chọn tập những luật “tốt
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 54-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
nhất” có là những luật có độ chính xác chấp nhận đ ợc (mức độ chính xác có
thể do ng ời dùng tùy chọn) và có độ phổ biến cao (là những luật mà áp dụng
đ ợc trên nhiều case trong tập dữ liệu thử nghiệm).
2. Sinh luật sản xuất là một tính năng mới, đem lại nhiều lợi ích của C4.5 so với
các thuật toán phân lớp dữ liệu khác. Nh ng quá trình sinh luật sản xuất tốn rất
nhiều tài nguyên tính toán so với quá trình sinh cây quyết định. Do vậy cần
song song hóa giai đoạn sinh luật để cải tiến hiệu năng của C4.5
3. C4.5 bị hạn chế về số l ợng thuộc tính trong tập dữ liệu đào tạo, và độ chính
xác của các cây quyết định hay các luật sinh ra nói chung là ch a cao. Cần tập
trung sử dụng các ph ơng pháp cải tiến độ chính xác của mô hình phân lớp nh
bagging, boosting.
4. C4.5 thao tác với thuộc tính liên tục lâu hơn thuộc tính rời rạc. Điều này có thể
giải thích bởi: với thuộc tính liên tục có n giá trị đã sẵp xếp, thuật toán cần độ
đo phân chia tại (n-1) ng ỡng nằm giữa 2 giá trị liền nhau trong dãy sắp xếp.
Từ đó mới có thể tìm ra đ ợc một ng ỡng tốt nhất để test trên thuộc tính đó.
Trong tập dữ liệu đào tạo, thuộc tính liên tục càng nhiều giá trị, thì tài nguyên
tính toán bỏ ra để thao tác với nó càng nhiều. Hiện nay đã có một số đề xuất cải
tiến cách xử lý với thuộc tính liên tục [3][8], đó là một trong những h ớng
nghiên cứu đang nghiên cứu của đề tài.
5. Chúng tôi đề xuất cơ chế sắp xếp tr ớc có sử dụng l ợc đồ phân phối lớp một
lần nh của SPRINT áp dụng vào C4.5. Từ đó tiến tới xây dựng cơ chế l u trữ
dữ liệu th ờng trú trên đĩa. Nếu thực hiện đ ợc sẽ làm tăng hiệu năng cũng nh
khả năng mở rộng của mô hình phân lớp C4.5.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 55-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
K T LU N
Trong khuôn khổ khóa luận tốt nghiệp này, chúng tôi đã nghiên cứu, phân
tích, đánh giá các thuật toán phân lớp dữ liệu dựa trên cây quyết định. Tiêu biểu là 2
thuật toán C4.5 và SPRINT. C4.5 và SPRINT có cách thức l u trữ dữ liệu và xây dựng
cây quyết định dựa trên những độ đo khác nhau. Do đó hai thuật toán này có phạm vi
ứng dụng vào các cơ sở dữ liệu có kích th ớc khác nhau.
C4.5 là thuật toán xử lý đầy đủ các vấn đề của quá trình phân lớp dữ liệu: lựa
chọn thuộc tính tốt nhất, l u trữ phân chia dữ liệu, xử lý giá trị thiếu, tránh quá vừa,
cắt tỉa cây,…Với những lý do đó C4.5 đã trở thành thuật toán phổ biến nhất trong
những ứng dụng vừa và nhỏ. Quá trình triển khai, cài đặt thử nghiệm cùng với các
đánh giá hiệu năng mô hình phân lớp C4.5 đã đ ợc tiến hành. Và đã thu đ ợc nhiều
kết quả có ý nghĩa thực tiến, cũng nh các kết quả gợi mở những h ớng nghiên cứu
tiếp theo.
SPRINT là một thuật toán tối u cho những cơ sở dữ liệu cực lớn. Những u
điểm của SPRINT là t t ởng của thuật toán khá đơn giản, có khả năng mở rộng cao,
lại rất dễ dàng song song hóa. Do vậy cài đặt và triển khai SPRINT có ý nghĩa khoa
học và có khả năng triển khai ứng dụng và đem lại nhiều lợi ích thực tế.
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 56-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
TÀI LI U THAM KH O
[1] Anurag Srivastava, Eui- Hong Han, Vipin Kumar, Vieet Singh. Parallel
Formulations of Decision-Tree Classification Algorithm. Kluwer Academic Publisher,
1999.
[2] Anurag Srivastava, Vineet Singh, Eui- Hong (Sam) Han, Vipin Kumar. An
Efficient, Scalable, Parallel Classifier for Data mining.
[3] Girija J. Narlikar. A Parallel, Multithreaded Decision Tree Builder. CMU-CS-98184. reports-archive.adm.cs.cmu.edu/ anon/1998/CMU-CS-98-184.pdf
[4] Henrique Andrade, Tahsin Kurc, Alan Sussman, Joel Saltz. Decision Tree
Construction for Data Ming on Cluster of Shared-Memory Multiprocessors.
http://citeseer.csail.mit.edu/178359.html
[5] Ho Tu Bao, Chapter 3:Data mining with Decision Tree –
http://www.netnam.vn/unescocourse/knowlegde/knowlegd.htm
[6] John Darlington, Moustafa M. Ghanem, Yike Guo, Hing Wing To. Performance
Model for Co-odinating Parallel Data Classification
[7] John Shafer, Rakesh Agrawal, Manish Mehta. SPRINT- A Scalable Paralllel
Classifier for Data mining. In Predeeings of the 22nd International Conference on Very
Large Database, India, 1996.
[8] J. R. Quinlan. Improve Used of Continuous Attribute in C4.5. In Joural of Artficial
Intelligence Research 4 (1996) 77-90
[9] Manish Mehta, Rakesh Agrawal, Jorma Rissanen. SLIQ: A Fast Scalable
Classifier for Data mining. IBM Amaden Research Center, 1996.
[10] Mohammed J. Zaki, Ching-Tien Ho, Rekesh Agrawal. Parallel Classification for
Data Mining on Shared-Memory Multiprocessors. IVM Almaden Research Center,
San Jose, CA 95120.
[11] Rajeev Rastogi, Kyuseok Shim (Bell Laboratories). PUBLIC: A Decision Tree
Classifier that Integrates Building and Pruning, 1998.
www.vldb.org/conf/1998/p404.pdf
[12] Richard Kufrin. Generating C4.5 Production Rules in Parallel. In Proceeding of
Fourteenth National Conference on Artificial Intelligence, Providence RI, 1997
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 57-
Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định
www.almaden.ibm.com/software/quest/Publications/papers/vldb96_sprint.pdf
[13] Ron Kohavi, J. Ross Quinlan. Decision Tree Discovery, 1999
[14] The Morgan Kaufmann Series in Data Management Systems, Jim Gray.
Datamining- Concepts and Techniques, Chapter 7-Classification and Prediction.
Series Editor Morgan Kaufmann Publishers, August 2000
Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA
- 58-