Khóa luận Áp dụng phương pháp trích chọn thuộc tính đặc trưng để nâng cao hiệu quả phân lớp khi khai phá dữ liệu lớn

giảm xấp xỉ 1.8 lần so với tập dữ liệu ban đầu. 
0
10
20
30
40
50
60
70
80
90
100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T
ỷ
 l
ệ
 đ
ú
n
g
Số lần thực hiện
Tập DL mới
Tập DL gốc
 48 
o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 74.05, tuy 
nhiên phương sai lại tăng (từ 4.21 lên 15.3) nên mô hình kiểm tra không ổn 
định bằng. 
o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 99.9, 
đồng thời phương sai cũng giảm (từ 1.19 còn 0.38) nên mô hình huấn luyện 
có tính ổn định hơn. 
 Trường hợp 3: Generations = 50 với 15 lần chạy thử. 
Bảng 5.5: Kết quả phân lớp trong trường hợp 3 
 Số lượng 
thuộc tính 
Tỷ lệ đúng của tập huấn 
luyện 
Kết quả của tập kiểm 
tra 
1 55 100 75 
2 58 100 75 
3 48 100 71.4286 
4 62 100 85.7143 
5 51 100 71.4286 
6 57 100 53.5714 
7 52 100 78.5714 
8 52 100 78.5714 
9 49 100 75 
10 57 100 89.2857 
11 57 100 92.8571 
12 63 100 67.8571 
13 49 100 92.8571 
14 59 100 75 
15 63 100 89.2857 
MAX 63 100 92.8571 
Phương sai 5.11 0 10.62 
Trung bình 100 78.10 
 49 
Hình 5.9: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới 
(trường hợp 3). 
Nhận xét: 
o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.9 lần so với tập dữ liệu ban đầu. 
o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 78.1, tuy 
nhiên phương sai lại tăng (từ 4.21 lên 10.62) nên mô hình kiểm tra không 
ổn định bằng. 
o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 100, 
đồng thời phương sai cũng giảm (từ 1.19 còn 0) nên mô hình huấn luyện có 
tính ổn định cao. 
 Trường hợp 4: Generations = 60 với 15 lần chạy thử. 
Bảng 5.6: Kết quả phân lớp trong trường hợp 4. 
Số lượng 
thuộc tính 
Tỷ lệ đúng của tập huấn 
luyện 
Kết quả của tập kiểm 
tra 
1 52 100 89.2857 
2 54 100 53.5714 
3 48 100 75 
4 60 100 82.1429 
0
10
20
30
40
50
60
70
80
90
100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T
ỷ
 l
ệ
 đ
ú
n
g
Số lần thực hiện
Tập DL mới
Tập DL gốc
 50 
5 59 100 50 
6 58 100 78.5714 
7 43 98.4615 96.4286 
8 65 100 67.8571 
9 64 100 78.5714 
10 57 100 96.4286 
11 63 100 85.7143 
12 65 100 75 
13 67 100 50 
14 57 100 85.7143 
15 54 100 60.7143 
MAX 67 100 96.4286 
Phương sai 6.76 0.40 15.57 
Trung bình 99.90 75.00 
Hình 5.10: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới 
(trường hợp 4). 
Nhận xét: 
o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.8 lần so với tập dữ liệu ban đầu. 
0
20
40
60
80
100
120
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T
ỷ
 l
ệ
 đ
ú
n
g
Số lần thực hiện
Tập DL mới
Tập DL gốc
 51 
o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 75, tuy 
nhiên phương sai lại tăng (từ 4.21 lên 15.57) nên mô hình kiểm tra không 
ổn định bằng. 
o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 99.9, 
đồng thời phưưng sai cũng giảm (từ 1.19 còn 0.4) nên mô hình huấn luyện 
có tính ổn định hơn. 
5.4.2.3. So sánh kết quả 4 trường hợp kiểm thử 
 Điều kiện dừng là Generations sẽ được tăng dần trong mỗi trường hợp. 
Hình 5.11: So sánh kết quả phân lớp trung bình trong 4 trường hợp kiểm thử và 
kết quả phân lớp của dữ liệu gốc. 
Nhận xét: 
o Tỷ lệ phân lớp chính xác đối với bộ dữ liệu huấn luyện với tập thuộc tính 
mới không thay đổi nhiều khi ta tăng dần giá trị của Generations và tỷ lệ 
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra
Generations=30
Generations=40
Generations=50
Generations=60
Dữ liệu gốc
 52 
này lớn hơn so với tỷ lệ phân lớp chính xác cho bộ dữ liệu huấn luyện gốc 
(119 thuộc tính). 
o Khi ta tăng dần giá trị của Generations, thì tỷ lệ phân lớp chính xác đối với 
bộ dữ liệu test không có sự cải thiện rõ ràng, nhưng mô hình huấn luyện lại 
có tính ổn định hơn. 
5.4.2.4. Kết luận 
o Sử dụng hàm kernel Poly (kernel tuyến tính) trong thuật toán phân lớp 
MPM vẫn chưa thực sự hiệu quả với tập dữ liệu phi tuyến chúng ta sử dụng 
để đánh giá mô hình. 
o Số lượng các đặc trưng giữ lại sau khi giảm chiều không làm ảnh hưởng 
nhiều tới kết quả phân lớp thu được. 
o Khi tiến hành giảm chiều tập dữ liệu ban đầu (311x119), rồi sử dụng bộ 
phân lớp MPM thì rõ ràng tỷ lệ phân lớp chính xác đã tăng lên, đồng thời tỷ 
lệ chính xác phân lớp trong huấn luyện cũng được cải thiện. 
o Khi ta tăng số thế hệ trong thuật toán di truyền nhằm tìm ra chromosome tốt 
nhất ở thế hệ cuối cùng làm dữ liệu đầu vào cho bộ phân lớp, thì tỷ lệ phân 
lớp chính xác của MPM cũng tăng lên nhưng độ ổn định của kết quả không 
thực sự tốt hơn. Tuy nhiện tỷ lệ chính xác trong huấn luyện được cải thiện 
rõ ràng và ổn định hơn. 
 53 
Chương 6: Tổng kết 
Trong khóa luận này, bước đầu tôi đã tìm hiểu cơ sở lý thuyết và thuật toán cho việc 
giải bài toán trích chọn thuộc tính phù hợp dựa trên các kỹ thuật giảm chiều dữ liệu. Tôi 
đã trình bày ý tưởng kết hợp thuật toán di truyền (Genetic Algorithm) trong cải tiến hiệu 
quả phân lớp của thuật toán phân lớp minimax probability machine. Các kết quả thực 
nghiệm của phương pháp này đã cải thiện hiệu quả phân lớp so với thuật toán nguyên gốc, 
tuy nhiên ta cũng nhận thấy sự kết hợp này vẫn còn những điểm hạn chế như: 
 Chưa cải thiện rõ rệt tốc độ xử lý của bộ phân lớp kết hợp so với bộ phân lớp gốc. 
 Số lượng chiều của dữ liệu cần giảm là bao nhiêu để vừa giảm được thuộc tính dư 
thừa vừa cải thiện được hiệu quả phân lớp tốt nhất. 
 Trong quá trình giảm chiều không thể tránh khỏi những mất mát hay sai sót, do đó 
sự mất mát thông tin quan trọng dẫn đến hiệu quả của giảm chiều đối với phương 
pháp phân lớp là không ổn định. 
 Kết quả phân lớp chính xác vẫn chưa thực sự làm hài lòng. 
Để giải quyết những vấn đề còn tồn tại trong phương pháp này, tôi sẽ thử nghiệm kết 
hợp các hàm đánh giá (fitness function) khác nhau trong thuật toán di truyền, nhằm tìm ra 
kết quả đầu vào tốt hơn cho thuật toán phân lớp và cũng để cải thiện tốc độ tìm kiếm. 
Ngoài ra, tôi sẽ thử nghiệm phương pháp tối ưu hàm kernel của thuật toán MPM nhằm 
thu được kết quả phân lớp chính xác hơn (lớn hơn 95%) và ổn định hơn. 
Trong khóa luận này tôi hi vọng thử nghiệm giải quyết bài toán phân lớp với dữ liệu 
nhiều chiều và tạo ra các hệ thống đánh giá và dự đoán để có thể áp dụng một cách thiết 
thực vào đời sống. 
 54 
Tài liệu tham khảo 
 Tài liệu tham khảo tiếng Anh 
[1] Fayyad, Piatesky-Shapiro, Smyth (1996) - From Data Mining to Knowledge 
Discovery: An Overview. In Fayyad, Piatesky-Shapiro, Smyth, Uthurusamy - 
Advances in Knowledge Discovery and Data Mining, AAAI Press/ The MIT Press, 
MenloPark, CA, 1996, 1-34. 
[2] Jiawei Han and Micheline Kamber (2001) - Data Mining: Concepts and 
Techniques (second edition). Chapter 1. 
[3] Boris Kovalerchuk and Evgenii Vityaev (2001) - Data mining in Finance: 
Advances in Relational and Hybrid Methods, Kluwer Academic Publishers, Boston, 
Dordrecht – London, 2001. 
[4] David Taniar, Monash University, Australia - Research and Trends in Data 
Mining Techonologies and Application, 2007. 
[5] Ralf Herbrich, the MIT Press, Cambridge, Massachussets, London, England - 
Learning Kernel Classification and Algorithms. 
[6] H. Liu and L.Yu, Department of Computer Science and Engineering, Arizona State 
University, Tempe - Feature Selection for Data mining. 
[7] H. Liu and H.Motoda - Feature Extraction, Construction and Selection: A Data 
Mining Perspective. 
[8] P.A. Devijver and J.Kittler - Pattern Recoginition: A Statistical Approach. 
[9] Peter Norvig, Palo Alto, California (2006) - Feature Selection Book. 
[10] JUN ZHAO(a,b), GUO-YIN WANG(b), HONG TANG(a), HUA LI(a) - The study on 
technologies for feature selection. 
(a)
 Department of Computer Science of Chongqing University, Chongqing, 400065, 
China. 
(b)
 Inst. of Computer Sci. & Tech. Of Chongqing Univ. of P. & T., Chongqing, 400065, 
China. 
[11] Ricardo Gutierrez-Osuna, Wright State University - Intelligent Sensor Systems 
(Cross Validation). 
[12] M. Pei1, E. D. Goodman1, W. F. Punch2 - Feature Extraction Using Genetic 
Algorithms. 
 55 
1
 Case Center for Computer – Aided Engineering and Manufacturing. 
2
 Department of Computer Science, Genetic Algorithms Research and Application 
Group (GARAGe), Michigan State University, 2325 Engineering Building, East 
Lansing, MI 48824. 
[13] Genetic Algorithm and Direct Search Toolbox 2.1.4 – Help Document. 
[14] Laetitia Jourdan, Clarisse Dhaenens, El-Ghazali Talbi. LIFL, University of Lille, 
France - A Genetic Algorithm for Feature Selection in Data-Mining for Genetics. 
[15] Grefenstette, J. J. (1991) - Strategy acquisition with genetic algorithms, in 
Handbook of Genetic Algorithms, Davis, L. D. (Ed.), Boston: Van Nostrand 
Reinhold. 
[16] Gert R. G. Lanckriet, Lauren El Ghaoui, Chrianjib Bhattacharyya and Micheal I. 
Jordan. University of California - Minimax Probability Machine. 
[17] Kaizhu Huang, Haiqin Yang, Irwin King, Michael R. Lyu and Laiwan Chan - The 
Minimum Error Minimax Probability Machine. 
[18] Kaizhu Huang, Haiqin Yang, Irwin King, Michael R. Lyu and Laiwan Chan - 
Biased Minimax Probability Machine for Medical Diagnosis. 
[19] Zhen-Guo Chen and Shu Wang. Department of Computer Science and Technology, 
North China Institute of Science and Technology, East Yanjiao, Beijing, China - 
Minimax Probability Machine with Genetic Feature Optimized for Intrusion 
Detection. 
[20] Genetic Algorithm:  
 Tài liệu tham khảo tiếng Việt 
[21] Nguyễn Đức Cường, Khoa Công nghệ thông tin, Đại học Bách Khoa, Thành phố 
Hồ Chí Minh - Tổng quan về khai phá dữ liệu (Reviewing of Data Mining). 
[22] Vấn đề tri thức và “xã hội tri thức” 
thuc.html;jsessionid=7D49738B61116C5B527B009CC142141F?zone=2 
[23] Giáo sư Hà Quang Thụy, Đại học Công Nghệ, Đại học Quốc Gia Hà Nội - Giáo 
trình giảng dạy môn Khai phá dữ liệu Web (2008).