TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
TIỂU LUẬN NHẬN DẠNG
Tên đề tài: Phương pháp học không có giám sát -
Các thuật toán học phân cấp nhóm dựa trên sự kết
hợp các phần tử. Tìm hiểu phân tích ứng dụng cụ
thể thuật toán học không giám sát.
NHÓM HỌC VIÊN THỰC HIỆN: ĐỖ ĐỨC TÙNG
BÙI ANH QUANG
PHẠM HOÀNG HÙNG
HàNội - 12/2012
MỤC LỤC
PHÂN CÔNG CÔNG VI CỆ 3
BÀI TOÁN PHÂN NHÓM 4
PHÂN NHÓM CÂY PHÂN C PẤ 7
THU T TOÁN K – MEANSẬ 10
THU T TOÁN ISODATAẬ 20
L P TRÌNH CÀI T THU T TOÁN K-MEANSẬ ĐẶ Ậ 25
TÀI LI U THAM KH OỆ Ả 27
27
PHÂN CÔNG CÔNG VIỆC
Họ và tên Lớp Công việc thực hiện
Bùi Anh Quang
Ths Kỹ Thuật
KTMT&TT - 2012B
- Phần I - Bài toán phân nhóm
- Phần II - Phân nhóm cây phân cấp
Đỗ Đức Tùng
Ths Kỹ Thuật
KTMT&TT - 2012B
- Phần III - Thuật toán K-means

thuật toán phân nhóm đối tượngnói chung đều nhằm thỏa mãn các yêu cầu
cơ bản sau:
• Có khả năng mở rộng, gia tăng: Thuật toán phân nhóm cần có khả
năng gia tăng, mở rộng. Rất nhiều thuật toán phân nhóm có thể làm
việc tốt với lượng đối tượngnhỏ, ít hơn 100 đối tượng đối tượng mà
chưa làm tốt với lượng đối tượng lớn, trong khi đó tập đối tượng lớn
chứa hàng triệu đối tượng vì vậy ta cần mở rộng bộ phân nhóm đó để
bao trùm cả tập đối tượng lớn.
• Khả năng thích nghi với các kiểu và thuộc tính đối tượng khác nhau:
có nhiều thuật toán phân nhóm, có những thuật toán phù hợp với đối
tượng số, có những thuật toán khi áp dụng cho loại đối tượng nhị phân
hay đối tượng ảnh …
• Nhận biết được các nhóm với hình thù bất kỳ: một số thuật toán xác
định nhóm dựa vào việc tính khoảng cách Euclidean hay Manhattan
với mục đích nhận biết độ dày và giống nhau của các đối tượng trong
nhóm. Tuy nhiên, một nhóm có thể có hình dạng bất kỳ vì vậy mà
việc phát triển thuật toán có khả năng xác định các nhóm với hình thù
bất kỳ là quan trọng và cần thiết.
• Tối thiểu miền tri thức cho xác định các tham số đầu vào: miền tri
thức đầu vào cần thiết cho một thuật toán phân nhóm càng ít, chi phí
cho việc phân nhóm càng giảm và nó càng khả thi hơn.
• Khả năng thích nghi với đối tượng nhiễu: Phần lớn các tập đối tượng
thực tế chứa đựng ngoại lệ hoặc thiếu, không xác định hay không
đúng. Các thuật toán nhạy cảm với nhiễu là nguyên nhân dẫn đến việc
tạo ra một bộ phân nhóm kém chất lượng.
• Không nhạy cảm với thứ tự của đói tượng vào: Một số thuật toán phân
nhóm không thể sát nhập thêm đối tượng mới vào trong bộ phân
nhóm, thêm đối tượng vào nhóm có sẵn hoặc tạo thêm nhóm mới. Bên
cạnh đó, một thuật toán phân nhóm tốt không tạo ra các bộ phân nhóm
khác nhau từ cùng một bộ đối tượng nhưng thứ tự sắp xếp khác nhau.

dựng các tiêu chuẩn phân nhóm, xây dựng mô hình cho dạng đối tượng, xây
dựng các thuật toán phân nhóm và xác lập các điều kiện khởi tạo, xây dựng
các thủ tục biểu diễn và đánh giá kết quả phân nhóm. Hiện nay chưa có một
phương pháp phân nhóm tổng quát nào có thể giải quyết trọn vẹn cho tất
cả các dạng đối tượng.
PHÂN NHÓM CÂY PHÂN CẤP
Phương pháp phân nhóm cây phân cấp xây dựng một cấu trúc cây
phân cấp cho các đối tượng, và có hai phương pháp chính là xây dựng cây
theo hướng từ trên xuống (top-down) và xây dựng theo hướng từ dưới lên
(bottom-up).
Với phương pháp bottom-up, đầu tiên mỗi đối tượng được coi như
một nhóm phân biệt và sau đó tiến hành ghép lần lượt 2 nhóm giống nhau
nhiều nhất hay khác nhau ít nhất làm một đến khi tất cả các nhóm được ghép
vào một nhóm duy nhất chứa tất cả các đối tượng. Phân nhóm phân cấp
bottom-up được gọi là hierachical agglomerative clustering (HAC). Còn
phân nhóm phân cấp top-down lại đòi hỏi một phương pháp để phân chia
nhóm. Phương pháp này được thực hiện bằng thuật toán đệ quy, tiến hành
tách đôi các nhóm đến khi từng đối tượng phân biệt được đưa ra.
IV. Phương pháp HAC
HAC dựa theo đặc thù của thuật toán phân nhóm đệ quy và coi mỗi
đối tượng như một điểm đối tượng trong không gian Euclide. Việc tính toán
độ tương tự giữa các nhóm dựa vào cách tính khoảng cách trong không gian
Euclide.
Bằng cách đi lên từ lớp dưới cùng lên nút trên đầu, sơ đồ cây phân cấp
cho chúng ta thấy các bước kết hợp đôi một từng nhóm. Ví dụ nhìn vào sơ
đồ ta có thể thấy rằng 2 nhóm mang nhãn 1 và 2 đầu tiên được nhóm với
nhau, sau đó được nhóm với nhóm mang nhãn 3 trở thành nhóm 123 được
đưa ra. Nhóm 4 và 5 được nhóm với nhau tạo thành nhóm 45, cuối cùng hai
nhóm 123 và 45 ghép lại thành một nhóm tổng thế chứa cả 5 đối tượng là
12345 để tạo thành một cây với gốc 12345 và các lá lần lượt là 1, 2, 3, 4, 5.

Average Agglomerative (GAAC) đánh giá ghép nhóm dựa vào toàn bộ độ
tương tự giữa tất cả các nhóm vì vậy mà nó tránh được những thiếu sót của
hai phương pháp single-linkage và complete-linkage – chỉ đánh giá được
một phần các nhóm. Phương pháp phân nhóm GAAC hay còn được gọi là
average-linkage, tính độ tương tự trung bình sim-ga của tất cả các cặp đối
tượng, bao gồm cả các cặp trong cùng một nhóm, nhưng những độ tương tự
tính trong cùng nhóm này không chứa trong phép tính trung bình
VI. Đặc điểm phân nhóm HAC
Ưu điểm:
• Khái niệm đơn giản
Nhược điểm:
• Quyết định trộn tách các nhóm là vĩnh cửu nên chương trình không có
tính quay lui, nếu có quyết định sai thì không thể khắc phục lại.
• Độ phức tạp thuật toán cao, thời gian thực hiện phân nhóm lâu.
THUẬT TOÁN K – MEANS
Thuật toán K-means được đưa ra năm 1957 bởi Stuart Lloyd như là
một kỹ thuật điều mã xung. K-means là thuật toán thuộc phương pháp phân
cụm phân hoạch
VII. Nguyên lý của thuật toán K-means
Thuật toán này dựa trên độ đo khoảng cách của các đối tượng dữ liệu
trong cụm. Giải thuật xử lý như sau: trước tiên nó lựa chọn ngẫu nhiên k đối
tượng, mỗi đối tượng đại diện cho một trung bình cụm hay tâm cụm. Đối với
những đối tượng còn lại, một đối tượng được ấn định vào một cụm mà nó
giống nhất dựa trên khoảng cách giữa đối tượng và trung bình cụm. Sau đó
cần tính giá trị trung bình mới cho mỗi cụm. Xử lý này được lặp lại cho tới
khi hàm tiêu chuẩn hội tụ
Phương pháp này có thể mở rộng có hiệu quả khi xử lý các tập dữ liệu
lớn bởi độ phức tạp tính toán của giải thuật là O(nkt), với n là số đối tượng,
k là số cụm, t là số lần lặp. Thông thường k << n và t << n. Phương pháp
thường kết thúc tại một điểm tối ưu cục bộ.

j
• Hàm trên không âm, giảm khi có 1 sự thay đổi trong 1 trong 2 bước:
gán dữ liệu và định lại vị trí tâm.
2
1
(|| || )
i j
N
i j
i x C
x c
= ∈
−
∑ ∑
3. Các bước của thuật toán
Bước 1 - Khởi tạo
Chọn K trọng tâm {c
i
} (i = 1÷K).
Bước 2 - Tính toán khoảng cách
S
i
(t)
= {x
j
:|| x
j
- c
i
(t)

Trọng tâm cụm 1 c1 ≡ A (1, 1)
Trọng tâm cụm 2 c2 (x,y) = ((2+4+5)/3, (1+3+4)/3) = (11/3, 8/3)
Bước 4-1: Lặp lại bước 2 – Tính toán khoảng cách
d(A, c1 ) = 0 < d(A, c2 ) = 9.89  A thuộc cụm 1
d(B, c1 ) = 1 < d(B, c2 ) = 5.56  B thuộc cụm 1
d(C, c1 ) = 13 > d(C, c2 ) = 0.22  C thuộc cụm 2
d(D, c1 ) = 25 > d(D, c2 ) = 3.56  D thuộc cụm 2
Bước 4-2: Lặp lại bước 3-Cập nhật trọng tâm
c1 = (3/2, 1) và c2 = (9/2, 7/2)
Bước 4-3: Lặp lại bước 2 – Tính toán khoảng cách
d(A, c1 ) = 0.25 < d(A, c2 ) = 18.5  A thuộc cụm 1
d(B, c1 ) = 0.25 < d(B, c2 ) = 12.5  B thuộc cụm 1
d(C, c1 ) = 10.25 < d(C, c2 ) = 0.5  C thuộc cụm 2
d(D, c1 ) = 21.25 > d(D, c2 ) = 0.5  D thuộc cụm 2
Bước 4-4: Lặp lại bước 3 - Cập nhật trọng tâm
c1 = (3/2, 1) và c2 = (9/2, 7/2)
Ta thấy trọng tâm c1 và c2 ở bước 4-3 trùng với bước 4-2  Dừng
Kết luận: Cụm C1 {A,B}, Cụm C2 {C,D}
X. Đánh giá ưu nhược điểm của K-means
1.Ưu điểm
• Do k-means đơn giản nên có thể áp dụng đối với tập dữ liệu lớn
• Bảo đảm hội tụ sau 1 số bước lặp hữu hạn.
• Luôn có ít nhất 1 điểm dữ liệu trong 1 cụm dữ liệu.
• Các cụm không phân cấp và không bị chồng chéo dữ liệu lên nhau.
• Độ phức tạp: O(K.N.l) với l: số lần lặp
• Có khả năng mở rộng, có thể dễ dàng sửa đổi với những dữ liệu mới.
• Luôn có K cụm dữ liệu
• Mọi thành viên của 1 cụm là gần với chính cụm đó hơn bất cứ 1 cụm
nào khác.
2.Nhược điểm

XII. Ứng dụng của thuật toán
• Phân cụm tài liệu web.
o Tìm kiếm và trích rút tài liệu
o Tiền xử lý tài liệu: Quá trình tách từ và vecto hóa tài liệu: tìm
kiếm và thay thế các từ bới chỉ số của từ đó trong từ điển.Biểu
diễn dữ liệu dưới dạng vectơ.
o Áp dụng K-Mean
Kết quả trả về là các cụm tài liệu và các trọng tâm tương ứng.
• Phân vùng ảnh
THUẬT TOÁN ISODATA
XIII. Nguyên lý hoạt động
Thuật toán ISODATA là thuật toán cải tiến của thuật toán K-means,
do đó về cơ bản hai thuật toán này có nhiều điểm tương đồng, tâm Cluster
đều được tính bằng trung bình các mẫu. Tuy nhiên, ISODATA mô tả bao
quát tập các thủ tục phỏng đoán bổ sung được kết hợp chặt chẽ trong sơ đồ
có ảnh hưởng lẫn nhau.
Nếu như kết quả của thuật toán K-means phụ thuộc rất nhiều vào số
lượng K nhóm đặt ra ban đầu thì ISODATA linh động hơn, các nhóm có thể
được tự động tách hoặc ghép trong giới hạn số nhóm K đặt ra ban đầu. Ví
dụ, nếu một nhóm quá tản mạn thì tách làm hai nhóm hoặc nếu hai nhóm
quá gần nhau thì gộp vào một nhóm. Việc quyết định tách nhóm hay phân
nhóm cũng được quyết định dựa vào khoảng cách từ tất cả các phần tử tới tất
cả các tâm.
Trước khi thực hiện thuật toán, ta cần xác định rõ tập N
c
các tâm
Cluster {z
1,
z
2,…,

j
nếu ||x-z
j
|| < || x-z
i
|| với i = 1,2,…,N
c
; i ≠ j
Điều kiện này được áp dụng với mọi x thuộc tập mẫu, S
j
là tập con các mẫu
của tâm z
j
.
Bước 3: Loại bỏ một tập con mẫu có ít hơn θ
N
phần tử
Bước 4: Tính lại các tâm Cluster {z
1,
z
2,…,
z
Nc
}, giá trị tâm mới z
j
bằng trung
bình mẫu của tập mẫu S
j
.
Bước 5: Tính khoảng cách trung bình D

j
, z
ij
là thành phần thứ I của z
j
và N
j
là số mẫu trong S
j
. Mỗi thành phần của
δ
j
là độ lệch chuẩn của các mẫu trong S
j
theo trục tọa độ gốc.
Bước 9: Tìm thành phần cực đại của mỗi δ
j
, j=1,2,…,N
c
và gọi là δ
j max
Bước 10: Nếu với bất cứ δ
j max
, j=1,2,…,N
c
chúng ta có δ
j max
> θ
S
Khi đó chi z

j
cho bằng một phần nhỏ δ
j max
tức là γ
j
=k δ
j max
(0<k≤1). Yêu cầu chọn γ
j
là
nó tạo ra sự khác biệt có thể nhận ra trong khoảng cách từ mẫu tùy ý tới 2
tâm mới, nhưng cũng không quá lớn tới mức làm thay đổi toàn bộ sự sắp xếp
miền cluster. Nếu sự phân chia xảy ra trong bước này, tới bước 2, các trường
hợp khác tiếp tục.
Bước 11: Tình các khoảng cách D
ij
giữa mọi tâm cluster
D
ij
= ||z
i
– z
j
||, i=1,2,…,N
c
-1; j=i+1,…,N
c
Bước 12: So sánh các khoảng cách D
ij
dựa vào tham số θ

kết quả L tâm nhóm lại.
Bước 14: Nếu đây là bước lặp cuối cùng, thuật toán kết thúc. Trong trường
hợp khác, bắt đầu tiếp tục với bước 1 nếu cần thay đổi bất kỳ tham số nào,
hoặc tới bước 2 nếu các tham số được giữ nguyên cho bước lặp tiếp theo.
Ví dụ:
Xét ví dụ đơn giản với tập mẫu ban đầu gồm 8 phần tử, và các thông
số giới hạn K = 2, θ
N
= 1, θ
S
= 1, θ
c
= 4, L = 0, I = 4.
Giả thiết tâm cluster của tập mẫu ban đầu là z{0;0}, N
c
=1, sau khi thực hiện
các bước trong thuật toán ISODATA ta thu được kết quả là hai cluster như
đồ hình trên với các tâm lần lượt là z
1
{1;1} và z
2
{4.8;3.8}.
XIV. Đánh giá thuật toán
Thuật toán ISODATA là thuật toán khá mềm dẻo, không cần phải cố
định các lớp trước. Một số đặc trưng của thuật toán ISODATA:
• Lựa chọn phân hoạch ban đầu dựa trên các tâm bất kỳ (Thực
nghiệm đã chứng minh, kết quả của quá trình nhận dạng không
phụ thuộc vào phân lớp ban đầu)
• Phân vùng bằng cách xắp xếp các mẫu vào tâm gần nhất
• Tự động phân tách hoặc ghép các cluster nếu thỏa mãn các yêu cầu