Nghiên cứu, xây dựng phương pháp trích chọn
thuộc tính nhằm làm tăng hiệu quả phân lớp
đối với dữ liệu đa chiều

Đồng Thị Ngọc Lan

Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Công nghệ phần mềm; Mã số: 60 48 10
Người hướng dẫn: PGS.TS Nguyễn Hà Nam
Năm bảo vệ: 2011

Abstract: Tổng quan về khai phá dữ liệu và trích chọn thuộc tính. Trình bày nội dung
chính của thuật toán phân lớp sử dụng trong luận văn là thuật toán Random Forest và
giải thuật di truyền. Trình bày phương pháp đề xuất và hướng giải quyết của luận văn.
Trình bày quá trình thực nghiệm và đánh giá kết quả thực nghiệm.

Keywords: Công nghệ thông tin; Thuật toán phân lớp; Cơ sở dữ liệu

Content
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ TRÍCH CHỌN THUỘC
TÍNH
1.1 Giới thiệu khai phá dữ liệu và trích chọn thuộc tính
Khai phá dữ liệu là một khái niệm ra đời từ những cuối những năm 80 của thế kỷ trước. Nó
bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có giá trị tiềm ẩn trong tập các dữ
liệu lớn.Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các
kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. Năm 1989, Fayyad,
Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu
(Kownledge Discovery in Database – KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có
ích từ các tập dữ liệu lớn[14]. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toàn bộ
quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu.
Trong khai phá dữ liệu thì phương pháp trích chọn thuộc tính đóng một vai trò quan

lượng các thuộc tính thường rất lớn nhưng các thuộc tính không liên quan hoặc thừa có thể có
những ảnh hưởng tiêu cực đối với các giải thuật phân lớp. Các thuộc tính/dữ liệu thừa hoặc
không liên quan có thể là nguyên nhân dẫn đến việc học của giải thuật không được chính xác.
Thêm vào đó, với sự có mặt của dữ liệu thừa hoặc dữ liệu không liên quan có thể làm cho bộ
phân lớp trở lên phức tạp hơn. Điều này sẽ gây ra những khó khăn không cần thiết cho chúng
ta trong việc diễn giải các kết quả học được từ tập huấn luyện. Do đó chúng ta cần giải quyết
vấn này đối với các bài toán phân lớp.
1.3 Phƣơng pháp lựa chọn thuộc tính
Có thể định nghĩa lựa chọn thuộc tính là một quá trình tìm ra một tập con các thuộc tính
từ M tập thuộc tính của tập dữ liệu N ban đầu, như vậy phải xác định tiêu chuẩn lựa chọn
thuộc tính. Một thuật toán lựa chọn gồm 4 bước cơ bản: Sinh tập con, lượng giá tập con, điều
kiện dừng và xác nhận kết quả.
Lựa chọn thuộc tính có thể dựa vào các mô hình, các chiến lược tìm kiếm, thước đo chất
lượng thuộc tính và ước lượng.Có ba loại mô hình như Filter, Wrapper, Embedded.
Các chiến lược tìm kiếm bao gồm: forward, backward, floating, branch and bound,
randomized. Ước lượng của việc chọn lựa thuộc tính bao gồm hai nhiệm vụ: một là so sánh

3
hai giai đoạn: trước và sau khi lựa chọn thuộc tính. Hai là so sánh hai thuật toán lựa chọn
thuộc tính [3].
Tóm lại lựa chọn thuộc tính được xem như là sự tổng hợp của ba thành phần chính: tìm
kiếm, đánh giá, chọn lựa mô hình.
1.4 Một số thuật toán lựa chọn thuộc tính
Các thuật toán lựa chọn thuộc tính được xét dưới góc độ chiến lược tìm kiếm nào được
sử dụng trong giải thuật đó: Tìm kiếm toàn bộ, Tìm kiếm theo kinh nghiệm và Tìm kiếm xác
suất. Ngoài ra chúng ta cũng nghiên cứu một vài phương pháp khác: phương pháp trọng số
thuộc tính (feature weighting method), phương pháp lai (hybrid method) và phương pháp lớn
dần (incremental method).
1.4.1 Tìm kiếm toàn bộ
a. Phương pháp Focus

Phương pháp này được xem như là một phương pháp tổng hợp kết quả có được từ các
bootstrap. Tư tưởng chính của phương pháp này như sau: Cho một tập huấn luyện D={(xi,
yi): i=1,2,…,n} và giả sử chúng ta muốn có một một dự đoán nào đó đối với biến x.
Một mẫu gồm B tập dữ liệu, mỗi tập dữ liệu gồm n phần tử được chọn lựa ngẫu nhiên từ D
với sự thay thế (giống như bootstrap). Do đó B=(D1, D2, ….,DB) trông giống như là một tập
các tập huấn luyện được nhân bản;
Tập huấn một máy hoặc một mô hình đối với mỗi tập Db (b=1, 2, …,B) và lần lượt thu thập
các kết quả dự báo có được trên mỗi tập Db;
Kết quả tổng hợp cuối cùng được tính toán bằng cách trung bình hóa (regression) hoặc thông
qua số phiếu bầu nhiều nhất (classification).
2.3 Random forest
Tóm tắt cuả giải thuật RF cho phân lớp đƣợc diễn giải nhƣ sau:
• Lấy ra K mẫu bootstrap từ tập huấn luyện.
• Đối với mỗi mẫu bootstrap xây dựng một cây phân lớp không đƣợc tỉa
(unpruned tree) theo hƣớng dẫn sau: Tại mỗi nút thay vì chọn một phân chia
tốt nhất trong tất cả các biến dự đoán, ta chọn ngẫu nhiên một mẫu m của
các biến dự đoán sau đó chọn một phân chia tốt nhất trong các biến này.
• Đƣa ra các dự đoán bằng cách tổng hợp các dự đoán của K cây.
Quá trình học của Random Forest bao gồm việc sử dụng ngẫu nhiên giá trịđầu vào,
hoặc kết hợp các giá trị đó tại mỗi node trong quá trình dựng từng câyquyết định. Kết quả của
Random Forest, qua thực nghiệm cho thấy, là tốt hơn khiso sánh với thuật toán Adaboost.
Trong đó Random Forest có một số thuộc tính mạnh như:
(1) Độ chính xác của nó tương tự Adaboost, trong một số trường hợp còn tốt hơn.
(2) Thuật toán giải quyết tốt các bài toán có nhiều dữ liệu nhiễu.
(3) Thuật toán chạy nhanh hơn so với bagging hoặc boosting.
(4) Có những sự ước lượng nội tại như độ chính xác của mô hình phỏngđoán hoặc độ
mạnh và liên quan giữa các thuộc tính.
(5) Dễ dàng thực hiện song song.
(6) Tuy nhiên để đạt được các tính chất mạnh trên, thời gian thực thi củathuật toán khá
lâu và phải sử dụng nhiều tài nguyên của hệ thống.

nhanh chóng và ứng dụng trong nhiều lĩnh vực khác nhau như tối ưu hàm, xử lý ảnh, bài toán
hành trình người bán hàng, nhận dạng hệ thống và điều khiển. Thuật toán di truyền cũng như
các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa
tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này
có thể xem như một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách
quan. Quá trình tiến hóa thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển
hơn, hoàn thiện hơn) thế hệ trước bởi tính kế thừa và đấu tranh sinh tồn [2].
CHƢƠNG 3: PHƢƠNG PHÁP ĐỀ XUẤT
3.1 Giới thiệu
Chương này luận văn trình bày phương pháp học máy nhằm tìm ra bộ thuộc tính tối
ưu từ tập các thuộc tính của bộ số liệu cho trước, đó là sử dụng giải thuật tựa giải thuật di
truyền (Genetic-Algorithm) kết hợp với thuật toán rừng ngẫu nhiên (Random Forest).
Chương này mô tả phương pháp đề xuất như là cách tiếp cận theo wrapper để tìm ra các thuộc
tính tối ưu, loại bỏ các thuộc tính dư thừa.

6
3.2 Cơ sở lí luận
Ta thấy các toán tử trong giải thuật di truyền đều mang tính ngẫu nhiên, thuật toán di
truyền cần xác định cỡ quần thểvà khởi tạo quần thể ban đầu một cách ngẫu nhiên, xác định
xác suất lai ghép và xác suất đột biến . Xác suất đột biến cần là xác suất thấp. Để khắc phục
việc hạn chế của vấn đề chọn ngẫu nhiên, luận văn đề xuất phương án:
- Tạo ra các bộ thuộc tính con từ tập thuộc tính ban đầu bằng phương pháp kết hợp việc
chọn ngẫu nhiên với việc phân bố đều các thuộc tính.
- Không thực hiện việc lai ghép, đột biến để tạo ra các bộ thuộc tính mới mà thực hiện việc
đánh giá các bộ thuộc tính, dựa vào đó đánh giá các thuộc tính để chọn ra các thuộc tính
có độ phù hợp cao.
- Dùng thuật toán học để làm tiêu chí đánh giá độ thích hợp của các bộ thuộc tính.
Cụ thể, phương pháp đề xuất được trình bày chi tiết ở phần tiếp theo.
3.3 Kiến trúc hệ thống


Bước 1: phương pháp đề nghị sẽ sinh ra các bảng con có kích cỡ m x k
i
; trong đó k
i
là số cột
(số thuộc tính) của bảng con thứ i (i=1,2…) và k
i
< n. Mỗi bảng là một tập con các thuộc tính
của bộ dữ liệu ban đầu.
Bước 2: Đánh giá độ thích nghi của mỗi bộ thuộc tính mới bằng việc áp dụng thuật toán học
máy random forest .
Bước 3: Sau đó, với mỗi thuộc tính của bộ thuộc tính ban đầu ta tính được độ phù hợp (trọng
số)w của mỗi thuộc tính theo công thức:

Với j=1, ,n tương ứng với n thuộc tính đầu tiên. Fitness
i
là độ phù hợp của bộ thuộc
tính thứ i trong m bộ thuộc tính mới. k nhận giá trị 1 nếu thuộc tính thứ j được chọn và nhận
giá trị 0 nếu thuộc tính j không được chọn trong bộ thuộc tính i.
Bước 4: Thực hiện sắp xếp n thuộc tính theo thứ tự giảm dần của trọng số w
j
. Lấy p% các
thuộc tính được theo thứ tự từ trên xuống dưới ta được một bộ thuộc tính mới gồm (n*p)/100
thuộc tính.
Bộ thuộc tính này lại lặp lại các bước trên cho đến khi thu được một bộ thuộc tính có
số thuộc tính đạt ngưỡng nào đó hoăc số lần lặp xác định. Kết thúc quá trình hoạt động ở Phần
1: thu được bộ thuộc tính có độ phù hợp cao nhất. Kết quả này được sử dụng để đưa vào Phần
2.
b. Hoạt động phần 2
Lấy tất cả bản ghi của bộ số liệu ban đầu nhưng chỉ với các thuộc tính vừa tìm được ở

gồm thời gian huấn luyện và
thời gian kiểm thử.
- Tính % đoán nhận(phân lớp)
đúng của RF với tham số tùy
chọn TreeNum là số lượng cây
của RF.
fitness<-function
(inpData,CrV,in
d)
Tính độ phù hợp của bộ dữ liệu
inpData với hệ số kiểm chứng
chéo là CrV.
proccess<-
function
(InpData,m,p)
- Hàm proccess có chức năng
lựa chọn ra tập các thuộc tính
tối ưu nhất từ tập dữ liệu đầu
vào InpData.
- m là tham số xác định số bộ
thuộc tính trong mỗi lần phân
chia.
- p xác định số thuộc tính loại bỏ
sau mỗi lần chọn lựa. (đây là
điều kiện dừng của thuật toán)
RF_Proccess<-
function
(train,test,TreeN
um,RunNum)
- Tính % đoàn nhận đúng, thời

5%, trung bình thuật toán RF cho kết quả đoán nhận là 78%, còn RF mới cho kết quả là 83%.
Ta cũng thấy thời gian huấn luyện và thời gian kiểm tra đều giảm đi đáng kể. Tỉ lệ đoán nhận
trên bộ thuộc tính mới tăng lên cho thấy bộ thuộc tính mới đã loại bỏ được một số thuộc tính
nhiễu, thuộc tính dư thừa. Còn thời gian giảm đi là vì số lượng thuộc tính đã giảm xuống
tương đối nhiều, cụ thể từ 119 thuộc tính ban đầu, sau khi lựa chọn bộ thuộc tính mới còn là
36 thuộc tính, như vậy số thuộc tính đã giảm khoảng 69% số thuộc tính ban đầu. Điều đó
chứng tỏ phương pháp thực nghiệm mà luận văn đề xuất cho hiệu quả tương đối tốt. Tuy
nhiên, để tìm ra một bộ thuộc tính mới chúng ta đã tiêu tốn một khoảng thời gian tương đối
lớn. Với bộ dữ liệu Stomach chúng ta mất khoảng 20 phút để tìm ra được một bộ thuộc tính
tối ưu hơn, và với các bộ dữ liệu lớn hơn thì thời gian đó lại tăng lên, nhưng chúng ta chỉ mất
thời gian 1 lần tìm bộ thuộc tính tối ưu. Sau đó, tất cả các bài toán sử dụng bộ dữ liệu này khi
thực thi trên bộ thuộc tính mới sẽ giảm thời gian tính toán trên tất cả các lần chạy. Và từ đó,
thì thời gian làm việc sẽ giảm đi đáng kể.
4.3.2 Bộ dữ liệu ung thƣ ruột kết Colon Turmo
4.3.2.1 Mô tả dữ liệu
Colon Turmo[1] là bộ dữ liệu gồm 2000 genes được chọn lựa từ 6500 genes, thu thập
từ 62 bệnh nhân ung thư (2000 x 62)
4.3.2.2 Kết quả thực nghiệm

Hình 4.13 Kết quả chạy RF 20 lần trên bộ thuộc tính Colon Tumor ban đầu và sau khi tối ưu
với số cây lần lượt là 100,300,500

Hình 4.14 Biểu đồ so sánh thời gian huấn luyện trung bình của 20 lần chạy RF trên bộ dữ
liệu Colon Tumor mới và bộ dữ liệu Colon Tumor ban đầu với số cây bằng 100,300,500.

11

Hình 4.15 Biểu đồ so sánh thời gian kiểm tra trung bình của 20 lần chạy RF trên bộ dữ liệu
Colon Tumor mới và bộ dữ liệu Colon Tumor ban đầu với số cây bằng 100,300,500.
4.3.2.2 Nhận xét

Tài liệu Tiếng Việt
[1] Nguyễn Hà Nam (2009), "Tối ưu hóa KPCA bằng GA để chọn các thuộc tính đặc trưng
nhằm tăng hiệu quả phân lớp của thuật toán Random Forest", Tạp chí Khoa học ĐHQGHN,
Khoa học Tự nhiên và Công nghệ, số 25, tr. 84-93.
[2] Nguyễn Đình Thúc (2001), Lập trình tiến hóa, Nhà xuất bản giáo dục, Hà Nội.
[3] Huỳnh Phụng Toàn, Nguyễn Hữu Lâm, Nguyễn Minh Trung, Đỗ Thanh Nghị (2012),
“Rừng ngẫu nhiên cải tiến cho phân loại dữ liệu gien”, Tạp chí khoa học Đại học Cần Thơ
2012:22b 9-17, Cần Thơ.
[4] Nguyễn Văn Tuấn (2007), Phân tích số liệu và tạo biểu đồ bằng R-Hướng dẫn thực hành,
NXB KHKT, Hà Nội.
Tài liệu Tiếng Anh
[5] Blum, A. L. and Langley (1997), Selection of Relevant Features and Examples in
Machine Learning, Artificial Intelligence, pp. 245-271.
[6] L. Breiman (2002), Manual On Setting Up, Using, And Understanding Random Forests
V3.1, Available:

[7] L. Breiman (2001), "Random Forests", Machine Learning Journal Paper, vol. 45.
[8] A. C. Leo Breiman, Random Forests, Available:

[9] R. O. Duda, P. E. Hart, D. G. Stork (2001), Pattern Classification (2nd Edition), John
Wiley & Sons Inc.
[10] E. F. Ian H.Witten (2005), Data Mining: Practical Machine Learning Tools and
Techniques, Second Edition ed.: Morgan KauFmann Publishers.
[11 ] Isabelle Guyon (2006), Feature Selection, pp. 12-30.
[12] M. K. Jiawei Han (2006), Data Mining:Concepts and Techniques, Second Edition ed.
Diane Cerra.
[13] Jacek Jarmulak and Susan Craw (1999), Genetic Algorithms for Feature Selection and
Weighting, IJCAI 99 workshop.
[14] Krzysztof J.Cios, Witold Deddrycz, Roman W.Swiniarski, Lukasz A.Kurgan (2007),
Data Mining A Knowledge Discovery Approach, Springer.

[31] Dataset Available (2003):
[32] Genetic Algorithm: