Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
KHỔNG MINH TỰ NGHIÊN CỨU, TÌM HIỂU MỘT SỐ
THUẬT TOÁN CƠ BẢN VỀ PHÂN NHÓM DỮ LIỆU
TRÊN CƠ SỞ DỮ LIỆU KHÔNG GIAN LUẬN VĂN THẠC SĨ KỸ THUẬT ĐIỆN TỬ


KHOA ĐIỆN TỬ
TRƢỞNG KHOA THÁI NGUYÊN - 2014

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

i
LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các số liệu, kết quả nêu
trong luận văn này là trung thực và là công trình nghiên cứu của riêng tôi, luận văn này
không giống hoàn toàn bất cứ luận văn hoặc các công trình đã có trƣớc đó.

Thái Nguyên, ngày 24 tháng 02 năm 2014
Tác giả luận văn Khổng Minh Tự

Mặc dù đã cố gắng, song do điều kiện thời gian và kinh nghiệm thực tế còn
nhiều hạn chế nên không thể tránh khỏi thiếu sót. Vì vậy, tôi rất mong nhận đƣợc
sự đóng góp ý kiến của các thầy cô cũng nhƣ của các bạn bè, đồng nghiệp.
Tôi xin chân thành cảm ơn! Tác giả luận văn

Khổng Minh Tự Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

iii
LỜI NÓI ĐẦU
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

iv
MỤC LỤC

LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
LỜI NÓI ĐẦU iii
MỤC LỤC iv
BẢNG THUẬT NGỮ VIẾT TẮT vii
DANH MỤC CÁC HÌNH viii
MỞ ĐẦU 1
Chƣơng 1. TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ
DỮ LIỆU KHÔNG GIAN 6
1.1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in
Databases - DD) 6
1.1.1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu 6
1.1.2. Khái niệm khai phá dữ liệu 7
1.1.3. Quá trình khai phá tri thức trong cơ sở dữ liệu 7
1.1.4. Các nhiệm vụ của khai phá dữ liệu 8
1.2. Phân nhóm (Clustering) và các cách tiếp cận chính 9
1.2.1. Phân nhóm và các ứng dụng 9
1.2.2. Các cách tiếp cận chính 11
1.3. Hệ quản trị cơ sở dữ liệu không gian 16
1.3.1. Cơ sở dữ liệu không gian 16
1.3.2. Hệ quản trị cơ sở dữ liệu không gian 17
1.3.3. Phƣơng pháp truy nhập không gian 18
1.4. Kết luận 20

4.3.2. Tối ƣu hoá việc lựa chọn các tham số và cho thuật toán DENCLUE 62
4.4. Cài đặt thử nghiệm và đánh giá kết quả 63
4.4.1. Xây dựng chƣơng trình cài đặt thuật toán phân nhóm 63
4.4.2. Tạo lập dữ liệu 64
4.4.3. Cài đặt thuật toán phân nhóm 65
4.4.4. Lƣu trữ và hiển thị kết quả 73
4.5. Đánh giá kết quả trên một số tập dữ liệu 74

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

vi
4.5.1. Tập dữ liệu 74
4.5.2. Đánh giá kết quả 75
4.5.3. Nhận xét 79
4.6. Kết luận 81
KẾT LUẬN 82
TÀI LIỆU THAM KHẢO 84


Khai phá dữ liệu
KPDL
Data Mining
Khai phá tri thức
KPTT
Knowledge Discovery
Khai phá tri thức trong cơ sở dữ liệu
KDD
Knowledge Discovery in Databases
Phân nhóm dữ liệu
PNDL
Data Clustering
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

viii
DANH MỤC CÁC HÌNH

Hình 1.1: Các bƣớc trong quá trình khám phá tri thức KDD 8
Hình 1.2: Biểu đồ Hertzsprung-Russell 10
Hình 1.3: Mô tả cách phân nhóm theo phƣơng pháp từ dƣới lên và từ trên
xuống 14
Hình 1.4: Những điểm nằm trong miền tô sẫm mới đƣợc xét đến khi tìm
điểm gần nhất cho điểm x. Những điểm ngoài miền không cần
xét đến 17

Hình 4.6 60
Hình 4.7 60
Hình 4.8 61
Hình 4.9. Các tập dữ liệu với mật độ phân bố khác nhau giữa các lớp 61
Hình 4.10: Đồ thị mô tả sự phụ thuộc m( ) vào . 62
Hình 4.11: Sơ đồ thực hiện chƣơng trình 63
Hình 4.12: Tập dữ liệu lấy từ nguồn tài liệu 74
Hình 4.13: Tập dữ liệu lấy từ nguồn tài liệu 75
Hình 4.14: Tập dữ liệu lấy từ nguồn tài liệu 75
Hình 4.15: Tập dữ liệu ban đầu 75
Hình 4.16a 76
Hình 4.16 b 76
Hình 4.16 c 76
Hình 4.17 a 77
Hình 4. 17 b 77
Hình 4.17 c 78
Hình 4.18 a 78
Hình 4.18 b 79 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

1
MỞ ĐẦU

Trong vài thập kỷ gần đây, công nghệ thông tin có nhiều bƣớc phát triển
nhanh chóng và đã đƣợc ứng dụng rộng rãi trong mọi lĩnh vực, ngành nghề xã hội,
đặc biệt là lĩnh vực quản lý – một lĩnh vực mà yếu tố công nghệ xử lý thông tin có
tính chất quyết định. Từ đó, theo quá trình hoạt động của các hệ thống quản lý dẫn
đến sự bùng nổ thông tin, kích thƣớc của các kho dữ liệu có kích thƣớc tăng nhanh

Dữ liệu không gian?
Với lý do, ngoài nhu cầu lƣu trữ và xử lý các kiểu dữ liệu thông thƣờng nhƣ
kiểu chuỗi, kiểu số, kiểu ngày tháng, … ngƣời sử dụng còn có thêm nhu cầu lƣu trữ
và xử lý dữ liệu không gian để lƣu trữ các đối tƣợng nhƣ Point, Line, Polugon, …
Và từ đó, một mô hình cơ sở dữ liệu đƣợc quan tâm nhất hiện nay chính là mô hình
cơ sở dữ liệu không gian (SDB – Spatial Database) đƣợc sử dụng cho xử lý và lƣu
trữ dữ liệu không gian, chẳng hạn nhƣ dữ liệu bản đồ, dữ liệu, dữ liệu của lĩnh vực
khí tƣợng thuỷ văn, quân sự, multimedia, … và đặc biệt là trong lĩnh vực viễn
thông. Thuật ngữ dữ liệu không gian (spatial data) đƣợc sử dụng theo nghĩa rộng,
bao gồm các phần tử dữ liệu (bản ghi) mô tả cho mỗi đối tƣợng mà trong đó bao
hàm 2 thành phần: thành phần thông tin về không gian (vị trí địa lý, vùng, toạ độ,
… ) và thành phần còn lại là các thuộc tính khác của đối tƣợng. Mối quan hệ giữa
thuộc tính không gian và thuộc tính phi không gian liên kết rất chặt chẽ và có thể
dựa vào thuộc tính chất không gian để đƣa ra đƣợc thuộc tính phi không gian và
ngƣợc lại. Ví dụ nhƣ dựa vào tính chất về tỷ lệ ngƣời thất nghiệp của một điểm dữ
liệu, chúng ta có thể đƣa ra đƣợc dự đoán về vị trí của điểm đó (trung tâm thành
phố, nông thôn, miền núi, …). Hoặc dựa vào vị trí của điểm đó với các điểm trung
tâm thành phố, chúng ta có thể đƣa ra đƣợc tỷ lệ thất nghiệp với một mức độ chính
xác nhất định. Một ví dụ khác là mức độ mƣa giữa các vùng, miền trên lãnh thổ
(lĩnh vực khí tƣợng) cũng đƣợc lƣu trữ trong cơ sở dữ liệu sau nhiều năm nhƣ một
kho dữ liệu không gian.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

3
Dữ liệu không gian trong lĩnh vực điện tử, truyền thông?
Trong hoạt động quản lý của các nhà cung cấp dịch vụ viễn thông, kích
thƣớc kho dữ liệu lƣu trữ về các cuộc thoại di động tăng nhanh đáng kể. Dữ liệu mô
tả cho các cuộc đàm thoại này cũng mang tính chất của dữ liệu không gian. Thuộc
tính không gian của nó có thể là tỉnh, vùng, cell, … và thuộc tính phi không gian có

phân bố của các đối tƣợng dữ liệu không gian.
4. Ý nghĩa khoa học và thực tiễn của đề tài
a. Ý nghĩa khoa học
Vào cuối thập kỷ 90, kỹ thuật khám phá tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Database -KDD) đƣợc đƣa ra nhằm tìm kiếm các thông tin,
tri thức cần thiết, có giá trị tiềm ẩn trong một khối dữ liệu lớn và phức tạp nhƣ dữ liệu
không gian, dữ liệu đa phƣơng tiện, … Trong đó, giai đoạn khai phá dữ liệu là giai
đoạn chính trong quá trình khai phá tri thức trong cơ sở dữ liệu. Có rất nhiều phƣơng
pháp khai phá dữ liệu nhƣ phân lớp, phân nhóm, phát hiện luật kết hợp, … Mỗi
phƣơng pháp có những đặc điểm riêng phù hợp với một lớp các bài toán, các dạng dữ
liệu và miền dữ liệu nhất định.
Đối với dữ liệu không gian, phƣơng pháp đang đƣợc quan tâm nghiên cứu là
phƣơng pháp phân nhóm (clustering). Đây là một bài toán quan trọng của lĩnh vực tìm
kiếm tri thức trong cơ sở dữ liệu không gian lớn và phải đƣợc giải quyết trƣớc tiên.
Hiện nay nhiều nhà khoa học đã đƣa ra nhiều giải thuật phân nhóm, tuy nhiên
không cho ra kết quả tốt trong trƣờng hợp kích thƣớc dữ liệu lớn, có hình dạng phức
tạp và có cả nhiễu.
b. Ý nghĩa thực tiễn
Kết quả nghiên cứu là tìm hiểu và đƣa ra một số thuật toán phân nhóm có hiệu
quả trên dữ liệu không gian, đặc biệt trong trƣờng hợp dữ liệu lớn, bị nhiễu, đa chiều.
Kết quả so sánh giữa các thuật toán cho thấy tính hiệu quả của mỗi thuật toán trên
những đối tƣợng dữ liệu khác nhau. Trong lĩnh vực viễn thông, là lĩnh vực phát triển
mạnh mẽ và lƣợng thông tin trao đổi cực lớn, dữ liệu lƣu trữ đồ sộ. Giải quyết đƣợc
bài toán phân nhóm dữ liệu không gian là giải quyết đƣợc bài toán lớn trong việc hỗ
trợ quyết định của nhiều lĩnh vực quản lý, đặc biệt là trong lĩnh vực viễn thông. Cho

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

5
phép các nhà lãnh đạo quản lý có những chiến lƣợc đúng đắn, kịp thời trong việc điều

TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ
DỮ LIỆU KHÔNG GIAN
1.1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD)
1.1.1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu
Trong những năm gần đây, cùng với sự thay đổi và phát triển không ngừng
của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng,
phần mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế
xã hội nói riêng đã làm cho khả năng thu thập và lƣu trữ thông tin của các hệ thống
thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hóa một cách ồ
ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng nhƣ nhiều lĩnh vực hoạt
động khác đã tạo ra cho chúng ta một lƣợng dữ liệu lƣu trữ khổng lồ. Hàng triệu
CSDL đã đƣợc sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí…, trong
đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm trí là Terabyte. Sự bùng nổ này đã
dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động
chuyển đổi lƣợng dữ liệu khổng lồ kia thành các tri thức có ích.
Sự phát triển nhanh chóng của một lƣợng lớn dữ liệu đƣợc thu thập và lƣu
trữ trong các cơ sở dữ liệu lớn đã vƣợt ra ngoài khả năng của con ngƣời để có thể
hiểu hết đƣợc chúng nếu không có những công cụ hỗ trợ tốt. Kết quả là, dữ liệu thu
thập đƣợc trong một lƣợng lớn cơ sở dữ liệu đã trở thành những đống dữ liệu mà ít
khi đƣợc xem xét đến. Do vậy, việc đƣa ra những quyết định thƣờng không dựa vào
những thông tin hoặc dữ liệu thu thập đƣợc mà chỉ dựa vào nhận thức, suy đoán của
ngƣời đƣa ra quyết định, đơn giản là vì họ không có những công cụ giúp cho việc
lấy ra những tri thức từ lƣợng lớn dữ liệu. Tình huống này đã đặt chúng ta trong
hoàn cảnh nhiều dữ liệu nhƣng thiếu thông tin, thiếu tri thức. Với một khối lƣợng
lớn dữ liệu nhƣ vậy rõ ràng là các phƣơng pháp thủ công truyền thống áp dụng để
phân tích dữ liệu nhƣ chia bảng hoặc ngôn ngữ truy vấn ad-hoc đã không thể áp
dụng đƣợc nữa. Dẫn đến nhu cầu về một kỹ thuật mới có các đặc tính thông minh

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/



Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

8
4. Thực hiện các phƣơng pháp chuyển đổi để làm giảm bớt số chiều của dữ
liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức.
5. Khai phá dữ liệu: Quá trình áp dụng các giải thuật về tìm kiếm tri thức để
đƣa ra đƣợc những thông tin cần thiết và tiềm ẩn trong tập dữ liệu.
6. Đánh giá, giải thích, thử lại các mẫu đã đƣợc khai phá, có thể lặp lại một
hoặc nhiều bƣớc kể trên để thu đƣợc các kết quả tốt hơn.
7. Sử dụng các tri thức phát hiện đƣợc: Hợp nhất các tri thức thu đƣợc vào một
hệ thống làm việc, hoặc đƣa ra các tài liệu về tri thức thu đƣợc từ dữ liệu về một vấn
đề quan tâm. Giải quyết các xung đột tiềm tàng trong tri thức khai thác đƣợc.

Hình 1.1: Các bƣớc trong quá trình khám phá tri thức KDD
Khai phá dữ liệu (Data mining) chỉ là một bƣớc trong quá trình khai phá tri
thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trò quan trọng nhất,
có ảnh hƣởng rất lớn đến chất lƣợng cũng nhƣ hiệu quả của toàn bộ quá trình khai
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD).
1.1.4. Các nhiệm vụ của khai phá dữ liệu
Nhìn chung, mục đích chính của khai phá dữ liệu là dự đoán (prediction) và
mô tả (description). Dự đoán là việc sử dụng các biến hoặc các trƣờng trong cơ sở
dữ liệu để đƣa ra dự đoán về những giá trị chƣa biết hoặc những giá trị chờ đợi
trong tƣơng lai. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con
ngƣời có thể hiểu đƣợc.
Để đạt đƣợc hai mục đích này, nhiệm vụ chính của khai phá dữ liệu gồm:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

9


10
Không giống nhƣ trong quá trình phân loại (classification), ta thƣờng biết
trƣớc tính chất hay đặc điểm của các đối tƣợng trong cùng một lớp và dựa vào đó để
ấn định một đối tƣợng mới vào lớp của nó. Thay vào đó, trong quá trình phân nhóm
ta không hề biết trƣớc tính chất của các lớp mà phải dựa vào mối quan hệ giữa các
đối tƣợng để tìm ra sự giống nhau giữa các đối tƣợng theo một độ đo nào đó đặc
trƣng cho mỗi lớp.
Một ví dụ cho việc phân nhóm để tìm hiểu về các vì sao và nhiệt độ của nó.
Biểu đồ trên hình 1.2 đƣợc gọi là biểu đồ Hertzsprung-Russell với trục tung là độ
sáng và trục hoành là nhiệt độ (theo độ K).

Hình 1.2: Biểu đồ Hertzsprung-Russell
Có thể thấy đƣợc rằng những ngôi sao trong biểu đồ thuộc vào một trong 3
lớp và trong mỗi lớp mối quan hệ giữa nhiệt độ và độ sáng là nhƣ nhau. Giữa các
lớp khác nhau mối quan hệ đó cũng khác nhau. [4]
b. Các ứng dụng của phân nhóm
Đây là một hoạt động quan trọng của con ngƣời. Khi còn bé, con ngƣời học
cách phân biệt giữa các đồ vật, giữa động vật và thực vật bằng cách liên tục thay đổi
nhận thức trong quan niệm phân chia các đối tƣợng dựa vào mối tƣơng quan giữa
chúng. Việc phân tích lớp đã đƣợc sử dụng rộng rãi trong các ứng dụng của nhiều
lĩnh vực, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh và phân tích thị
trƣờng. Trong kinh doanh, phân nhóm có thể giúp các nhà nghiên cứu thị trƣờng
phát hiện đƣợc các nhóm khách hàng khác nhau và đặc tính của từng nhóm khách
hàng dựa vào dữ liệu mua bán. Trong sinh học, phân nhóm đƣợc dùng để chia nhóm
các loài thực vật và động vật, phân loại gen có chức năng tƣơng tự nhau và có đƣợc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

11


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

12
Bƣớc 1: Chọn k điểm dữ liệu làm điểm tâm (center) hay nhân (seed) (ví dụ
nhƣ thuật toán MacQueen là lấy k điểm dữ liệu đầu tiên). Trong những trƣờng hợp
tổng quát, việc chọn nhân là những điểm có khoảng cách không gian giữa chúng lớn
có thể đáp ứng đƣợc việc phân nhóm tốt hơn.
Bƣớc 2: Xác định các điểm dữ liệu còn lại vào các lớp sao cho việc chia đó
là thích hợp nhất. Điều đó có thể thực hiện một cách đơn giản bằng cách chia điểm
dữ liệu đó vào lớp nào gần với nó nhất. Khoảng cách đó đƣợc đo bằng chính
khoảng cách từ điểm đó tới nhân của lớp.
Bƣớc 3: Tính lại điểm tâm của các lớp. Một cách đơn giản để tính lại điểm
tâm của lớp là xác định trung bình cộng của tất cả các điểm trong lớp.
Lặp lại quá trình trên bắt đầu từ bƣớc 2 cho đến khi không có sự thay đổi về lớp
của các điểm dữ liệu (nghĩa là điểm tâm sẽ không thay đổi trong một sai số cho phép).
Có thể mô tả thuật toán K-means nhƣ sau:
Đầu vào:
Tập X = {x
1
, x
2
, . . ., x
n
} R
m

số lƣợng các nhóm k cần phân chia
Đầu ra: c
1

l
).// d: hàm khoảng cách
end
for all s
i
do// cập nhật lại các điểm tâm
s
i
= (c
i
)// : hàm tính độ trung bình
end
end
Thuật toán phân hoạch CLARANS [4]
Thuật toán CLARANS (Clustering Large Applications based on Randomized
Search) là sự cải tiến của thuật toán K-MEANS với việc tìm k điểm nhân đƣợc xác
định một cách ngẫu nhiên và thuật toán tìm biên đã làm tăng hiệu quả của việc phân
nhóm và do vậy thuật toán này thƣờng đƣợc sử dụng khi xử lý dữ liệu lớn. Để có

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

13
đƣợc một chƣơng trình hiệu quả về thời gian thực hiện thuật toán CLARANS đã có
những sửa đổi sau:
1. Một lớp chỉ cần tính lại tâm nếu nhƣ có sự thêm hoặc bớt điểm vào lớp và
cách tính tâm đó có thể đƣợc xác định nhƣ sau:
 Khi thêm một điểm (x
p
, y
p

2. Khi có một tâm của một lớp thay đổi
 Đối với những điểm trong lớp nếu khoảng cách từ điểm đó tới tâm mới
lớn hơn khoảng cách đến tâm cũ thì kiểm tra xem có thể chuyển điểm đó sang lớp
khác hay không. Nếu có thể, thực hiện việc chuyển.
 Đối với những điểm ngoài lớp, nếu khoảng cách từ điểm đó tới tâm mới ngắn
hơn khoảng cách đến tâm hiện tại thì thực hiện việc chuyển điểm đó tới lớp mới.
Ƣu điểm của thuật toán K-MEANS (hoặc thuật toán CLARANS) là rất đơn
giản, dễ hiểu và dễ áp dụng. Tuy nhiên, nhƣợc điểm của K-MEANS (hay
CLARANS) là tốc độ khi áp dụng với cơ sở dữ liệu lớn. Thêm vào nữa, những thuật
toán trên không thể làm việc với cơ sở dữ liệu có tồn tại dữ liệu nhiễu.
b. Phƣơng pháp phân cấp (Hierarchical methods)
Phƣơng pháp phân cấp thực hiện bằng cách nhóm các đối tƣợng dữ liệu trên
cây phân cấp. Phƣơng pháp phân nhóm theo phân cấp đƣợc chia làm hai loại đó là
phƣơng pháp phân nhóm theo kiểu từ dƣới lên (bottom up) và phƣơng pháp phân
nhóm từ trên xuống (top down). Chất lƣợng và hiệu quả của phƣơng pháp tùy thuộc
vào quyết định ghép hoặc chia lớp.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

14
 Phân nhóm theo phƣơng pháp từ dƣới lên
Phân nhóm theo phƣơng pháp từ dƣới lên dựa vào độ đo khoảng cách giữa hai
lớp ở mỗi bƣớc để quyết định ghép hai lớp đó hay không. Khởi tạo số lớp bằng số
điểm dữ liệu, mỗi một lớp chỉ có duy nhất một điểm dữ liệu (nếu cơ sở dữ liệu có N
điểm dữ liệu thì ban đầu sẽ có N lớp). Sau đó, tại một bƣớc ghép hai lớp có khoảng
cách nhỏ nhất (hay mức độ tƣơng tự giữa chúng là lớn nhất). Thực hiện nhƣ vậy
N-1 bƣớc, chúng ta đƣợc duy nhất một lớp.
Lớp sau khi thực hiện N-1 bƣớc đƣợc tạo thành gọi là lớp gốc. Cùng với cây
mới tạo đƣợc chúng ta có thể chọn k lớp thích hợp nhất cho bài toán bằng cách cho
vào một tham số để kết thúc việc ghép lớp. Cách làm này đƣa đến một bài toán nhỏ