1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Phạm Duy An PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU
BẰNG CÂY QUYẾT ĐỊNH

Chuyên ngành : Truyền dữ liệu và Mạng máy tính
Mã số : 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012
2
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: PGS.TS VŨ ĐỨC THI
Tìm hiểu được những ưu điểm cũng như những khó
khăn trong việc đào tạo theo tín chỉ, sử dụng phần mềm mã
nguồn mở Weka cho việc sinh ra các luật kết hợp nhằm phục
vụ việc phân loại. Xây dựng một hệ thống tư vấn môn học cho
sinh viên nhằm trợ giúp sinh viên định hướng được trong việc
lựa chọn môn học,chuyên ngành học phù hợp.
Hướng phát triển tiếp theo của luận văn:
Để quá trình đào tạo theo tín chỉ hoạt động có hiệu quả,
cần thiết phải xây dựng một hệ thống hoàn chỉnh hỗ trợ cả quá
trình đào tạo (xây dựng thêm nhiều chức năng: sắp xếp lịch
học, thời khóa biểu, đăng ký học trực tuyến,…)
Hiện nay, dữ liệu được lưu trữ ngày một tăng, để ứng dụng khai
phá dữ liệu vào các bài toán này cần tiếp tục nghiên cứu các
phương pháp xử lý cho bài toán với dữ liệu lớn. xem xét nghiên
cứu thêm một số ứng dụng khác của Khai phá dữ liệu.

3
MỞ ĐẦU
Trong thời đại ngày nay, yếu tố quyết định thành công
trong mọi lĩnh vực luôn gắn liền với việc nắm bắt, thống kê và
khai thác thông tin hiệu quả. Dữ liệu ngày càng lớn nên việc
tìm ra những thông tin tiềm ẩn trong chúng càng khó khăn hơn.
Khám phá tri thức là một lĩnh vực nghiên cứu mới, mở
ra một thời kỳ trong việc tìm ra thông tin hữu ích. Nhiệm vụ cơ
bản của lĩnh vực này là khám phá tri thức trong cơ sở dữ liệu,
khám phá dữ liệu trong cơ sở dữ liệu không phải là một hệ
thống phân tích tự động mà là một quá trình tương tác thường
xuyên giữa con người với cơ sở dữ liệu được sự trợ giúp của
nhiều phương pháp và công cụ tin học.
Nội dung luận văn tôi xin trình bày bao gồm ba chương:

lược kinh doanh kịp thời mang lại những lợi nhuận to lớn cho
doanh nghiệp của mình. Tất cả lý do đó khiến cho các cơ quan,
doanh nghiệp đã tạo ra một lượng dữ liệu khổng lồ cỡ Gigabyte
thậm chí là Terabyte.
Nhiều người coi khai phá dữ liệu và khám phá tri thức
trong cơ sở dữ liệu là như nhau, tuy nhiên trong thực tế chúng
có quan hệ mật thiết với nhau, khai phá dữ liệu chỉ là một bước
thiết yếu trong quá trình phát hiện tri thức trong cơ sở dữ liệu.
1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu.
Quá trình phát hiện tri thức có thể chia thành các bước
như sau:
- Làm sạch dữ liệu (Data cleaning): Loại bỏ
những dữ liệu nhiễu, không thích hợp, dư thừa hoặc
không đầy đủ.
- Tích hợp dữ liệu (Data intergration):Tích hợp dữ
liệu từ nhiều nguồn khác nhau
- Lựa chọn dữ liệu (Data selection): Chọn những
dữ liệu có liên quan trực tiếp đến nhiệm vụ.
- Chuyển đổi dữ liệu (Data transformation): Các
dữ liệu sau khi được xử lý ở các giai đoạn trên được biến
đổi về dạng phù hợp với việc khai phá.
25

Hình 3.8 : Giao diện truy cập demo
24
Phần 2: Tư vấn cho người dùng.
Chương trình được viết trên giao diện Web, sử dụng
ngôn ngữ lập trình ASP. NET. Đưa các luật được sinh ra từ
phần 1 vào cơ sở dữ liệu SQL server của Website, ta có bảng
luật lưu trữ các luật định hướng chuyên ngành. Ngoài ra có các

chọn để trích xuất ra những thông tin hữu ích, có tiềm
năng.
- Đánh giá mẫu (Pattern evaluation): Các mẫu, tri
thức được đánh giá dựa trên các tiêu chí sẵn có.
- Trình diễn tri thức (Knowledge representation):
Đây là bước cuối cùng, tại bước này dữ liệu được củng cố,
biểu diễn và sử dụng.
Hình 1.1. Quá trình khám phá tri thức từ cơ sở dữ liệu.
1.2.1. Xác định vấn đề.
1.2.2. Thu thập và xử lý dữ liệu.
1.2.3. Khai thác dữ liệu.
1.2.4. Minh họa, đánh giá và đưa kết quả vào thực tế.
1.3. Khai phá dữ liệu.
1. hi
ểu v
à xác đ
ịnh
v
ấn đề

2. Thu th
ập v
à ti
ền xử
lý d
ữ liệu

3. Khai thác dữ liệu – trích
ra các m
ẫu/mô h

Web.
Khám phá tri thức là quá trình nhận biết các mẫu
hoặc các mô hình trong dữ liệu với các tính chất: Đúng đắn,
mới, khả ích và có thể hiểu được. Khai phá dữ liệu là một
bước trong quá trình khám phá tri thức bao gồm các thuật
toán khai phá dữ liệu chuyên dùng dưới một số quy định về
hiệu quả tính toán chấp nhận được để tìm ra các mẫu và các
mô hình trong dữ liệu.
Như vậy, mục đích của khám phá tri thức và khai
phá dữ liệu là tìm ra các mẫu hoặc mô hình đang tồn tại
trong các cơ sở dữ liệu nhưng vẫn còn bị khuất bởi số lượng
dữ liệu khổng lồ.
1.3.2. Nhiệm vụ của khai phá dữ liệu.
* Phân cụm, phân nhóm, phân loại, phân lớp. Nhiệm vụ
này trả lời câu hỏi: Một dữ liệu mới thu thập được sẽ thuộc về
23

Giai đoạn 1: Sử dụng dữ liệu sau khi đã xây dựng để tiến hành
tập huấn. Tìm tất cả các tập mục thường xuyên.
Giai đoạn 2: Khai phá luật kết hợp.
3.3.3. Thiết kế cơ sở dữ liệu.
Tiến hành xây dựng cơ sở dữ liệu với các bảng sau:
Bảng 3.1 : Lưu trữ danh sách sinh viên toàn trường
Bảng 3.2: Lưu trữ danh sách các môn học trong trường
Bảng 3.3: Lưu trữ danh sách sinh viên đã tốt nghiệp.
3.3.4. Tập huấn và xử lý dữ liệu.
Phần 1: khai phá dữ liệu.
Trong phần này, phần mềm Weka được sử dụng để sinh
ra các luật kết hợp từ dữ liệu thu thập được. Trường Đại học
Phương Đông cung cấp cho dữ liệu về cựu sinh viên, dữ liệu

không cần tổ chức thi lại.
3.3.2. Mô tả hệ thống dữ liệu của bài toán.
Bài toán đặt ra: Cho một kho dữ liệu lưu giữ các thông
tin về kết quả học tập của sinh viên đã tốt nghiệp. Hãy tìm ra
những quy luật lựa chọn các chuyên ngành một cách hợp lý sao
cho đạt được kết quả tốt nhất.
Nhằm mục đích này người ta mong muốn nhận được từ
dữ liệu những phát biểu như: “80% sinh viên học tốt môn Kinh
tế chính trị và Tiếng Anh khá thì tốt nghiệp chuyên ngành Kế
toán ngân hàng loại giỏi”, …
Để đạt được những phát biểu như trên, chúng ta sử dụng các
thuật toán Khai phá luật kết hợp từ cơ sở dữ liệu. Mặc dù hiện
tại đã có nhiều thuật toán khai phá dữ liệu với luật kết hợp
nhưng nhìn chung mỗi thuật toán đều qua hai giai đoạn. 7
nhóm nào? Qúa trình này thường được thực hiện một cách tự
động.
* Khai phá luật kết hợp. Nhiệm vụ là phát hiện ra
những mối quan hệ giống nhau của các bản ghi giao dịch. Luật
kết hợp X => Y có dạng tổng quát là: Nếu một giao dịch đã sở
hữu các tính chất X thì đồng thời nó cũng sở hữu các tính chất
Y, ở một mức độ nào đó. Khai phá luật kết hợp được hiểu theo
nghĩa: Biết trước các tính chất X, vậy các tính chất Y là những
tính chất nào?
* Lập mô hình dự báo, bao gồm 2 nhiệm vụ: Hoặc là
phân nhóm dữ liệu vào một hay nhiều lớp dữ liệu đã xác định
từ trước, hoặc là sử dụng các trường đã cho trong một cơ sở dữ
liệu để dự báo sự xuất hiện (hoặc không xuất hiện) của các

(Clustering), tóm tắt (Summerization), trực quan hóa
(Visualization), phân tích sự phát triển và độ lệch
(Evolution and Deviation analyst), phân tích luật kết hợp
(Association rules), …
- Kỹ thuật khai phá dữ liệu 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 có: Phân lớp (Classifacation),
hồi quy (regession), …
Tuy nhiên, chỉ có một số phương pháp thông dụng nhất
là: Phân cụm dữ liệu, phân lớp dữ liệu, phương pháp hồi quy,
và khai phá luật kết hợp.
1.3.5. Kiến trúc của hệ thống khai phá dữ liệu.
Kiến trúc của hệ thống khai phá dữ liệu có các thành
phần như sau:
- Cơ sở dữ liệu, kho dữ liệu: Đó là một hoặc nhiều
tập cơ sở dữ liệu, kho dữ liệu,… Các kỹ thuật làm sạch
dữ liệu, tích hợp, lọc dữ liệu có thể thực hiện trên dữ liệu.
- Cơ sở dữ liệu hoặc kho dữ liệu phục vụ: Là kết
quả lấy dữ liệu có liên quan trên cơ sở khai phá dữ liệu
của người dùng.
21
Server computer. Một RDBMS bao gồm databases, database
engine và các ứng dụng dùng để quản lý dữ liệu và các bộ phận
khác nhau trong RDBMS.
SQL Server cung cấp các công cụ quản trị và phát triển để cho
người sử dụng dễ dàng cài đặt, sử dụng và quản lý hệ thống.
SQL Server được sử dụng trong luận văn với mục đích
lưu trữ các dữ liệu liên quan đến luật để phục vụ cho quá trình
truy vấn của sinh viên.
3.2.3. Ngôn ngữ lập trình ASP.NET

hồi quy, với những công việc có giá trị, phương pháp và
tham số tốt nhất cho vấn đề đã cho. Cho phép bạn tự động
hóa xử lý, làm cho nó phân lớp và lọc dễ dàng với những
cách thiết lập tham số khác nhau trên toàn bảng dữ liệu.
 KnowledgeFlow: Cho phép người dùng kéo thả
những chiếc hộp tượng trưng cho các giải thuật và dữ liệu
để kết nối chúng lại với nhau và đưa ra cấu trúc.
 Simple CLI: Sử dụng câu lệnh thực thi.
3.2.2. Hệ quản trị cơ sở dữ liệu SQL 2000 server
SQL Server 2000 là một hệ thống quản lý cơ sở dữ liệu
(Relational Database Management System (RDBMS) ) sử dụng
Transact-SQL để trao đổi dữ liệu giữa Client computer và SQL
9
- Cơ sở tri thức: Đó là lĩnh vực tri thức được sử
dụng để hướng dẫn việc tìm hoặc đánh giá các mẫu kết
quả thu được.
- Mô tả khai phá dữ liệu: Bao gồm tập các modul
chức năng để thực hiện các nhiệm vụ mô tả các đặc điểm,
kết hợp, phân lớp, phân cụm dữ liệu,…
- Đánh giá mẫu: Thành phần này sử dụng các độ
đo và tương tác với modul khai phá dữ liệu để tập chung
vào tìm các mẫu quan tâm.
- Giao diện người dùng: Đây là modul giữa người
dùng và hệ thống khai phá dữ liệu, cho phép người dùng tương
tác với hệ thống trên cơ sở những truy vấn hay tác vụ, cung cấp
thông tin cho việc tìm kiếm.
1.3.6. Những khó khăn trong khai phá dữ liệu.
- Dữ liệu lớn.
- Kích thước lớn.
- Dữ liệu động.

là độ tin cậy (confidence). Độ tin cậy chính là phần trăm các
bản ghi có sách thiếu nhi trong số các bản ghi có sách âm nhạc
và thể thao.
1.4.3. Mạng Nơron.
Có nhiều kiến trúc khác nhau cho mạng nơron và mỗi
trong số chúng sử dụng các cách kết nối mạng khác nhau và
chiến lược học khác nhau để thực hiện các nhiệm vụ. Khi sử
dụng mạng nơron chúng ta phải phân biệt hai giai đoạn: giai
đoạn mã hóa trong mạng nơron được học trên các mẫu dữ liệu
huấn luyện, thực hiện một nhiệm vụ nào đó và giai đoạn giải
mã trong đó mạng được sử dụng để phân lớp, làm dự báo hoặc
thực hiện bất cứ nhiệm vụ học nào liên quan. Có nhiều dạng
mạng nơron nhưng về cơ bản có các loại chính sau:
- Perceptrons
- Mạng lan truyền ngược (Back propagation networks)
- Mạng tự tổ chức Konhonen (Kohonen self –
organizedmap)

19
Chương 3- XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG
KHAI PHÁ DỮ LIỆU
“Tư vấn lựa chọn chuyên ngành tại trường đại học
Phương Đông”

3.1. Giới thiệu khai phá dữ liệu trong giáo dục.
Các nhà nghiên cứu về việc khai phá dữ liệu trong giáo
dục tập chung vào nhiều vấn đề bao gồm việc học của cá nhân
từ phần mềm giáo dục, học cộng tác với sự giúp đỡ của máy
tính, kiểm nghiệm khả năng thích ứng với máy tính, và nhiều
nhân tố được kết hợp với các sinh viên không có khả năng hoặc

dụng phép thử thống kê để loại bỏ các luật không cần thiết:
Loại bỏ các tiên đề không cần thiết để đơn giản hóa các
luật.
Xây dựng các bảng ngẫu nhiên (contingency table) cho
mỗi luật chứa nhiều hơn một tiên đề.
Kiểm chứng sự độc lập của kết quả đối với một tiên đề
bằng một trong các phép thử sau:
Sử dụng phép chi bình phương nếu các tuần xuất mong
đợi lớn hơn 10.
Sử dụng phép thử Yates nếu các tần xuất mong đợi
trong khoảng [5,10].
Sử dụng phép thử Fisher nếu các tần xuất mong đợi nhỏ
hơn 5.
Loại bỏ các luật không cần thiết.
11
1.4.4. Giải thuật di truyền.
Việc xây dựng các thuật toán di truyền mô phỏng sinh
học nhằm tìm ra các giải pháp tốt nhất bao gồm các bước sau:
1. Tạo ra cơ chế mã di truyền dưới dạng các xâu của
một bảng mã ký tự hạn chế.
2. Thiết lập môi trường nhân tạo trên máy tính có các
giải pháp có thể tham gia “đấu tranh sinh tồn” với nhau để xác
định độ đo thành công hay thất bại, hay còn gọi là “hàm thích
nghi”.
3. Phát triển các “phép lai ghép” để các giải pháp kết
hợp với nhau. Khi đó các xâu mã di truyền của giải pháp cha và
mẹ bị cắt đi và xếp lại, trong quá trình sinh sản như vậy các
kiểu đột biến có thể được áp dụng.
4. Cung cấp một quần thể các giải pháp ban đầu tương
đối đa dạng và để máy tính thực hiện “cuộc chơi tiến hóa” bằng

Lá: các đỉnh có bậc 0 được gọi là lá của cây.
Đường đi: mỗi dãy các đỉnh a
1
, a
2
, …, a
n
(n≥ 1), sao cho
a
i
(i = 1, 2, …, n-1) là cha của a
i+1
được gọi là đường đi từ a
1

đến a
n
. Độ dài đường đi là n-1.
Cành: là đường đi từ đỉnh một cha đến đỉnh một con.
Độ cao, mức: trong một cây, độ cao của một đỉnh a là độ
dài của đường đi dài nhất từ a đến một lá. Độ cao của gốc được
gọi là độ cao của cây, mức của đỉnh a là độ dài của đường đi từ
gốc đến a.
2.1.3. Ưu điểm của cây quyết định.
So với các phương pháp khai phá dữ liệu khác, cây
quyết định là phương pháp có một số ưu điểm:
Cây quyết định dễ hiểu. Người ta có thể hiểu
mô hình cây quyết định sau khi được giải thích
ngắn.
Việc chuẩn bị dữ liệu cho một cây quyết định

2.4.2. Phương pháp tỉa cây sau.
Khác với phương pháp trên, quá trình tỉa cây sau chỉ
được thực hiện khi đã có một cây quyết định hoàn chỉnh.
16
SplitInformation(S,A) = -


c
i
ii
S
S
S
S
1
2
log

GainRatio: Sự đánh giá thay đổi các giá trị của thuộc
tính.

( , )
( , )
( , )
Gain S A
GainRation S A
SplitInformation S A


Tất cả các thuộc tính sẽ được tính toán độ đo tỷ lệ Gain,

số.
Cây quyết định là một mô hình hộp trắng.
Mạng nơ-ron là một ví dụ về mô hình hộp đen, do
lời giải thích cho kết quả quá phức tạp để có thể
hiểu được.
Có thể thẩm định một mô hình bằng các kiểm
tra thống kê. Điều này làm cho ta có thể tin tưởng
vào mô hình.
2.2. Thuật toán ID3.
2.2.1. Giới thiệu.
Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết
định từ một tập các ví dụ rèn luyện (training example) hay còn
gọi là dữ liệu rèn luyện (training data). Hay nói khác hơn, giải
thuật có:
Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các
thuộc tính mô tả một tình huống, hay một đối tượng nào
đó, và một giá trị phân loại của nó.
Đầu ra: Cây quyết định có khả năng phân loại đúng đắn
các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân
loại đúng cho cả các ví dụ chưa gặp trong tương lai.
2.2.2. Thuật toán ID3
ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên
xuống. Lưu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng
có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập
con tách rời, mà ở đó mọi ví dụ trong một phân vùng (partition)
14
có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính
để kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để
phân vùng tập hợp các ví dụ; thuật toán khi đó xây dựng theo
cách đệ quy một cây con cho từng phân vùng. Việc này tiếp tục




2.2.4. Thí dụ mô phỏng thuật toán.
2.2.5. Tìm kiếm không gian giả thuyết trong ID3.
Từ cách nhìn ID3 như là một giải thuật tìm kiếm trong
không gian các giả thuyết, ta có một số nhận xét như sau:
 Không gian giả thuyết các cây quyết định của
ID3 là một không gian đầy đủ các cây quyết định trên các
thuộc tính đã cho trong tập rèn luyện. Điều này có nghĩa
là không gian mà ID3 tìm kiếm chắc chắn có chứa cây
quyết định cần tìm.
 Trong khi tìm kiếm, ID3 chỉ duy trì một giả
thuyết hiện tại. Vì vậy, giải thuật này không có khả năng
biểu diễn được tất cả các cây quyết định khác nhau có
khả năng phân loại đúng dữ liệu hiện có.
 Vì ID3 sử dụng tất cả các ví dụ ở mỗi bước để
đưa ra các quyết định dựa trên thống kê, nên kết quả tìm
15
kiếm của ID3 rất ít bị ảnh hưởng bởi một vài dữ liệu sai
(hay dữ liệu nhiễu).
 Trong quá trình tìm kiếm, giải thuật ID3 có xu
hướng chọn cây quyết định ngắn hơn là những cây quyết
định dài.
2.2.6. Đánh giá hiệu suất của cây quyết định.
Để đánh giá hiệu suất của một cây quyết định người ta
thường sử dụng một tập ví dụ tách rời, tập này khác với tập dữ
liệu rèn luyện, để đánh giá khả năng phân loại của cây trên các
ví dụ của tập này. Tập dữ liệu này gọi là tập kiểm tra
(validation set). Thông thường, tập dữ liệu sẵn có sẽ được chia