Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CAO HỌC CÔNG NGHỆ THÔNG TIN QUA MẠNG
LẬP TRÌNH SYMBOLIC VÀ ỨNG DỤNG

BÀI THU HOẠCH:
NGHIÊN CỨU VÀ CÀI ĐẶT CÁC THUẬT
TOÁN PHÂN LỚP DỮ LIỆU VỚI MAPLE

Giảng viên:
PGS. TS. Đỗ Văn Nhơn
Học viên thực hiện:
Huỳnh Tuấn Anh
CH1101004
Khóa 6

TpHCM, 02/2013

GV: PGS. TS. Đỗ Văn Nhơn

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

Lời cám ơn.
Em xin chân thành cám ơn PGS. TS. Đỗ Văn Nhơn đã tận tình hướng dẫn, chỉ bảo
chúng em trong suốt thời gian học chuyên đề này.
Xin chân thành cám ơn quý thầy cô trong Trường Đại Học Công Nghệ Thông Tin, Đại
Học Quốc Gia Tp.HCM đã tận tình giảng dạy, trang bị cho em những kiến thức quý báu, tạo

CÀI ĐẶT CHƯƠNG TRÌNH ............................................................................................... 4

4.

HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH .................................................................... 7

5.

MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH ........................................................... 8

Chương 2: THUẬT TOÁN ID3......................................................................................................... 11
1.

MÔ TẢ CHUNG THUẬT TOÁN ID3 VÀ BÀI TOÁN .................................................... 11

2.

THUẬT TOÁN ID3 VÀ CƠ SỞ LÝ THUYẾT ................................................................. 12

3.

CÀI ĐẶT CHƯƠNG TRÌNH ............................................................................................. 18

4.

HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH .................................................................. 25

5.

MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH ......................................................... 26

Đưa ra khái niệm tổng quát phân loại tập huấn luyện. Khái niệm tổng quát là
hàm boolean được định nghĩa trên tập cá thể.

-

“Học khái niệm là đưa ra một hàm boolean từ tập input và putput của các ví dụ
huấn luyện” (Tom M.Mitchell – Machine Learning)


Ví dụ:
o (Input) Các ví dụ huấn luyện:


Tập các animal cùng thuộc tính của nó.

o (Output) Khái niệm được trích ra:


Bird



Cat



…

1.2. Bài toán cụ thể
-


Warm

Same

Positive

2

Sunny

Warm

High

Strong

Warm

Same

Positive

3

Rainy

Cold

High



Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

Bảng 1.1 – Các ví dụ huấn luyện thuộc và không thuộc khái niệm đích EnjoySport
-

(Output) Khái niệm được học: “EnjoySport”

1.3.Giả thiết
-

Cũng được hiểu là khái niệm. Là hội của các ràng buộc trên thuộc tính của cá
thể.

-

X là cá thể, và X thoả mãn tất cả các ràng buộc trên giả thiết h thì h [hân loại X
là positive (h(X) = 1)

-

Ví dụ: Giả thiết là Aldo thích môn thể thao dưới nước vào nagỳ “cold days with
high humidity”, giả thiết được ghi là:
o <?, Clod, High, ?, ?, ?>

-

Giả thiết tổng quát nhất:
o <?, ?, ?, ?, ?, ?>


Các ví dụ huấn luyện, gồm có:
o Một cá thể thuộc X.
o Khái niệm đích c(X).
Viết là: <X, x(X)>

-

Tập các giả thiết (H): các giả thiết về sự phân loại tập cá thể.

-

Chương trình học:
o Cho trước tập ví dụ huấn luyện.

GV: PGS. TS. Đỗ Văn Nhơn

2

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

o Đưa ra giả thiết về sự phân loại tập cá thể: h(X) = c(X)
1.5. Thứ tự các giả thiết
-

Các giả thiết trong không gian đều có thứ tự


bởi x

3. Xuất ra h.

2.2. Áp dụng thuật toán với ví dụ huấn luyện mục 1.2:
-

h  <∅ ,∅ ,∅ ,∅ ,∅ ,∅ >

-

Cá thể 1 (positive):
<Sunny, Warm, Normal, Strong , Warm , Same >
o h  <Sunny, Warm, Normal, Strong , Warm , Same >

-

Cá thể 2 (positive):

GV: PGS. TS. Đỗ Văn Nhơn

3

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

<Sunny, Warm, High, Strong , Warm , Same >
o h  <Sunny, Warm, ?, Strong , Warm , Same >

o Cách đặt biến môi trường:


Click chuột phải vào My computer, chọn Properties.



Trong hộp thoại mới hiện ra, chọn tiếp Advanced System Setting nếu là
Win Vista hoặc Win 7, Win XP thì chọn Advanced.



Trong hộp thoại System Properties, chọn Environment Variables…



Trong bảng System Variables, chọn Path trong phần Variables, rồi bấm
Edit.



Trong hộp thoại Edit System Variable, thêm dòng sau vào mục Variable
value “C:\Program Files\Maple 12\bin.win”. Lưu ý: ngăn cách giữa các
Variable value là các dấu “;”.

-



Bấm chọn OK (hoặc Apply) để đồng ý thay đổi.

luyện.

-

Tập tin Main.java: tạo form với các thao tác tương ứng trong chương trình (Tạo bảng,
Đọc ví dụ huấn luyện từ tập tin, Hiển thị giả thiết đặc thù nhất).
3.2.2. Các tập tin training examples:

Cấu trúc chung của các tập tin training examples dạng .txt là:
-

Mỗi dòng là một mô tả chi tiết các thuộc tính của một cá thể trong tập cá thể, mỗi thuộc
tính cách nhau ít nhất một khoảng trắng hoặc một tab. Mỗi thuộc tính có một số giá trị
hữu hạn. Cuối cùng là khái niệm đích.

-

Thứ tự giá trị cho mỗi thuộc tính trong ví dụ đó được nhập tương ứng. Tên tập tin, thuộc
tính và các giá trị không chấp nhận các giá trị đặc biệt như: `, ~, &, (, ), !, #, %, ^, -, \, |,
{, }, [, ], ;, ... có thể chấp nhận ký tự gạch dưới.

3.3. Nội dung các hàm chính và các tham số có liên quan
-

Trong Java, tập tin Main.java:
o public Main() throwMapleException:


Khởi tạo Maple Engine với Java.



Sự kiện button Create Table.



Tạo bảng với số dòng và số cột được cho trong jTextField1
ColunmCount và jTextField2 RowCount

o void ShowMaximallySpecificHypothesis()


Hiển thị Maximally Specific Hypothesis lên jTextArea1



Thực hiện hàm FindS của package FindSAlgorithm bằng Maple với tập
ví dụ huấn luyện đưa vào là D, sau đó lấy kết quả Maximally Specific
Hypothesis trả về hiển thị lên jTextArea1 Maximally Specific Hypothesis
trong form. Chuỗi S chứa tập ví dụ từ D[1] đến D[i], nhằm hiển thị kết
quả theo từng bước thực hiện giải thuật.

-

Trong Maple, tập tin Find-S.mw:
+ Finding maximally specific hypothesis consistent with the training examples D
FindS:=proc(D::list)
h: kết quả trả về
x: danh sách lưu mỗi ví dụ, không bao gồm giá trị phân loại
cx: bằng 1 nếu giá trị của thuộc tính phân loại là positive, bằng 0 nếu là negative
local h,x,cx,d,i;

Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

h[i]:=x[i];
else
h[i]:=`?`;
fi;
fi;
od;
fi;
od;
RETURN (h);
end:
+ Kiểm tra x có thỏa h hay không (x thỏa h nghĩa là h(x)=1, bất kể x là positive hay
negative), kết quả trả về bằng 1 nếu thỏa, bằng 0 nếu ngược lại
Classification:=proc(h::list,x::list)
local i;
for i from 1 to nops(h) do
if h[i]=`?` or h[i]=x[i] then
# do nothing
elif h[i]=` ` or h[i]x[i] then
RETURN (0);
fi;
od;
RETURN (1);
end:
4. HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH
-

Đặt biến môi trường như mục 3.1



5. MỘT SỐ VÍ DỤ VÀ KẾT QUẢ CHƯƠNG TRÌNH
5.1.EnjoySport training examples:
-

TrainingExample1.txt

Sunny
Sunny
Rainy
Sunny

-

Warm
Warm
Cold
Warm

Normal
High
High
High

Strong
Strong
Strong
Strong

Warm

luyện mục 2.2
-

Phân lớp một New Instance mới:
x:= [Sunny,Cold,Low,Strong,Warm,Same]
Kết quả x thuộc lớp: Negative

5.2. Sunburned training examples:
-

TrainingExample2.txt

blonde
blonde
brown
blonde
red
brown
brown
blonde
-

average
tall
short
short
average
tall
average
short

h2 = [blonde, tall, average, yes]
h3 = [`?`, `?`, average, yes]
h4 = [`?`, `?`, average, yes]
h5 = [`?`, `?`, average, yes]
h6 = [`?`, `?`, `?`, `?`]
h7 = [`?`, `?`, `?`, `?`]
h8 = [`?`, `?`, `?`, `?`]

-

Phân lớp một New Instance mới:
x:=[blonde,short,light,no]
Kết quả x thuộc lớp: Positive

5.3. Auto training examples:
-

TrainingExample3.txt

Japan

Honda

GV: PGS. TS. Đỗ Văn Nhơn

Blue

1980

9

1980

Sports
Sedan
Sedan
Sedan

Negative
Positive
Negative
Positive

Hiển thị Maximally Specific Hypothesis theo từng bước tính toán:
h1 = [Japan, Honda, Blue, `1980`, Sedan]
h2 = [Japan, Honda, Blue, `1980`, Sedan]
h3 = [Japan, `?`, Blue, `?`, Sedan]
h4 = [Japan, `?`, Blue, `?`, Sedan]
h5 = [Japan, `?`, `?`, `?`, Sedan]

-

Phân lớp một New Instance mới:
x:= [Japan,Honda,Red,1990,Sports]
Kết quả x thuộc lớp: Negative

GV: PGS. TS. Đỗ Văn Nhơn

10

HVTH: Huỳnh Tuấn Anh

Xét bài toán phân loại xem “có đi chơi Tennis” (PlayTennis) ứng với một điều kiện
nào đó hay không? Thuật toán ID3 sẽ học cây quyết định từ tập hợp các ví dụ huấn luyện
sau (Table 3.2 – Training examples for target concept PlayTennis, Machine Learning –
Tom M.Mitchell, 2003):
Day

Outlook

Temp

Humidity

Wind

PlayTennis

D1

Sunny

Hot

High

Weak

No

D2



D4

Rain

Mild

High

Weak

Yes

D5

Rain

Cool

Normal

Weak

Yes

D6

Rain

Cool


D9

Sunny

Cool

Normal

Weak

Yes

D10

Rain

Mild

Normal

Weak

Yes

D11

Sunny

Mild


D14

Rain

Mild

High

Strong

No

Bảng 1.1 – Tập dữ liệu huấn luyện cho khái niệm “PlayTennis”
Tập dữ liệu này bao gồm 14 ví dụ. Mỗi ví dụ biểu diễn cho điều kiện thời tiết gồm các thuộc
tính Outlook (quang cảnh), Temp (nhiệt độ), Humidity (độ ẩm) và Wind (gió); và đều có một thuộc
tính phân loại PlayTennis (Yes, No), còn được gọi là thuộc tính đích. “No” nghĩa là không đi chơi
Tennis ứng với thời tiết đó, “Yes” nghĩa là ngược lại. Giá trị phân loại ở đây chỉ có hai loại (Yes,
No).
Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính Outlook có ba giá trị
(Overcast, Rain, Sunny), Temp có ba giá trị (Hot, Cool, Warm), Humidity có hai giá trị (High,
Normal) và Wind có hai giá trị (Strong, Weak). Các giá trị này chính là ký hiệu (symbol) dùng để
biểu diễn bài toán.
2. THUẬT TOÁN ID3 VÀ CƠ SỞ LÝ THUYẾT
Quinlan (1983) là người đầu tiên đề xuất việc sử dụng lý thuyết thông tin để tạo ra các cây
quyết định và công trình của ông là cơ sở cho phần trình bày ở đây. Lý thuyết thông tin của
Shannon (1948) cung cấp khái niệm Entropy để đo tính thuần nhất (hay ngược lại là độ pha trộn)
của một tập hợp. Một tập hợp là thuần nhất nếu như tất cả các phần tử của tập hợp đều thuộc cùng
một loại, và khi đó ta nói tập hợp này có độ pha trộn là thấp nhất. Trong trường hợp của tập ví dụ,
thì tập ví dụ là thuần nhất nếu như tất cả các ví dụ đều có cùng giá trị phân loại.

Hình 3.4 minh họa sự phụ thuộc của giá trị entropy vào xác
suất xuất hiện của ví dụ dương.
Cho trước:

GV: PGS. TS. Đỗ Văn Nhơn
Hình 3.4 – Entropy(S)

13

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

• Tập S là tập dữ liệu rèn luyện, trong đó thuộc tính phân loại có hai giá trị, giả sử là âm (-) và
dương (+)
• p+ là phần các ví dụ dương trong tập S.
• p_ là phần các ví dụ âm trong tập S.
Khi đó, entropy đo độ pha trộn của tập S theo công thức sau:

Entropy(S) = - p+ log2 p+ - p- log2 pMột cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả sử là có c giá
trị phân loại thì công thức entropy tổng quát là:

Entropy(S) =

I

log2 pi

2.2.Lượng thông tin thu được đo mức độ giảm entropy mong đợi


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

-

Bước 2: Cây cho Ssunny
o Ssunny={D1,D2,D8,D9,D11}
o Gain(Ssunny, Humidity) = 0.97- (3/5)0.0 – (2/5)0.0 = 0.97
o Gain(Ssunny, Wind) = 0.97 – (2/5)1.0 –(3/5)0.918 = 0.019
o Gain(Ssunny, Temperature) = 0.97-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.57
 Humidity : thuộc tính phân loại tốt nhất tại bước này.
 Humidity: root của Ssunny.


Cây như sau:

GV: PGS. TS. Đỗ Văn Nhơn

15

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

-

Bước 3: Cây cho Srain
o Srain={D4,D5,D6,D10,D14}


Entropy=0, Tất cả cá thể đều -  Phân loại No.

2.4. Thuật toán ID3
-

Tạo node gốc cho cây.

-

if tất cả các cá thể là positive then trả về cây chỉ có node, nhãn là +

-

if tất cả các cá thể là negative then trả về cây chỉ có node, nhãn là –

-

if Attributes trống then trả về cây chỉ có 1 node, nhãn là giá trị chung nhất của
Target_Attribute trong tập cá thể.

-

else: Begin
o A  Thuộc tính từ Attributes tốt nhất phân loại tập cá thể.
o Thuộc tính cho root là A. (root  A)
o For each trị Vi của A:


Thêm 1 nhánh mới dưới root, tương ứng A = Vi.



-

Return Root.

3. CÀI ĐẶT CHƯƠNG TRÌNH
3.1.Ngôn ngữ lập trình, biến môi trường, các thư viện được sử dụng
-

Thuật toán ID3 được viết bằng ngôn ngữ Maple (dùng Maple 12), sau đó đóng gói lại
thành môt thư viện và lưu vào thư mục “C:\ID3\”.

-

Chương trình được viết hoàn chỉnh dưới dạng thể hiện form liên kết bên dưới với
package đã được tạo ra ở trên, bằng ngôn ngữ Java (dùng NetBeans IDE 6.5).

-

Biến môi trường:
o Mục đích: kế nối Java với Maple
o Cách đặt biến môi trường:


Click chuột phải vào My computer, chọn Properties.



Trong hộp thoại mới hiện ra, chọn tiếp Advanced System Setting nếu là
Win Vista hoặc Win 7, Win XP thì chọn Advanced.

với Maple để thực hiện các lệnh trong Maple.

GV: PGS. TS. Đỗ Văn Nhơn

18

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

3.2. Cấu trúc, chức năng các tập tin cài đặt và tập tin training examples
3.2.1. Các tập tin cài đặt:
-

Tập tin ID3.mw: cài đặt thuật toán ID3 rồi đóng gói lại thành thư viện bằng chương trình
Maple 12.

-

Tập tin demo.mw: chạy thử thuật toán đã được cài đặt ở trên với một số dữ liệu huấn
luyện; tính các chỉ số Entropy, Gain… trong các trường hợp tương ứng.

-

Tập tin DecisionTreeFrame.java: hiển thị cây quyết định.

-

Tập tin Main.java: tạo form với các thao tác tương ứng (Tạo bảng, Đọc ví dụ huấn luyện


o String GetDecisionTree():


Gán các thuộc tính cho chuỗi A, gán các tập ví dụ cho S lấy từ bảng dữ
liệu Training Examples trong form.



Thực hiện các lệnh trong Maple với package ID3.lib trong thư mực
C:/ID3/, gán các giá trị cho từng thuộc tính trong bảng dữ liệu Training

GV: PGS. TS. Đỗ Văn Nhơn

19

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

Examples (từ form); thực hiện giải thuật ID3 bằng Maple cho tập thuộc
tính A và tập ví dụ S
o Vector ListNodes(String Nodes):


Chuyển chuỗi Nodes kết quả trả về của hàm GetNodes(T) trong Maple
thành 1 Vector trong Java.





Duyệt qua các nút con của nút parent (khởi tạo = 0). Trường hợp nếu chỉ
có 1 nút con, vẽ nút đó ngay bên dưới nút parent; nếu số nút con là chẵn,
vẽ bên dưới nút parent, lấy nút parent là điểm giữa cách đều các nút con;
nếu số nút con là lẻ, vẽ bên dưới nút parent, lấy phần tử ở giữa của nút
con là điểm cách đều.


-

Vẽ 1 đường thẳng từ nút parent đến các nút con.

Trong Maple, tập tin ID3.mw:
+ Hàm tìm tập con Sv của S1 cho mỗi thuộc tính attr có giá trị là val(Sv = {s S ∣ A(s) =

0})
Sv:=proc(S1,attr,val)
result: lưu tập con Sv của S1 (dưới dạng danh sách)
local i,j,result;
result:=[];

GV: PGS. TS. Đỗ Văn Nhơn

20

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

val[i] trên tổng số phần tử của S1
p:=nops(Sv(S1,target_attribute,val[i]))/nops(S1);
fi;
if p0 then
E:=E+(-p*log[2](p));
fi;
od;
RETURN (E);
end:
+ Hàm tính Gain của thuộc tính attr trên tập S
Gain:=proc(S1,attr)
G: Entropy(S) - s;
s=
Entropy(Sv1)
local G,s,Sv1,i,val;
G:=0;s:=0;

GV: PGS. TS. Đỗ Văn Nhơn

21

HVTH: Huỳnh Tuấn Anh


Nghiên cứu và cài đặt các thuật toán phân lớp dữ liệu với Maple

val:=GetValue(attr);
for i from 1 to nops(val) do
Sv1:=Sv(S1,attr,val[i]);
if nops(S1)0 then

g: Tính giá trị Gain của mỗi thuộc tính trong danh sách các thuộc tính Attributes
trên tập Examples
maxG: giá trị Gain cao nhất
A1: thuộc tính được chọn bởi giá trị Gain cao nhất
V: danh sách các giá trị của thuộc tính A1
Vi: mỗi giá trị trong V
ExamplesVi: tập con của Examples cho thuộc tính A1 có giá trị là Vi
val: danh sách các giá trị của thuộc tính phân loại
vertice: mỗi đỉnh trong cây quyết định
turn: lưu lại đỉnh rẽ nhánh trước đó của cây quyết định
T: danh sách các nhánh của cây, có nhánh ko lưu hết từ nút gốc đến nút lá mà chỉ
lưu từ chỗ rẽ nhánh của nhánh cây trước đến nút lá

GV: PGS. TS. Đỗ Văn Nhơn

22

HVTH: Huỳnh Tuấn Anh