ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
-----------------------------
TRỊNH VĂN HÀ

LỰA CHỌN THUỘC TÍNH TRONG
KHAI PHÁ DỮ LIỆU

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

KHAI PHÁ DỮ LIỆU Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số : 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hướng dẫn khoa học: TS NGUYỄN THANH TÙNG
THÁI NGUYÊN 2008

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
MỤC LỤC
Trang phụ bìa ......................................................................................................1
Mục lục ...............................................................................................................2
Lời mở đầu .........................................................................................................4

3.3.2 Thuật toán NEURALNET ..........................................................43
3.3. Một số thuật toán khác ..........................................................................44
3.3.1. Thuật toán Genetic .....................................................................44
3.3.2. Lựa chọn thuộc tính thông qua rời rạc hóa dữ liệu ......................46
3.4. Kết luận chương 3 .................................................................................53
KẾT LUẬN .....................................................................................................54
Tài liệu tham khảo ..........................................................................................56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
LỜI MỞ ĐẦU
Như đã biết, trong những năm gần đây công nghệ thông tin phát triển vô
cùng nhanh chóng và được ứng dụng rộng rãi trong mọi lĩnh vực đời sống xã
hội, nhất là trong quản lý, một lĩnh vực mà yếu tố khoa học công nghệ có tính
quyết định. Sự việc đó dẫn đến sự bùng nổ thông tin, làm cho những nhà quản lý
rơi vào tình trạng “ngập lụt thông tin". Chính vì vậy, các chuyên gia cho rằng,
hiện nay chúng ta đang sống trong một xã hội “rất giàu về thông tin nhưng
nghèo về tri thức”. Tình hình đó đòi hỏi phải phát triển các phương pháp khai
phá, phát hiện ra những thông tin, tri thức có ích bị che giấu trong các “núi” dữ
liệu phục vụ cho công việc của các nhà quản lý, các chuyên gia, từ đó thúc đẩy
khả năng sản xuất, kinh doanh, cạnh tranh của các tổ chức, doanh nghiệp.
Khai phá dữ liệu (Data Mining) là một lĩnh vực khoa học liên ngành mới
xuất hiện gần đây nhằm đáp ứng nhu cầu này. Các kết quả nghiên cứu cùng với
những ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy
khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích,
đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống.
Hiện nay, các CSDL cần khai phá thường có kích thước rất lớn, chẳng hạn
các CSDL tin-sinh-học (Bioinformatics), CSDL đa phương tiện, CSDL giao tác,
… . Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó

Trịnh Văn Hà Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
CHƢƠNG 1
KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU
1.1. Tại sao phải khai phá dữ liệu.
Ước tính cứ khoảng 20 tháng lượng thông tin trên thế giới lại tăng gấp đôi.
Chính vì vậy, hiện nay lượng dữ liệu mà con người thu thập và lưu trữ được
trong các kho dữ liệu là rất lớn, nhiều khi vượt quá khả năng quản lý. Thời gian
này, người ta bắt đầu đề cập đến khái niệm khủng hoảng phân tích dữ liệu tác
nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho những
người ra quyết định trong các tổ chức tài chính, thương mại, khoa học, ... . Đúng
như John Naisbett đã cảnh báo “Chúng ta đang chìm ngập trong dữ liệu mà vẫn
đói tri thức”.
Với một khối lượng dữ liệu tăng nhanh và khổng lồ như vậy, rõ ràng các
phương pháp thủ công truyền thống áp dụng để phân tích dữ liệu sẽ không hiệu
quả, tốn kém và dễ dẫn đến những sai lệch. Do đó để có thể khai phá hiệu quả
các cơ sở dữ liệu lớn cần phải có những kỹ thuật mới, các kỹ thuật khai phá dữ
liệu (Data Mining).
Khai phá dữ liệu là một lĩnh vực khoa học mới xuất hiện, nhằm tự động
hóa khai thác những thông tin, tri thức hữu ích, tiềm ẩn trong các CSDL cho các
tổ chức, doanh nghiệp, ... từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh
tranh của tổ chức, doanh nghiệp này. Các kết quả nghiên cứu cùng với những
ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai
phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng
thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện
nay, khai phá dữ liệu được ứng dụng rộng rãi trong các lĩnh vực như: Phân tích
dữ liệu hỗ trợ ra quyết định, điều trị y học, tin-sinh học, thương mại, tài chính,


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
Biến đổi dữ liệu: Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu
về dạng thuận lợi nhất nhằm phục vụ việc áp dụng các kỹ thuật khai
phá ở bước sau.
Khai phá dữ liệu: Là bước áp dụng những kỹ thuật phân tích (phần
nhiều là các kỹ thuật học máy) nhằm khai thác dữ liệu, trích lọc những
mẫu tin (information patterns), những mối quan hệ đặc biệt trong dữ
liệu. Đây được xem là bước quan trọng và tiêu tốn thời gian nhất của
toàn bộ quá trình KDD.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối quan hệ
trong dữ liệu đã được phát hiện ở bước khai phá dữ liệu được chuyển
sang và biểu diễn ở dạng gần gũi với người sử dụng như đồ thị, cây,
bảng biểu, luật, ... . Đồng thời bước này cũng đánh giá những tri thức
khai phá được theo những tiêu chí nhất định.
Hình 1.1 dưới đây mô tả các công đoạn của khai phá dữ liệu:
Hình 1.1. Các bƣớc thực hiện quá trình khai phá dữ liệu
Nếu theo quan điểm của học máy (Machine Learning), thì các kỹ thuật khai
phá dữ liệu bao gồm:
 Học có giám sát (Supervised Learning) : Là quá trình phân lớp các

phát triển và độ lệch (Evolution and deviation analysis), phân tích luật kết hợp
(association rules analysis)… .
Kỹ thuật dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn
trên dữ liệu hiện thời. Các kỹ thuật này gồm: Phân lớp (classification), hồi quy
(regression), … .
Với hai đích chính của khai phá dữ liệu là Dự đoán (Prediction) và Mô tả
(Description), người ta thường sử dụng các kỹ thuật sau cho khai phá dữ liệu:
 Phân lớp và dự đoán (classification and prediction) : Là việc xếp các
đối tượng vào những lớp đã biết trước. Ví dụ, phân lớp các bệnh
nhân, phân lớp các loài thực vật, ... . Hướng tiếp cận này thường sử
dụng một số kỹ thuật của học máy như cây quyết định (decision tree),
mạng nơ-ron nhân tạo (neural network), ... . Phân lớp và dự đoán còn
được gọi là học có giám sát.
 Phân cụm (clustering/segmentation) : Là việc xếp các đối tượng theo
từng cụm tự nhiên.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
 Luật kết hợp (association rules) : Là việc phát hiện các luật biểu diễn
tri thức dưới dạng khá đơn giản. Ví dụ: “70% nữ giới vào siêu thị
mua phấn thì có tới 80% trong số họ cũng mua thêm son”.
 Phân tích hồi quy (regression analysis) : Là việc học một hàm ánh xạ
từ một tập dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ
của phân tích hồi quy tương tự như của phân lớp, điểm khác nhau là ở
chỗ thuộc tính dự báo là liên tục chứ không phải rời rạc.
 Phân tích các mẫu theo thời gian (sequential/temporal patterns) :
Tương tự như khai phá luật kết hợp nhưng có quan tâm đến tính thứ
tự theo thời gian.
 Mô tả khái niệm (concept description and summarization) : Thiên về
mô tả, tổng hợp và tóm tắt các khái niệm. Ví dụ tóm tắt văn bản.

liệu trong CSDL, và chúng thường chỉ bao hàm được các trường hợp quan
trọng. Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các
mẫu phát hiện được.
Phương pháp thống kê là một trong những nền tảng lý thuyết của khai phá
dữ liệu, nhưng khi so sánh hai phương pháp với nhau ta có thể thấy các
phương pháp thống kê cũng tồn tại một số điểm yếu mà khai phá dữ liệu
khắc phục được:
Với nhưng ưu điểm đó, khai phá dữ liệu hiện đang được áp dụng một
cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau như:
marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet…
rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ
liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích
to lớn. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng
tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle tích hợp các

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đã đi tiên phong trong việc phát
triển các ứng dụng khai phá dữ liệu với các ứng dụng như Intelligence Miner…
Các ứng dụng này được chia thành 3 nhóm ứng dụng khác nhau : Phát hiện
gian lận (fraud detection), các ứng dụng hỗ trợ tiếp thị và quản lý khách hàng,
cuối cùng là các ứng dụng về phát hiện và xử lý lỗi hệ thống mạng.
Phát hiện gian lận ( fraud detection ):
Gian lận là một trong những vấn đề nghiêm trọng của các công ty viễn
thông, nó có thể làm thất thoát hàng tỷ đồng mỗi năm. Có thể chia ra làm 2 hình
thức gian lận khác nhau thường xảy ra đối với các công ty viễn thông : Trường
hợp thứ nhất xảy ra khi một khách hàng đăng ký thuê bao với ý định không bao
giờ thanh toán khoản chi phí sử dụng dịch vụ. Trường hợp thứ hai liên quan đến
một thuê bao hợp lệ nhưng lại có một số hoạt động bất hợp pháp gây ra bởi một
người khác. Những ứng dụng này sẽ thực hiện theo thời gian thực bằng cách sử

Một vấn đề khá phổ biến ở các công ty viễn thông hiện là sự thay đổi nhà
cung cấp dịch vụ (customer churn) đặc biệt với các công ty điện thoại di động.
Đây là vấn đề khá nghiêm trọng ảnh hưởng đến tốc độ phát triển thuê bao, cũng
như doanh thu của các nhà cung cấp dịch vụ. Thời gian gần đây các nhà cung
cấp dịch vụ di động luôn có chính sách khuyến mãi lớn để lôi kéo khách hàng.
Điều đó dẫn đến một lượng không nhỏ khách hàng thường xuyên thay đổi nhà
cung cấp để hưởng những chính sách khuyến mãi đó. Kỹ thuật data mining hiện
nay có thể dựa trên dữ liệu tiền sử để tìm ra các quy luật, từ đó có thể tiên đoán
trước được khách hàng nào có ý định rời khỏi mạng trước khi họ thực hiện. Dựa
trên các kỹ thuật data mining như cây quyết định (decision tree), mạng nơ ron
nhân tạo (neural nerwork) trên dữ liệu cước (billing data), dữ liệu chi tiết cuộc
gọi (call detail data), dữ liệu khách hàng (customer data) tìm ra các quy luật mà
dựa trên đó ta có thể tiên đoán trước ý định rời khỏi mạng của khách hàng, từ đó
công ty viễn thông sẽ có các ứng xử phù hợp nhằm lôi kéo khách hàng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
Cuối cùng, một ứng dụng cũng rất phổ biến đó là phân lớp khách hàng
(classifying). Dựa vào kỹ thuật data mining học trên cây quyết định (decision
tree) trên dữ liệu khách hàng và chi tiết cuộc gọi có thể tìm ra các luật để phân
loại khách hàng. Ví dụ ta có thể phân biệt được khách hàng nào thuộc đối tượng
kinh doanh hay nhà riêng dựa vào các luật sau :
Luật 1 : nếu không quá 43% cuộc gọi có thời gian từ 0 đến 10 giây và không
đến 13% cuộc gọi vào cuối tuần thì đó là khách hàng kinh doanh.
Luật 2 : Nếu trong 2 tháng có các cuộc gọi đến hầu hết từ 3 mã vùng giống
nhau và <56,6% cuộc gọi từ 0-10 giây thì có là khách hàng nhà riêng.
Trên cơ sở tìm ra được các luật tương tự vậy, ta dể dàng phân loại khách hàng,
để từ đó có chính sách phân khúc thị trường hợp lý.
Các ứng dụng phát hiện và cô lập lỗi trên hệ thống mạng viễn thông
(Network fault isolation )

Lựa chọn thuộc tính là một nhiệm vụ quan trọng trong bước tiền xử lý
của quá trình khai phá dữ liệu. Mục đích của nó là làm giảm bớt kích thước dữ
liệu, giúp cho việc khai phá hiệu quả hơn, các kết quả thu được chính xác hơn.
Chương 2 sau đây sẽ trình bày về vấn đề này.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
CHƢƠNG 2
KHÁI QUÁT VỀ LỰA CHỌN THUỘC TÍNH
TRONG KHAI PHÁ DỮ LIỆU
2.1. Rút gọn thuộc tính
Hiện nay, các CSDL cần khai phá thường có kích thước rất lớn, chẳng hạn
các CSDL tin-sinh-học (Bioinformatics), CSDL đa phương tiện, CSDL giao tác,
… . Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó
khăn cho việc khai phá, thậm chí còn làm cho nhiệm vụ khai phá trở nên bất khả
thi. Vấn đề đặt ra là phải tìm cách rút gọn số thuộc tính mà không làm những
thông tin cần thiết phục vụ nhiệm vụ khai phá.
Chính vì thế, từ năm 1970 đến nay, rút gọn thuộc tính (hay còn gọi là rút
gọn thứ nguyên – Dimension reduction) đã trở thành đề tài được quan tâm bởi
nhiều nhà nghiên cứu thuộc các lĩnh vực nhận dạng thống kê, học máy, khai phá
dữ liệu.
Mục đích của rút gọn thuộc tính là làm giảm số chiều của không gian thuộc
tính, loại bỏ dữ liệu dư thừa, không liên quan. Rút gọn thuộc tính đóng vai trò
quan trọng trong bước tiền xử lý dữ liệu cũng như trong quá trình khai phá. Kết
quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ
khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu
được.
Các kỹ thuật rút gọn thuộc tính có thể được phân thành hai loại: Lựa chọn
thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation).
Lựa chọn thuộc tính là chọn một tập con tối tiểu tốt nhất (theo một nghĩa

Kích thước lớn
Dữ liệu kích
thước nhỏ hơn
Hệ thống
Xử lý
Khó Xử lý
Hình 2.1: Vấn đề giảm kích thước

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18
2.2. Khái quát về lựa chọn thuộc tính
2.2.1. Bài toán lựa chọn thuộc tính
Lựa chọn thuộc tính là qúa trình lựa chọn một tập con gồm P thuộc tính từ
tập gồm M thuộc tính (P ≤ M) sao cho không gian thuộc tính được thu gọn lại
một cách tối ưu theo một tiêu chuẩn nhất định. Việc tìm ra một tập con thuộc
tính tốt nhất (làm mất đi ít nhất lượng thông tin cần thiết) thường khó thực hiện;
nhiều bài toán liên quan đến vấn đề này là những bài toán NP-khó. Nhìn chung,
một thuật toán lựa chọn thuộc tính thường bao gồm bốn khâu cơ bản:
Tạo lập tập con,
Đánh giá tập con,
Kiểm tra điều kiện dừng,
Kiểm chứng kết quả.
Tạo lập tập con thuộc tính là quá trình tìm kiếm liên tiếp nhằm tạo ra các
tập con để đánh giá, lựa chọn. Giả sử có M thuộc tính trong tập dữ liệu ban đầu,
khi đó số tất cả các tập con từ M thuộc tính sẽ là
2
M
. Với số ứng viên này, việc
tìm tập con tối ưu, ngay cả khi M không lớn lắm, cũng là một việc không thể.
Vì vậy, phương pháp chung để tìm tập con thuộc tính tối ưu là lần lượt tạo ra các


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
20
Cách tiếp cận filter có ưu điểm là thời gian tính toán nhanh, nhược điểm là
không sử dụng sử dụng thông tin nhãn lớp của các bộ dữ liệu nên độ chính xác
không cao Hình 2.3. Các cách tiếp cận filter và wrapper
Gần đây một số cách tiếp cận mới cũng đã được các tác giả đã đề xuất,
chẳng hạn cách tiếp cận lai ghép (hybrid approach) nhằm kết hợp các ưu điểm
của cả hai cách tiếp cận filter và wrapper, cách tiếp cận tập thô. Cũng có thể
phân chia các cách tiếp cận bài toán lựa chọn thuộc tính thành hai loại: có giám
sát (supervised) và không có giám sát (unsupervised), tùy theo việc lựa chọn có
sử dụng hay không sử dụng thông tin nhãn lớp của các đối tượng.
2.2.2. Đặc điểm chung của các thuật toán lựa chọn thuộc tính
Hai khâu chủ yếu trong quá trình lựa chọn thuộc tính là tạo lập các tập con
và đánh giá các tập con.
2.2.2.1 Tạo lập các tập con
Thông thường có hai phương pháp tạo lập các tập con cho việc chọn lựa:
phương pháp tiến (Forward Generation) và phương pháp lùi (Backward

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21
Generation). Tạo lập theo phương pháp tiến bắt đầu bằng tập rỗng. Sau đó, tại
mỗi bước lặp một thuộc tính tốt nhất (theo tiêu chuẩn đánh giá) trong số các
thuộc tính còn lại sẽ được thêm vào. Quá trình tạo lập dừng lại khi đã vét cạn tất
cả các thuộc tính của tập dữ liệu ban đầu hoặc đã tìm được tập con tối ưu.
Ngược lại với phương pháp tiến, phương pháp lùi bắt đầu bằng tập tất cả các
thuộc tính. Tại mỗi bước lặp, một thuộc tính tồi nhất (theo tiêu chuẩn đánh giá)

quyết định), X là một tập con thuộc tính nào đó. Người ta có thể sử
dụng khoảng cách giữa hai phân phối xác suất có điều kiện
( / )P D C

( / )P D X
để lựa chọn. Thuộc tính X sẽ được coi là tốt hơn thuộc tính
Y nếu khoảng cách giữa
( / )P D C
và
( / )P D X
lớn hơn khoảng cách
( / )P D C
và
( / )P D Y
.
Số đo lượng thông tin thu thêm (information gain). Lượng thông tin
thu thêm từ thuộc tính X được định nghĩa bằng hiệu số giữa độ bất
định (entropy) tiên nghiệm và giá trị kỳ vọng của độ bất định hậu
nghiệm của thuộc tính quyết định D khi đã biết X. Thuộc tính X được
coi là tốt hơn thuộc tính Y nếu lượng thông tin thu thêm được từ X lớn
hơn lượng thông tin thu thêm được từ Y.
Số đo độ phụ thuộc (dependency - hay còn gọi là số đo độ tương quan).
Số đo này đánh giá khả năng dự đoán của một thuộc tính đối với giá trị
của một thuộc tính khác. Trong hai thuộc tính điều kiện X và Y, thuộc
tính nào tương quan mạnh hơn với thuộc tính quyết định D thì nó sẽ
được ưu tiên lựa chọn. Số đo độ tương quan giữa hai thuộc tính cũng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
23
được mở rộng để đánh giá sự phụ thuộc giữa một thuộc tính vào một
khối u ác tính của các bác sĩ chuyên khoa qua chỉ vào khoảng 65% đến 85%.
Với việc ứng dụng các giải thuật lựa chọn thuộc tính, hiện nay các những hệ
thống nhận dạng tự động khối u có thể đạt kết quả phân loại khối u chính xác
đến 95%.
Lựa chọn
thuộc tính
Nhận dạng ảnh
Phân loại văn bản
Kiểm tra hệ thống Phân cụm

Tin-sinh-học

Qui nạp luật
If ... ... then

X