ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

HOÀNG VĂN TRÌU

TÌM HIỂU PHƢƠNG PHÁP TÌM THUỘC TÍNH TỐI ƢU
NHẰM TĂNG HIỆU QUẢ PHÂN TÍCH TRONG PHÂN
TÍCH DỮ LIỆU LỚN

LUẬN VĂN THẠC SỸ - NGÀNH CÔNG NGHỆ THÔNG TIN

HÀ NỘI - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

HOÀNG VĂN TRÌU

TÌM HIỂU PHƢƠNG PHÁP TÌM THUỘC TÍNH TỐI
ƢU NHẰM TĂNG HIỆU QUẢ PHÂN TÍCH TRONG PHÂN
TÍCH DỮ LIỆU LỚN
Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã Số: 60480103

LUẬN VĂN THẠC SỸ - NGÀNH CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN HÀ NAM

HÀ NỘI - 2015

3.2.3 Mô tả chương trình ..................................................... Error! Bookmark not defined.
3.3. Kết quả thực nghiệm..................................................... Error! Bookmark not defined.
3.3.1. Dữ liệu sử dụng ........................................................ Error! Bookmark not defined.
3.3.2. Kết quả chạy trên bộ dữ liệu Arcene ......................... Error! Bookmark not defined.
3.3.3. Kết quả chạy trên bộ dữ liệu DLBCL (Diffuse large B-cell lymphoma) .......... Error!
Bookmark not defined.
3.4. Kết luận ........................................................................ Error! Bookmark not defined.


1

Kết

luận....................................................................................................Error!
Bookmark not defined.

Tài liệu tham khảo ................................................................................................. 8

Giới thiệu
Khoa học kỹ thuật phát triển, đi cùng với nó là sự phát triển không ngừng
của dữ liệu về kích thước và chủng loại. Nhiệm vụ khai phá dữ liệu nói chung
cũng như nghiên cứu các thuật toán phân lớp nói riêng trở nên ngày càng bức
thiết và đóng vai trò trung tâm trong việc giải quyết các bài toán cụ thể. Thực tế
cho thấy, chúng ta chỉ có thể tìm ra một số thuật toán phù hợp với một số loại dữ
liệu cụ thể và bị giới hạn về kích thước dữ liệu. Kết quả của thuật toán phụ thuộc
rất nhiều vào việc xử lý dữ liệu thô. Trong khai phá dữ liệu, phương pháp trích
chọn đóng vai trò quan trọng trong tiền xử lý số liệu, đặc biệt đối với ngành tin
sinh học, xử lý dữ liệu âm thanh, hình ảnh, dữ liệu mạng xã hội... Đặc điểm
chung của những lĩnh vực này là kích thước rất lớn (hàng trăm, hàng trăm nghìn
thuộc tính) nhưng chỉ một số ít thuộc tính có giá trị dùng để phân tích. Trích

Trong luận văn này tôi đưa ra một cách tiếp cận mới, kết hợp thuật toán
GA và Kernel k-NN theo mô hình Wrapper. GA giúp tìm ra các tập thuộc tính
và Kernel k-NN trả về kết quả của hàm mục tiêu trong GA. Hay nói một cách
khác, GA đã chọn một tập thuộc tính được coi là tốt nhất trong quần thể các
thuộc tính, tập thuộc tính tốt được hiểu trong ngữ cảnh hiện tại là các thuộc tính
được trích chọn giúp phân lớp tốt nhất dựa trên kết quả của hàm tính khoảng
cách trong thuật toán Kernel k-NN. GA đã giúp tăng độ chính xác phân lớp nhờ
việc tối ưu dữ liệu đầu vào cho thuật toán Kernel k-NN.
Nội dung của luận văn được chia thành các chương như sau:
Chƣơng 1: Giới thiệu Khai phá dữ liệu
Chƣơng 2: Cơ sở lý thuyết.
Chƣơng 3: Mô hình GA_Kernel k-NN và kết quả thực nghiệm.
Kết luận: Tóm lược kết quả đạt được của luận văn.


3

Chƣơng 1. Giới thiệu Khai phá dữ liệu
1.1. Tổng quan Khai phá dữ liệu
Khai phá dữ liệu là một khái niệm ra đời 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 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 (Knowledge
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 [11]. 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.
Ở một góc độ nào đó, khái niệm khai phá dữ liệu và khai phá tri thức

chuyển dạng

Làm sạch và
tích hợp

Kho dữ
liệu

Mẫu
Dữ liệu
chuyển
dạng

Dữ liệu
Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu
Một số phương pháp khai phá dữ liệu tiêu biểu:
 Phân lớp (Classification) : Khai thác một hàm đã được huấn luyện
trước để phân loại một đối tượng dữ liệu vào một trong các lớp được
định nghĩa trước.
 Hồi qui (Regression) : Khai thác một hàm đã được huấn luyện trước
để ánh xạ một đối tượng dữ liệu thành một giá trị thực là kết quả dự
báo.
 Phân cụm (Clustering) : Giải quyết vấn đề tìm kiếm, phát hiện số
lượng hữu hạn các cụm mô tả một tập hợp dữ liệu ban đầu không có
nhãn. Đó là quá trình tìm cách nhóm các đối tượng đã cho vào các
cụm, sao cho các đối tượng trong cùng một cụm tương tự nhau
(similar), và các đối tượng khác cụm thì không tương tự nhau
(dissimilar).



phương pháp trích chọn theo hai cách tiếp cận khác nhau là Filter và Wrapper
được trình bày trong các tài liệu [3, 13]. Lược đồ thực hiện [2] được giản hóa
trong hai hình vẽ dưới đây.


6

Dữ liệu

Thuật toán
phân lớp

Trích lọc tập con của danh
sách các thuộc tính

Hình 1.2 : Hướng tiếp cận Filter
Theo mô hình Filter, các thuộc tính được chọn độc lập với thuật toán khai phá
dữ liệu. Ngược lại, mô hình Wrapper các thuộc tính được chọn phụ thuộc theo
một nghĩa nào đó với thuật toán khai phá dữ liệu

Dữ liệu
huấn
luyện

Tìm kiếm thuộc tính
Tập thuộc tính
lựa chọn

Đánh giá kết quả


nào đó, rồi chọn ra tập con các thuộc tính được đánh giá cao nhất. Nhìn
chung, Filter coi tiến trình của trích chọn thuộc tính như tiến trình thực thi
trước, sau đó mới sử dụng thuật toán để phân lớp.
Mô hình Wrapper sử dụng một thuật toán tìm kiếm để đánh giá tập con các
thuộc tính coi như là một nhóm hơn là một cá thể riêng lẻ. Cốt lõi của mô hình
Wrapper là một thuật toán máy học cụ thể. Nó đánh giá độ tốt của những tập
con đặc trưng tùy theo độ chính xác học của tập con, điều này xác định thông
qua một tiêu chí nào đó. Những thuật toán tìm kiếm cũng sử dụng hàm đánh
giá kinh nghiệm (heuristics) để hướng dẫn việc tìm kiếm tập trung vào các
đối tượng có triển vọng.
Công việc cần thực hiện trong thuật toán trích chọn bao gồm :


7

- Phương pháp để sinh ra tập thuộc tính đặc trưng : (Có thể hiểu tương ứng
với các chiến lược tìm kiếm). Đầu ra của bộ sinh sẽ xác định thuật toán trích
chọn đặc trưng. Có hai chiến lược để sinh tập con :
 Đầy đủ (Complete) : Áp dụng chiến lược tìm kiếm vét cạn để sinh
tập con. Đối với hầu hết các hệ thông máy thực, chiến lược này
không phù hợp do đỏi hỏi tài nguyên quá lớn
 Kinh nghiệm (Heuristically) : Để giảm bớt không gian tìm kiếm, kết
quả thu được ở mức chấp nhận được, chiến lược sinh tập con đặc
trưng dựa vào kinh nghiệm nào đó, có ba kỹ thuật điển hình là lựa
chọn tiến (Forward Selection), lược bỏ lùi (Backward Elimination)
và lựa chọn hai hướng (Bi – direction Selection).
- Định nghĩa hàm đánh giá : (đưa ra các tiêu chí để có thế xác định một thuộc
tính hay nhóm thuộc tính là tốt hay không tốt). Bộ đánh giá của những mô hình
thuật toán khác nhau là khác nhau. Bộ đánh giá mô hình Filter thường là các
hàm đánh giá, trong khi mô hình Wrapper là độ học chính xác đạt được bởi quá

 Tiếng Anh
[3] A.L. Blum, P. Langley, “Selection of Relevant Features and Examples in
Machine Learning”, Artificial Intelligence Vol 97 (1997) 245.
[4] Alexander Statnikov, Constantin F. Aliferis, Ioannis Tsamardinos, Douglas
Hardin, Shawn Levy, “A comprehensive evaluation of multicategory
classification methods for microarray gene expression cancer diagnosis,
Bioinformatics”, 21(5), 2005, 631-643
[5] Binh Tran, Bing Xue, and Mengjie Zhang, “Improved PSO for Feature
Selection on High-Dimensional Datasets”, page 503, Simulated Evolution
and Learning 10th International Conference, SEAL 2014
[6] Dong-Sheng Cao, Jian-Hua Huang, Jun Yan, Liang-Xiao Zhang, Qian-Nan
Hu, Qing-Song Xu, Yi-Zeng Liang (2012), “Kernel k-nearest neighbor
algorithm as a flexible SAR modeling tool”, Chemometrics and Intelligent
Laboratory Systems 114 (2012) 19–23
[7] Hechenbichler Klaus, Schliep Klaus (2004), “Weighted k-Nearest-Neighbor
Techniques and Ordinal Classification”, Discussion Paper 399, SFB 386,
Ludwig-Maximilians University Munich.
[8] Huazhen Wang, Cheng Wang∗ , Bing Lv, Xiaoming Pan (2015), “Improved
Variable Importance Measure of Random Forest via Combining of Proximity
Measure and Support Vector Machine for Stable Feature Selection” Journal
of Information & Computational Science 12:8 (2015) 3241–3252


9

[9] Ivica Kopriva, “A Nonlinear Mixture Model based Unsupervised Variable
Selection in Genomics and Proteomics”, BIOINFORMATICS 2015 –
International Conference on Bioinformatics Models, Method and
Algorithms
[10] Leif E.Peterson (2009), “K-Nearest Neighbor”, Scholarpedia, 4 (2).