i
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Th¸i Nguyªn - 2012
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
ii ĐÀO HUY HIỆU NGHIÊN CỨU MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ
LIỆU WEB VÀ ỨNG DỤNG VÀO WEBSITE GIỚI
THIỆU VIỆC LÀM CHO SINH VIÊN
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. Phạm Việt Bình
i
MỤC LỤC
MỤC LỤC i
DANH MỤC HÌNH iii
MỞ ĐẦU 1
CHƢƠNG 1: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU 4
1.1 Giới thiệu chung 4
1.2 Khai phá dữ liệu là gì ? 5
1.3 Quá trình khám phá tri thức trong CSDL 6
1.4 Các kỹ thuật áp dụng trong Data Mining 8
1.4.1 Các kỹ thuật tiếp cận trong Data Mining 8
1.4.2 Các dạng dữ liệu có thể khai phá 9
1.5 Ứng dụng của Data Mining 10
1.6 Phân cụm dữ liệu và ứng dụng 11
1.7 Khai phá dữ liệu web 12
CHƢƠNG 2: MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU WEB 18
2.1. Khai phá nội dung Web 18
2.1.1. Khai phá kết quả tìm kiếm 19
2.1.2. Khai phá văn bản Web 20
2.2. Khai phá theo sử dụng Web 23
2.2.1. Ứng dụng của khai phá theo sử dụng Web 24
2.2.2. Các kỹ thuật đƣợc sử dụng trong khai phá dữ liệu Web 24
2.2.3. Những vấn đề trong khai phá theo sử dụng Web 25
2.2.4. Quá trình khai phá theo sử dụng Web 27
2.3. Khai phá cấu trúc Web 32
2.3.1. Tiêu chuẩn đánh giá độ tƣơng tự 33
2.3.2. Khai phá và quản lý cộng đồng Web 34
CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM 47
3.1. Quy trình hoạt động của Hệ thống cung cấp dữ liệu việc làm 47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vniii
DANH MỤC HÌNH
Hình 1.1 7
Hình 1.2 8
Hình 1.3 17
Hình 2.1 18
Hình 2.2 26
Hình 2.3 31
Hình 2.4 31
Hình 2.5 33
Hình 2.6 34
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn1
MỞ ĐẦU
Từ vài thập niên trở lại đây, với những tác động mạnh mẽ của các tiến
bộ trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ
cho các lĩnh vực kinh tế - xã hội đã phát triển bùng nổ, lượng dữ liệu được tạo
ra ngày càng lớn. Sự phong phú về dữ liệu, thông tin cùng với khả năng kịp
các kỹ thuật khai phá dữ liệu web làm đề tài nghiên cứu cho luận văn của
mình. Luận văn trình bày một khảo cứu hệ thống về các họ thuật toán Khai
phá dữ liệu, bao gồm các cách tiếp cận và đặc điểm ứng dụng. Trên cơ sở đó
tôi đi sâu vào tìm hiểu, phân tích, đánh giá họ các thuật toán khai phá dữ liệu.
Tiếp đến, tôi lựa chọn và đi sâu vào phân tích, thiết kế và xây dựng ứng dụng
cho bài toán xây dựng website giới thiệu việc làm cho sinh viên, đây là một
bài toán Khai phá dữ liệu áp dụng cho dữ liệu có thuộc tính hỗn hợp giữa kiểu
số và hạng mục và đưa ra mô hình xử lý song song cho bài toán xây dựng
website giới thiệu việc làm cho sinh viên này.
Ngoài phần mở đầu và kết luận, cấu trúc nội dung của luận văn bao
gồm có 3 chương:
Chương 1 Tập trung trình bày khái quát về lĩnh vực khai phá dữ liệu và
một số khái niệm liên quan, đồng thời chỉ ra các giai đoạn thực hiện trong quá
trình khám phá tri thức. Phần tiếp theo của chương là trình bày ngắn gọn, có
hệ thống về các kỹ thuật, các dạng dữ liệu thường được sử dụng trong khai
phá dữ liệu.
Chương 2 Hệ thống hóa các kỹ thuật khai phá dữ liệu web, khai phá
theo nội dung web, khai phá theo sử dụng web, khai phá theo cấu trúc web.
Qua đó, đi sâu phân tích chi tiết các kỹ thuật, giải pháp trong Khai phá dữ liệ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.vn3
web và ý nghĩa của Khai phá dữ liệu web, các kỹ thuật được sử dụng trong
quá trình khai phá dữ liệu web, quy trình khai phá dữ liệu web theo thuật toán
Crawler, Hits, Phần cuối của chương trình bày vắn tắt, tổng kết về các đặc
trưng của các phương pháp khai phá dữ liệu web đồng thời nêu các kỹ thuật
đánh giá kết quả khai phá dữ liệu web.
Chương 3 Giới thiệu chương trình giới thiệu việc làm, quy trình hoạt
động của hệ thống cung cấp dữ liệu việc làm, thu thập dữ liệu về kho cơ sở dữ
trong các tổ chức tài chính, thương mại, khoa học,…
Đúng như John Naisbett đã cảnh báo “Chúng ta đang chìm ngập trong
dữ liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một
nguồn “tài nguyên” có nhiều giá trị bởi thông tin là yếu tố then chốt trong mọi
hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ, … nó giúp
những người điều hành và quản lý có hiểu biết về môi trường và tiến trình
hoạt động của tổ chức mình trước khi ra quyết định để tác động đến quá trình
hoạt động nhằm đạt được các mục tiêu một cách hiệu quả và bền vững.
Khai phá dữ liệu là một lĩnh vực mới xuất hiện, nhằm tự động khai thác
những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL lớn
cho các đơn vị, tổ chức, doanh nghiệp, … từ đó làm 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ả khoa
học cùng những ứng dụng thành công trong khám phá tri thức, cho thấy khai
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn5
phá dữ liệu 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ụ phân tích dữ
liệu truyền thống. Hiện nay, khai phá dữ liệu đã ứ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, điều trị y học, viễn thông, tin
– sinh,…
1.2 Khai phá dữ liệu là gì ?
Khai phá dữ liệu là một hướng nghiên mới ra đời hơn một thập niên trở
lại đây, các kỹ thuật chính được áp dụng trong lĩnh vực này phần lớn được
thừa kế từ lĩnh vực CSDL, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác
suất thống kê, và tính toán hiệu năng cao. Do sự phát triển nhanh của khai phá
dữ liệu về phạm vi áp dụng và các phương pháp tìm kiếm tri thức, nên đã có
nhiều quan điểm khác nhau về khai phá dữ liệu. Tuy nhiên, ở một mức trừu
tượng nhất định, chúng ta định nghĩa Khai phá dữ liệu như sau:
song song và hiệu năng cao,…
Quá trình KDD có thể phân thành các giai đoạn sau:
Trích chọn dữ liệu: 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 (databases, data warehouses, data
repositories) ban đầu theo một số tiêu chí nhất định.
Tiền xử lý dữ liệu: là bước làm sạch dữ liệu (xử lý với dữ liệu
không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .v.v.), 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, .v.v.), rời rạc hóa dữ liệu (rời rạc hóa dựa vào
histograms, dựa vào entropy, dựa vào phân khoảng, .v.v.). 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ề dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở
bước sau.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn7
Khai phá dữ liệu: đây là bước áp dụng những kỹ thuật phân tích
(phần nhiều là 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 thông tin, 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 chuyển dạng 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,
.v.v. Đồ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.
Các giai đoạn trong KDD đƣợc thể hiện trực quan nhƣ hình dƣới đây :
Data Mining
Các mẫu
Đánh giá và
giải thích
Biểu diễn
tri
Tri thứ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.vn8
1.4 Các kỹ thuật áp dụng trong khai phá dữ liệu
1.4.1 Các kỹ thuật tiếp cận trong khai phá dữ liệu
Khám phá tri thức trong CSDL là một lĩnh vực liên ngành, bao gồm :
Tổ chức dữ liệu, học máy, trí tuệ nhân tạo và các khoa học khác, sự kết hợp
này có thể được diễn tả như trong hình 2 dưới đây : Hình 1.2 Các lĩnh vực liên quan đến Khám phá tri thức trong CSDL
Nếu đứng trên quan điểm của học máy (Machine Learning), thì các
kỹ thuật trong khai phá dữ liệu, bao gồm :
Học có giám sát (Supervised learning) : Là quá trình gán nhãn lớp cho
các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông
tin về nhãn lớp đã biết.
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
(unsupervised learning).
Mô tả khái niệm (concept description and summarization): thiên
về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.
1.4.2 Các dạng dữ liệu có thể khai phá
Do khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với
rất nhiều kiểu dữ liệu khác nhau . Sau đây là một số dạng dữ liệu điển hình:
CSDL quan hệ, CSDL đa chiều (multidimensional structures, data
warehouses), CSDL dạng giao dịch, CSDL quan hệ - hướng đối tượng, dữ
liệu không gian và thời gian, Dữ liệu chuỗi thời gian, CSDL đa phương tiện,
dữ liệu Text và Web,…
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn10
1.5 Ứng dụng của khai phá dữ liệu
Phạm vi ứng dụng của data mining rất rộng, bao phủ hầu hết các lĩnh
vực. Tuy vậy có thể tóm lược lại phạm vi ứng dụng của data ming trong các
bài toán yêu cầu có cần có các chức năng nghiệp vụ sau:
Tự động hóa việc dự doán các xu thế và hành vi sẽ diễn ra trong tương
lai: Khai phá dữ liệu tự động hóa quá trình tìm kiếm và trích xuất các tập
thông tin có mối quan hệ hoặc tương quan trong một tập dữ liệu cực lớn.
Những vấn đề trên câu hỏi đặt ra với các cách truyền thống đòi hỏi một quá
trình rất phức tạp và tốn kém cả về tài chính và thời gian để giải đáp thì giờ có
thể trả lời một cách nhanh chóng trong khi giá thành là thấp nhất. Một ví dụ
đơn giản trong quảng cáo online là quá trình targeting, khi một người dùng
click vào một banner quảng cáo bán giầy dành cho nữ giới, thì khả năng
người đó là nữ và họ đang quan tâm đến đôi giầy đó, khi hệ thống nhận diện
được điều này thì có thể target thêm các kiểu dáng giầy khác nhau, kích cỡ
khác nhau, giá thành khác nhau với mục tiêu là người dùng sẽ kết thúc quá
"Khám phá ra các vị trí địa lý thuận lợi cho việc xây dựng các kho hàng phục
vụ mua bàn hàng của một công ty thương mại" hoặc "Xác định các cụm ảnh
như ảnh của các loài động vật như loài thú, chim, … trong tập CSDL ảnh về
động vật nhằm phục vụ cho việc tìm kiếm ảnh" hoặc “xác định các nhóm
người bệnh nhằm cung cấp thông tin cho việc phân phối các thuốc điều trị
trong y tế ”, hoặc “nhóm các khách hàng trong CSDL ngân hàng có vốn các
đầu tư vào bất động sản cao”… Như vậy, PCDL là một phương pháp xử 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 tương tự. Hiện nay, các
kỹ thuật phân cụm đã được ứng dụng rộng rãi trong các ứng dụng như : nhận
dạng mẫu, xử lý ảnh, nghiên cứu thị trường, trực quan hoá, ….Trong nội dung
tiếp theo, luận văn sẽ đề cập đến vấn đề PCDL, đây là một hướng nghiên cứ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.vn12
quan trọng trong lĩnh vực khai phá dữ liệu và là nội dung tìm hiểu, nghiên cứu
trọng tâm của luận văn.
1.7 Khai phá dữ liệu web
Khai phá dữ liệu web là việc sử dụng các phương pháp khai phá dữ liệu
để tự động hóa quá trình khám phá và trích rút những thông tin hữu ích từ các
tài liệu, các dịch vụ và cấu trúc web. Hay nói cách khác khai phá dữ liệu web
là việc trích chọn ra các thành phần được quan tâm hay được đánh giá là có
ích cùng các thông tin tiềm năng từ các tài nguyên hoặc các hoạt động liên
quan tới World Wide Web, nó có thể giúp con người rút ra những tri thức
mới, cải tiến việc thiết kế các website và phát triển thương mại điện tử tốt
hơn.
a. Nhu cầu
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một
khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với
ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm
và ngược lại. Còn về phía khách hàng sau khi phân tích chúng ta cũng biết
được khách hàng hay tập trung về vấn đề gì, để từ đó có thể đưa ra những hỗ
trợ thêm cho khách hàng đó. Từ những nhu cầu thực tế trên, phân lớp và tìm
kiếm trang Web vẫn là bài toán hay và cần phát triển nghiên cứu hiện nay.
b. Khó khăn
Hệ thống phục vụ World Wide Web như là một hệ thống trung tâm rất
lớn phân bố rộng cung cấp thông tin trên mọi lĩnh vực khoa học, xã hội,
thương mại, văn hóa, Web là một nguồn tài nguyên giàu có cho Khai phá dữ
liệu. Những quan sát sau đây cho thấy Web đã đưa ra sự thách thức lớn cho
công nghệ Khai phá dữ liệu
1. Web dƣờng nhƣ quá lớn để tổ chức thành một kho dữ liệu phục
vụ Dataming
Các CSDL truyền thống thì có kích thước không lớn lắm và thường
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn14
được lưu trữ ở một nơi, Trong khi đó kích thước Web rất lớn, tới hàng
terabytes và thay đổi liên tục, không những thế còn phân tán trên rất nhiều
máy tính khắp nơi trên thế giới. Một vài nghiên cứu về kích thước của Web
đã đưa ra các số liệu như sau: Hiện nay trên Internet có khoảng hơn một tỷ
các trang Web được cung cấp cho người sử dụng. giả sử kích thước trung
bình của mỗi trang là 5-10Kb thì tổng kích thước của nó ít nhất là khoảng 10
terabyte. Còn tỷ lệt ăng của các trang Web thì thật sự gây ấn tượng. Hai năm
gần đây số các trang Web tăng gấp đôi và còng tiếp tục tăng trong hai năm
tới. Nhiều tổ chức và xã hội đặt hầu hết những thông tin công cộng của họ lên
Web. Như vậy việc xây dựng một kho dữ liệu (datawarehouse) để lưu trữ, sao
chép hay tích hợp các dữ liệu trên Web là gần như không thể.
2. Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài
dùng vẫn đang nhanh chóng lan rộng. Mỗi người dùng có một kiến thức, mối
quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng không có kiến thức
tốt về cấu trúc mạng thông tin, hoặc không có ý thức cho những tìm kiếm, rất
dễ bị "lạc" khi đang "mò mẫm" trong "bóng tối" của mạng hoặc sẽ chán khi
tìm kiếm mà chỉ nhận những mảng thông tin không mấy hữu ích.
5. Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích
Theo thống kê, 99% của thông tin Web là vô ích với 99% người dùng
Web. Trong khi những phần Web không được quan tâm lại bị búi vào kết quả
nhận được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào
để nhận được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng?
Như vậy chúng ta có thể thấy các điểm khác nhau giữa việc tìm kiếm trong
một CSDL truyền thống với vviệc tìm kiếm trên Internet. Những thách thức
trên đã đẩy mạnh việc nghiên cứu khai phá và sử dụng tài nguyên trên
Internet.
c. Thuận lợi
Bên cạnh những thử thách trên, còn một số lợi thế của trang Web cung
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn16
cấp cho công việc khai phá Web.
1. Web bao gồm không chỉ có các trang mà còn có cả các hyperlink trỏ
từ trang này tới trang khác. Khi một tác giả tạo một hyperlink từ trang của
ông ta tới một trang A có nghĩa là A là trang có hữu ích với vấn đề đang bàn
luận. Nếu trang A càng nhiều Hyperlink từ trang khác trỏ đến chứng tỏ trang
A quan trọng. Vì vậy số lượng lớn các thông tin liên kết trang sẽ cung cấp
một lượng thông tin giàu có về mối liên quan, chất lượng, và cấu trúc của nội
dung trang Web, và vì thế là một nguồn tài nguyên lớn cho khai phá Web.
2. Một máy chủ Web thường đăng ký một bản ghi đầu vào (Weblog
entry) cho mọi lần truy cập trang Web. Nó bao gồm địa chỉ URL, địa chỉ IP,
Trong đó khai phá nội dung web được chia thành khai phá theo kết quả
tìm kiếm và khai phá văn bản web.
Khai phá sử dụng web được chia thành khai phá các mẫu truy cập và
phân tích các xu hướng cá nhân.
Tồng kết chƣơng 1:
Trong chương này trình bày những kiến thức cơ bản về lĩnh vực khai
phá dữ liệu và một số khái niệm liên quan, đồng thời chỉ ra các giai đoạn thực
hiện trong quá trình khám phá tri thức. Phần tiếp theo của chương là trình bày
ngắn gọn, có hệ thống về các kỹ thuật, các dạng dữ liệu thường được sử dụng
trong khai phá dữ liệu.
Ngoài ra trong chương này còn đề cập đến một lĩnh vực cụ thể của khai
phá dữ liệu đó là khai phá dữ liệu web. Trong phạm vi chương 1 chỉ đề cập
đến khái niệm, các đặc trưng và phân loại khai phá dữ liệu web.
KHAI PHÁ WEB
Khai phá nội
dung Web
Khai phá cấu trúc
Web
Khai phá sử dụng
Web
Khai phá kết quả
tìm kiếm
Khai phá văn bản
Web
Khai phá các
mẫu truy cập
Phân tích các xu
hướng cá nhân
liệu đa phương tiện như âm thanh, hình ảnh, phần biến đổi dữ liệu và siêu liên
kết,…
KHAI PHÁ WEB
Khai phá nội
dung Web
Khai phá cấu trúc
Web
Khai phá sử dụng
Web
Khai phá kết quả
tìm kiếm
Khai phá văn bản
Web
Khai phá các mẫu
truy cập
Phân tích các xu
hướng cá nhân
Hình 2.1 Phân loại khai phá Web
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
Copyright: Tài liệu đại học ©