TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO THỰC TẬP
TỐT NGHIỆP
ĐỀ TÀI: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH VÀ
ỨNG DỤNG
Giảng viên hƣớng dẫn: Ths. Trần Hùng Cƣờng
Sinh viên thực hiện: Nguyễn Bá Nguyện
Lớp: Khoa học máy tính 3
Khóa: 4
Hà Nội, Tháng 3 năm 2013 LỜI 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.
Khai 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à khai phá tri thức trong
cơ sở dữ liệu, khai 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.
DANH SÁCH HÌNH VẼ 6
PHẦN MỞ ĐẦU 7
CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC 8
1.1 Phát hiện tri thức và khai phá dữ liệu 8
1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu 8
1.2.1. Hình thành và định nghĩa bài toán. 9
1.2.2. Thu thập và xử lý dữ liệu. 9
1.2.3. Khai thác dữ liệu và rút ra tri thức 10
1.2.4. Phân tích và đánh giá tri thức 10
1.2.5. Sử dụng tri thức phát hiện được 10
1.3. Khai phá dữ liệu 11
1.3.1. Các quan niệm về khai phá dữ liệu. 11
1.3.2. Quá trình khái phá dữ liệu. 12
1.3.3. Kiến trúc của hệ thống khai phá dữ liệu. 14
1.4. Các kỹ thuật khai phá dữ liệu 15
1.4.1. Phân lớp dữ liệu 15
1.4.2. Phân cụm dữ liệu 16
1.4.3. Cây quyết định 16
1.4.4. Luật kết hợp 16
1.4.5. Hồi quy 16
1.4.6. Mạng Nơron 16
1.4.7. Giải thuật di truyền 17 CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY
QUYẾT ĐỊNH 18
2.1 Cây quyết định 18
2.1.1 Giới thiệu 18
2.1.2 Các kiểu cây quyết định 18
2.1.3 Ưu điểm của cây quyết định 19
Hình 3. 2 Load dữ liệu và tạo cây quyết định 41
Hình 3. 3 Tiến hành cắt tỉa cây 42
Hình 3. 4 Hình ảnh của cây quyết định 42
Hình 3. 5 Rút ra luật từ cây quyết định 43
Hình 3. 6 Phân tích dữ liệu mới 43
7
PHẦN MỞ ĐẦU
Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng dụng
của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, thì lƣợng dữ liệu
đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều lên. Ngƣời ta lƣu trữ
những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên
theo thống kê thì chỉ có một lƣợng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%)
là luôn đƣợc phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm gì với
những dữ liệu này, nhƣng họ vẫn tiếp tục thu thập và lƣu trữ vì hy vọng
những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách
nhanh chóng để đƣa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy,
các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp
ứng đƣợc thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là Kỹ thuật phát
hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining). Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang đƣợc nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau trên thế giới, tại Việt Nam kỹ thuật này còn
tƣơng đối mới mẻ tuy nhiên cũng đang đƣợc nghiên cứu và bắt đầu đƣa vào
một số ứng dụng thực tế. Vì vậy, hiện nay ở nƣớc ta vấn đề phát hiện tri thức và khai
phá dữ liệu đang thu hút đƣợc sự quan tâm của nhiều ngƣời và nhiều công ty phát triển
ứng dụng công nghệ thông tin. Trong phạm vi đề tài nghiên cứu khoa học này của em,
em sẽ trình bày những nội dung sau:
Chƣơng 1: Giới thiệu những kiến thức tổng quan về khám phá tri thức và khai phá
dữ liệu.
Chƣơng 2: Nghiên cứu kỹ thuật khai phá dữ liệu bằng cây quyết định.
1.2.1. Hình thành và định nghĩa bài toán.
Đây là bƣớc tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bƣớc này sẽ
quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các phƣơng
pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ liệu.
1.2.2. Thu thập và xử lý dữ liệu.
Trong bƣớc này dữ liệu đƣợc thu thập ở dạng thô (nguồn dữ liệu thu thập có thể
là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này dữ liệu cũng
đƣợc tiền xử lý để biến đổi và cải thiện chất lƣợng dữ liệu cho phù hợp với phƣơng
pháp khai phá dữ liệu đƣợc chọn lựa trong bƣớc trên.
Bƣớc này thƣờng chiếm nhiều thời gian nhất trong quá trình khám phá tri thức.
Các giải thuật tiền xử lý dữ liệu bao gồm :
1. Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ đƣợc thay thế bởi các
giá trị thích hợp
2. Khử sự trùng lắp: các đối tƣợng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ thuật
này không đƣợc sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu.
Hình thành và
định nghĩa bài toán
Thu thập và tiền
xử lý dữ liệu
KHAI PHÁ DỮ LIỆU
(Triết xuất tri thức)
Phân tích và
đánh giá tri thức
Sử dụng tri thức
phát hiện đƣợc
Hình 1. 1 Quá trình khai phá dữ liệu từ cơ sở dữ liệu
10
3. Giảm nhiễu: nhiễu và các đối tƣợng tách rời khỏi phân bố chung sẽ bị
loại đi khỏi dữ liệu.
ích từ kho dữ liệu khổng lồ.
Khai phá dữ liệu đƣợc định nghĩa nhƣ một quá trình phát hiện mẫu trong dữ
liệu, quá trình này có thể là tự động hay bán tự động, song phần nhiều là bán tự
động. Các mẫu đƣợc phát hiện thƣờng hữu ích theo định nghĩa:các mẫu mang lại
cho ngƣời sử dụng một lợi thế nào đó, thƣờng là lợi ích về kinh tế.
Khai phá dữ liệu giống nhƣ quá trình tìm ra và mô tả mẫu dữ liệu. Dữ liệu nhƣ
là một tập hợp các vật hay sự kiện, còn đầu ra của quá trình khai phá dữ liệu thƣờng
nhƣ là những dự báo của các vật hay các sự kiện mới.
Khai phá dữ liệu đƣợc áp dụng trong các cơ sở dữ liệu quan hệ, giao dịch, cơ sở
dữ liệu không gian, cũng nhƣ các kho dữ liệu phi cấu trúc, mà điển hình là World
Wide 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ồ. Nhiệm vụ của khai phá dữ liệu.
12
1.3.2. Quá trình khái phá dữ liệu.
Hình 1. 2 Quá trình khai phá dữ liệu
1.3.2.1. Gom dữ liệu (gatherin)
Tập hợp dữ liệu là bƣớc đầu tiên trong khai phá dữ liệu. Bƣớc này lấy dữ liệu
từ trong một cơ sở dữ liệu, một kho dữ liệu, thậm chí dữ liệu từ những nguồn
cung ứng web.
1.3.2.2. Trích lọc dữ liệu (selection)
1.3.3. Kiến trúc của hệ thống khai phá dữ liệu.
Database, data warehouse, World Wide Web, và information repositories
- Thành phần này là các nguồn dữ liệu/thông tin sẽ đƣợc khai phá.
- Trong những tình huống cụ thể, thành phần này là nguồn nhập (input)
của các kỹ thuật tích hợp và làm sạch dữ liệu.
Database hay data warehouse server
- Thành phần chịu trách nhiệm chuẩn bị dữ liệu thích hợp cho các yêu cầu
khai phá dữ liệu.
Knowledge base
- Thành phần chứa tri thức miền, đƣợc dùng để hƣớng dẫn quá trình tìm
kiếm, đánh giá các mẫu kết quả đƣợc tìm thấy.
- Tri thức miền có thể là các phân cấp khái niệm, niềm tin của ngƣời sử
dụng, các ràng buộc hay các ngƣỡng giá trị, siêu dữ liệu, …
Data mining engine
User Interface
Pattern Evaluation
Data mining Enggine
Database or Data
Warehouse Server
Knowledge
Base
Database
Data
Warehouse
Other Infor
Repositories
World Wide
(Decision tree), thống kê (statictics), mạng nơron (neural network), luật kết
hợp,….
Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để khai phá dữ liệu hiện
nay là :
1.4.1. Phân lớp dữ liệu
Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ
16
liệu( mỗi mẫu 1 lớp). Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ
chính xác của mô hình chấp nhận đƣợc.
1.4.2. Phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong
tập dữ liệu vào các cum, sao cho các đối tƣợng thuộc cùng một lớp là tƣơng đồng.
1.4.3. Cây quyết định
Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân
lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá trị của đối
tƣợng dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo. Tri thức đƣợc rút ra trong kỹ
thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản, trực quan, dễ hiểu
đối với ngƣời sử dụng.
1.4.4. Luật kết hợp
Chẳng hạn nhƣ có luật: âm nhac, thể thao => thiếu nhi, nghĩa là những ngƣời
mua sách âm nhạc và thể thao thì cũng mua sách thiếu nhi. Lúc đó ta sẽ quan tâm
đến số lƣợng trƣờng hợp khách hàng thỏa mãn luật này trong cơ sở dữ liệu hay độ
hỗ trợ (Support) cho luật này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có
cả sách âm nhạc, thể thao và thiếu nhi hay tất cả những ngƣời thích cả ba loại
sách nói trên. Tuy nhiên, giá trị độ hỗ trợ là không đủ, có thể có trƣờng hợp ta có
một nhóm tƣơng đối những ngƣời đọc cả ba loại trên nhƣng lại có một nhóm với
lực lƣợng lớn hơn những ngƣời thích sách thể thao, âm nhạc mà không thích sách
thiếu nhi. Trong trƣờng hợp này tính kết hợp rất yếu mặc dù độ hỗ trợ tƣơng đối
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 cách loại bỏ các giải pháp
từ mỗi cá thể và thay thế chúng bằng các con cháu hoặc các đột biến của
các giải pháp tốt. Thuật toán sẽ kết thúc khi một họ các giải pháp thành
công đƣợc sinh ra.
18
CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY
QUYẾT ĐỊNH
2.1 Cây quyết định
2.1.1 Giới thiệu
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo
(predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tƣợng
tới các kết luận về giá trị mục tiêu của sự vật/hiện tƣợng. Mỗi nút trong (internal
node) tƣơng ứng với một biến; đƣờng nối giữa nó với nút con của nó thể hiện giá
trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu,
cho trƣớc các giá trị dự đoán của các biến đƣợc biểu diễn bởi đƣờng đi từ nút gốc
tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định đƣợc gọi là học bằng
cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định.
Ví dụ: Cây quyết định phân lớp mức lƣơng
2.1.2 Các kiểu cây quyết định
Cây quyết định còn có hai loại:
- Cây hồi quy (Regression tree): ƣớc lƣợng các hàm giá có giá trị là số thực
thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. (Ví dụ: ƣớc tính giá một
ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện.)
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.1.4 Phân lớp dữ liệu bằng cây quyết định
Phân lớp dựa trên cây quyết định rất thích hợp cho việc khai phá dữ liệu vì cây
quyết định có cấu trúc đơn giản, dễ hiểu và có thể đƣợc xây dựng khá nhanh, từ
cây quyết định có thể dễ dàng rút ra các luật.
Quy nạp cây quyết định là một quá trình học tập của cây quyết định từ các
nhãn lớp của bộ dữ liệu huấn luyện (training tuple). Một cây quyết định là một biểu
đồ dòng dữ liệu nhƣ cấu trúc cây, mỗi nút trong (không phải lá) tƣợng trƣng cho
một thuộc tính kiểm tra, mỗi nhánh đại diện cho kết quả của việc kiểm tra, và mỗi
nút lá (hay nút giới hạn) giữ một lớp nhãn. Nút đầu tiên trên cây là nút gốc.
20
Quá trình phân lớp dữ liệu thông qua 2 bƣớc cơ bản nhƣ sau:
Bƣớc 1: Xây dựng mô hình từ tập huấn luyện
Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc.
Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn lớp.
Tập các bộ/mẫu dữ liệu huấn luyện - tập huấn luyện - đƣợc dùng để xây
dựng mô hình.
Mô hình đƣợc biểu diễn bởi các luật phân lớp, các cây quyết định hoặc các
công thức toán học.
Hình 2. 2 Xây dựng mô hình
Bƣớc 2: Sử dụng mô hình, kiểm tra tính đúng đắn của mô hình và dùng nó để
phân lớp dữ liệu mới.
Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp.
Đánh giá độ chính xác của mô hình:
Ví dụ từ cây 2.1 ta có thể rút ra đƣợc các luật sau.
IF (Age <= 35) AND (salary<=40) THEN class = bad
IF (Age<=35) AND (salary>40) THEN class = good
IF (Age>35) AND (salary <=50 ) THEN class = bad
IF (Age > 35) AND(salary>50) THEN class = good
2.2 Các thuật toán xây dựng cây quyết định
2.2.1 Thuật toán CLS
Thuật toán này đƣợc Hovland và Hint giới thiệu trong Concept learning
System (CLS) vào những năm 50 của thế kỷ 20. Sau đó gọi tắt là thuật toán CLS.
Thuật toán CLS đƣợc thiết kế theo chiến lƣợc chia để trị từ trên xuống. Nó gồm
các bƣớc sau:
1. Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện.
2. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị
"yes" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "yes" và
dừng lại. T lúc này là nút lá.
3. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị
"no" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "no" và
dừng lại. T lúc này là nút lá.
4. Trƣờng hợp ngƣợc lại các mẫu của tập huấn luyện thuộc cả hai lớp
"yes" và "no" thì:
23
+ Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ
liệu, X có các giá trị v
1
,v
2
, …v
n
learning năm 1986. ID3 đƣợc xem nhƣ là một cải tiến của CLS với khả năng lựa
chọn thuộc tính tốt nhất để tiếp tục triển khai cây tại mỗi bƣớc. ID3 xây dựng cây
quyết định từ trên- xuống (top -down).
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ụ huấn
luyện (training example) hay còn gọi là dữ liệu huấ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ó.
24
Đầ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 huấ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.
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) 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 cho đến khi mọi thành viên của phân vùng đều nằm
trong cùng một lớp; lớp đó trở thành nút lá của cây.
Các thuộc tính phân loại:
Entropy: dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của một tập S
đƣợc tính theo công thức +-
22
Entropy(S)= - P log ( ) P log ( )PP
25
Information Gain (viết tắt là Gain): Gain là đại lƣợng dùng để đo tính hiệu quả
của một thuộc tính đƣợc lựa chọn cho việc phân lớp. Đại lƣợng này đƣợc tính
thông qua hai giá trị Information và Entropy.
Cho tập dữ liệu S gồm có n thuộc tính A
i
(i=1,2…n) giá trị Information của thuộc
tính A
i
ký hiệu là Information(A
i
) đƣợc xác định bởi công thức .
(2.3) Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S,A) và đƣợc tính
theo công thức sau:
(2.4)
Trong
đó :
S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tƣơng ứng là các
giá trị của thuộc tính A.
S
v
bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.
|S
S
S
Entropy(S)) Gain(S,
V
Value(A)V
V
A
Copyright: Tài liệu đại học ©