NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN MỤC LỤC
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN
MỤC LỤC
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN 1

1.3.6. Một vài thách thức đặt ra trong việc khai phá dữ liệu 15
Chương 2 16
2.1. Cây quyết định 16
2.1.2. Các kiểu cây quyết định 18
2.2.4.Thuật toán SLIQ 26
2.2.5.Cắt tỉa cây quyết định 29
3.1. Mô tả bài toán 32
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
LỜI NÓI ĐẦU
Kỹ nguyên Internet, Intranets, Warehouses, đã mở ra nhiều cơ hội cho
các cơ quan, các doanh nghiệp, các đơn vị trong việc thu thập và xử lý thông
tin. Bên cạnh đó, với sự phát triển mạnh mẽ của công nghệ điện tử và các
thiết bị thu thập dữ liệu tự động đã tạo ra những kho dữ liệu khổng lồ; những
bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các hệ thống mạng
viễn thông, các chủ doanh nghiệp đã xây dựng các hệ thống thông tin nhằm tự
động hoá mọi hoạt động kinh doanh của họ. Điều này đã tạo ra một dòng dữ
liệu tăng lên không ngừng vì ngay từ các giao dịch đơn giản nhất như: một
cuộc điện thoại, kiểm tra sức khỏe, sử dụng thẻ tín dụng, đều được ghi vào
trong máy tính.
Vấn đề đặt ra là làm thế nào để xử lý khối lượng thông tin cực lớn như
vậy để phát hiện ra các tri thưc tiềm ẩn trong nó. Trong điều kiện và yêu cầu
của thương trường, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự
động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các phương
pháp quản trị và khai thác cơ sở dữ liệu truyền thống không đáp ứng được kỳ
vọng này, và giải pháp là sự ra đời của “Kỹ thuật phát hiện tri thức và khai
phá dữ liệu” (KDD - Knowledge Discovery and Data Mining).
Nhiệm vụ của KDD là từ dữ liệu sẵn có phải tìm ra những thông tin
tiềm ẩn có giá trị mà trước đó chưa được phát hiện cũng như tìm ra những xu
hướng phát triển và các xu hướng tác động lên chúng .Các kỹ thuật cho phép
HVTH: Phạm Ngọc Giàu – CH1101080 Trang

phát hiện vấn đề, thu thập và tiền xử lý dữ liệu, phát hiện tri thức, minh hoạ
và đánh giá tri thức đã phát hiện và đưa kết quả vào thực tế.
Khai phá dữ liệu có những điểm khác nhau về mặt ngữ nghĩa so với
phát hiện tri thức từ cơ sở dữ liệu nhưng thực tế ta thấy khai phá dữ liệu là
chỉ một giai đoạn phát hiện tri thức trong một chuỗi các giai đoạn quá trình
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
4
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
phát hiện tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai
trò chủ chốt và là giai đoạn chính tạo nên tính đa ngành của 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
Phát hiện tri thức từ cơ sở dữ liệu là một quá trình có sử dụng nhiều
phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con
người làm trung tâm. Do đó nó không phải là một hệ thống phân tích tự động
mà là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa
con người và cơ sở dữ liệu, tất nhiên là với sự hỗ trợ của các công cụ tin học.
Hình 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu
Mặc dù có 5 giai đoạn như trên(hình 1.1), song quá trình phát hiện tri
thức từ cơ sở dữ liệu là một quá trình tương tác và lặp đi lặp lại theo kiểu
xoắn trôn ốc, trong đó lần lặp sau hoàn chỉnh hơn lần lặp trước. Ngoài ra giai
đoạn sau lại dựa trên kết quả thu được của giai đoạn trước theo mô hình thác
nước. Đây là một quá trình biện chứng mang tính chất học của quá trình phát
hiện tri thức và là phương pháp luận trong việc phát hiện tri thức. Các giai
đoạn đó được trình bày cụ thể như sau:
1.2.1. Xác định bài toán
Đây là một quá trình mang tính định hình với mục đích xác định được
lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực
tế các cơ sở dữ liệu được chuyên môn hoá và phân chia theo các lĩnh vực
khác nhau như: Sản phẩm, kinh doanh, tài chính, Với mỗi tri thức phát hiện

hình thức khác nhau. Ví dụ nơi này dùng kiểu chuỗi, nơi kia lại dùng kiểu số
để khai báo một thuộc tính nào đó của khách hàng. Đồng thời chất lượng dữ
liệu của các nơi cũng không giống nhau. Vì vậy chúng ta cần chọn lọc dữ liệu
thật tốt để chuyển sang giai đoạn tiếp theo.
1.2.2.3. Làm sạch
Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là
một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường
mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logíc. Vì vậy, dữ
liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu.
Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên.
Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị.
Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được
“làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch
nghiệm trọng.
Giai đoạn này thực hiện một số chức năng sau:
- Điều hoà dữ liệu
- Xử lý các giá trị khuyết.
- Xử lý nhiễu và các ngoại lệ
1.2.2.4. Làm giàu dữ liệu
Mục đích của giai đoạn này là bổ sung thêm nhiều loại thông tin có
liên quan vào cơ sở dữ liệu gốc. Để làm được điều này, chúng ta phải có
các cơ sở dữ liệu khác ở bên ngoài có liên quan tới cơ sở dữ liệu gốc ban
đầu. Ta tiến hành bổ sung những thông tin cần thiết, làm tăng khả năng
khám phá tri thức.
Đây là bước mang tính tư duy trong khai phá dữ liệu.Ở giai đoạn
này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ
liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết hợp
hoặc các mô hình dữ liệu tuần tự, v. v.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
7

1.2.4. Phát biểu và đánh giá kết quả
Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các
báo cáo phục vụ cho các mục đích hỗ trợ các quyết định khác nhau.
Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có
mức độ tốt, xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiết, các
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
8
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục
vụ cho các mục đích hỗ trợ các quyết định khác nhau.
Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có
mức độ tốt, xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiêt, giúp
tạo cơ sở cho những quyết định chiến lược. Thông thường, chúng được tổng
hợp, so sánh bằng các biểu đồ và được kiểm nghiệm, tin hoc.
1.2.5. Sử dụng tri thức đã phát hiện
Củng cố, tinh chế các tri thức đã được phát hiện. Kết hợp các tri thức
thành hệ thống. Giải quyết các xung đột tiềm tàng trong tri thức khai thác
được. Sau đó tri thức được chuẩn bị sẵn sàng cho ứng dụng.
Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng
dụng trong những lĩnh vực khác nhau. Do các kết quả có thể là các dự báo
hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết
định nhằm tự động hoá quá trình này.
1.3. Khai phá dữ liệu
1.3.1. Khái niệm khai phá dữ liệu
Khai phá dữ liệu là một khái niệm ra đời vào những năn cuối của thập
kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có
giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). 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 (regularities) trong tập dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm

giữa các thuộc tính dự báo và thuộc tính phân lớp, từ đó sử dụng mối quan hệ
này để dự báo lớp cho các bộ dữ liệu mới khác cùng khuông dạng.
1.3.2.2. Hồi quy (Regression)
Hồi quy là việc l ọc một hàm ánh xạ từ một mẫu dữ liệu thành một
biến dự đoán có giá trị thực. Có rất nhiều ứng dụng khai phá dữ liệu với
nhiệm vụ hồi quy, ví dụ như biết các phép đo vi sóng từ xa, đánh giá khả năng
tử vong của bệnh nhân biết các kết quả xét nghiệm chẩn đoán, dự đoán nhu
cầu tiêu thụ một sản phẩm mới bằng một hàm chỉ tiêu quảng cáo,
1.3.2.3. Gom nhóm (Clustering)
Là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để
mô tả dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên
nhau. Có nghĩa là một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia.
Các ứng dụng khai phá dữ liệu có nhiệm vụ gom nhóm như: Phát hiện tập các
khách hàng có phản ứng giống nhau trong cơ sở dữ liệu tiếp thị, xác định các
loại quang phổ từ các phương pháp đo tia hồng ngoại.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
10
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
1.3.2.4. Tổng hợp (Summarization)
Nhiệm vụ tổng hợp là việc sản sinh ra các mô tả đặc trưng cho một
lớp. Các mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của
tất cả các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.
Các mô tả đặc trưng thể hiện dưới dạng các luật thường có khuôn
dạng: “Nếu một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiền đề, thì bộ dữ
liệu đó có tất cả các thuộc tính đã nêu trong kết luận”. Những luật này có
những đặc trưng khác biệt so với các luật phân lớp. Luật phát hiện đặc trưng
cho một lớp chỉ được sản sinh khi các bộ dữ liệu thuộc về lớp đó.
1.3.2.5. Mô hình ràng buộc (Dependency modeling)
Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa
các biến. Các mô hình phụ thuộc tồn tại dưới hai mức: Mức cấu trúc của mô

Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ
liệu có cấu trúc trong rất nhiều CSDL.
Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó
không sử dụng tri thức có sẵn về lĩnh vực.
Kết quả phân tích của hệ thống sẽ rất nhiều và khó có thể làm rõ ra
được.
Phương pháp thống kê cần có sự hướng dẫn của người dùng để xác
định phân tích dữ liệu như thế nào và ở đâu.
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.
Một số ứng dụng của khai phá dữ liệu trong lĩnh vực kinh doanh:
Brandaid: Mô hình Marketing linh hoạt tập chung vào hàng tiêu dùng.
Callpla: Giúp nhân viên bán hàng xác định số lần viếng thăm của
khách hàng triển vọng và khách hàng hiện có.
Detailer: Xác định khách hàng nào nên viếng thăm và sản phẩm nào
nên giới thiệu trong từng chuyến viếng thăm.
Geoline: Mô hình thiết kế địa bàn tiêu thụ và dịch vụ.
Mediac: Giúp người quảng cáo mua phương tiện trong một năm, lập kế
hoạch sử dụng phương tiện bao gồm phác hoạ khúc thị trường, ước tính
tiềm năng.
1.3.4. Một số kỹ thuật khai phá dữ liệu
1.3.4.1. Phương pháp quy nạp (Induction)
Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn
cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực
hiện việc này là suy diễn và quy nạp.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang

lớn thoả mãn tiền đề của luật.
Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các
luật dạng X => B sao cho tần số của luật không nhỏ hơn ngưỡng Minsup cho
trước và độ tin cậy của luật không nhỏ hơn ngưỡng Minconfi cho trước. Từ
một cơ sở dữ liệu ta có thể tìm được hàng nghìn và thậm chí hàng trăm nghìn
các luật kết hợp.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
13
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
1.3.4.4. Mạng Neuron
Mạng Neuron là tiếp cận tính toán mới liên quan tới việc phát triển
cấu trúc toán học và khả năng học. Các phương pháp là kết quả của việc
nghiên cứu mô hình học của hệ thống thần kinh con người.
Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến
mạng Neuron. Tuy mạng Neuron có một số hạn chế gây khó khăn trong việc
áp dụng và phát triển nhưng nó cũng có những ưu điểm đáng kể.
Hình 1.4.Thể hiện sơ đồ khai phá dữ liệu bằng mạng Neunon.
1.3.4.5. Giải thuật di truyền
Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống
tiến hóa trong tự nhiên, chính xác hơn đó là giải thuật chỉ ra tập các cá thể
được hình thành, được ước lựợng và biến đổi như thế nào? Ví dụ như xác
định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể
nào sẽ bị loại bỏ. Giải thuật cũng mô phỏng lại yếu tố gen trong nhiễm sắc thể
sinh học trên máy tính để có thể giải quyết nhiều bài toán thực tế khác nhau.
Giải thuật di truyền là một giải thuật tối ưu hóa. Nó được sử dụng
rất rộng rãi trong việc tối ưu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ
thuật mạng Neuron. Ví dụ như trong kỹ thuật cây quyết định, tạo luật. Như đã
đề cập ở phần trước, các luật mô hình hóa dữ liệu chứa các tham số được xác
định bởi các giải thuật phát hiện tri thức.
Giai đoạn tối ưu hóa là cần thiết để xác định xem các giá trị tham

Tích hợp khai phá dữ liệu vào trong các hệ cơ sở dữ liệu. Ứng dụng khai
phá dữ liệu để khai phá dữ liệu web trực tuyến. Một vấn đề quan trọng trong
việc phát triển khám phá tri thức và khai phá dữ liệu đó là vấn đề an toàn và
bảo mật thông tin trong khai phá dữ liệu.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
15
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
Chương 2
CÁC THUẬT TOÁN KHAI PHÁ DỮ LIỆU
DÙNG CÂY QUYẾT ĐỊNH
2.1. Cây quyết định
2.1.1. Khái niệm cây quyết định
Trong lý thuyết quyết định (chẳng hạn quản lí rủi ro), một cây quyết định
(tiếng Anh: decision tree) là một đồ thị của các quyết định và các hậu quả có
thể của nó (bao gồm rủi ro và hao phí tài nguyên). Cây quyết định được sử
dụng để xây dựng một kế hoạch nhằm đạt được mục tiêu mong muốn. Các
cây quyết định được dùng để hỗ trợ quá trình ra quyết định. Cây quyết định là
một dạng đặc biệt của cấu trúc cây.
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 một 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 một 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ị 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
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
16
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
đị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.

≤ 35
salary
> 35
salary
≤ 40 >40
bad good
≤50 >50
bad good
17
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
Có thể mô tả cây quyết định là một cấu trúc phân cấp của các nút và
các nhánh, bao gồm :
- 3 loại nút trên cây: Nút gốc; Nút nội bộ: mang tên thuộc tính của
CSDL; Nút lá: mang tên lớp Ci;
- Nhánh: mang giá trị có thể của thuộc tính.
Cây quyết định được sử dụng trong phân lớp bằng cách duyệt từ nút
gốc của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tượng cần
xét.
2.1.2. Các kiểu cây quyết định
Cây quyết định còn có hai tên khác:
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)
Cây phân loại (Classification tree): nếu y là một biến phân loại như: giới
tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua).
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 có một số ưu
điểm như sau:
- Cây quyết định tương đối dể hiểu.
- Đòi hỏi mức tiền xử lý dữ liệu đơn giả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:
Bước 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.
Bước 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á.
Bước 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á.
Bước 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ì:
+ 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
.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
19
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
+ Chia tập mẫu trong T thành các tập con T
1
, T
2
, ,T
n
. Chia theo giá trị
của X.

−

Trong trường hợp các mẫu dữ liệu có hai thuộc tính phân lớp "yes" (+), "no"
(-). Ký hiệu P
+
là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là
"yes", và P
-
là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no" trong
tập S.
Trường hợp tổng quát, đối với tập con S có n phân lớp thì ta có công thức sau:
n
i 2
i=1
Entropy(S)= (- P log ( ))
i
P
∑

Trong đó P
i
là tỷ lệ các mẫu thuộc lớp i trên tập hợp S các mẫu kiểm tra.
Các trường hợp đặc biệt:
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
20
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
- Nếu tất cả các mẫu thành viên trong tập S đều thuộc một lớp thì
Entropy(S) =0
- Nếu trong tập S có số mẫu phân bổ đều nhau vào các lớp thì
Entropy(S) =1

( , ) Information(A) - Entropy(A)= Entropy(S)- Entropy(S )
S
Gain S A
∉
=
∑

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
v
| là số phần tử của tập S
v
.
 |S| là số phần tử của tập S.
Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi bước
triển khai cây, thuộc tính được chọn để triển khai là thuộc tính có giá trị Gain
lớn nhất.
2.2.2.3. Hàm xây dựng cây quyết định trong thuật toán ID3
Function induce_tree(tập_ví_dụ, tập_thuộc_tính)
begin
if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then
return một nút lá được gán nhãn bởi lớp đó
else if tập_thuộc_tính là rỗng then
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
21

và và làm việc được với tập dữ liệu bị thiếu và bị nhiễu. Nó thực hiện phân
lớp tập mẫu dữ liệu theo chiến lược ưu tiên theo chiều sâu (Depth - First).
Thuật toán xét tất cả các phép thử có thể để phân chia tập dữ liệu đã cho và
chọn ra một phép thử có giá trị GainRatio tốt nhất. GainRatio là một đại
lượng để đánh giá độ hiệu quả của thuộc tính dùng để thực hiện phép tách
trong thuật toán để phát triển cây quyết định.
GainRatio được tính dựa trên kết quả tính toán đại lượng Information
Gain theo công thức sau:
( , )
( , )
(X,T)
Gain X T
GainRation X T
SplitInfo
=

HVTH: Phạm Ngọc Giàu – CH1101080 Trang
22
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
Với:
i i
2
i Value(X)
|T | |T |
info(X,T) = - log
| | | |
Split
T T
∉
∑

23
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
<Gán nút con này của nút N là nút lá>;
Else
<Gán nút con này là nút được trả về bằng cách gọi đệ qui lại đối
với hàm xay_dung_cay(T'), với tập T'>;
}
<Tính toán các lỗi của nút N>;
<Trả về nút N>;
}
Một số công thức được sử dụng:
n
i
x i
i=1
T
Info (T)=- *Info(T )
T
∑
X
( ) Info(T)-Info ( )Gain X T=
(*)
Công thức (*) được sử dụng làm tiêu chuẩn để lựa chọn thuộc tính khi
phân lớp. Thuộc tính được chọn là thuộc tính có giá trị Gain tính theo (*) đạt
giá trị lớn nhất.
2.2.3.2. Một số cải tiến của thuật toán C4.5:
2.2.3.2.1 Làm việc với thuộc tính đa trị
Tiêu chuẩn (*) có một khuyết điểm là không chấp nhận các thuộc
tính đa trị. Vì vậy thuật toán C4.5 đã đưa ra các đại lượng GainRatio và
SplitInfo (SplitInformation), chúng được xác định theo các công thức sau:

Giá trị SplitInfo là đại lượng đánh giá thông tin tiềm năng thu thập
được khi phân chia tập T thành n tập hợp con.
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
24
Thu hoạch Môn Công nghệ tri thức và ứng dụng GVHD: GS. TS Hoàng Văn Kiếm
GainRatio là tiêu chuẩn để đánh giá việc lựa chọn thuộc tính phân loại.
2.2.3.2.2 Làm việc với dữ liệu bị thiếu
Thuật toán vừa xây dựng dựa vào giả thuyết tất cả các mẫu dữ liệu có
đủ các thuộc tính. Nhưng trong thực tế, xẩy ra hiện tượng dữ liệu bị thiếu, tức
là ở một số mẫu dữ liệu có những thuộc tính không được xác định,hoặc mâu
thuẫn, hoặc không bình thường. Ta xem xét kỹ hơn với trường hợp dữ liệu bị
thiếu. Đơn giản nhất là không đưa các mẫu với các giá trị bị thiếu vào, nếu
làm như vậy thì có thể dẫn đến tình trạng thiếu các mẫu học. Giả sử T là một
tập hợp gồm các mẫu cần được phân loại, X là phép kiểm tra theo thuộc tính
L, U là số lượng các giá trị bị thiếu của thuộc tính L. Khi đó ta có:
k
j
2
j=1
freq(C ,T) ( , )
Info(T) = - *log
|T|-U | |
j
freq C T
T U
 
 ÷
−
 
∑

2
,….O
n
được lựa chọn theo tiểu
chuẩn (****), ta cần xử lý như thế nào với các dữ liệu bị thiếu. Giả sử mẫu từ
tập hợp T với đầu ra là Oi có liên quan đến tập hợp Ti thì khả năng mẫu đó
thuộc tập hợp Ti là 1.
Giả sử mỗi mẫu trong T
i
có một chỉ số xác định xác suất thuộc tập hợp
T
i
. Nếu mẫu có giá trị thuộc tính L thì có trọng số bằng 1. Nếu trong trường
hợp ngược lại, thì mẫu này liên quan đến tập con T
1
,T
2
,…T
n
với xác xuất
tương ứng là :
1 2
, , ,
| | | | | |
n
T T T
T U T U T U− − −
HVTH: Phạm Ngọc Giàu – CH1101080 Trang
25