Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
1
LỜI CẢM ƠN

Em xin chân thành cảm ơn Thầy, Tiến sĩ Nguyễn Đình Thuân đã tận
tình hướng dẫn và giúp đỡ, cung cấp cho em những ý kiến đóng góp, nhận
xét quý báu trong quá trình thực hiện đồ án này.
Em xin chân thành cảm ơn các giảng viên trong khoa Công nghệ thông
tin cũng như các giảng viên giảng dạy trong trường Đại học Đại học Nha
trang những người đã truyền thụ cho em những kiến thức quí báu trong
suốt thời gian học tập và nghiên cứu tại trường Đại học Nha trang, giúp em
có được những điều kiện cần thiết để hoàn thành tốt đồ án tốt nghiệp này.
Sự quan tâm và giúp đỡ của Bố mẹ, cùng toàn thể gia đình là một
nguồn động viên rất lớn, tạo cho con sự yên tâm về vật chất và tinh thần để
con hoàn thành nhiệm vụ của mình.
Cuối cùng xin cảm ơn sự quan tâm và đóng góp ý kiến của tất cả các
bạn. Nha Trang, ngày 10 tháng 12 năm 2007
Sinh viên thực hiện
Hứa Văn Lắm

1 CD Count Distribution
2 CSDL Cơ sở dữ liệu
3 DB Database
4 DBMS Database Management System
5 DD Data Distribution
6 DHP Direct Hashing and Puning
7 DIC Dynamic Itemset Counting
8 KDD Knowledge Discovery from Data
9 K-NN K- Nearest Neighbor
10 TID Transaction identifier
11 MAP Maximum A Posterior
12 NB Naïve Bayes
13 TREE Cây quyết định
14 ILA Inductive Learning Algorithm
15 BAYES Algorithm Bayes
16 PLDL Phân lớp dữ liệu
17 IG Information Gain
18 OOP Lập trình hướng đối tượng
19 IDE Môi trường thiết kế tích hợp
7 Transaction Một giao dịch trong cơ sở dữ liệu
8 Transaction identifier Định danh duy nhất của một giao dịch
9 Tập học
Tập hợp những bộ được dùng để xây
dựng mô hình
10 Information gain
Độ lợi thông tin là đại lượng được dùng
để chọn thuộc tính nhằm phân chia tập
học.
11 Java Là ngôn ngữ lập trình hướng đối tượng
Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp

3.6 Các lớp sử dụng trong chương trình 28
Chương 4: XÂY DỰNG GIẢI PHÁP VÀ THỬ NGHIỆM KẾT QUẢ 29
4.1. Tổng quan về hệ thống 29
4.1.1. Mô hình chung của hệ thống 32
4.1.2. Sơ đồ chức năng chương trình 29
4.1.3. Module hóa chức năng chương trình 30
4.1.4 Kiến trúc hệ thống 30
4.1.5 Mô tả chức năng 31
4.1.6 Cấu trúc dữ liệu 31
4.2. Giải pháp, cài đặt 31
4.2.1. Môi trường, công cụ, ngôn ngữ sử dụng 31
4.2.2. Lựa chọn thuật toán 32
4.2.3. Thiết kế môđun 32
4.3. Kết quả thử nghiệm và đánh giá 33
4.3.1. Giao diện chương trình: 33
4.3.2. Cơ sở dữ liệu thử 33
4.3.3. Đánh giá kết quả 34 Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
5

4.4. Thông tin rút ra từ dữ liệu thử 48
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 49
TÀI LIỆU THAM KHẢO 50



Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
6

LỜI MỞ ĐẦU

Ngày nay, cơ sở dữ liệu có kích thước lên tới Terabyte . Bên trong khối
lượng dữ liệu lớn như vậy còn ẩn chứa rất nhều thông tin quan trọng. Khai phá
dữ liệu (data mining) là một quá trình sử dụng rất nhiều công cụ phân tích dữ
liệu để phát hiện ra các mẫu và các mối quan hệ trong dữ liệu để đưa ra được
những dự đoán hiệu quả. Nhiệm vụ chính của data mining là phát hiện ra các tri
thức chưa được phát hiện hay còn ẩn chứa trong tập dữ liệu lớn.
Những tiến bộ gần đây trong việc thu thập và lưu trữ dữ liệu đã được áp
dụng trong các công ty (kỹ thuật mã vạch), các cơ quan hành chính (dữ liệu
điều tra) hay các phòng thí nghiệm khoa học (CSDL phân tử trong hoá học hay
sinh học) để lưu giữ được một lượng lớn các dữ liệu liên quan đến hoạt động
của các tổ chức này. Cùng thời gian này, khả năng dùng nguồn năng lượng tính

Chương 4: Xây dựng giải pháp và thử nghiệm kết quả với các thuật toán
phân lớp dữ liệu đã cài đặt.
Kết luận: Nêu ra các nhận xét, kết quả đạt được và một số phương hướng
phát triển tiếp theo của đề tài.
mẫu hay mô hình đáng quan tâm có trong CSDL nhưng đang ẩn dấu trong một
lượng lớn dữ liệu.
1.1. Các bước của quá trình khai phá dữ liệu
Các giải thuật khai phá dữ liệu thường được miêu tả như những chương
trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp máy học và
thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp
dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan
đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được.
Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó
có thể chiết suất dữ liệu ra các tệp đơn giản để phân tích được.
Quá trình xử lý khai phá dữ liệu bắt đầu bằng cách xác định chính xác vấn
đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng
giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng
thành dạng sao cho các giải thuật khai phá dữ liệu có thể hiểu được. Về lý Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
9

thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá
trình rất khó khăn, gặp phải nhiều vướng mắc như : các dữ liệu phải được sao
ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải
lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi),
Sẽ là quá cồng kềnh với một giải thuật khai phá dữ liệu nếu phải truy
nhập vào toàn bộ nội dung của CSDL và làm những việc như trên. Vả lại, điều
này cũng không cần thiết. Có rất nhiều giải thuật khai phá dữ liệu thực hiện
trên những thống kê tóm tắt khá đơn giản của CSDL, khi mà toàn bộ thông tin
trong CSDL là quá dư thừa đối với mục đích của việc khai phá dữ liệu.
Bước tiếp theo là chọn thuật toán khai phá dữ liệu thích hợp và thực hiện

Xác định
dữ liệu
liên quan

Thu thập
và tiền
x
ử lý dữ
Dữ liệu
tr
ực tiếp

Thống
kê tóm
Giải
thuật
khai phá
Mẫu Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
10

một mô tả xu hướng, có thể dưới dạng văn bản, một đồ thị mô tả các mối quan
hệ trong mô hình, cũng có thể là một hành động, ví dụ như yêu cầu của người
dùng đối với những gì khai thác được trong CSDL.
Kỹ thuật khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết
hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như máy
học, nhận dạng, thống kê (hồi quy, xếp loại, phân nhóm), các mô hình đồ thị,

• Khai phá luật kết hợp (Association Rule): tìm ra các large
itemset, các mối liên quan, kết hợp và cấu trúc nhân quả trong tập Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
11

các khoản mục hay đối tượng trong CSDL giao dịch, CSDL quan hệ
hay từ các kho lưu trữ thông tin khác.
• Tóm tắt (Summarization) : Liên quan đến các phương pháp tìm
kiếm một mô tả tóm tắt cho một tập con dữ liệu.
• Mô hình hoá phụ thuộ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ô
hình xác định (thường ở dạng đồ hoạ) các biến nào là phụ thuộc cục
bộ với nhau, mức định lượng của một mô hình xác định độ mạnh
của sự phụ thuộc theo một thước đo nào đó.
• Phát hiện sự thay đổi và lạc hướng (Change and Deviation
Detection): Tập trung vào khai thác những thay đổi đáng kể nhất
trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó.
Những nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin
rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật
khai phá dữ liệu khác nhau.

1.3. Khai phá dữ liệu mô tả
1.3.1. Phân nhóm
Cân nhắc việc nhóm tập các đối tượng dựa trên độ tương đồng của chúng
với các thuộc tính và/ hoặc trạng thái gần kề của chúng trong một không gian
véctơ. Phân nhóm dữ liệu Error! Reference source not found., [4] được gọi

SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
12

Bài toán có ứng dụng rất nhiều trong phân nhóm tài liệu, phân nhóm thuật
ngữ.
Các thuật toán chính của bài toán phân nhóm là K-means, thuật toán phân
nhóm bậc tích luỹ.
Không nên nhầm lẫn phân nhóm với phân đoạn. Phân đoạn liên quan tới bài
toán chỉ ra các nhóm có đặc điểm chung. Phân nhóm là cách phân dữ liệu
vào các nhóm chưa được định nghĩa trước, còn phân loại sẽ phân dữ liệu
vào thành các nhóm đã định nghĩa trước.

1.4. Khai phá dữ liệu dự đoán
Trước khi xây dựng được mô hình dự đoán hiệu quả, ta cần phải hiểu dữ
liệu. Mục tiêu của khai phá dữ liệu là tìm ra những tri thức ẩn chứa bên trong
dữ liệu. Nhờ xây dựng một mô hình thức tế dựa trên tập hợp dữ liệu từ nhiều
nguồn khác nhau gồm cả dữ liệu kinh doanh, thị hiếu khách hàng, thông tin
nhân khẩu, điều khiển dữ liệu và các cơ sở dữ liệu mở rộng có liên quan như
thông tin thời tiết, thông tin văn phòng. Kết quả của việc xây dựng mô hình là
một bản mô tả các mẫu và mối quan hệ dữ liệu có thể hỗ trợ cho việc dự đoán.
Để tránh khó hiểu trong các khía cạnh khác nhau của khai phá dữ liệu, cần đưa
ra cấu trúc công việc cần thực hiện cho quá trình dự đoán
• Mục tiêu công việc
• Kiểu dự đoán
• Kiểu mô hình
• Thuật toán
Mức cao nhất cần quan tâm là công việc nhằm mục đích gì. Như tìm kiếm
các mẫu trong dữ liệu kinh doanh để dự đoán đối tượng khách hàng sẽ thu được
lợi nhiều nhất. Quyết định kiểu dự đoán phù hợp nhất: phân loại hay hồi quy.
Kiểu mô hình: mạng noron cho bài toán hồi quy hay một cây quyết đinh cho

Có 80% khách hàng mua Ao thun Việt Tiến, mua bóng Động lực thì sau
3 ngày mua quần Việt Tiến.
Nhờ mẫu tuần tự, có thể khám phá các xu thế phát triển hành vi của đối tượng.
1.5.3 Phân lớp dữ liệu: là tiến trình khám phá các luật phân loại hay đặc
trưng cho các tập dữ liệu đã được xếp lớp. Tập dữ liệu học bao gồm tập đối
tượng đã được xác định lớp sẽ được dùng để tạo mô hình phân lớp dựa trên đặc
trưng của đối tượng trong tập dữ liệu học. Các luật phân lớp được sử dụng để
xây dựng các bộ phân lớp dữ liệu. Phân lớp dữ liệu có vai trò quan trọng trong
tiến trình dự báo các khuynh hướng quy luật phát triển. Áp dụng vào tiến trình
phân lớp dữ liệu khách hàng trong CSDL có thể xây dựng các luật phân lớp
khách hàng. Một luật phân lớp có dạng tiêu biểu sau:
Nếu khách hàng ở khu vực 1 và có doanh số năm trước > 200 triệu và
có cửa hàng ở khu thị tứ thì thuộc loại khách hàng có thể giao hàng
trước trả tiền sau
1.5.4 Khai thác cụm: là tiến trình nhận diện các cụm tiềm ẩn trong tập các
đối tượng chưa được xếp lớp. Tiến trình khai thác cụm dựa trên mức độ tương
tự giữa các đối tượng. Các đối tượng được gom cụm sao cho mức độ tương tự
giữa các đối tượng trong cùng một cụm là cực đại và mức độ tương tự giữa các
đối tượng nằm trong các cụm khác nhau là cực tiểu. Các cụm được đặc trưng
bằng các tính chất chung của tất cả các đối tượng trong cụm. Do vậy, khảo sát
các cụm sẽ giúp khái quát, tổng kết nhanh chóng nội dung của khối dữ liệu lớn.
1.6 Những thách thức trong KTDL
KTDL phải làm việc với khối lượng dữ liệu lớn và do từ nhiều nguồn khác
nhau(CSDL, Internet, các loại thiết bị thu nhận tín hiệu, các loại thiết bị nhận
dạng, các loại thiết bị lưu trữ như băng từ, CD…) nên vấn đề tốc độ xử lý là
vấn đề quan tâm trước nhất. Có hai phương hướng để giải quyết vấn đề này là
nâng cao năng lực của phần cứng và cải tiến phần mềm, trong đó việc nghiên
cứu đề xuất các thuật toán hiệu quả có khả năng làm việc trên khối lượng dữ
liệu lớn, và có độ phức tạp tính toán thấp là một hướng nghiên cứu đầy tiềm
năng. Từ nhu cầu thực tế trên, gần đây đã xuất hiện nhiều ngành khoa học công

định hoặc là công thức toán học 2.1.2 Vận hành mô hình: nhằm mục đích xác định lớp của dữ liệu trong
tương lai hoặc phân lớp những đối tượng chưa biết. Trước khi vận hành mô
hình cần đánh giá độ chính xác của mô hình trong đó các mẫu kiểm tra (đã biết
được lớp) được đem so sánh với kết quả phân lớp của mô hình. Độ chính xác là
phần trăm của số mẫu kiểm tra được phân lớp đúng. Lưu ý tập kiểm tra và tập
học là hai tập độc lập với nhau.
Dữ liệu huấn
luy
ện

Bộ phân lớp
(Mô hình)

2.2 Phân lớp quy nạp trên cây quyết định:
Cây quyết định gồm các nút trong biểu diễn giá trị thuộc tính, các nhánh
biểu diễn đầu ra của kiểm tra, nút là biểu diễn nhãn lớp. Cây quyết định được
tạo theo hai giai đoạn là tạo cây và tỉa nhánh.
Trong giai đoạn tạo cây, lúc bắt đầu tất cả các mẫu học đều nằm ở nút
gốc, sau đó các mẫu học được phân chia một cách đệ quy dựa trên thuộc tính
được chọn. Bước tỉa nhánh nhằm tìm và xóa những nhánh có phần tử không thể
xếp vào lớp nào cả.
Bước vận hành nhằm kiểm tra những giá trị thuộc tính của mẫu đối với
các giá trị trên nhánh của cây quyết định.
Thuật toán tạo cây quyết định bao gồm các bước sau:
Bước 1: Cây được xây dựng đệ quy từ trên xuống và theo cách chia để trị
Bước 2: Ban đầu tất cả mẫu học đều nằm ở gốc.
Bước 3: Thuộc tính được phân loại(nếu là giá trị liên tục được rời rạc hóa)
Bước 4: Các mẫu học được phân chia đệ quy dựa trên thuộc tính chọn lựa
Bước 5: Kiểm tra những thuộc tính được chọn dựa trên heristic hoặc của một
tiêu chuẩn thống kê.
Điều kiện để dừng phân chia tập học:
1. Tất cả những mẫu học đối với một nút cho trước đều cùng lớp.
2. Không còn thuộc tính nào để phân chia tiếp:
3. Không còn mẫu học.
Độ lợi thông tin (ìnormation gain) là đại lượng được dùng để chọn thuộc
tính nhằm phân chia tập học. Thuộc tính được chọn là thuộc tính có độ lợi
thông tin lớn nhất.


K
ết quả

Hình 2.2 V
ận h
ành mô hình

TRỜI ÁP SUẤT GIÓ KẾT QUẢ
Trong Cao Nam Không mưa
Mây Thấp Nam Không mưa
Mây Trung bình Bắc Mưa
Trong Cao Bắc Không mưa
Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
16

Giả sử thuộc tính A được chọn để phân hoạch S thành các tập hợp { S
1
,S
2
…
S
v
, }. Nếu S
i
chứa p

Thuật toán ID3 là một thuật toán học trên cây quyết định được phát triển
bởi Ross Quinlan(1983). Ý tưởng cơ bản của thuật toán ID3 là tạo cây quyết
định bằng việc sử dụng cách tiềm kiếm từ trên xuống trên tập học. Độ lợi thông
tin được sử dụng để chọn thuộc tính có khả năng phân loại tốt nhất. Thuật toán
ID3 được trình bày sau đây:
Thuật toán ID3(S, D, A)
Vào: Tập học S: thuộc tính quyết định D, tập thuộc tính A
Ra: Nút gốc của cây_quyết định
Begin
- Tạo “Nút_gốc” cho cây quyết định
- If tất cả mẫu học của S đều có giá trị của D là P, trả về cây có
một nút duy nhất là nút_gốc với nhãn “P”
- If tất cả mẫu học của S đều có giá trị của D là N, trả về cây có
một nút duy nhất là nút_gốc với nhãn “N”
- If A là rỗng, trả về cây có nút duy nhất là nút_gốc với nhãn là
trị phổ biến nhất của D trong tập mẫu.
- Else Begin
• Gọi X là thuộc tính của A phân lớp S tốt nhất// tính độ
lợi
• Gán X vào thuộc tính quyết định D của nút_gốc
• For each trị v của X
+ Thêm một nhánh cây mới dưới nút_gốc ứng với X=v
+ Gọi S
v
là tập con của v trị của X là v
+ If S
v
là rỗng
_ Thêm dưới nhánh mới này, một nút là có nhãn là
trị phổ biến nhất của thuộc tính quyết định trong S

i
)
Nắng 2 3 0,971
U ám 4 0 0
Mưa 3 2 0,971
Ta có:
E(Thờitiết)=
Nên Gain(Thờitiết)= I(9,5) –E (Thờitiết)= 0,246
Gain(Nhiệtđộ)=0,029;
Gain(Độẩm)=0,151;
Gain(Gió)=0,048.
Bảng 2.1: Tập dữ liệu học “Chơi tennis”
Thời tiết Nhiệt độ Độ ẩm Gió Lớp
Nắng Nóng Cao Không

N
Nắng Nóng Cao Không

N
U_ám Nóng Cao Không

P
Mưa Ấm_ áp Cao Không

P
Mưa Mát Vừa Không

P
Mưa Mát Vừa Có N
U_ám Mát Vừa Có P

Thời tiết
Gió Độ ẩm
P

N

P

N

P

mưa U ám Nắng
cao

Vừa có không
Hình 2.3. Cây quyết định Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
18

Rút luật từ cây quyết định:
- Mỗi một đường dẫn từ gốc đến là trong cây tạo thành một luật
- Mỗi cặp giá trị thuộc tính trên một đường dẫn tạo nên một sự
liên kết
- Nút lá giữ quyết định phân lớp dự đoán.
- Các luật tạo được dễ hiểu hơn các cây


những bản ghi có những giá trị thuộc tính chưa biết bằng việc ước lượng xác
suất những kết quả có khả năng xảy ra. Trong ví dụ chơi tennis, nếu có một bản
ghi chưa biết giá trị của thuộc tính Độẩm, nhưng biết giá trị của thuộc tính
Thờitiết là Nắng ta xử lý như sau.
Di chuyển từ nút gốc Thời tiết đến nút Độ ẩm theo cạnh được đánh nhãn
là Nắng. Lưu ý nếu thuộc tính Độẩm có giá trị 75 thì có 2 bản ghi, nếu thuộc
tính Độ ẩm có trị lớn hơn 75 thì có 3 bản ghi. Do vậy có thể đưa ra câu trả lời
Thời tiết
Gió Độ ẩm
P

N

P

N

P

mưa U ám Nắng
cao

Vừa có không
Hình 2.4. Rút luật từ Cây quyết định Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
19


quyết định được thực hiện bằng cách biến cây con thành nút lá. Công việc này
được thực hiện tại nơi nếu lỗi phân lớp do cây con sinh ra lớn hơn nút lá.
Winston đã giới thiệu cách dùng phép thử Fisher để xác định thuộc tính phân
loại có thực sự phụ thuộc vào các thuộc tính khác hay không. Nếu điều này
không xảy ra thì thuộc tính đó không cần phải xuất hiện trong đường đi hiện tại
của cây quyết định. Quninlan và Breiman đề xuất những heuristic phức tạp để
rút gọn cây quyết định. Từ mỗi đường đi từ gốc đến lá trong cây quyết định, ta
dễ dàng tạo ra vế trái của luật phân lớp dựa trên nhãn của các nút và nhãn của
các các cung.
2.2.2. Phân lớp với chỉ số Gini.
Tương tự như độ lợi ở trên. IBM trong phần mềm IBM Intelligent Miner
đã đưa ra đại lượng cho việc phân lớp là chỉ số Gini như sau.
Nếu một tập dữ liệu T chứa những mẫu từ n lớp, chỉ số Gini, gini(T) được định
nghĩa như sau:
Gini(T)= 1-
∑
=
n
j
j
p
1
2

Với p
j
là tần số liên quan của lớp j trong T.
Nếu một tập hợp dữ liệu T được chia thành hai tập con T
1
và T
Cài đặt một số thuật toán phân lớp dữ liệu GVHD: T.S Nguyễn Đình Thuân
SVTH: Hứa Văn Lắm Đồ án tốt nghiệp
20

2.3 Phương pháp phân lớp Bayes
2.3.1. Sự phân hoạch và công thức Bayes
Cho H
1
, H
2
, …H
n
là một phân hoạch không gian mẫu M và A là biến cố
bất kỳ trong M. Ta có:
P(A)=
∑
=
n
i
H
H
A
PP
1
1
1
)()(


Định lý Bayes: Cho H
1
, H
2
, …H
n
là một phân hoạch không gian mẫu và A là
biến cố trong M. Khi đó với mọi i=1, 2, …,n ta có:
P(H
i
/A)=
∑
=
n
k
k
k
i
i
H
H
H
H
A
PP
A
PP
1
)()(
)()(

cho thể hiện mới. Chữ
MAP viết tắt của cụm từ Maximum A Posterior.
V
MAP
= max P(v
i
, a
1
, a
2
,… a
n
)
Sử dụng định lý Bayes, ta có:
V
MAP
=
), ,(
)|, ,()(
max
21
121
a
a
a
vaaav
n
ni
V
P

1
, a
2
,… a
n
) ta giả thuyết ban đầu các thuộc tính là độc lập
nhau. Nói cách khác, xác suất của một thể hiện quan sát được <a
1
, a
2
,… a
n
>
trên mỗi lớp v
j
là tích các khả năng của từng thuộc tính riêng biệt trên v
j
.
P(a
1
, a
2
,… a
n
|v
i
) =
∏
i
ii

Bộ phân lớp Bayes liên quan đến bước học trong đó P(v
j
) và P(a
1
, a
2
,… a
n
)
được tính dựa trên tập học.
Để phân lớp, ta dùng công thức:
V
NB
=
max
V
v
i
∈
P(
v
i
)
∏
i
ii
v
a
P )|(
Với ví dụ ở bảng 2.1 ta có thể tính các xác suất sau:

Ví dụ 2.3: Với ví dụ play-tennis ở bảng 2.1 ở trên : phân lớp X. Cho mẫu chưa
được thấy như sau X=<mưa, nóng, cao, không>
• Phân lớp X:
* một mẫu chưa gặp X=<mưa, nóng, cao, không>
* P(X | p). P(p)= P(mưa | p).P(nóng | p). P(cao | p).P(không | p).
P(p)
= 3/9 x 2/9 x 3/9 x 6/9 x 9/14 = 0,010582
* P(X | n). P(n)= P(mưa | n).P(nóng | n). P(cao | n).P(không |
n).P(n)
= 2/5 x 2/5 x 4/5 x 2/5 x 5/14 = 0,018286
* Mẫu X được phân vào lớp n (không chơi tennis)
Giải thuật Naïve Bayes viết bằng mã giả như sau:
NAÏVE_BAYSES_LEARN (Example)
For each target value v
i
do
P(v
i
)← extimate P(v
j
)
For each thuoc_tinh a
i

P(a
i
/ v
j
) ← extimate P(a
i

nhất là tổ hợp lớn nhất.
-Bước 5: Nếu tổ hợp lớn nhất bằng Ø, tăng j lên 1 và quay lại bước 3.
-Bước 6: Đánh dấu các dòng thỏa tổ hợp lớn nhất của bảng con đang xử lý theo
lớp.
-Bước 7: Thêm luật mới vào tập luật R, với vế trái là tập các giá trị của thuộc
tính ứng với tổ hợp lớn nhất(kết hợp các thuộc tính bằng toán tử AND) và vế
phải là giá trị thuộc tính quyết định tương ứng.
-Bước 8: Nếu tất cả các dòng đều đã được đánh dấu phân lớp, tiếp tục thực hiện
từ bước 2 cho các bảng con còn lại. Ngược lại (nếu chưa đánh dấu hết các
dòng) thì quay lại bước 4. Nếu tất cả các bảng con đã được xét thì kết thúc, kết
quả thu được là tập luật cần tìm.
2.4.3 Minh họa thuật giải ILA

Mẫu số Size Color Shape Decision
1 Medium Blue Brick Yes
2 Small Red Wedge No
3 Small Red Sphere Yes
4 Large Red Wedge No

thuộc tính “medium” chỉ bằng 1.
-Xét tiếp tổ hợp {Color}thì giá trị tổ hợp lớn nhất là bảng 2, ứng với thuộc
tính”green”, còn thuộc tính “blue” bằng 1.
-Tương tự, với tổ hợp {Shape} ta có “brick” xuất hiện một lần, và “sphere” hai
lần. Đến cuối bước 4, ta có tổ hợp {Color} với thuộc tính “green” và {Shape}
với thuộc tính “sphere” đều có số lần xuất hiện lớn nhất là 2. Thuật toán mặc
định chọn trường hợp thứ nhất để xác định luật tổ hợp lớn nhất. Dòng 3 và 4
được đánh dấu đã phân lớp, ta có luật dẫn như sau:
Rule 1: IF Color là green THEN Decision là yes
-Tiếp tục thực hiện bước 4 đến 8 cho các mẫu còn lại (chưa đánh dấu) trong
bảng con này (tức dòng 1 và 2). Áp dụng tương tự như trên, ta thấy giá trị
thuộc tính “medium” của {Size}, “blue” của “Color”, “brick” và “sphere” của
{Shape} đều xuất hiện một lần. Bởi vì số lần xuất hiện này giống nhau, thuật
giải áp dụng luật mặc định chọn trường hợp đầu tiên. Ta có thêm luật sau:
Rule 2: IF Size là medium THEN Decision là yes.
Đánh dấu cho dòng 1 trong bảng con thứ nhất. Tiếp tục áp dụng bước 4 đến 8
trên dòng còn lại (tức dòng 2). Giá trị thuộc tính “sphere” của {Shape} xuất
hiện một lần, ta có luật thứ ba
Rule 3: IF Shape là sphere THEN Decision là yes
Dòng 2 được đánh dấu. Như vậy, tất cả các dòng trong bảng con 1 đã được
đánh dấu, ta chuyển qua xử lý bảng con 2.
-Thuộc tính “wedge” của {Shape} xuất hiện hai lần trong dòng 1 và 2 của bảng
con này. Đánh dấu các dòng này với luật dẫn thứ tư sau:
Rule 4: IF Shape là wedge THEN Decision là no
-Với dòng còn lại (tức dòng ) của bảng con 2, ta có thuộc tính {Size} với giá trị
“large” có xuất hiện trong bảng con 1. Do đó, theo thuật giải, ta loại bỏ trường
hợp này. Tương tự như vậy cho giá trị “red” của {Color} và “pillar” của
Bảng con 1
Mẫu số cũ,mới Size Color Shape Decision
1 1 Medium Blue Brick Yes

Rule 2: IF Size là medium THEN Decision là yes
Rule 3: IF Shape là sphere THEN Decision là yes
Rule 4: IF Shape là wedge THEN Decision là no
Rule 5: IF Size là large AND Color là red THEN Decision là no
Đánh giá thuật giải:
-Số lượng các luật thu được xác định mức độ thành công của thuật giải. Đây
chính là mục đích chính của các bài toán phân lớp thông qua một tập mẫu học.
Ngoài ra, để đánh giá các hệ học quy nạp là khả năng hệ thống có thể phân lớp
các mẫu được đưa vào sau này.
-Thuật giả ILA được đánh giá mạnh hơn hai thuật giải về phương pháp học quy
nạp trước đây là ID3 và AQ.
2.5 Các phương pháp phân lớp khác:
2.5.1 Phân lớp dựa trên luật kết hợp
Tìm các luật kết hợp có độ hỗ trợ và độ tin cậy cao có dạng “cond_set =
y” với y là một nhãn lớp.
2.5.2 Thuật giải di truyền
Thuật giải di truyền (genetic algorithm) dựa trên nguyên lý Darwin về
sự tiến hóa sinh học. Mỗi luật được biểu diễn bởi một chuỗi bit. Một mẫu khởi
tạo được tạo ra bao hàm những luật tạo một cách ngẫu nhiên. Dựa trên khái
niệm cái phù hợp nhất sẽ tồn tại, những quy luật phù hợp nhất sẽ được biểu
diễn bởi sự phân lớp chính xác trên tập hợp huấn luyện. Sự phù hợp của một
luật được biểu diễn bởi độ chính xác của phân lớp trên tập hợp những ví dụ
huấn luyện. Kết quả được tạo ra bởi sự lai ghép và đột biến.
2.5.3 Tiếp cận tập thô
Tập thô được sử dụng để xấp xỉ hoặc định nghĩa “thô” những lớp tương
đương. Một tập thô cho một lớp C được xấp xỉ bởi hai tập hợp xấp xỉ dưới và
xấp xỉ trên.

tương tác cho khách hàng Web. Sức mạnh của Java không bị giới hạn ở chương
trình ứng dụng Web. Java thật sự là ngôn ngữ lập trình đa năng. Nó có đầy đủ
đặc tính độc lập trình lập trình và có thể dùng vào việc thiết kế chương trình
ứng dụng độc lập. Bản chất của Java là ngôn ngữ hướng đối tượng xuất thân từ
ngôn ngữ thủ tục, nhưng Java đã được thiết kế ở dạng ngôn ngữ hướng đối
tượng ngay từ đầu. Lập trình hướng đối tượng( OOP) hiện là phương pháp lập
trình phổ biến, thay thế vị trí của các kỹ thuật lập trình thủ tục truyền thống.
3.2 Thiết kế và ưu điểm của Java
Java là ngôn ngữ lập trình hướng đối tượng. Một ngôn ngữ hướng đối
tượng sử dụng kỷ thuật phân chia, đóng gói, thừa kế và đa hình hầu cung cấp
tính linh động, tính đơn thể chức năng và khả năng sử dụng ở mức cao trong
thiết kế phần mềm. Java là ngôn ngữ độc lập với hệ nền. Chương trình Java có
thể chạy trên bất cứ máy tính nào có hệ điều hành hỗ trợ Java Virtual Machine,
một thành phần phần mềm dịch mã lệnh Java và thực thi các hành động phối
hợp.
Java có tính phân tán với khả năng nối mạng cài sẵn. Việc xử lý đồng
thời có thể xảy ra trên nhiều máy tính trên Internet.
Java có cơ chế đa tuyến thi hành. Đa tuyến thi hành là khả năng chương
trình thực hiện đồng thời nhiều tác vụ; ví dụ, chương trình có thể tải về và phát
tập tin video cùng lúc.
Java rất an toàn. Máy tính trở nên dễ bị tấn công khi được kết nối với
nhau. Virus và các chương trình phá hoại có thể gây tổn hại cho máy tính của