ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
ĐỀ TÀI: ỨNG DỤNG NAÏVE BAYESIAN TRONG
KHAI PHÁ DỮ LIỆU – PHÂN LỚP EMAIL
GVHD : PGS. TS. Đỗ Phúc
Thực hiện: Vưu Văn Tòng - CH1101146
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
Thành phố Hồ Chí Minh - Tháng 10 Năm 2012LỜI MỞ ĐẦU
Trong thời đại ngày nay, nhân tố quan trọng quyết định sự thành công chính là
kỷ năng phân tích đánh giá, tìm ra cái mới từ những dữ liệu tưởng chừng như vô
nghĩa. Hay nói chính xác hơn đó là kỷ năng nắm bắt và khai thác thông tin hiệu
quả từ những dữ liệu có sẵn.
Tuy nhiên, vấn đề đặt ra là: làm cách nào để khai thác thông tin một cách hiệu
quả nhất ? Làm cách nào để đảm bảo độ chính xác của thông tin đã khai phá
được ? Làm cách nào có thể áp dụng quá trình khai phá đó vào một lĩnh vực cụ
thể ?
Để giải quyết các vấn đề trên, lĩnh vực nghiên cứu mới “khám phá tri thức” được
ra đời. Nhiệm vụ cơ bản của “khám phá tri thức” là tìm ra những tri thức, những
thông tin hữu ích trong cơ sở dữ liệu. “Khám phá tri thức” không có nghĩa là một
quá trình tự động hoàn toàn mà là sự tương tác giữa người dung và cơ sở dữ liệu
bằng cách sử dụng các công cụ trong toán học và tin học.
Nội dung của bài thu hoạch em xin trình bày gồm bốn chương:
Chương 1: giới thiệu chung về lĩnh vực “khám phá tri thức”, các khái niệm cơ
bản, các phương pháp được áp dụng để khai phá dữ liệu – một bước quan trọng
trong khám phá tri thức
Chương 2: tìm hiểu về bộ phân lớp Naïve Bayesian
Chương 3: ứng dụng bộ phân lớp Naïve Bayesian để phân lớp email
Chương 4: những hạn chế và hướng phát triển
Em xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS. Đỗ Phúc – người đã hướng dẫn

Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
DANH SÁCH HÌNH
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
DANH SÁCH BẢNG
Khai phá dữ liệu và kho dữ liệu

•
Nhận dạng vấn đề
•
Định nghĩa vấn đề

•
Thu thập dữ liệu
•
Tiền xử lý dữ liệu

•
Khai phá dữ liệu
•
Tách tri thức

•
Làm rõ tri thức
•
Đánh giá tri thức

•
Sử dụng tri thức
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email

trong dữ liệu thì chúng ta có thể dùng nó kết hợp với một số dữ liệu đầu vào để sinh ra
dữ liệu gần như nguyên gốc (mức độ tùy thuộc vào độ tin cậy của mô hình). Một mô
hình có thể là một cấu trúc “nếu…thì…” đơn giản. Ví dụ: xét cơ sở dữ liệu lưu lại
thông tin của những nhà khoa học (cá nhân) đã đoạt giải Nobel thì người ta rút ra quy
luật rằng: nếu là nam, đã kết hôn, khoảng 61 tuổi và sinh vào mùa xuân, đã từng học
đại học Harvard và không mang kính thì tỷ lệ đoạt giải Nobel là cao nhất (nguồn:
)
Bước 4: làm rõ và đánh giá tri thức. Việc làm rõ tri thức nghĩa là chuyển những
“mẫu” hay “mô hình” đã tìm được ở bước 3 sang dạng “mô tả được và dự đoán được”
– 2 mục tiêu quan trọng của tiến trình khám phá tri thức. Trong khi đánh giá tri thức
nhằm kiểm tra mức độ chính xác của tri thức. Thông thường, người ta chia tập dữ liệu
ban đầu thành hai phần: tập huấn luyện và tập kiểm tra. Sau đó, thực hiện quá trình
đánh giá nhiều lần dựa trên mức độ chia khác nhau và lấy trung bình kết quả của những
lần chia đó. Ví dụ: lần đầu, ta chia theo tỷ lệ huấn luyện/kiểm tra là 60/40, lần hai, chia
theo 70/30…
Bước 5: sử dụng những tri thức được khám phá vào thực tế. Thực tế ở đây không
có nghĩa là phải liên quan đến máy vi tính. Vì có một số người sử dụng những tri thức
này vào cuộc sống và một số người lại đặt những tri thức này vào máy tính để dung các
chương trình khám phá. Bước này là đích đến lớn nhất của tất cả tiến trình khám phá
tri thức.
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
1.3. Các phương pháp khai phá dữ liệu
Hình dưới đây thể hiện một mảng 2 chiều của dữ liệu chứa 23 mẫu. Mỗi chấm thể
hiện một người nào đó đã từng được ngân hàng cho vay trong quá khứ. Màu khác nhau
của mỗi chấm là một sự phân lớp thể hiện khoản vay của người đó trong tình trạng tốt
hay xấu (nợ khó đòi).

Debt
Income

Hình 4: Ví dụ về cây quyết định
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
 Luật:
- Các luật được tạo ra nhằm suy diễn các mẫu dữ liệu có ý nghĩa về mặt
thống kê
- Dạng của luật là nếu P thì Q, trong đó P là mệnh đề kiểm chứng được
trong cơ sở dữ liệu và Q là mệnh đề kết quả (dự đoán).
- Ví dụ: nếu giảm giá sản phẩm còn 2.900 đồng từ 3.000 đồng thì sức
mua sẽ tăng thêm 30%.
- Những luật được sử dụng rộng rãi trong các hệ chuyên gia vì chúng
đơn giản, dễ hiểu.
 Giải thuật di truyền
- Dựa trên sự tương tự của tiến hóa trong sinh học
- Mỗi luật được thể hiện bằng một chuổi các bit
- Một quần thể ban đầu được tạo dựa trên những luật ngẫu nhiên. Ví
dụ: nếu A1 và không phải là A2 thì C2 có thể được thể hiện bằng
chuỗi 100 (trong đó A1, A2 là các mệnh đề)
- Dựa trên quan niệm về sự tồn tại, một quần thể mới được tạo thành từ
các con của quần thể ban đầu và các quy tắc thích hợp nhất.
 Tập thô
- Tập thô dùng để định nghĩa lớp một cách gần đúng
- Một tập thô cho một lớp C nào đó được xấp xỉ bởi hai tập hợp: xấp xỉ
dưới (chắc chắn thuộc C) và xấp xỉ trên (không thể nói là không thuộc
C)
- Ma trận phân biệt được xử dụng để tìm tập tối tiểu các thuộc tính
(dung để rút gọn thuộc tính)
Ngoài ra, còn có các kỹ thuật khác như: tập mờ, mạng Bayes, mạng nơ-ron…
được dung trong phương pháp phân lớp.
Gom cụm: trong khi phân lớp dữ liệu là tìm lớp mà đối tượng đó thuộc về, gom

Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
Ta thấy rằng, hễ có bánh mì xuất hiện trong một hóa đơn nào đó thì bơ cũng xuất
hiện trong hóa đơn đó. Điều này dẫn tới một luật kết hợp đơn giản: “Bánh mì”  “bơ”.
Trong tìm luật kết hợp có hai đại lượng cần chú ý là độ hỗ trợ (ký hiệu:
support(AB)) và độ tin cậy (ký hiệu: confidence(AB)). Giả sử, ta xét luật: “Bánh
mì”  “bơ” thì độ hỗ trợ là số dòng chứa cả “bánh mì” và “bơ” trên tổng số dòng
trong cơ sở dữ liệu (2/3 = 66.6%) còn độ tin cậy là số dòng chứa cả “bánh mì” và “bơ”
trên tổng số dòng có chứa bánh mì (2/2 = 100%)
Một luật kết hợp là hợp lệ khi thỏa mãn cả minsupport (độ hỗ trợ nhỏ nhất) và
minconfidence (độ tin cậy nhỏ nhất). minsupport và minconfidence được cung cấp bởi
người dùng tùy vào lĩnh vực và kinh nghiệm.
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
2. BỘ PHÂN LỚP NAÏVE BAYESIAN
2.1. Cơ sở lý thuyết về xác suất
Sự độc lập về xác suất
Giả sử ta có 2 sự kiện:
F1: cô A đang dạy
F2: trời đang nắng
Ta thấy rằng, việc trời nắng hay mưa không phụ thuộc vào việc cô A có đang dạy
hay không. Vậy hai sự kiện xảy ra là độc lập với nhau.
Gọi P(F1) là xác suất xảy ra sự kiện F1, P(~F1) là xác suất không xảy ra F1
Tương tự, P(F2) là xác suất xảy ra sự kiện F2, P(~F2) là xác suất không xảy ra F2
Và P(F2|F1) là xác suất xảy ra F2 khi đã biết F1. Ta có các công thức:
Hai sự kiện được gọi là độc lập với nhau khi xác suất xảy ra một sự kiện luôn
không đổi cho dù sự kiện còn lại có xảy ra, không xảy ra hay thậm chỉ không biết rõ.
Xác suất có điều kiện
Giả sử có 2 sự kiện:
F1: đau đầu
F2: bị cảm

3 40 Thap Co G Khong
4 35 Trung binh Khong F Co
5 45 Thap Khong F Co
6 35 Cao Khong E Co
7 35 Trung binh Khong G Khong
8 25 Thap Khong G Khong
9 28 Cao Khong A Khong
10 35 Trung binh Co A Co
Bảng 1: Dữ liệu mẫu cho suy diễn Bayes
Giả sử, chúng ta biết được thông tin của một người như sau: “người đó 35 tuổi và
có mức thu nhập trung bình”. Hỏi rằng, ông ta có mua máy tính hay không ?
Áp dụng lý thuyết về Bayes, ta có công thức như sau:
Trong đó:
D: tập các điều kiện giả thuyết
h: một giá trị của tập kết quả
P(h): xác suất xảy ra sự kiện h
P(D): xác suất các sự kiện điều kiện xảy ra cùng lúc
P(D|h): xác suất các sự kiện điều kiện xảy ra khi h xảy ra
P(h|D): xác xuất h xảy ra khi các điều kiện D đã xảy ra  kết quả
Giả sử h có hai giá trị như trong ví dụ trên h1=“Co” hoặc h2=“Khong”. Tính
xác suất xảy ra cho hai trường hợp của kết quả như sau:
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
P(D) = xác suất một người 35 tuổi có mức thu nhập trung bình = 4/10 (người số
1,4,7 và 10)
P(D|h1) = xác suất một người 35 tuổi, mức thu nhập trung bình CÓ mua máy
tính = 3/5
P(h1) = xác suất để một người nào đó (không quan tâm tới tuổi, thu nhập…) CÓ
mua máy tính = 5/10 (số lượng ô “Co” trong cột Mua_May_Tinh)
P(D|h2) = xác suất một người 35 tuổi, mức thu nhập trung bình KHÔNG mua

P(C
i
|X) > P(C
j
|X) với
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
3. ỨNG DỤNG NAÏVE BAYESIAN TRONG PHÂN LỚP EMAIL
3.1. Giới thiệu ứng dụng
Trong thời đại ngày nay, email và internet là công cụ trao đổi chính, nó giúp
chúng ta có thể trao đổi, giao dịch với những người cách xa chúng ta cả vòng trái đất.
Tuy nhiên, trong cái lợi cũng có cái hại đó là với lượng email khổng lồ mà một
người nhận được hàng ngày có bao nhiêu email là mong muốn và thực sự có giá trị?
Có bao nhiêu email là công việc gấp? Những con số này chỉ được biết khi người dùng
đọc từng email và phân loại bằng tay.
Rõ ràng, việc phân loại thực hiện trên một số lượng khổng lồ email không phải là
việc dễ dàng, vừa tốn thời gian, công sức…
Do đó, một số công cụ tự động đã được ra đời để giúp người dùng phân loại
email nhận được, giúp giảm đi những phiền toái mà quá trình phân lớp bằng tay gây ra.
Công cụ phân loại như vậy trong ngữ cảnh của khai phá dữ liệu được gọi là một bộ
phân lớp và Naïve Bayesian là một bộ phân lớp tiêu biểu như vậy.
Chúng ta có thể để ý rằng, thật ra việc phân lớp email có thể dựa vào tiêu đề hoặc
nội dung email. Có nghĩa là, bộ phân lớp hoạt động dựa trên việc phân tích tiêu đề, nội
dung của email để biết được một email thuộc loại gì: công việc, spam, du lịch…Mà
tiêu đề hay nội dung email lại là những đoạn văn bản. Như vậy, công việc phân lớp
email lại đưa về bản chất của một loại khai phá dữ liệu đó là khai phá văn bản (text
mining)
Trong phạm vi bài thu hoạch này, em xin trình bày quá trình cài đặt bộ phân lớp
Naïve Bayesian đơn giản để phân lớp văn bản (email).
3.2. Môi trường và tài nguyên

o Mã hóa mỗi mẫu trong training data thành một vector có giá trị
nhị phân dựa trên túi từ. Ví dụ: túi từ có 5 từ thì vector có 5
chiều, mỗi chiều nhận các giá trị 0 (từ tương ứng trong túi từ
không xuất hiện trong mẫu) hoặc 1 (từ tương ứng trong túi từ
xuất hiện trong mẫu)
o Tạo thành file trong thư mục models để lưu lại cấu trúc đã học
được
Một số yêu cầu về training data cung cấp cho hệ thống:
- Mỗi mẫu dữ liệu được viết trên một dòng duy nhất
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
- Lớp của mẫu là một từ đầu tiên trong cùng dòng của mẫu dữ liệu.
- Các mẫu cách nhau bởi dấu xuống dòng trong window (\r\n).
Ví dụ:
SPAM Register account and get 100$ free
JOB We are pleasure to offer you the position of software engineer
Chữ in đậm là lớp của mẫu.
Giao diện huấn luyện trong ứng dụng như sau:
Hình 6: Giao diện huấn luyện
Khai phá dữ liệu và kho dữ liệu

 !"#$
%#&
'()*+,
#/01/23#
4567869
-:;<=
>67*/6?
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
3.3.2.2. Thành phần dùng để phân lớp

-::;
>67*/6?
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
Hình 8: Huấn luyện hệ thống
Mô hình được lưu dưới tên là sampletest.
Sau đó, qua test mode để thực hiện việc phân lớp cho một mẫu dữ liệu nào đó:
Khai phá dữ liệu và kho dữ liệu
Ứng dụng Naïve Bayesian trong khai phá dữ liệu – phân lớp email
Hình 9: Kết quả phân lớp
Kết quả thử nghiệm hệ thống đã nhận dạng đúng đoạn email đã nhập thuộc về lớp
“family”.
Em cũng đã upload ứng dụng web này lên internet để thầy và các bạn có thể chạy
thử một cách dễ dàng:
/>Khai phá dữ liệu và kho dữ liệu
@:KC6*:
LD6E"!F!M.#/
68(N!O#1
#/!F!
P;