Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
ÔN TẬP LÝ THUYẾT VÀ BÀI TẬP
BÀI 3: Episode và Luật Episode
1. Các khái niệm cơ bản về Episode
Episodes:
o Episode là cặp (V, ≤)
 V là tập hợp các loại sự kiện,ví dụ loại tín hiệu báo động
 ≤ là thứ tự riêng phần trên V
o Cho chuỗi S các tín hiệu báo động, episode
α
= (V,
≤
) xảy ra trong phạm vi S nếu
có cách thỏa loại sự kiện (ví dụ loại tín hiệu báo động) trong V dùng các tín hiệu
báo động của S để thứ tự riêng phần ≤ được tôn trọng
o Nhận xét: episodes chứa các tín hiệu báo động có các tính chất nào đó và xày ra
theo một thứ tự riêng phần nào đó.
Các thứ tự riêng phần phổ dụng như:
o Thứ tự toàn phần
 Các vị từ của mỗi episode có thứ tự cố định
 Các episodes như vậy được gọi là tuần tự (hay “có thứ tự")
o Các thứ tự riêng phần hiển nhiên
 Không xét trật tự của các vị từ
 Các episodes này được gọi là song song (hay “không có thứ tự")
Ví dụ:
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 1/26
A
B
C
Episode vừa tuần
tự vừa song song

tần suất nhỏ nhất trong phạm vi chuỗi dữ liệu s và với bề rộng cửa sổ win"
• F(s, win, min_fr): tập hợp các episodes phổ biến trong s ứng với win và min_fr
• Meo Apriori: Nếu episode
α
là phổ biến trong chuỗi sự kiện s, thì tất cả các episodes con
β
p
α
là phổ biến
• Luật episode rule là biểu thức β ⇒ γ, với β và γ là các episodes sao cho β là episode con của γ
• Episode β là episode con của γ (β p γ), nếu đồ thị biểu diễn β là đồ thị con của đồ thị biểu diễn γ
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 3/26
|Sw ∈ W(S, W) | α xuất hiện trong Sw |
fr(α, S, W) =
|W(S, W)|
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
• Nhận xét:
– Các luật WINEPI giống luật kết hợp nhưng có thêm yếu tố thời gian:
Nếu sự kiện (tín hiệu báo động) thỏa về trái của luật xuất hiện theo thứ tự bên phải trong phạm
vi W đơn vị thời gian, thì cũng xuất hiện trong phần kết luận (vế phải ) xuất hiện trong vị trí được
mô tả bởi quan hệ thứ tự ≤, trong phạm vi W đơn vị thời gian.
phần thân ⇒ kết luận [bề rộng cửa sổ ] (f, c)
Bài toán đầu tiên: cho chuỗi và episode, xác định episode có xuất hiện trong chuỗi.
• Tìm số các cửa sổ có episode xuất hiện
• Các cửa sổ liền nhau có nhiều phần chung
• Cách xử lý?
– Thuật toán tăng cường (incremental algorithm)
– Giống ý tưởng luật kết hợp
– Episode ứng viên là tổ hợp của hai episodes có kích thước nhỏ hơn
– Các episodes song song, episodes tuân tự

Giải
1. Tìm các cửa sổ trượt qua chuỗi tín hiệu
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 5/26
-20
-10 0 10
20 30
40
50 60 70 80 90
D
C
A
B
D
A B
C
W1
W2
W3
W4
W5
W6
W7
W8
W9
W11
W10
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
Bề rộng cửa số là 40 giây, bước dịch chuyển là 10 giây. Chiều dài của chuỗi sự kiện là 70 giây (10 đến
80). Bằng cách trượt cửa sổ, ta thu được 11 cửa sổ :
Cửa sổ Wi Khoảng thời gian/cửa sổ Nội dung của Wi

Tập ứng viên C1 A B C D
Số lần xuất hiện trong cửa sổ 7 7 8 8
Dựa vào bảng trên ta thấy Eps một phần tử đều xuất hiện nhiều hơn 5 cửa sổ và thỏa minfr
 Tập các Eps phổ biến một phần tử L1 = {A,B,C,D}
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 6/26
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
Tập cá Eps 2 phần tử được tạo ra từ tập Eps phổ biến 1 phần tử
Tập ứng viên C2 AB AC AD BC BD CD
Số lần xuất hiện trong cửa sổ 6 5 6 5 5 5
Dựa vào bảng trên thì các Eps 2 phần tử đều thỏa vì xuất hiện từ 5 cửa sổ trở lên thỏa minfr
 Tập các Eps phổ biến 2 phần tử L2 = {AB, AC, AD, BC,BD,CD}
Từ L2 ta có C3 = {ABC, ABD, ACD, BCD}
Tập ứng viên C3 ABC ABD ACD BCD
Số lần xuất hiện trong cửa sổ 3 5 4 3
Tương tự ta thấy chỉ có {ABD} xuất hiện trong 5 cửa số nên tập các Eps phổ biến 3 phần tử
là L3={ABD}
Tóm lại các tập Eps song song phổ biến là :
L1 = {A,B,C,D}
L2 = {AB, AC, AD, BC,BD,CD}
L3={ABD}
Tập các luật Eps
Ta không xét tập Eps 1 phần tử
Để tìm ra những luật có độ tin cậy là 100% thì ρ(vế trái) ⊆ ρ(vế phải) nghĩa là tập các cửa
sổ có chứa vế trái là tập con của các cửa sổ chứa vế phải
Luật Kết Hợp
ρ(S1) (vế trái) ρ(S2} (vế phải) ρ(S1) ⊆ ρ(S2)
Kết quả
{AB}
A ⇒ B
W

3,4,5,6,7,8,9
W
1,2,3,4,5,6,7,8
ρ(A) ⊄ ρ(D)
Loại
D ⇒ A
W
1,2,3,4,5,6,7,8
W
3,4,5,6,7,8,9
ρ(D) ⊄ ρ(A)
Loại
BC
B ⇒ C
W
4,5,6,7,8,9,10
W
2,3,4,5,8,9,10,11
ρ(B) ⊄ ρ(C)
Loại
C ⇒ B
W
2,3,4,5,8,9,10,11
W
4,5,6,7,8,9,10
ρ(C) ⊄ ρ(B)
Loại
BD
B ⇒ D
W

3,4,5,6,7,8,9
W
4,5,6,7,8
ρ(A) ⊄ ρ(BD)
Loại
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 7/26
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
BD ⇒ A
W
4,5,6,7,8
W
3,4,5,6,7,8,9
ρ(BD) ⊆ ρ(A)
Nhận
B ⇒ AD
W
4,5,6,7,8,9,10
W
3,4,5,6,7,8
ρ(B) ⊄ ρ(AD)
Loại
AD ⇒ B
W
3,4,5,6,7,8
W
4,5,6,7,8,9,10
ρ(AD) ⊄ ρ(B)
Loại
D ⇒ AB
W

HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 8/26
A
7
B
7
C
8
D
8
Hình 1
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
b. Tìm luật Eps tuần tự
Từ các Eps tuần tự phổ biến tối đại, rút ra các luật dạng vế_trái => vế_phải
p(A)={W3, W4, W5, W6, W7, W8, W9} (1)
p(B)={W4, W5, W6, W7, W8, W9, W10} (2)
p(D)={W1, W2, W3, W4, W5, W6, W7, W8} (4)
Nhưng từ (1), (2) và (4) cho thấy không có luật nào có độ tin cậy là 100%.
 Tổng kết
- Có 11 cửa sổ duyệt qua chuỗi tín hiệu có 8 sự kiện.
- Tập các Eps song song phổ biến L={A, B, C, D, AB,AC,AD,BC,BD,CD, ABD} với {ABD} là
Eps song song phổ biên tối đại.
- Có duy nhất một luật BD => A được dẫn ra từ Eps song song phổ biến tối đại có độ tin cậy
là 100%.
- Tập các Eps tuần tự phổ biến L={A, B, C, D, AB,DA} với {AB} và {DA} là 2 Eps tuần tự phổ
biến tối đại. Không có luật nào được dẫn ra từ các Eps tuần tự phổ biến tối đại.
2. Đề xuất ứng dụng
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 9/26
Hình 2
Hình 2
A

4
AB
6
DA
5
ABD
2
DAB
3
BDA
1
Hình 3
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
BÀI 4: Phân lớp dữ liệu
1. Phân lớp là gì ?
Phân lớp dữ liệu là tiến trình có 2 bước
 Huấn luyện : Dữ liệu huấn luyện được phân tích bởi thuật toán phân lớp ( có thuộc tính
nhãn lớp)
 Phân lớp : Dữ liệu kiểm tra được dùng để ước lượng độ chính xác của bộ phân lớp. Nếu
độ chính xác là chấp nhận được thì có thể dùng bộ phân lớp để phân lớp các mẫu dữ liệu
mới.
 Độ chính xác (accuracy) của bộ phân lớp trên tập kiểm tra cho trước là phần trăm của
các mẫu trong tập kiểm tra được bộ phân lớp xếp lớp đúng
2. Phân lớp trên cây quyết định (ID3)
a. Cây quyết định là cấu trúc cây sao cho:
 Mỗi nút trong ứng với một phép kiểm tra trên một thuộc tính
 Mỗi nhánh biểu diễn kết quả phép kiểm tra
 Các nút lá biểu diễn các lớp hay các phân bố lớp
 Nút cao nhất trong cây là nút gốc.
ví dụ

b. Thuật toán ID3
Ý nghĩa : thuật toán ID3 là một thuật toán học trên cây quyết định dược phát triển bởi Ross
Quilan(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 tìm
kiếm từ trên xuống trên tập học. Độ lợi thông tin đựoc 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 :
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 12/26
Thuật toán tạo cây quyết định bao gồm các bước sau ( Sách Giáo trình khai thác dữ liệu)
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 cá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 hay của một tiêu chuẩn
thống kê
Điều kiện dừng để phân chia tập học :
a. Tất cả những mẫu học đối với một nút cho trước đều cùng một lớp
b. Không còn thuộc tính nào để phân chia tiếp
c. Không còn mẫu học
Độ lợi thông tin (information 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.
np
n
np
p
npI
++
−
++
=
22

 if tất cả mẫu học của S đều có 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ó 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
 Else
•Thêm cây con vào dưới nhánh mới này
•ID3 (S
v
, D, A – {X} )
♦ End
 Return Nút_gốc
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
Bài tập 1: Câu 2: Cho bảng quyết định sau (4 điểm) (đề thi khóa 1)
Vóc dáng Quốc tịch Gia cảnh Nhóm
O1 Nhỏ Đức Độc thân A

3
log
53
3
- )5,3(
22
=+=
++
−
++
=I
Vóc dáng p
i
n
i
I(p
i
, n
i
)
Nhỏ 1 2
0.92
Lớn 2 3
0.97
E(Vóc dáng) = 3/8 * I(1,2) + 5/8 * I(2,3) = 0.891
Gain(Vóc dáng) = I(3,5) - E(Vóc dáng) = 0.06
Gia cảnh p
i
n
i

{Đức} là :
Vóc dáng Gia cảnh Nhóm
O1 Nhỏ Độc thân A
O3 Lớn Độc thân A
O5 Lớn Có gia đình B
O8 Nhỏ Có gia đình B
a. Khối lượng thông tin cần để quyết định các mẫu trong S thuộc về lớp P hay lớp N được xác định
bởi :
b. Tính Entropy cho thuộc tính
 Chọn thuộc tính có độ lợi thông tin lớn nhất đó là “Gia cảnh”
Cây quyết định cho thuật toán ID3 tạo ra
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 15/26
Quốc tịch
{o1,o3, o5,o8}
[+2,-2]
Đức Pháp Ý
? A B
{o2}
[+1,-0]
{o4,o6, o7}
[+0,-3]
1
22
2
log
22
2

22
2

i
, n
i
)
Độc thân 2 0
0
Có gia đình 0 2
0
E(Gia cảnh) = 2/4 * 0 + 2/4 * 0 = 0
Gain(Gia cảnh) = I(2,2) - E(Vóc dáng) = 1
Quốc tịch
Đức Pháp Ý
Gia cảnh A B
A B
Độc Thân Có gia đình
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
Rút luật từ cây quyết định :
a. IF Quốctịch Pháp THEN nhóm A
b. IF Quốctịch Ý THEN nhóm B
c. IF Quốctịch Đức và Giacảnh độc thân THEN nhóm A
d. IF Quốctịch Đức và Giacảnh có gia đình THEN nhóm B
Ta có thể rút gọn lại luật như sau :
a. IF Quốctịch Pháp THEN nhóm A
b. ELSE IF Quốctịch Ý THEN nhóm B
c. ELSE IF Giacảnh độc thân THEN nhóm A ELSE nhóm B
Bài tập 2:
Sử dụng cây định danh để tìm các luật phân lớp từ bảng quyết định sau đây:
# Trời Áp Suất Gió Kết quả
1 Trong Cao Bắc Không mưa
2 Mây Cao Nam Mưa

6 Cao Bắc Mưa
7 Thấp Nam Không mưa
a. Khối lượng thông tin cần để quyết định các mẫu trong S thuộc về lớp P hay lớp N được xác
định bởi :
b. Tính Entropy cho thuộc tính
.Cả hai thuộc tính đều có độ lợi thông tin bằng nhau nên chọn ngẫu nhiên thuộc tính đó là “Gió”
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 17/26
1
44
4
log
44
4

44
4
log
44
4
- )4,4(
22
=
++
−
++
=I
Trời p
i
n
i

I(p
i
, n
i
)
Cao 2 0
0
Trung Bình 1 0
0
Thấp 1 1
1
E(Áp suất) = 2/5 * I(2,0) + 1/5 * I(1,0) + 2/5 *I(1,1) 1=0.4
Gain(Áp suất) = I(4,4) - E(Áp suất) = 0.15
Trời
{1,4, 8}
[0,-3]
Trong
Mây
Không mưa
?
{2,3,5,6,7}
[4,1]
0.74
14
1
log
14
1

14

Rút luật từ cây quyết định :
a. IF Trời trong THEN Không mưa
b. IF Trời mây và Gió Bắc THEN mưa
c. IF Trời mây và Gió Nam và Áp suất cao THEN mưa
d. IF Trời mây và Gió Nam và Áp suất thấp THEN không mưa
Ta có thể rút gọn lại luật như sau :
a. IF Trời mây AND (Gió Bắc OR Áp Suất cao) THEN Mưa
b. ELSE Không mưa

HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 18/26
Trời
Trong
Mây
Không mưa
Gió
Bắc Nam
Mưa
Áp suất
Cao Thấp
Mưa
Thấp Mưa
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
3. Phân lớp Bayes
a. Định lý Bayes
 X là mẫu dữ liệu chưa biết nhãn lớp
 H là giả thuyết sao cho X thuộc về lớp C
 Ấn định xác suất hậu nghiệm posterior probability P(H|X) sao cho H đúng khi cho trước
quan sát X (H conditioned on X)
 Giả sử thế giới các mẫu dữ liệu gồm trái cây, được mô tả bằng màu sắc và hình dáng.
- Giả sử X là màu đỏ và tròn

k
cho A
k
và s
i
là số các mẫu thuộc về lớp C
i
Nếu Ak là liên tục thì nó được giả định có phân bố Gaussian
 Để phân lớp mẫu chưa biết X, ta tính P(X|Ci) P(Ci) cho từng Ci. Sau đó mẫu X được
gán vào Ci if P(Ci|X) > P(Cj|X) for 1 ≤ j ≤ m, j ≠ i
 Nói cách khác, NBC gán X vào lớp Ci sao cho P(X|Ci) P(Ci) là cực đại
4. Đề xuất ứng dụng
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 19/26
P(X)
H)P(H)|P(X
X)|P(H =
∑
=
=
n
1j
jj
ii
i
))P(HH|P(X
))P(HH|P(X
X)|P(H
P(X)
))P(CC|P(X
X)|P(C

πσ
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
Bài tập 1: dùng thuật toán Bayes
Giải bài tập 2 đề thi khóa 1
Vóc dáng Quốc tịch Gia cảnh Nhóm
O1 Nhỏ Đức Độc thân A
O2 Lớn Pháp Độc thân A
O3 Lớn Đức Độc thân A
O4 Nhỏ Ý Độc thân B
O5 Lớn Đức Có gia đình B
O6 Lớn Ý Độc thân B
O7 Lớn Ý Có gia đình B
O8 Nhỏ Đức Có gia đình B
tìm các luật phân lớp của bảng quyết định trên với
- Tập thuộc tính điều kiện là {Vóc dáng, Quốc tịch, Gia cảnh}
- Thuộc tính phân lớp là {Nhóm}
Giải :
Đặt p=A và n=B
 P(p) =3/8
 P(n)=5/8
Ước lượng
Vóc dáng
P(X| p) P(X| n)
P(Nhỏ | p) = 1/3 P(Nhỏ | n) = 2/5
P(Lớn | p) = 2/3 P(Lớn | n) = 3/5
Quốc Tịch
P(Đức | p) = 2/3 P(Đức | n) = 2/5
P(Pháp | p) = 1/3 P(Pháp | n) = 0/5
P(Ý | p) = 0/3 P(Ý | n) = 3/5
Gia cảnh

Kết quả
1 Đen Tầm thước Nhẹ Không Bị rám
2 Đen Cao Vừa phải Có Không
3 Râm Thấp Vừa phải Có Không
4 Đen Thấp Vừa phải Không Bị rám
5 Bạc Tầm thước Nặng Không Bị rám
6 Râm Cao Nặng Không Không
7 Râm Tầm thước Nặng Không Không
8 Đen Thấp Nhẹ Có Không
Bi giải :của Lý Thnh _CH0601069
Ta có: P(p) = 5/8
P(n) = 3/8
Trong đó p là lớp Không bị rám, n là lớp bị rám.
Màu tóc
P(Đen | p) = 2/5 P(Đen | n) = 2/3
P(Râm | p) = 3/5 P(Râm | n) = 0/3
P(Bạc | p) = 0/5 P(Bạc | n) = 1/3
Chiều cao
P(Cao | p) = 2/5 P(Cao | n) = 0/3
P(Tầm thước | p) = 1/5 P(Tầm thước | n) = 2/3
P(Thấp | p) = 2/5 P(Thấp | n) = 1/3
Cân nặng
P(Nặng | p) = 2/5 P(Nặng | n) = 1/3
P(Vừa phải | p) = 2/5 P(Vừa phải | n) = 1/3
P(Nhẹ | p) = 1/5 P(Nhẹ | n) = 1/3
Dùng thuốc
P(Có | p) = 3/5 P(Có | n) = 0/3
P(Không | p) = 2/5 P(Không | n) = 3/3
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 21/26
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc

P(X1/rám).P(p)=
P(đen/rám).P(thấp/rám).P(nặng vừa/rám).P(không dùng thuốc/rám).P(rám)
= 2/3 * 1/3 * 1/3 * 3/3 * 3/8 = 0.02777
P(đen/không rám).P(thấp/ không rám).P(nặng vừa /không rám).P(không dùng thuốc/không
rám).P(không rám)
= 2/5 * 2/5 * 2/5 * 2/5 * 5/8 = 0.016
Mẫu X5 được phân vào lớp rám
X6= <Đen, thấp, nặng, không dùng thuốc)
P(X1/rám).P(p)=
P(đen/rám).P(thấp/rám).P(nặng/rám).P(không dùng thuốc/rám).P(rám)=
= 2/3 * 1/3 * 1/3 * 3/3 * 3/8 = 0.02777
P(đen/không rám).P(thấp/ không rám).P(nặng /không rám).P(không dùng thuốc/không rám).P(không
rám)
= 2/5 * 2/5 * 2/5 * 2/5 * 5/8 = 0.016
Mẫu X6 được phân vào lớp rám
• Rút ra các luật phân lớp:
1. Màu tóc râm thì không bị rám
2. Màu tóc bạc thì bị rám
3. Cao thì không bị rám
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 22/26
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc
4. Có dùng thuốc → không rám
5. Màu tóc Đen, Tầm thước, Nhẹ, Không dùng thuốc thì bị rám
6. Màu tóc Đen, Tầm thước, Vừa, Không dùng thuốc thì bị rám
7. Màu tóc Đen, Tầm thước, Nặng, Không dùng thuốc thì bị rám
8. Màu tóc Đen, Thấp, Nhẹ, Không dùng thuốc thì bị rám
9. Màu tóc Đen, Thấp, Vừa, Không dùng thuốc thì bị rám
10. Màu tóc Đen, Thấp, Nặng, Không dùng thuốc thì bị rám
• Rút gọn các luật phân lớp:
1. Màu tóc râm thì không bị rám

Hiệu suất tương đối: O(tkn), với n là số đối tượng, k là số cụm, và t là số lần lặp. Thông
thường k, t << n.
 Thường kết thúc ở điểm tối ưu cục bộ; có thể tìm được tối ưu toàn cục dùng các kỹ thuật
như thuật toán di truyền
ii)
ii)
Điểm yếu của phương pháp gom cụm k-means
Điểm yếu của phương pháp gom cụm k-means


Có thể áp dụng chỉ khi xác định được trị trung bình của các đối tượng
Có thể áp dụng chỉ khi xác định được trị trung bình của các đối tượng


Cần chỉ định trức k, số các cụm
Cần chỉ định trức k, số các cụm


Không thể xử lý dữ liệu chuỗi và outliers
Không thể xử lý dữ liệu chuỗi và outliers


Không phù hợp để khám phá các cụm với dạng không lồi hay cụm có kích thước khác
Không phù hợp để khám phá các cụm với dạng không lồi hay cụm có kích thước khác
nhau.
nhau.
iii)
iii)
Thuật toán K-Means
Thuật toán K-Means

Dùng ma trận làm tiêu chuẩn gom cụm

Có thể có điều kiện kết thúc
Có thể có điều kiện kết thúc (ví dụ số cụm)
Cây các cụm


Phân cấp cụm thường tạo cây các cụm hay còn được gọi là
dendrogram
dendrogram
o Các lá của cây biểu diễn các đối tượng riêng lẻ
o Các nút trong của cây biểu diễn các cụm
4. Đề xuất ứng dụng
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 24/26
Chuyên đề khai phá dữ liệu và nhà kho dữ liệu Giáo viên :TS Đỗ Phúc

Tiếp thị:
Tiếp thị: khám phá các nhóm khác hàng phân biệt trong CSDL mua hàng

Sử dụng đất:
Sử dụng đất: nhận dạng các vùng đất sử dụng giống nhau khi khảo sát CSDL quả đất

Bảo hiểm:
Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với chi phí đền bù
trung bình cao

Hoạch định thành phố:
Hoạch định thành phố: nhận dạng các nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý.
HọTên: Trần Thị Ngọc Châu – CH0601005 Trang 25/26