HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

-------------------------------------------

PHẠM VĂN VƯỢNG

Phạm Văn Vượng

ỨNG DỤNG PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU
HỆ THỐNG THÔNG TIN

CHO TƯ VẤN NGÀNH NGHỀ SINH VIÊN
TRƯỜNG ĐẠI HỌC KIẾN TRÚC HÀ NỘI

LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

2016- 2017
HÀ
NỘI
2017

HÀ NỘI, NĂM 2017


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

Phạm Văn Vượng

ỨNG DỤNG PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU

nghệ Bưu chính Viễn thông đã cung cấp cho em những kiến thức và tận tình chỉ bảo
cho em trong suốt quá trình em học tập tại trường.
Bên cạnh đó, để vượt qua mọi khó khăn và hoàn thành luận văn trong thời
gian cho phép, em đã nhận được rất nhiều sự giúp đỡ, ủng hộ nhiệt thành từ gia
đình, đồng nghiệp, cơ quan và bạn bè. Em xin chân thành cảm ơn
Tuy nhiên, do thời gian hạn hẹp, mặc dù đã nỗ lực hết sức và nghiêm túc
nghiên cứu đề tài, nhưng luận văn khó tránh khỏi những thiếu sót. Em rất mong
nhận được sự thông cảm và góp ý chỉ bảo tận tình của thầy cô và mọi người.
Hà Nội, tháng 11 năm 2017
Họ và tên


iii

MỤC LỤC

LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ................................................v
DANH MỤC CÁC BẢNG........................................................................................ vi
DANH MỤC CÁC HÌNH VẼ.................................................................................. vii
MỞ ĐẦU .....................................................................................................................1
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ........................................5
1.1 Giới thiệu..............................................................................................................5
1.2 Kỹ thuật phân cụm dữ liệu ...................................................................................7
1.2.1 Khái niệm ......................................................................................................7
1.2.2 Các bước cơ bản để phân cụm ......................................................................8
1.2.3 Các loại đặc trưng trong phân cụm ............................................................9
1.2.4 Ứng dụng của kỹ thuật phân cụm ...............................................................10

(Binding data clustering

Methods)....................................................................................................................36
2.8 Tổng hợp và đánh giá các phương pháp ............................................................37
2.9 Kết luận ..............................................................................................................40
CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ .......................................................41
3.1 Giới thiệu............................................................................................................41
3.2 Lựa chọn thuật toán và mô tả .............................................................................42
3.3 Xây dựng hệ thống .............................................................................................44
3.4 Kết luận ..............................................................................................................57
KẾT LUẬN ...............................................................................................................58
DANH MỤC TÀI LIỆU THAM KHẢO ..................................................................60


v

DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT
Viết tắt
KPDL
CSDL
PCDL

Tiếng Anh

Tiếng Việt
Khai phá dữ liệu
Cơ sở dữ liệu
Phân cụm dữ liệu



nền kinh tế được xây dựng trên cơ sở sản xuất, phân phối và sử dụng tri thức, thông
tin, trong đó máy tính và các công nghệ truyền thông viễn thông là những yếu tố
chiến lược. Trong khi ngành công nghệ thông tin phát triển không ngừng như hiện
nay, để đạt được mục tiêu trên, chúng ta cần một lực lượng lao động có đủ trình độ
năng lực và làm chủ được công nghệ kỹ thuật mới, đủ điều kiện đảm bảo hoàn
thành tốt công việc trong mọi lĩnh vực của đời sống xã hội. Nếu chúng ta không
chiếm hữu được tri thức, không sáng tạo và sử dụng được thông tin trong các ngành
sản xuất thì không thể thành công trong sự cạnh tranh quyết liệt của thị trường.
Chính vì vậy việc nâng cao trình độ học vấn, trình độ văn hóa cho nhân dân,
đặc biệt là việc định hướng ngành học và định hướng nghề nghiệp cho thế hệ
trẻ hôm nay, chủ nhân tương lai của đất nước, cần được quan tâm hơn bao giờ hết.
Như vậy nghề nghiệp luôn được coi là một trong nhiều yếu tố quan trọng
quyết định đến tương lai mỗi con người. Vì thế lựa chọn cho mình một ngành nghề
phù hợp là vấn đề được nhiều bạn trẻ quan tâm, đặc biệt là những bạn sinh viên trẻ
học tập những năm đầu tại các trường đại học. Theo khảo sát tại trường đại học
Kiến trúc Hà Nội, rất nhiều bạn sinh viên sau khi ra trường không tìm được công
việc phù hợp với năng lực cũng như sở thích của bản thân. Có một số sinh viên do
định hướng kém lựa chọn chuyên ngành không đúng khả năng dẫn đến quá trình
học tập kết quả kém, sau thời gian học tập không đạt kết quả tốt dẫn đến việc bỏ học
ngay từ những năm đầu, tạo tâm lý chán nản, không có động lực trong học tập.
Vì những lý do trên nên học viên đã quyết định lựa chọn đề tài: Ứng dụng
phân cụm trong khai phá dữ liệu cho tư vấn ngành nghề sinh viên trường Đại
học Kiến trúc Hà Nội.


2

Tổng quan về vấn đề nghiên cứu
Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ

nhằm hỗ trợ định hướng các ngành học cho sinh viên các khoa trong
trường.
- Thu thập dữ liệu và cài đặt thử nghiệm chương trình.
Đối tượng nghiên cứu
- Tìm hiểu một số thuật toán phân cụm dữ liệu.
- Lựa chọn một thuật toán phân cụm dữ liệu phù hợp có thể áp dụng giải
quyết yêu cầu bài toán.
- Thu thập dữ liệu: Sinh viên năm đầu đang học tập tại trường Đại học Kiến
trúc Hà Nội. Tuy nhiên số lượng sinh viên năm đầu rất lớn nên dữ liệu mẫu
sẽ được thu hẹp vào sinh viên của một khoa trong trường.
- Tiến hành thực nghiệm trên tập dữ liệu mẫu.
Phương pháp nghiên cứu:
- Nghiên cứu lý thuyết về khai phá dữ liệu.
- Tìm hiểu một số thuật toán phân cụm dữ liệu.
- Xây dựng và phân tích yêu cầu bài toán đặt ra.
- Lựa chọn một thuật toán phân cụm dữ liệu phù hợp có thể áp dụng giải
quyết yêu cầu bài toán.
- Tiến hành thực nghiệm trên tập dữ liệu mẫu.
- Phân tích, đánh giá kết quả đạt được.
- Phương hướng phát triển.
Cấu trúc luận văn:
Ngoài phần mở đầu và kết luận, luận văn có cấu trúc gồm 03 chương có nội
dung như sau:


4

Chương 1: Tổng quan về phân cụm dữ liệu
Trình bày tổng quan về phân cụm dữ liệu và giới thiệu một số phương pháp
phân cụm dữ liệu, đưa ra so sánh, đánh giá, lựa chọn.

− Phân tích hồi quy (Regression analysis)
− Phân tích các mẫu tuần tự hay theo thời gian (Sequential/Temporal
patterns)
− Mô tả khái niệm (Concept description and summarization)
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các
phương pháp học không giám sát trong học máy. Có rất nhiều định nghĩa khác nhau
về kỹ thuật này, nhưng về bản chất ta có thể hiểu phân cụm là các qui trình tìm
cách nhóm các đối tượng đã cho vào các cụm (clusters), sao cho các đối tượng


6

trong cùng 1 cụm tương tự (similar) nhau và các đối tượng khác cụm thì không
tương tự (Dissimilar) nhau.
Phân cụm dữ liệu là xử lý một tập các đối tượng vào trong các lớp các đối
tượng giống nhau được gọi là phân cụm. Một cụm là một tập hợp các đối tượng dữ
liệu giống nhau trong phạm vi cùng một cụm và không giống nhau với các đối
tượng trong các cụm khác. Số các cụm dữ liệu được phân ở đây có thể được xác
định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp
phân cụm.
Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm của dữ liệu.
Các thuật toán phân cụm (Clustering Algorithms) đều sinh ra các cụm (clusters).
Tuy nhiên, không có tiêu chí nào là được xem là tốt nhất để đánh hiệu của của phân
tích phân cụm, điều này phụ thuộc vào mục đích của phân cụm như: data reduction,
“natural clusters”, “useful” clusters, outlier detection

Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như [4]:
• Marketing: Xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng
giá trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch
vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu quả hơn;

8

các cụm khác. Một cụm các đối tượng dữ liệu có thể xem như là một nhóm
trong nhiều ứng dụng.

1.2.2 Các bước cơ bản để phân cụm
• Chọn lựa đặc trưng : Các đặc trưng phải được chọn lựa một cách hợp lý
để có thể “mã hoá” nhiều nhất thông tin liên quan đến công việc quan tâm. Mục tiêu
chính là phải giảm thiểu sự dư thừa thông tin giữa các đặc trưng. Các đặc trưng cần
được tiền xử lý trước khi dùng trong các bước sau.
• Chọn độ đo gần gũi: Đây là một độ đo chỉ ra mức độ tương tự hay không
tương tự giữa hai vector đặc trưng. Phải đảm bảo rằng tất cả các vector đặc trưng
góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc trưng nào át
hẳn đặc trưng nào. Điều này được đảm nhận bởi quá trình tiền xử lý.
• Tiêu chuẩn phân cụm: Điều này phụ thuộc vào sự giải thích của chuyên
gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm được chuyên gia cho
rằng đang ẩn dấu dưới tập dữ liệu. Chẳng hạn, một cụm loại chặt (compact) của các
vector đặc trưng trong không gian ℓ-chiều có thể dễ nhận thấy theo một tiêu chuẩn,
trong khi một cụm loại “dài và mỏng” lại có thể đươc dễ nhận thấy bởi một tiêu
chuẩn khác. Tiêu chuẩn phân loại có thể được diễn đạt bởi hàm chi phí hay một vài
loại quy tắc khác.
• Thuật toán phân loại: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm
làm sáng tỏ cấu trúc cụm của tập dữ liệu.
• Công nhận kết quả: Khi đã có kết quả phân loại thì ta phải kiểm tra tính
đúng đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định phù
hợp.
• Giải thích kết quả: Trong nhiều trường hợp, chuyên gia trong lĩnh vực
ứng dụng phải kết hợp kết quả phân loại với bằng chứng thực nghiệm và phân tích
để đưa ra các kết luận đúng đắn. Trong một số trường hợp, nên có cả bước khuynh
hướng phân cụm; trong bước này có các kiểm định khác nhau để chỉ ra một dữ liệu

1.2.3 Các loại đặc trưng trong phân cụm

Có bốn loại đặc trưng, đó là:
- Các đặc trưng danh nghĩa (nominal): Gồm các đặc trưng mà các giá trị của nó

mã hoá các trạng thái. Chẳng hạn cho một đặc trưng là giới tính của một người thì


10

các giá trị có thể của nó là 1 ứng với nam và 0 ứng với nữ. Rõ ràng là bất kỳ sự so
sánh về lượng nào giữa các giá trị loại này đều là vô nghĩa.
- Các đặc trưng thứ tự (ordinal): Là các đặc trưng mà các giá trị của nó có thể

sắp một cách có ý nghĩa. Ví dụ về một đặc trưng thể hiện sự hoàn thành khoá học
của một sinh viên. Giả sử các giá trị có thể là 4, 3, 2, 1 tương ứng với các ý nghĩa:
”xuất sắc”, “rất tốt“, “tốt“, “không tốt“. Các giá trị này được sắp xếp theo một thứ
tự có ý nghĩa nhưng sự so sánh giữa hai giá trị liên tiếp là không quan trọng lắm về
lượng.
- Các đặc trưng đo theo khoảng ( interval – scaled): Với một đặc trưng cụ thể

nếu sự khác biệt giữa hai giá trị là có ý nghĩa về mặt số lượng thì ta có đặc trưng đo
theo khoảng (còn gọi là thang khoảng). Ví dụ về đặc trưng nhiệt độ, nếu từ 10 – 15
độ thì được coi là rét đậm, còn nếu
- Các đặc trưng đo theo tỷ lệ (ratio-scaled): Cũng với ví dụ nhiệt độ ở trên ta
không thể coi tỷ lệ giữa nhiệt độ Hà Nội 10 độ với nhiệt độ Matxcơva 1 độ mang ý
nghĩa rằng Hà Nội nóng gấp mười lần Matxcơva. Trong khi đó, một người nặng
100 kg được coi là nặng gấp hai lần một người nặng 50 kg. Đặc trưng cân nặng là
một đặc trưng đo theo tỷ lệ (thang tỷ lệ).


1.3 Phân loại các thuật toán phân cụm
Các thuật toán phân cụm có thể được xem như các sơ đồ cung cấp cho ta các
cụm “dễ nhận thấy” bởi việc chỉ xem xét một phần của tập chứa tất cả các cách
phân cụm của X. Kết quả phân cụm phụ thuộc vào thuật toán và tiêu chuẩn phân
cụm. Như vậy, một thuật toán phân cụm là một chức năng học cố gắng tìm ra các
đặc trưng riêng biệt của các cụm ẩn dấu dưới tập dữ liệu. Có nhiều cách để phân
loại các thuật toán phân cụm, sau đây là một cách phân loại:
•

Các thuật toán phân cụm tuần tự (Sequential Algorithms):

Các thuật toán này sinh ra một cách phân cụm duy nhất, chúng là các phương
pháp trực tiếp và thuật toán một hoặc vài lần (không hơn 6 lần). Kết quả cuối cùng
thường phụ thuộc nhanh. Trong hầu hết các thuật toán thuộc loại này, tất cả các
vector đặc trưng tham gia vào vào thứ tự các vector tham gia vào thuật toán. Những
sơ đồ loại này có khuynh hướng sinh ra các cụm có hình dạng chặt siêu cầu hoặc
siêu elipxoit tuỳ theo độ đo được dùng.


12

•

Các thuật toán phân cụm phân cấp (Hierachical Algorithms)

- Các thuật toán tích tụ (Agglomerative Algorithms):

Chúng sinh ra một dãy cách phân cụm mà số cụm, m, giảm dần ở mỗi bước.
Cách phân cụm ở mỗi bước là kết quả của cách phân cụm ở bước trước đó bằng
việc trộn hai cụm vào một. Các đại diện chính của loại này là thuật toán liên kết đơn

Các thuật toán phân cụm mờ:

-

Các vector thuộc về một cụm nào đó với một độ chắc chắn.
Các thuật toán phân cụm theo khả năng :

-

Trong trường hợp này ta đo khả năng một vector đặc trưng thuộc về một cụm
nào đó.
- Các thuật toán phát hiện biên phân tách :

Các thuật toán này cố gắng đặt các biên phân tách một cách tối ưu giữa các
cụm.
•

Các thuật toán khác

- Các thuật toán phân cụm nhánh và cận :

Các thuật toán này cung cấp cho ta các cách phân cụm tối ưu toàn cục mà
không phải xét tới tất cả các cách phân cụm có thể, với m cố định và một tiêu chuẩn
phân cụm định trước. Nhưng đòi hỏi rất nhiều tính toán.
- Các thuật toán phân cụm di truyền :

Sử dụng dân số ban đầu của các cách phân cụm có thể và sinh ra các số dân
mới một cách lặp đi lặp lại. Số dân mới này nhìn chung chứa các cách phân cụm tốt
hơn so với thế hệ trước, theo một tiêu chuẩn đã định trước.
- Phương pháp thư giãn ngẫu nhiên :


15

CHƯƠNG 2: PHÂN CỤM CHO TƯ VẤN LỰA CHỌN
NGÀNH NGHỀ
2.1 Giới thiệu
Hiện nay, lĩnh vực nghiên cứu khai thác dữ liệu giáo dục đang tiếp tục phát
triển, vô số các kỹ thuật khai thác dữ liệu đã được áp dụng cho một loạt các phạm vi
giáo dục. Trong mỗi trường hợp, mục tiêu là để dịch dữ liệu thô thành các thông tin
có ý nghĩa về quá trình học tập để đưa ra quyết định tốt hơn về thiết kế và quy trình
của một môi trường học tập.
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực
tế, nó đều hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá
được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể
phân loại theo các phương pháp tiếp cận chính sau: phương pháp phân hoạch
(Partitioning Methods); phương pháp phân cấp (Hierarchical Methods); phương
pháp dựa trên mật độ (Density-Based Methods); phương pháp dựa trên lưới (GridBasesd Methods) [4].

2.2 Phương pháp phân hoạch (Partitioning Methods)
Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho
đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc
trưng được lựa chọn trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu
trong không gian Euclidean. Ngoài ra, phương pháp này cũng phụ thuộc vào
khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là
gần nhau với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có
quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể
xử lí các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các
thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu
toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân
hoạch có thể được. Chính vì vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ