BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
——-o0o——-
ĐỒ ÁN TỐT NGHIỆP
NGÀNH CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG 2016
H¶i Phßng 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
——-o0o——-
KẾT HỢP CÁC PHƢƠNG PHÁP PHÂN CỤM TRONG
KHAI PHÁ DỮ LIỆU WEB
ĐỒ ÁN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY
Ngành: Công nghệ Thông tin
HẢI PHÒNG 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
——-o0o——-
KẾT HỢP CÁC PHƢƠNG PHÁP PHÂN CỤM TRONG
KHAI PHÁ DỮ LIỆU WEB
ĐỒ ÁN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY
Ngành: Công nghệ Thông tin
Sinh viên thực hiện: Cao Hữu Hải
Giáo viên hƣớng dẫn: Nguyễn Trịnh Đông
Mã sinh viên: 1212101007
HẢI PHÒNG 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
Độc lập – Tự do – Hạnh phúc
——-o0o——-
NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP
Sinh viên: Cao Hữu Hải
Mã số: 1212101007
Lớp:CT1601
Ngành: Công nghệ Thông tin
Tên đề tài: Kết hợp các phƣơng pháp phân cụm trong khai phá dữ liệu Web
NHIỆM VỤ ĐỀ TÀI
1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp.
a. Nội dung:
–
Tìm hiểu về khai phá dữ liệu, khai phá dữ liệu Web.
–
Tìm hiểu các thuật toán phân cụm phổ biến.
–
Áp dụng các thuật toán phân cụm trong tìm kiếm và phân cụm tài liệu
Web.
–
Đề ra phƣơng pháp xây dựng hệ thống.
–
Thử nghiệm với các công cụ để giải quyết bài toán.
b. Các yêu cầu cần giải quyết.
– Nắm đƣợc lý thuyết về khai phá dữ liệu Web.
– Nắm đƣợc các thuật toán phân cụm dữ liệu.
– Nắm đƣợc quá trình phân cụm dữ liệu Web.
– Xây đựng đƣợc mô hình phân cụm dữ liệu với phần mền Orange.
2. Các số liệu cần thiết để thiết kế, tính toán
3. Địa điểm thực tập
CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP
Ngƣời hƣớng dẫn thứ nhất:
Họ và tên: Nguyễn Trịnh Đông
Học hàm, học vị: Thạc sĩ
Cơ quan công tác: Đại học Dân lập Hải Phòng
Nội dung hƣớng dẫn: Tìm hiểu các phƣơng pháp phân cụm. Tìm hiểu một số phƣơng
pháp tạo các luật cơ bản và các giải thuật liên quan. Đề ra phƣơng pháp xây dựng hệ
thống. Thử nghiệm với các công cụ để giải quyết bài toán.
Đề tài tốt nghiệp đƣợc giao ngày 03 tháng 10 năm 2016
Yêu cầu phải hoàn thành trƣớc ngày 24 tháng 12 năm 2016
Đã nhận nhiệm vụ: Đ.T.T.N
Sinh viên
Đã nhận nhiệm vụ: Đ.T.T.N
Cán bộ hƣớng dẫn Đ.T.T.N
Hải Phòng, ngày …………tháng………năm 2016
HIỆU TRƢỞNG
GS.TS.NGƯT Trần Hữu Nghị
PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN
1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp:
…………………………………………………………………………………………
…………………………………………………………………………………………
…………………………………………………………………………………………
…………………………………………………………………………………………
…………………………………………………………………………………………
2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong
nhiệm vụ đề tài tốt nghiệp):
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………
1. Cho điểm của cán bộ hƣớng dẫn:
( Điểm ghi bằng số và chữ )
…………………………………………………………………………………
……………………………………………………………………………
Ngày…….tháng………năm 2016
Cán bộ hƣớng dẫn chính
( Ký, ghi rõ họ tên )
PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM
PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP
1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận,
thuyết minh chƣơng trình, giá trị thực tế,…):
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
2. Cho điểm của cán bộ phản biện
(Điểm ghi bằng số và chữ)
…………………………………………………………………………………………………
…………………………………………………………………………………………………
Ngày…….tháng………năm 2016
Cán bộ chấm phản biện
( Ký, ghi rõ họ tên )
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
1
LỜI CẢM ƠN
Trong lời đầu tiên của báo cáo đồ án tốt nghiệp “Áp dụng các phƣơng pháp phân
cụm trong khai phá dữ liệu Web”, em muốn gửi những lời cám ơn và biết ơn chân
thành nhất của mình tới tất cả những ngƣời đã hỗ trợ, giúp đỡ em về kiến thức và tinh
thần trong quá trình thực hiện đồ án.
Trƣớc hết, em xin chân thành cám ơn thầy giáo Ths. Nguyễn Trịnh Đông, giảng
viên khoa Công nghệ Thông tin, Trƣờng Đại học Dân lập Hải Phòng, ngƣời đã trực
tiếp hƣớng dẫn, nhận xét, giúp đỡ em trong suốt quá trình thực hiện đồ án.
Xin chân thành cảm ơn GS.TS.NGƢT Trần Hữu Nghị Hiệu trƣởng trƣờng Đại
học Dân lập Hải Phòng, ban giám hiệu nhà trƣờng, các thầy cô trong khoa Công nghệ
Thông tin và các phòng ban nhà trƣờng đã tạo điều kiện tốt nhất cho em cũng nhƣ các
bạn khác trong suốt thời gian học tập và làm tốt nghiệp.
Cuối cùng em xin gửi lời cảm ơn đến gia đình, bạn bè, ngƣời thân đã giúp đỡ
động viên em rất nhiều trong quá trình học tập và làm đồ án tốt nghiệp.
Mặc dù em đã hết sức cố gắng để hoàn thiện báo cáo tốt nghiệp song khả năng
còn hạn chế nên bài báo cáo vẫn còn thiếu nhiều sai sót. Vì vậy em rất mong đƣợc sự
đóng góp của các thầy cô và bạn bè.
Em xin chân thành cảm ơn!
Hải Phòng,ngày 24 tháng 12 năm 2016
Sinh viên
Cao Hữu Hải
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
2
MỤC LỤC
LỜI CẢM ƠN
……………………………………………………………………………………………
1
MỤC LỤC ………………………………………………………………………………………………..
2
DANH SÁCH HÌNH ………………………………………………………………………………….
4
DANH SÁCH BẢNG
…………………………………………………………………………………
6
DANH MỤC TỪ VIẾT TẮT ………………………………………………………………………
6
CHƢƠNG 1: GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU WEB ………………………….
8
1.1
Khai phá dữ liệu và khai phá tri thức
……………………………………………….
8
1.1.1 Khai phá dữ liệu ……………………………………………………………………….
8
1.1.2 Quá trình khám phá tri thức ……………………………………………………….
8
1.1.3 Khai phá dữ liệu và các lĩnh vực liên quan …………………………………..
9
1.1.4 Các kỹ thuật áp dụng trong khai phá dữ liệu
…………………………………
9
1.1.5 Những chức năng chính của khai phá dữ liệu ……………………………..
10
1.1.6 Ứng dụng của khai phá dữ liệu …………………………………………………
11
1.2
Phƣơng pháp phân cụm dữ liệu …………………………………………………….
12
1.2.1 Giới thiệu về kỹ thuật phân cụm ……………………………………………….
12
1.2.2 Ứng dụng của phân cụm dữ liệu ……………………………………………….
14
1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu …………………………..
14
1.2.4 Các kiểu dữ liệu và độ đo tƣơng tự ……………………………………………
15
1.3
Khai phá Web …………………………………………………………………………….
19
1.3.1 Các kiểu dữ liệu Web ………………………………………………………………
21
1.3.2 Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web
………..
22
1.3.3 Một số vấn đề trong xử lý dữ liệu văn bản
………………………………….
22
1.4
Tiểu kết chƣơng 1 ……………………………………………………………………….
24
CHƢƠNG 2: MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU ……………………….
25
2.1
Thuật toán k-means
……………………………………………………………………..
25
2.2
Thuật toán PAM………………………………………………………………………….
27
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
3
2.3
Thuật toán BIRCH ………………………………………………………………………
31
2.4
Thuật toán DBSCAN …………………………………………………………………..
33
2.5
Tiểu kết chƣơng 2 ……………………………………………………………………….
36
CHƢƠNG 3: KHAI PHÁ DỮ LIỆU WEB
………………………………………………….
37
3.1
Khai phá nội dung Web ……………………………………………………………….
37
3.1.1 Khai phá kết quả tìm kiếm ……………………………………………………….
38
3.1.2 Khai phá văn bản Web …………………………………………………………….
38
3.2
Khai phá theo sử dụng Web
………………………………………………………….
43
3.2.1 Các kỹ thuật đƣợc sử dụng trong khai phá theo sử dụng Web ………
44
3.2.2 Quá trình khai phá theo sử dụng Web
………………………………………..
44
3.3
Khai phá cấu trúc Web ………………………………………………………………..
45
3.3.1 Tiêu chuẩn đánh giá độ tƣơng tự
……………………………………………….
46
3.3.2 Khai phá và quản lý cộng đồng Web …………………………………………
47
3.4
Áp dụng thuật toán trong tìm kiếm và phân cụm tài liệu Web
…………..
48
3.4.1 Tìm hiểu kỹ thuật phân cụm tài liệu Web …………………………………..
48
3.4.2 Quá trình tìm kiếm và phân cụm tài liệu
…………………………………….
49
3.5
Thực nghiệm ………………………………………………………………………………
53
3.6
Tiểu kết chƣơng 3 ……………………………………………………………………….
59
Kết luận
…………………………………………………………………………………………………..
60
Tài liệu tham khảo ……………………………………………………………………………………
61
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
4
DANH SÁCH HÌNH
Hình 1-1: Quy trình khai phá tri thức ……………………………………………………………
8
Hình 1-2: Mô phỏng sự phân cụm ………………………………………………………………
13
Hình 1-3: Phân loại dữ liệu Web ………………………………………………………………..
21
Hình 1-4: Đồ thị thống kê tần số của từ theo định luật Zipf
……………………………
24
Hình 2-1: Hình dạng cụm dữ liệu đƣợc khám phá bởi k-means ……………………..
26
Hình 2-2: = d( , ) – d( , ) Cjmp không âm …………………….
28
Hình 2-3 : có thể âm hoặc dƣơng.
……………….
29
Hình 2-4 Trƣờng hợp Cjmp= 0 …………………………………………………………………….
29
Hình 2-5: Trƣờng hợp Cjmp= (Oj,Op)- d(Oj, Om,2). Cjmp luôn âm
……………………..
30
Hình 2-6: Cây CF đƣợc tạo bởi BIRCH ………………………………………………………
31
Hình 2-7: Lân cận của một điểm p với ngƣỡng Eps
………………………………………
33
Hình 2-8: Mật độ-đến đƣợc trực tiếp
…………………………………………………………..
34
Hình 2-9: Mật độ – đến đƣợc ……………………………………………………………………..
34
Hình 2-10: Mật độ- liên thông ……………………………………………………………………
35
Hình 2-11: Các đối tƣợng nhiễu …………………………………………………………………
35
Hình 3-1: Phân loại khai phá Web
………………………………………………………………
37
Hình 3-2: Quá trình khai phá văn bản Web
………………………………………………….
38
Hình 3-3: Quan hệ trực tiếp giữa 2 trang
……………………………………………………..
46
Hình 3-4: Độ tƣơng đồng trích dẫn……………………………………………………………..
47
Hình 3-5: Độ tƣơng tự chỉ mục
…………………………………………………………………..
47
Hình 3-6: Các bƣớc phân cụm kết quả tìm kiếm trên Web …………………………….
50
Hình 3-7: Mô hình phân cụm dữ liệu trên Orange ………………………………………..
54
Hình 3-8: Đƣa dữ liệu chuẩn hóa và mô hình……………………………………………….
54
Hình 3-9: Bảng chuẩn hóa …………………………………………………………………………
55
Hình 3-10: Do khoảng cách bằng Euclidean ………………………………………………..
55
Hình 3-11: Phân cụm dữ liệu theo phƣơng pháp phân cụm phân cấp
………………
56
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
5
Hình 3-12: Dữ liệu sau khi phân cụm phân cấp ……………………………………………
57
Hình 3-13: Phân cụm bằng k-means, 8 cụm là tối ƣu nhất……………………………..
58
Hình 3-14: Biểu diễn dữ liệu sau khi phân cụm k-means
……………………………….
59
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
6
DANH SÁCH BẢNG
Bảng 1-1: Bảng tham số thuộc tính nhị phân ……………………………………………….
17
Bảng 1-2: Thống kê các tần số xuất hiện cao ……………………………………………….
23
DANH MỤC TỪ VIẾT TẮT
Stt
Từ viết
tắt
Từ tiếng anh
Nghĩa tiếng việt
1
KPDL
Khai phá dữ liệu
2
PCDL
Phân cụm dữ liệu
3
CSDL
Cơ sở dữ liệu
4
KDD
Knowledge Discovery in Database
Khám phá tri thức trong
cơ sở dữ liệu
5
KPVB
Khai phá văn bản
6
IF
Term Frequency
Tần số xuất hiện của từ
trong 1 văn bản
7
IDF
Inverse Document Frequency
Tần số nghịch của 1
từ trong tập văn bản
8
PAM
Partitioning Around Medoids
Thuật toán phân cụm dựa
trên ý tƣởng k-medoid
9
BIRCH
Balanced Iterative Reducing and
Clustering Using Hierarchies
Thuật toán phân cụm dựa
trên ý tƣởng cây phân cấp
10
DBSCAN Density Based Spatial Clustering of
Applications with Noise
Thuật toán phân cụm dựa
trên mật độ
11
HTML
Hypertext Markup Language
Ngôn ngữ đánh dấu siêu
văn bản
12
URL
Uniform Resource Locator
Định vị tài nguyên thống
nhất
13
CF
Cluster Features
Đặc điểm cụm
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
7
ỜI MỞ ĐẦU
Trong những năm ngành công nghệ thông tin đã có những bƣớc phát triển chóng
mặt. Do việc ứng dụng công nghệ thông tin vào hầu hết các lĩnh vực trong đời sống
nhƣ: giáo dục, văn hóa, kinh tế, giải trí,… và sự tăng nhanh về số lƣợng ngƣời dùng
Intenet trên toàn cầu. Đẫn đến việc bùng nổ, sự cập nhật nhanh chóng, liên tục của kh8
dữ liệu số đã đặt ra thách thức về việc khai thác,sử lý thông tin từ kho dữ liệu khổng lồ
thành các tri thức có ích một cách nhanh chóng để phục vụ cho việc quản lý, hoạt động
kinh doanh,… Để đáp ứng yêu cầu này ngƣời ta đã xây dựng các công cụ tìm kiếm và
xử lý thông tin để giúp ngƣời dùng tìm kiếm đƣợc các thông tin cần thiết, nhƣng so với
sự rộng lớn về nguồn tài nguyên Web thì dẫn đến sự khó khăn với những kết quả tìm
đƣợc.
Với các phƣơng pháp khai thác cơ sở dữ liệu truyền thống chƣa đáp ứng đƣợc
đầu đủ các yêu cầu từ ngƣời dùng. Vì vậy một hƣớng đi mới đó là nghiên cứu và áp
dụng kỹ thuật khai phá dữ liệu và khám phá tri thức trong môi trƣờng Web. Do đó,
việc nghiên cứu các mô hình dữ pháp khai liệu mới và áp dụng các phƣơng phá dữ liệu
trong khai phá tài nguyên Web là một xu thế tất yếu vừa có ý nghĩa khoa học vừa
mang ý nghĩa thực tiễn cao.
Vì vậy, em chọn đề tài đồ án tốt nghiệp “Kết hợp các phƣơng pháp phân cụm
trong khai phá dữ liệu Web”.
Bố cục đồ án gồm 3 chƣơng:
Chƣơng 1: Trình bày các kiến thức cơ bản về khám phá tri thức, khai phá dữ liệu,
một số vấn đề về biểu diễn và xử lý dữ liệu văn bản áp dụng trong khai phá dữ liệu.
Chƣơng 2 : Giới thiệu một số thuật toán phân cụm dữ liệu phổ biến và thƣờng
đƣợc sử dụng trong lĩnh vực khai phá dữ liệu Web.
Chƣơng 3: Trình bày khai phá nội dung Web và tiếp cận theo hƣớng sử dụng các
kỹ thuật phân cụm dữ liệu để giải quyết bài toán khai phá dữ liệu Web. Trong phần
này cũng trình bày một mô hình áp dụng kỹ thuật phân cụm dữ liệu trong tìm kiếm và
phân cụm tài liệu Web.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
8
CHƢƠNG 1: GIỚI THIỆU VỀ KH I PHÁ LIỆU WEB
1.1 Khai phá dữ liệu và khai phá tri thức
1.1.1 Khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực mới đƣợc nghiên cứu, nhằm tự động khai thác
thông tin, tri thức mới hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị, tổ chức,
doanh nghiệp,…. từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các
đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học cùng những ứng dụng thành
công trong KDD cho thấy KPDL là một lĩnh vực phát triển bền vững, mang lại nhiều
lợi ích và có nhiều triển vọng, đồng thời có ƣu thế hơn hẳn so với các công cụ tìm
kiếm phân tích dữ liệu truyền thống. Hiện nay, KPDL đã ứng dụng ngày càng rộng rãi
trong các lĩnh vực nhƣ thƣơng mại, tài chính, y học, viễn thông, tin – sinh…
Nhƣ vậy, Khai phá dữ liệu là quá trình khai phá, trích xuất, khai thác và sử dụng
những dữ liệu có giá trị tiềm ẩn từ bên trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các
cơ sở dữ liệu (CSDL), kho dữ liệu, trung tâm dữ liệu…
1.1.2 Quá trình khám phá tri thức
Quá trình khá phá tri thức có thể chia thành 5 bƣớc nhƣ sau [1]:
Quá trình KPDL có thể phân thành các giai đoạn sau:
Trích chọn dữ liệu: Đây là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá
từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định.
Tiền xử lý dữ liệu: Đây là bƣớc làm sạch dữ liệu (loại bỏ dữ liệu không đúng,xử
lý dữ liệu thiếu sót,…), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phƣơng
pháp nén dữ liệu, sử dụng histograms, lấy mẫu,…), rời rạc hóa dữ liệu (rời rạc hóa dựa
Dữ liệu
thô
Dữ liệu
lựa chọn
Dữ liệu
tiền xử lý
Dữ liệu
biến đổi
Các mẫu
Tri
thức
Trích chọn
Tiền xử lý
Biến đổi
Khai phá
Đánh giá,
biểu diễn
Hình 1-1: Quy trình khai phá tri thức
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
9
vào histograms, entropy,…). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn
và đƣợc rời rạc hóa.
Biến đổi dữ liệu: Đây là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về
cùng một kiểu, dạng thuận lợi nhất nhằm phục vụ quá trình xử lý ở bƣớc sau.
Khai phá dữ liệu: Đây là bƣớc áp dụng những kỹ thuật phân tích (nhƣ các kỹ
thuật của học máy) nhằm để khai thác dữ liệu, trích chọn đƣợc những mẫu dữ liệu,
những mối liên hệ đặc biệt trong dữ liệu. Đây đƣợc xem là bƣớc quan trọng và tốn
nhiều thời gian nhất của toàn quá trình KDD.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu
đã đƣợc khám phá ở bƣớc trên đƣợc biến đổi và biểu diễn ở một dạng gần gũi với
ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,… Đồng thời bƣớc này cũng đánh giá
những tri thức khám phá đƣợc theo những tiêu chí nhất định.
1.1.3 Khai phá dữ liệu v các l nh vực li n qu n
KPDL là một lĩnh vực liên quan tới thống kê, học máy, CSDL, thuật toán, tính
toán song song, thu nhận tri thức từ hệ chuyên gia và dữ liệu trừu tƣợng. Đặc trƣng của
hệ thống khám phá tri thức là nhờ vào các phƣơng pháp, thuật toán và kỹ thuật từ
những lĩnh vực khác nhau để KPDL. Với lĩnh vực học máy và nhận dạng mẫu thì
KDD nghiên cứu các lý thuyết và thuật toán của hệ thống để trích ra các mẫu và mô
hình từ dữ liệu lớn. KDD tập trung vào việc mở rộng các lý thuyết và thuật toán cho
các vấn đề tìm ra các mẫu đặc biệt (hữu ích hoặc có thể rút ra tri thức quan trọng)
trong CSDL lớn. Với lĩnh vực thống kê, hệ thống KDD thƣờng gắn những thủ tục
thống kê cho mô hình dữ liệu, đặc biệt là trong lĩnh vực thăm dò (Exploratory Data
Analysis – EDA).
1.1.4 Các kỹ thuật áp dụng trong khai phá dữ liệu
Căn cứ vào các bài toán cần giải quyết thì KPDL gồm các kỹ thuật sau [5]:
Phân lớp và dự báo: Xếp một đối tƣợng vào một trong những lớp đã biết trƣớc.
Ví dụ nhƣ phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hƣớng tiếp cận này
thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định, mạng nơron nhân
tạo,… Phân lớp và dự báo còn đƣợc gọi là học có giám sát.
Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 %
nữ giới vào siêu thị nếu mua phấn thì có tới 80% trong số họ sẽ mua thêm son”. Luật
kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và
thị trƣờng chứng khoán,…
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
10
Phân tích chuỗi theo thời gian: Tƣơng tự nhƣ khai phá luật kết hợp nhƣng có
thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh
vực tài chính và thị trƣờng chứng khoán vì nó có tính dự báo cao.
Phân cụm: Xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên. Phân cụm còn
đƣợc gọi là học không có giám sát.
Mô tả và tóm tắt khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khái niệm, ví dụ
nhƣ tóm tắt văn bản.
1.1.5 Những chức năng chính của khai phá dữ liệu
KPDL có hai mục tiêu chính là: mô tả và dự báo . Dự báo là dùng một số biến
hoặc trƣờng trong CSDL để dự đoán ra các giá trị chƣa biết hoặc sẽ có của các biến
quan trọng khác. Việc mô tả tập trung vào tìm kiếm các mẫu mà con ngƣời có thể hiểu
đƣợc để mô tả dữ liệu. Trong lĩnh vực KDD, mô tả đƣợc quan tâm nhiều hơn dự báo,
nó ngƣợc với các ứng dụng học máy và nhận dạng mẫu mà trong đó việc dự báo
thƣờng là mục tiêu chính. Trên cơ sở mục tiêu chính của KPDL, các chức năng chính
của KDD gồm [1]:
Mô tả lớp và khái niệm: Dữ liệu có thể đƣợc kết hợp trong lớp và khái niệm. Ví
dụ: trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng bao gồm máy tính,
máy in,…và khái niệm khách hàng bao gồm khách hàng mua sỉ và khách mua lẻ. Việc
mô tả lớp và khái niệm là rất hữu ích cho giai đoạn tổng hợp, tóm lƣợc và chính xác
hoá. Mô tả lớp và khái niệm đƣợc bắt nguồn từ đặc trƣng hoá dữ liệu và phân biệt dữ
liệu. Đặc trƣng hoá dữ liệu là quá trình tổng hợp những đặc tính hoặc các thành phần
chung của một lớp dữ liệu mục tiêu. Phân biệt dữ liệu là so sánh lớp dữ liệu mục tiêu
với những lớp dữ liệu đối chiếu khác. Lớp dữ liệu mục tiêu và các lớp đối chiếu là do
ngƣời dùng chỉ ra và tƣơng ứng với các đối tƣợng dữ liệu nhận đƣợc nhờ truy vấn.
Phân tích sự kết hợp: Phân tích sự kết hợp là khám phá luật kết hợp thể hiện mối
quan hệ giữa các thuộc tính giá trị mà ta nhận biết đƣợc nhờ tần suất xuất hiện cùng
nhau của chúng.
Phân lớp và dự báo: Phân lớp là quá trình tìm kiếm một tập các mô hình hoặc
chức năng mà nó mô tả và phân biệt nó với các lớp hoặc khái niệm khác. Các mô hình
này nhằm mục đích dự báo về lớp của một số đối tƣợng. Việc xây dựng mô hình dựa
trên sự phân tích một tập các dữ liệu đƣợc huấn luyện có nhiều dạng thể hiện mô hình
nhƣ luật phân lớp (IF-THEN), cây quyết định, công thức toán học hay mạng nơron,…
Sự phân lớp đƣợc sử dụng để dự đoán nhãn lớp của các đối tƣợng trong dữ liệu. Tuy
nhiên trong nhiều ứng dụng, ngƣời ta mong muốn dự đoán những giá trị khuyết thiếu
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
11
nào đó. Thông thƣờng đó là trƣờng hợp dự đoán các giá trị của dữ liệu kiểu số. Trƣớc
khi phân lớp và dự báo, có thể cần thực hiện phân tích thích hợp để xác định và loại bỏ
các thuộc tính không tham gia vào quá trình phân lớp và dự báo.
Phân cụm: Không giống nhƣ phân lớp và dự báo, phân cụm phân tích các đối
tƣợng dữ liệu khi chƣa biết nhãn của lớp. Nhìn chung, nhãn lớp không tồn tại trong
suốt quá trình huấn luyện dữ liệu, nó phân cụm có thể đƣợc sử dụng để đƣa ra nhãn
của lớp. Sự phân cụm thực hiện nhóm các đối tƣợng dữ liệu theo nguyên tắc: Các đối
tƣợng trong cùng một nhóm thì giống nhau hơn các đối tƣợng khác nhóm. Mỗi cụm
đƣợc tạo thành có thể đƣợc xem nhƣ một lớp các đối tƣợng mà các luật đƣợc lấy ra từ
đó. Dạng của cụm đƣợc hình thành theo một cấu trúc phân cấp của các lớp mà mỗi lớp
là một nhóm các sự kiện tƣơng tự nhau.
Phân tích các đối tượng ngoài cuộc: Là các đối tƣợng không tuân theo mô hình
dữ liệu trong CSDL. Hầu hết các phƣơng pháp KPDL đều coi các đối tƣợng ngoài
cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng, chẳng hạn nhƣ phát
hiện nhiễu, thì sự kiện hiếm khi xảy ra lại đƣợc chú ý hơn những gì thƣờng xuyên gặp
phải. Sự phân tích dữ liệu ngoài cuộc đƣợc coi nhƣ là sự khai phá các đối tƣợng ngoài
cuộc. Một số phƣơng pháp đƣợc sử dụng để phát hiện đối tƣợng ngoài cuộc: sử dụng
các test mang tính thống kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất
cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các đối tƣợng có một khoảng
cách đáng kể đến cụm bất kì khác đƣợc coi là đối tƣợng ngoài cuộc, dùng các phƣơng
pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc trƣng chính của các
nhóm đối tƣợng.
Phân tích sự tiến hoá: Phân tích sự tiến hoá thực hiện việc mô tả và mô hình hoá
các quy luật hay khuynh hƣớng của những đối tƣợng mà hành vi của chúng thay đổi
theo thời gian. Phân tích sự tiến hoá có thể bao gồm cả đặc trƣng hoá, phân biệt, tìm
luật kết hợp, phân lớp hay PCDL liên quan đến thời gian, phân tích dữ liệu theo chuỗi
thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên độ tƣơng tự.
1.1.6 Ứng dụng của khai phá dữ liệu
KPDL là lĩnh vực đƣợc ứng dụng vào nhiều lĩnh vực hiện nay nhƣ:
Kinh do nh – thư ng m i:
– Xác định thới quen mua hàng của khách hàng
– Dự doán chu kỳ kinh doanh sản phẩm
– Liên hệ giữa khách hàng và yếu tố khác
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
12
– Xác định khách hàng tiềm năng, đối tƣợng có khả năng trở thành khách
hàng
– Dự đoán hiệu quả của một đợt quảng cáo, tiếp thị
Thư ng m i điện tử:
– Phân tích hoạt động duyệt Web để phân tích sở thích của khách hàng
Ngân hàng:
– Dự đoán các dấu hiệu của một cuộc giao dịnh trái luật
– Xác dịnh khách hàng sẽ cộng tác lâu dài
– Dự đoán rủi do của các khoản cho vay
– Xác định nhân tố đẫn đến vỡ nợ vay
– Liên hệ các chỉ số tài chính đến hoạt động ngân hàng
ảo hiểm
– Loại khách hàng có rủi do cao, gian lận
– Xác định khách hàng tiềm năng
– Xác định các đối tƣợng sẽ trở thành khác hàng
iễn th ng
– Nhận biết các dấu hiệu của cuộc gian lận dịch vụ
– Xu thế phát triển khách hàng, đối tƣợng, khu vực cần phát triển
tế
– Chuẩn đoán bệnh qua các triệu chứng
– Liên hệ giữa các loại bệnh
– Dự doán hiệu quả của một cuộc phẫu thuật, điều trị
1.2 Phƣơng pháp phân cụm dữ liệu
1.2.1 Giới thiệu về kỹ thuật phân cụm
PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao
cho các đối tƣợng trong một cụm đó “tƣơng tự” với nhau. PCDL là một kỹ thuật trong
KPDL, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên, tiềm ẩn, quan
trọng trong tập dữ liệu lớn từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết
định. Mục đích chính của PCDL nhằm khám phá cấu trúc của mẫu dữ liệu để thành lập
các nhóm dữ liệu từ tập dữ liệu lớn, theo đó nó cho phép ngƣời ta đi sâu vào phân tích
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
13
và nghiên cứu cho từng cụm dữ liệu này nhằm khám phá và tìm kiếm các thông tin
tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. Ví dụ: “Nhóm khách hàng có khả
năng trả nợ cao”… Nhƣ vậy, PCDL xử là một phƣơng pháp lý thông tin quan trọng và
phổ biến, nó nhằm khám phá mối liên hệ giữa các mẫu dữ liệu bằng cách tổ chức
chúng thành các cụm [1].
Hình 1-2: Mô phỏng sự phân cụm
Trong hình trên sau khi phân cụm thì những phần tử tƣơng tự nhau thì đƣợc sắp
xếp vào một cụm và ngƣợc lại, hay là những phần tử có chung một định nghĩa hoặc
xấp xỉ về khái niệm cho trƣớc cũng đƣợc xếp vào một cụm. Một số vấn đề thƣờng gặp
trong PCDL là dữ liệu “nhiễu” và “phần tử ngoại lai”. “Nhiễu” có thể là các đối tƣợng
dữ liệu không chính xác hoặc các đối tƣợng dữ liệu khuyết thiếu thông tin về một số
thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các
thuộc tính của đối tƣợng “nhiễu” bằng giá trị thuộc tính tƣơng ứng của đối tƣợng dữ
liệu gần nhất. “Phần tử ngoại lai” là những phần tử có sự khác biệt đáng kể đối với
những phần tử còn lại. Có nhiều cách xác định phần tử ngoại lai, nhƣ xác định theo
khoảng cách: Sử dụng hàm đo khoảng cách giữa các phần tử trong tập dữ liệu, các
phần tử ngoại lai là các phần tử cách khá xa so với các phần tử còn lại. Xác định theo
thống kê: Xác định các mô hình phân phối thống kê mà các phần tử phải tuân theo,
“phần tử ngoại lai” là những phần tử không tuân theo các quy luật này. Xác định theo
độ khác biệt: Xác định những đặc trƣng cơ bản của các cụm, “phần tử ngoại lai” sẽ có
đặc trƣng khác biệt lớn với những phần tử còn lại.
Những v n đ cần gi i qu t hi
– Biểu diễn dữ liệu
– Xây dựng hàm tính độ tƣơng tự
– Xây dựng các tiêu chuẩn phân cụm
– Xây dựng mô hình cho cấu trúc cụm dữ liệu
– Xây dựng thuật toán phân cụ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 cụm
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
14
1.2.2 Ứng dụng của phân cụm dữ liệu
PCDL là một trong những công cụ chính của KPDL đƣợc ứng dụng trong nhiều
lĩnh vực nhƣ thƣơng mại và khoa học. Các kỹ thuật PCDL đã đƣợc áp dụng cho một
số ứng dụng điển hình trong các lĩnh vực sau [5]:
Thư ng m i: PCDL có thể giúp các thƣơng nhân khám phá ra các nhóm khách
hàng quan trọng có các đặc trƣng tƣơng đồng nhau và đặc tả họ từ các mẫu mua bán
trong CSDL khách hàng, phát hiện và dự đoán các giao dịch gian lận.
Sinh học: PCDL đƣợc sử dụng để phân cụm các loại sinh vật, phân loại các Gen
với chức năng tƣơng đồng và thu đƣợc các cấu trúc trong các mẫu, phát hiện và dự
đoán các biến dị.
Lập quy ho ch đ thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý,…
nhằm cung cấp thông tin cho quy hoạch đô thị.
Địa lý: Phân lớp các động vật, thực vật và đƣa ra đặc trƣng của chúng theo vị trí
địa lý.
Khai phá Web: PCDL có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý
nghĩa trong môi trƣờng Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức
từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng đặc biệt hay khám phá
ra cộng đồng Web,…
1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
Việc xây dựng, lựa chọn một thuật toán phân cụm là bƣớc then chốt cho việc giải
quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm,
mục đích của ứng dụng thực tế hoặc xác định độ ƣu tiên giữa chất lƣợng của các cụm
hay tốc độ thực hiện thuật toán,…
Những u cầu để phát triển thuật toán PC [5]:
Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ
(khoảng 200 bản ghi dữ liệu) nhƣng không hiệu quả khi áp dụng cho tập dữ liệu lớn
(khoảng 1 triệu bản ghi).
Thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu quả
cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau nhƣ dữ liệu kiểu
số, kiểu nhị phân, dữ liệu định danh, hạng mục,… và thích nghi với kiểu dữ liệu hỗn
hợp.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
15
Khám phá ra các cụm với hình thù bất kỳ: Do hầu hết các CSDL có chứa nhiều
cụm dữ liệu với các hình thù khác nhau nhƣ: hình lõm, hình cầu, hình que,… Vì vậy,
để khám phá đƣợc các cụm có tính tự nhiên thì các thuật toán phân cụm cần phải có
khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ.
Tối thiểu lượng tri thức cần cho xác định các tham số vào: Do các giá trị đầu vào
thƣờng ảnh hƣởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá
trị vào thích hợp đối với các CSDL lớn.
Ít nh y cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu, khi đƣa vào xử lý
cho thuật toán PCDL với các thứ tự vào của các đối tƣợng dữ liệu ở các lần thực hiện
khác nhau thì không ảnh hƣởng lớn đến kết quả phân cụm.
Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm trong
KPDL đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác. Thuật toán
phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất
lƣợng phân cụm thấp do nhạy cảm với nhiễu.
Ít nh y cảm với các tham số đầu vào: Nghĩa là giá trị của các tham số đầu vào
khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm.
Thích nghi với dữ liệu đ chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ
liệu có số chiều khác nhau.
Dễ hiểu, dễ cài đặt và khả thi.
1.2.4 Các kiểu dữ liệu v độ đo tƣơng tự
Trong PCDL, các đối tƣợng dữ liệu cần phân tích có thể là con ngƣời, nhà cửa,
tiền lƣơng, các thực thể phần mềm,… Các đối tƣợng này thƣờng đƣợc diễn tả dƣới
dạng các thuộc tính của nó. Việc phân loại các kiểu thuộc tính khác nhau là một vấn đề
cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phƣơng tiện thuận lợi
để nhận dạng sự khác nhau của các phần tử dữ liệu. Có hai cách phân lớp dựa trên hai
đặc trƣng của dữ liệu là: kích thƣớc miền và hệ đo [2].
1.2.4.1 Phân loại kiểu dữ liệu dựa trên ích thước mi n
Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm đƣợc, nghĩa là
giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ nhƣ các thuộc tính về màu, nhiệt độ
hoặc cƣờng độ âm thanh.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
16
– Thuộc tính rời r c: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm đƣợc. Thí
dụ nhƣ các thuộc tính về số serial của một cuốn sách, số thành viên trong một gia
đình,…
1.2.4.2 Phân loại kiểu dữ liệu dựa trên hệ đo
Giả sử rằng chúng ta có hai đối tƣợng x, y và các thuộc tính tƣơng ứng với
thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu nhƣ sau:
Thuộc tính định danh (Nominal Scale ): đây là dạng thuộc tính khái quát hóa của
thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều
hơn hai phần tử: nghĩa là nếu x và y là hai đối tƣợng thuộc tính thì chỉ có thể xác định
là x # y hoặc x = y.
Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự,
nhƣng chúng không đƣợc định lƣợng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể
xác định là x # y hoặc x = y hoặc x>y hoặc x
thứ i.
Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhƣng đƣợc xác định một
cách tƣơng đối so với điểm mốc, thí dụ nhƣ thuộc tính chiều cao hoặc cân nặng lấy
điểm 0 làm mốc.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính
có thứ tự gọi chung là thuộc tính h ng mục (Categorical), thuộc tính khoảng và thuộc
tính tỉ lệ đƣợc gọi là thuộc tính số (Numeric).
1.2.4.3 Khái niệm và phép đo độ tương tự, phi tương tự
Để phân cụm, ngƣời ta phải đi tìm cách thích hợp để xác định “khoảng cách”
giữa các đối tƣợng, hay là phép đo tƣơng tự dữ liệu. Đây là các hàm để đo sự giống
nhau giữa các cặp đối tƣợng dữ liệu, thông thƣờng các hàm này hoặc là để tính độ
tƣơng tự (Similar) hoặc là tính độ phi tƣơng tự (Dissimilar) giữa các đối tƣợng dữ liệu.
Tất cả các độ đo dƣới đây đƣợc xác định trong không gian metric. Một không
gian metric là một tập trong đó có xác định các “khoảng cách” giữa từng cặp phần tử,
với những tính chất thông thƣờng của khoảng cách hình học. Nghĩa là, một tập X (các
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin
17
phần tử của nó có thể là những đối tƣợng bất kỳ) các đối tƣợng dữ liệu trong cơ sở dữ
liệu D nhƣ đã đề cập ở trên đƣợc gọi là một không gian metric nếu:
Với mỗi cặp phần tử x, y thuộc X đều có xác định, theo một quy tắc nào đó, một
số thực δ(x, y), đƣợc gọi là khoảng cách giữa x và y.
Quy tắc trên thoả mãn hệ tính chất sau:
–
δ(x, y) > 0 nếu x ≠ y ;
–
δ(x, y)=0 nếu x =y;
–
δ(x, y) = δ(y, x) với mọi x, y; (iv) δ(x, y) ≤ δ(x, z)+δ(z, y).
Hàm δ(x, y) đƣợc gọi là một metric của không gian. Các phần tử của
X đƣợc gọi là các điểm của không gian này.
Mỗi phép đo độ tƣơng tự sẽ phù hợp với mỗi kiểu dữ liệu khác nhau[5].
Thuộc tính kho ng:
Sau khi chuẩn hoá, độ đo phi tƣơng tự của hai đối tƣợng dữ liệu x, y đƣợc xác
định bằng các metric nhƣ sau:
Khoảng cách Minskowski: ∑
| |
, với q là số nguyên
dƣơng.
Khoảng cách Euclidean: √∑
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q =2).
Khoảng cách Manhattan: ∑
| |
, (trƣờng hợp đặc biệt của
khoảng cách Minskowski trong trƣờng hợp q=1).
Khoảng cách cực đ i:
| |, đây là trƣờng hợp của
khoảng cách Minskowski trong trƣờng hợp .
Thuộc tính nhị phân:
Trƣớc hết ta có xây dựng bảng tham số sau:
y:1
y:0
x:1
y:1
Bảng 1-1: Bảng tham số thuộc tính nhị phân
