Tài liệu Luận văn Nghiên cứu một số kỹ thuật lấy tin tự động trên internet: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------------------
TRƯƠNG MẠNH HÀ
NGHIÊN CỨU MỘT SỐ KỸ THUẬT LẤY TIN
TỰ ĐỘNG TRÊN INTERNET
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Người hướng dẫn khoa học: TS. Phạm Việt Bình
Thái Nguyên - Năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sưu tầm,
tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ
hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên
cứu nào.
Tất cả phần mã nguồn của chương trình đều do tôi tự thiết kế và xây
dựng, trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các
tác giả xuất bản công khai và miễn phí trên mạng Internet.
Nếu sai tôi xin tôi xin hoàn toàn chịu trách nh...
72 trang |
Chia sẻ: hunglv | Lượt xem: 1281 | Lượt tải: 1
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Nghiên cứu một số kỹ thuật lấy tin tự động trên internet, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------------------
TRƯƠNG MẠNH HÀ
NGHIÊN CỨU MỘT SỐ KỸ THUẬT LẤY TIN
TỰ ĐỘNG TRÊN INTERNET
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Người hướng dẫn khoa học: TS. Phạm Việt Bình
Thái Nguyên - Năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sưu tầm,
tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ
hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên
cứu nào.
Tất cả phần mã nguồn của chương trình đều do tôi tự thiết kế và xây
dựng, trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các
tác giả xuất bản công khai và miễn phí trên mạng Internet.
Nếu sai tôi xin tôi xin hoàn toàn chịu trách nhiệm.
Thái Nguyên, ngày 11 tháng 11 năm 2009
Người cam đoan
Trương Mạnh Hà
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
MỞ ĐẦU
Sự phát triển nhanh chóng của mạng Internet đã 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ác tài liệu siêu văn
bản chứa đựng văn bản và thường nhúng các liên kết đến các tài liệu khác
phân bố trên Web. Ngày nay, Web bao gồm hàng tỉ tài liệu của hàng triệu tác
giả được tạo ra và được phân tán qua hàng triệu máy tính được kết nối qua
đường dây điện thoại, cáp quang, sóng radio... Web đang ngày càng được sử
dụng phổ biến trong nhiều lĩnh vực như báo chí, phát thanh, truyền hình, hệ
thống bưu điện, trường học, các tổ chức thương mại, chính phủ ... Chính vì
vậy lĩnh vực Web mining hay tìm kiếm tự động các thông tin phù hợp và có
giá trị trên Web là một chủ đề quan trọng trong Data Mining và là vấn đề
quan trọng của mỗi đơn vị, tổ chức có nhu cầu thu thập và tìm kiếm thông tin
trên Internet [2].
Các hệ thống tìm kiếm thông tin hay nói ngắn gọn là các máy tìm kiếm
Web thông thường trả lại một danh sách các tài liệu được phân hạng mà người
dùng sẽ phải tốn công chọn lọc trong một danh sách rất dài để có được những
tài liệu phù hợp. Ngoài ra các thông tin đó thường rất phong phú, đa dạng và
liên quan đến nhiều đối tượng khác nhau. Điều này tạo nên sự nhập nhằng gây
khó khăn cho người sự dụng trong việc lấy được các thông tin cần thiết.
Có nhiều hướng tiếp cận khác nhau để giải quyết vấn đề này, các hướng
này thường chú ý giảm sự nhập nhằng bằng các phương pháp lọc hay thêm
các tùy chọn để cắt bớt thông tin và hướng biểu diễn các thông tin trả về bởi
các máy tìm kiếm thành từng cụm để cho người dùng có thể dễ dàng tìm được
thông tin mà họ cần. Đã có nhiều thuật toán phân cụm tài liệu dựa trên phân
cụm ngoại tuyến toàn bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu của các
máy tìm kiếm là quá lớn và luôn thay đổi để có thể phân cụm ngoại tuyến. Do
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
đó, việc phân cụm phải được ứng dụng trên tập các tài liệu nhỏ hơn được trả
về từ các truy vấn và thay vì trả về một danh sách rất dài các thông tin gây
nhập nhằng cho người sử dụng cần có một phương pháp tổ chức lại các kết
quả tìm kiếm một cách hợp lý.
Do những vấn đề cấp thiết được đề cập ở trên nên em chọn đề tài:
"Nghiên cứu một số kỹ thuật lấy tin tự động trên internet"
Mục tiêu của đề tài: Nghiên cứu xây dựng giải pháp phát triển hệ thống
phần mềm thu thập, đánh giá và phân cụm thông tin tự động trên Internet
phục vụ cho việc nghiên cứu, học tập, giảng dạy.
Ngoài phần mở đầu, phần kết luận, mục lục, tài liệu tham khảo, phụ lục,
luận văn gồm 3 chương:
- Chương 1: Khái quát về khai phá dữ liệu và phân cụm tài liệu Web
Giới thiệu một số khái niệm cơ bản về khai phá dữ liệu, khai phá dữ liệu
web, các hướng tiếp cận, ứng dụng của khai phá dữ liệu, và nêu bài toàn phân
cụm tài liệu Web.
- Chương 2: Một số thuật toán phân cụm tài liệu
Nghiên cứu một số kỹ thuật phân cụm tài liệu liên quan, tư tưởng của
các thuật toán đã được nghiên cứu, nghiên cứu đề xuất phương pháp cải tiến.
- Chương 3: Ứng dụng trong lấy tin tự động
Ứng dụng xây dựng bài toán Thu thập dữ liệu về Kinh tế trên Internet.
Để hoàn thành được luận văn Cao học, em xin được gửi lời cảm ơn tới
các thầy trong Viện Công nghệ thông tin, các thầy trong Khoa Công nghệ
thông tin đã tận tình giảng dạy, cung cấp nguồn kiến thức quý giá trong suốt
quá trình học tập.
Đặc biệt em xin chân thành cảm ơn TS. Phạm Việt Bình, đã tận tình
hướng dẫn, góp ý, tạo điều kiện cho em hoàn thành luận văn này.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
Xin chân thành cảm ơn các thầy cô, anh chị em đang công tác tại phòng
VRLAB - Viện công nghệ thông tin - Viện khoa học và Công nghệ Việt Nam,
các thầy cô đang công tác tại Viện Công nghệ thông tin - Viện khoa học và
Công nghệ Việt Nam.
Cảm ơn đồng nghiệp Đỗ Văn Đại đã cung cấp những tài liệu, cùng những
kinh nghiệm quý báu đã được làm trong cuốn Đồ án tốt nghiệp đại học của
đồng nghiệp Đỗ Văn Đại giúp cho em trong quá trình nghiên cứu giảm bớt
được những khó khăn trong việc tiếp cận vấn đề và nghiên cứu tài liệu.
Xin được cảm ơn Ban lãnh đạo Khoa Công nghệ thông tin - Đại học Thái
Nguyên, lãnh đạo phòng Công nghệ thông tin - Thư viện, cùng toàn thể các
đồng nghiệp trong Khoa Công nghệ thông tin - Đại học Thái Nguyên đã giúp
đỡ em về thời gian, vật chất và tinh thần giúp em hoàn thành tốt nhiệm vụ học
tập, công tác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Chương 1: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ
PHÂN CỤM TÀI LIỆU WEB
1.1 Khai phá dữ liệu:
Trong thời đại ngày nay, với sự phát triển vượt bậc của công nghệ thông
tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt
động hàng ngày. Từ khối dữ liệu này, các kỹ thuật trong Khai phá dữ liệu và
Máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa
biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt
động của hệ thống thông tin ban đầu.
Giáo sư Tom Mitchell đã đưa ra định nghĩa của Khai phá dữ liệu như
sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui
tắc và cải thiện những quyết định trong tương lai.” Với một cách tiếp cận ứng
dụng hơn, Tiến sĩ Fayyad đã phát biểu: “Khai phá dữ liệu, thường được xem
là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất
những thông tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng
các qui luật, ràng buộc, qui tắc trong cơ sở dữ liệu”. Nói tóm lại, Khai phá dữ
liệu là một quá trình học tri thức mới từ những dữ liệu đã thu thập được [4].
Mô hình khai phá dữ liệu bao gồm năm giai đoạn chính:
- Tìm hiểu nghiệp vụ và dữ liệu
- Chuẩn bị dữ liệu
- Mô hình hoá dữ liệu
- Hậu xử lý và đánh giá mô hình
- Triển khai tri thức
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa
trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình
Khai phá dữ liệu là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực
Khai phá dữ liệu.
Trong giai đoạn đầu tiên, tìm hiểu nghiệp vụ dữ liệu, nhà tư vấn nghiên
cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm các tri thức cấu trúc về hệ
thống và tri thức, các nguồn dữ liệu hiện hữu, ý nghĩa, vai trò và tầm quan
trọng của các thực thể dữ liệu. Việc nghiên cứu này được thực hiện qua việc
tiếp xúc giữa nhà từ vấn và người dùng. Khác với phương pháp giải quyết vấn
đề truyền thống khi bài toán được xác định chính xác ở bước đầu tiên, nhà tư
vấn tìm hiểu các yêu cầu sơ khởi của người dùng và đề nghị các bài toán tiềm
năng có thể giải quyết với nguồn dữ liệu hiện hữu. Tập các bài toán tiềm năng
được tinh chỉnh và làm hẹp lại trong các giai đoạn sau. Các nguồn và đặc tả
dữ liệu có liên quan đến tập các bài toán tiềm năng cũng được xác định [4].
Giai đoạn chuẩn bị dữ liệu sử dụng các kỹ thuật tiền xử lý để biến đổi và
cải thiện chất lượng dữ liệu để thích hợp với những yêu cầu của các giải thuật
học. Phần lớn các giải thuật khai phá dữ liệu hiện nay chỉ làm việc trên một
tập dữ liệu đơn và phẳng, do đó dữ liệu phải được trích xuất và biến đối từ các
dạng cơ sơ dữ liệu phân bố, quan hệ hay hướng đối tượng sang dạng cơ sở dữ
liệu quan hệ đơn giản với một bảng dữ liệu. Các giải thuật tiền xử lý tiêu biểu
bao gồm:
(a) Xử lý dữ liệu bị thiếu/mất: các dữ liệu bị thiếu sẽ được thay thế bởi
các giá trị thích hợp.
(b) Khử sự trùng lắp: các đối tượng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ
thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
(c) Giảm nhiễu: nhiễu và các đối tượng tách rời (outlier) khỏi phân bố
chung sẽ bị loại đi khỏi dữ liệu.
(d) Chuẩn hóa: miền giá trị của dữ liệu sẽ được chuẩn hóa.
(e) Rời rạc hóa: các dữ liệu số sẽ được biến đổi ra các giá trị rời rạc.
(f) Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có.
(g) Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt.
Các bài toán được giải quyết trong giai đoạn Mô hình hóa dữ liệu. Các
giải thuật học sử dụng các dữ liệu đã được tiền xử lý trong giai đoạn hai để
tìm kiếm các qui tắc ẩn và chưa biết. Công việc quan trọng nhất trong giai
đoạn này là lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Các bài
toán được phân loại vào một trong những nhóm bài toán chính trong Khai phá
dữ liệu dựa trên đặc tả của chúng [4].
Các mô hình kết quả của giai đoạn ba sẽ được hậu xử lý và đánh giá
trong giai đoạn (d). Dựa trên các đánh giá của người dùng sau khi kiểm tra
trên các tập thử, các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần. Chỉ
các mô hình đạt được mức yêu cầu cơ bản của người dùng mới đưa ra triển
khai trong thực tế. Trong giai đoạn này, các kết quả được biến đổi từ dạng học
thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng.
Trong giai đoạn cuối, Triển khai tri thức, các mô hình được đưa vào
những hệ thống thông tin thực tế dưới dạng các module hỗ trợ việc đưa ra
quyết định.
Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình Khai phá dữ liệu
là rất quan trọng cho việc nghiên cứu trong Khai phá dữ liệu [3]. Một giải
thuật trong Khai phá dữ liệu không thể được phát triển độc lập, không quan
tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục
tiêu cụ thể. Do đó, sự hiểu biết bối cảnh vận dụng là rất cần thiết. Thêm vào
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
đó, các kỹ thuật được sử dụng trong các giai đoạn trước có thể ảnh hưởng đến
hiệu quả của các giải thuật sử dụng trong các giai đoạn tiếp theo.
1.1.1 Các dạng dữ liệu
1.1.1.1 Full text
Dữ liệu dạng Full text là một dạng dữ liệu phi cấu trúc với thông tin chỉ
gồm các tài liệu dạng text. Mỗi tài liệu chứa thông tin về một vấn đề nào đó
thể hiện qua nội dung của tất cả các từ cấu thành tài liệu đó. Ý nghĩa của mỗi
từ trong tài liệu không cố định mà tùy thuộc vào từng ngữ cảnh khác nhau sẽ
mang ý nghĩa khác nhau. Các từ trong tài liệu được liên kết với nhau theo một
ngôn ngữ nào đó.
Trong các dữ liệu hiện nay thì văn bản là một trong những dữ liệu phổ
biến nhất, nó có mặt khắp mọi nơi và chúng ta thường xuyên bắt gặp do đó
các bài toán về xử lý văn bản đã được đặt ra khá lâu và hiện nay vẫn là một
trong những vấn đề trong khai phá dữ liệu Text, trong đó có những bài toán
đáng chú ý như tìm kiếm văn bản, phân loại văn bản, phân cụm văn bản hoặc
dẫn đường văn bản.
Cơ sở dữ liệu Full text là một dạng cơ sở dữ liệu phi cấu trúc mà dữ liệu
bao gồm các tài liệu và thuộc tính của tài liệu. Cơ sở dữ liệu Full_Text thường
được tổ chức như một tổ hợp của hai thành phần: Một cơ sở dữ liệu có cấu
trúc thông thường (chứa đặc điểm của các tài liệu) và các tài liệu.
1.1.1.2 Hypertext
Theo từ điển của Đại Học Oxford (Oxford English Dictionary Additions
Series) thì Hypertext được định nghĩa như sau: Đó là loại Text không phải
đọc theo dạng liên tục đơn, nó có thể được đọc theo các thứ tự khác nhau, đặc
biệt là Text và ảnh đồ họa (Graphic) là các dạng có mối liên kết với nhau theo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
cách mà người đọc có thể không cần đọc một cách liên tục. Ví dụ khi đọc một
cuốn sách người đọc không phải đọc lần lượt từng trang từ đầu đến cuối mà
có thể nhảy cóc đến các đoạn sau để tham khảo về các vấn đề họ quan tâm.
Như vậy văn bản Hypertext bao gồm dạng chữ viết không liên tục,
chúng được phân nhánh và cho phép người đọc có thể chọn cách đọc theo ý
muốn của mình. Hiểu theo nghĩa thông thường thì Hypertext là một tập các
trang chữ viết được kết nối với nhau bởi các liên kết và cho phép người đọc
có thể đọc theo các cách khác nhau. Như ta đã làm quen nhiều với các trang
định dạng HTML, trong các trang có những liên kết trỏ tới từng phần khác
nhau của trang đó hoặc trỏ tới trang khác và người đọc sẽ đọc văn bản dựa
vào những liên kết đó.
Bên cạnh đó, Hypertext cũng là một dạng văn bản Text đặc biệt nên
cũng có thể bao gồm các chữ viết liên tục (là dạng phổ biến nhất của chữ
viết). Do không bị hạn chế bởi tính liên tục trong Hypertext, chúng ta có thể
tạo ra các dạng trình bày mới, do đó tài liệu sẽ phản ánh tốt hơn nội dung
muốn diễn đạt. Hơn nữa người đọc có thể chọn cho mình một cách đọc phù
hợp chẳng hạn như đi sâu vào một vấn đề mà họ quan tâm. Sáng kiến tạo ra
một tập các văn bản cùng với các con trỏ tới các văn bản khác để liên kết một
tập các văn bản có mối quan hệ với nhau là một cách thực sự hay và hữu ích
để tổ chức thông tin. Với người viết, cách này cho phép họ có thể thoải mái
loại bỏ những băn khoăn về thứ tự trình bày mà có thể tổ chức vấn đề thành
những phần nhỏ rồi sử dụng kết nối để chỉ ra mối liên hệ giữa các phần nhỏ
đó với nhau.
Với người đọc, cách này cho phép họ có thể đi tắt trên mạng thông tin và
quyết định phần thông tin nào có liên quan đến vấn đề mà họ quan tâm để tiếp
tục tìm hiểu. So sánh với cách đọc tuyến tính tức là đọc lần lượt thì Hypertext
đã cung cấp cho chúng ta một giao diện để có thể tiếp xúc với nội dung thông
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
tin hiệu quả hơn rất nhiều. Theo khía cạnh của các thuật toán học máy thì
Hypertext đã cung cấp cho chúng ta cơ hội nhìn ra ngoài phạm vi một tài liệu
để đánh giá nó, nghĩa là có tính cả đến các tài liệu có liên kết với nó. Tất
nhiên không phải tất cả các tài liệu có liên kết đến nó đều có ích cho việc
đánh giá, đặc biệt là khi các siêu liên kết có thể chỉ đến nhiều loại các tài liệu
khác nhau.
Có hai khái niệm về Hypertext cần quan tâm:
Hypertext Document (Tài liệu siêu văn bản): Là một tài liệu văn bản đơn
trong hệ thống siêu văn bản. Nếu tưởng tượng hệ thống siêu văn bản là một
đồ thị thì các tài liệu tương ứng các nút.
Hypertext Link (Liên kết siêu văn bản): Là một tham chiếu để nối một
tài liệu Hypertext này với một tài liệu Hypertext khác. Các siêu liên kết đóng
vai trò quan trọng như những đường nối trong đô thị nói trên.
Hypertext là loại dữ liệu phổ biến hiện nay và cũng là loại dữ liệu có nhu
cầu tìm kiếm rất lớn. Nó là dữ liệu phổ biến trên mạng thông tin Internet cơ
sở dữ liệu Hypertext với văn bản dạng “ mửa cấu trúc” do xuất hiện thêm các
“thẻ ”: Thẻ cấu trúc (tiêu đề, mở đầu, nội dung), thẻ nhấn trình bày chữ (đậm,
nghiêng,..). Nhờ các thẻ này mà chúng ta có thêm một tiêu chuẩn (so với tài
liệu Full text) để có thể tìm kiếm và phân loại chúng. Dựa vào các thẻ đã quy
định trước chúng ta có thể phân thành các độ ưu tiên khác nhau cho các từ
khóa nếu chúng xuất hiện ở những vị trí khác nhau. Ví dụ khi tìm kiếm các tài
liệu có nội dung liên quan đến “people ” thì chúng ta đưa từ khóa tìm kiếm là
“people ” và các tài liệu có từ khóa “people ” đứng ở tiêu đề thì sẽ gần với
yêu cầu tìm kiếm hơn.
1.1.2 Các bài toán thông dụng trong Khai phá dữ liệu
Trong Khai phá dữ liệu, các bài toán có thể phân thành bốn loại chính.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
Bài toán thông dụng nhất trong Khai phá dữ liệu là Phân lớp
(Classification). Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện
của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng
để phân các dữ liệu mới vào một trong những lớp (còn gọi là loại) đã được xác
định trước. Nhận dạng cũng là một bài toán thuộc kiểu phân loại.
Với mô hình học tương tự như bài toán Phân loại, lớp bài toán Dự đoán
(Prediction) sẽ học ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ
dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán.
Bài toán tiêu biểu trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch
trong kinh doanh.
Các giải thuật Tìm luật liên kết (Association Rule) tìm kiếm các mối liên
kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua
kèm với nhau trong siêu thị.
Các kỹ thuật Phân cụm (Clustering) sẽ nhóm các đối tượng dữ liệu có tính
chất giống nhau vào cùng một nhóm. Có nhiều cách tiếp cận với những mục tiêu
khác nhau trong phân loại. Các kỹ thuật trong bài toán này thường được vận
dụng trong vấn đề phân hoạch dữ liệu tiếp thị hay khảo sát sơ bộ các dữ liệu.
1.1.3 Các môi trường khai phá dữ liệu
Do các đặc tính được nêu ra trong phần 2, các công cụ Khai phá dữ liệu
thường được xây dựng theo dạng môi trường phát triển, dễ thử nghiệm và
thay đổi các tác vụ Khai phá dữ liệu. Hình 1.1 giới thiệu giao diện trực quan
của một quá trình Khai phá dữ liệu trong môi trường Clementine [4].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Hình 1.1: Giao diện trực quan của môi trường khai phá dữ liệu Clementine
Trong các môi trường này, một quá trình Khai phá dữ liệu được mô tả
như một dòng các tác vụ nối tiếp, bắt đầu bằng việc lấy dữ liệu thực từ nguồn
dữ liệu lịch sử, thao tác biến đổi dữ liệu sang dạng thích hợp, học và sinh ra
mô hình mới. Mô hình này sau đó được thử nghiệm trên dữ liệu thực để đưa
ra các đánh giá. Nếu mô hình được đánh giá chưa thỏa mãn các yêu cầu đề ra,
các tác vụ trong quá trình được tinh chỉnh rồi thực hiện lại. Qui trình này
được lặp lại cho đến khi nào mô hình sinh ra được đánh giá có hiệu quả tốt.
Mô hình sinh ra cuối cùng sẽ được triển khai sử dụng trong thực tế. Các môi
trường như vậy rất phù hợp cho quá trình Khai phá dữ liệu vì tính chất thử
nghiệm và cần thay đổi nhiều của nó.
Việc sử dụng các môi trường thử nghiệm đã thúc đẩy nhanh việc áp
dụng Khai phá dữ liệu. Thay vì phải bỏ nhiều công sức và thời gian vào việc
xây dựng các chương trình hoàn chỉnh và hiện thực các giải thuật, khi dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
sẵn sàng cho việc sử dụng, người vận dụng Khai phá dữ liệu chỉ cần phải tìm
hiểu các kiến thức cần thiết, khảo sát tính chất dữ liệu, vận dụng các kỹ thuật
đã được hiện thực sẵn trên dữ liệu, đánh giá các kết quả tạm thời và vận dụng
kết quả cuối cùng. Với phương thức hiện đại như vậy, việc áp dụng Khai phá
dữ liệu trở nên rất dễ dàng và tiện lợi.
Weka là môi trường thử nghiệm Khai phá dữ liệu do các nhà khoa học
thuộc trường Đại học Waitako, NZ, khởi xướng và được sự đóng góp của rất
nhiều nhà nghiên cứu trên thế giới. Weka là phần mềm mã nguồn mở, cung
cấp công cụ trực quan và sinh động cho sinh viên và người ngoài ngành Công
nghệ thông tin tìm hiểu về Khai phá dữ liệu. Weka còn cho phép các giải
thuật học mới phát triển có thể tích hợp vào môi trường của nó.
1.1.4 Các ứng dụng của khai phá dữ liệu
Khai phá dữ liệu được vận dụng trong nhiều lĩnh vực khác nhau nhằm
khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin
Tùy theo bản chất của từng lĩnh vực, việc vận dụng Khai phá dữ liệu có
những cách tiếp cận khác nhau. Khai phá dữ liệu cũng được vận dụng hiệu
quả để giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao
như tìm kiếm mỏ dầu từ ảnh viễn thám, xác định các vùng gãy trong ảnh địa
chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất,…
Các bài toán này đã được giải quyết từ khá lâu bằng các kỹ thuật nhận dạng
hay xác suất nhưng được giải quyết với yêu cầu cao hơn bởi các kỹ thuật của
Khai phá dữ liệu. Phân nhóm và dự đoán là những công cụ rất cần thiết cho
việc qui hoạch và phát triển các hệ thống quản lý và sản xuất trong thực tế.
Các kỹ thuật Khai phá dữ liệu đã được áp dụng thành công trong việc dự đoán
tải sử dụng điện năng cho các công ty cung cấp điện, lưu lượng viễn thông
cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
giá trị của sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm
các khách hàng tiềm năng,…
Ngoài ra, Khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như
phát hiện tội phạm hay tăng cường an ninh xã. Việc vận dụng thành công đã
mang lại những hiệu quả thiết thực cho các hoạt động diễn ra hàng ngày trong
đời sống.
1.2. Phân cụm tài liệu và phân cụm tài liệu Web
Phân cụm (Clustering) là quá trình nhóm một tập các đối tượng vật lý
hoặc trừu tượng thành các nhóm hay các lớp đối tượng tương tự nhau. Một
cụm (cluster) là một tập các đối tượng giống nhau hay là tương tự nhau,
chúng khác hoặc ít tương tự so với các đối tượng thuộc lớp khác. Không
giống như quá trình phân loại, 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 vào
lớp của nó, trong quá trình chia lớp ta không hề biết trước tính chất của các
lớp và thường dựa vào mối quan hệ của các đối tượng để tìm ra sự giống nhau
giữa các đối tượng dựa vào một độ đo nào đó đặc trưng cho mỗi lớp.
Việc phân cụm không thực hiện độc lập mà thường sử dụng kết hợp với
các phương pháp khác. Một cách phân cụm được đưa ra cũng phải có một
phương pháp áp dụng trên các lớp đó để đưa ra được ý nghĩa của lớp đó.
Ở một mức cơ bản nhất, người ta đã đưa ra định nghĩa Phân cụm dữ liệu
như sau:
"Phân cụm dữ liệu là một kỹ thuật trong DATA MINING, 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 tâm trong tập
dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho ra quyết định".
Hiện nay có rất nhiều vấn đề nghiên cứu về phân cụm trong các lĩnh
vực khác nhau như: Khai phá dữ liệu, thống kê, học máy, công nghệ dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
không gian, sinh học... Do kích thước của các cơ sở dữ liệu tăng lên rất nhanh
nên phân cụm đang là vấn đề đã và đang thu hút nhiều sự quan tâm của các
nhà khoa học trên thế giới.
Trong lĩnh vực thống kê, phân cụm đã được nghiên cứu và phát triển
trong nhiều năm, các vấn đề tập trung chủ yếu vào phân tích các lớp dựa vào
khoảng cách. Các công cụ phân tích lớp dựa trên một số các phương pháp như
k-means, k-medoids đã được ứng dụng trong nhiều hệ thống phần mềm phân
tích thống kê như: S-Plus, SPSS, SAS...
Trong học máy, phân cụm dữ liệu được xem là vấn đề học không có
giám sát, vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ
liệu chưa biết trước các thông tin về lớp hay các thông tin về tập ví dụ huấn
luyện. Trong nhiều trường hợp, khi phân lớp (Classification) được xem vấn
đề học có giám sát thì phân cụm dữ liệu là một bước trong phân lớp dữ liệu,
trong đó Phân cụm dữ liệu sẽ khởi tạo các lớp cho phân lớp bằng cách xác
định các nhãn cho các nhóm dữ liệu.
Trong lĩnh vực khai thác dữ liệu, các vấn đề nghiên cứu trong phân
cụm chủ yếu tập trung vào tìm kiếm các phương pháp phân cụm hiệu quả và
tin cậy trong cơ sở dữ liệu lớn.
Trong lĩnh vực khai phá dữ liệu Web, phân cụm có thể khám phá ra 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...
1.2.1 Khai phá dữ liệu Web
1.2.1.1 Khai phá nội dung Web
Khai phá nội dung web tập trung vào việc khám phá một cách tự động
nguồn thông tin có giá trị trực tuyến. Khai phá nội dung web có thể được tiếp
cận theo 2 cách khác nhau: Tìm kiếm thông tin và khai phá dữ liệu trong cơ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
sở dữ liệu lớn. Khai phá dữ liệu đa phương tiện là một phần của khai phá nội
dung Web, nó hứa hẹn việc khai thác được các thông tin và tri thức ở mức cao
từ nguồn đa phương tiện trực tuyến rộng lớn.
1.2.1.2 Khai phá văn bản Web
Khai phá văn bản Web là việc sử dụng kỹ thuật khai phá dữ liệu đối với
các tập văn bản để tìm ra tri thức có ý nghĩa tiềm ẩm trong nó [12]. Dữ liệu
của nó có là dữ liệu có cấu trúc hoặc không cấu trúc. Kết quả khai phá không
chỉ là trạng thái chung của mỗi tài liệu văn bản mà còn là sự phân loại, phân
cụm các tập văn bản phục vụ cho mục đích nào đó.
Hình 1.2: Quá trình khai phá văn bản Web
- Lựa chọn dữ liệu: Về cơ bản, văn bản văn bản cục bộ được định dạng
tích hợp thành các tài liệu theo mong muốn để khai phá và phân phối trong
nhiều dịch vụ Web bằng việc sử dụng kỹ thuật truy xuất thông tin.
- Tiền xử lý dữ liệu: Để có một kết quả khai phá tốt ta cần có dữ liệu rõ
ràng, chính xác và xoá bỏ dữ liệu hỗn độn và dư thừa. Sau bước tiền xử lý, tập
dữ liệu đạt được thường có các đặc điểm sau:
+ Dữ liệu thống nhất và hỗn hợp cưỡng bức.
+ Làm sạch dữ liệu không liên quan, nhiễu và dữ liệu rỗng. Dữ liệu
không bị mất mát và không bị lặp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
+ Giảm bớt số chiều và làm tăng hiệu quả việc phát hiện tri thức bằng
việc chuyển đổi, quy nạp, cưỡng bức dữ liệu...
+ Làm sạch các thuộc tính không liên quan để giảm bớt số chiều của dữ liệu.
- Biểu diễn văn bản: Khai phá văn bản Web là khai phá các tập tài liệu
HTML. Do đó ta sẽ phải biến đổi và biểu diễn dữ liệu thích hợp cho quá trình
xử lý. Người ta thường dùng mô hình TF-IDF để vector hoá dữ liệu. Nhưng có
một vấn đề quan trọng là việc biểu diễn này sẽ dẫn đến số chiều vector khá lớn.
- Trích rút đặc trưng: Rút ra các đặc trưng là một phương pháp, nó có thể
giải quyết số chiều vector đặc trưng lớn được mang lại bởi khai phá văn bản.
Việc rút ra các đặc trưng dựa trên hàm trọng số:
+ Mỗi từ đặc trưng sẽ nhận được một giá trị trọng số tin cậy bằng việc
tính toán hàm trọng số tin cậy. Tần số xuất hiện cao của các từ đặc trưng là
khả năng chắc chắn nó sẽ phản ánh đến chủ đề của văn bản, thì ta sẽ gán cho
nó một giá trị tin cậy lớn hơn. Hơn nữa, nếu nó là tiêu đề, từ khoá hoặc cụm
từ thì chắc chắn nó có giá trị tin cậy lớn hơn.
+ Việc rút ra các đặc trưng dựa trên việc phân tích thành phần chính
trong phân tích thông kê. Ý tưởng chính của phương pháp này là sử dụng thay
thế từ đặc trưng bao hàm của một số ít các từ đặc trưng chính trong mô tả để
thực hiện giảm bớt số chiều.
- Sau khi tập hợp, lựa chọn và trích ra tập văn bản hình thành nên các
đặc trưng cơ bản, nó sẽ là cơ sở để Khai phá dữ liệu. Từ đó ta có thể thực hiện
trích, phân loại, phân cụm, phân tích và dự đoán.
- Việc trích rút văn bản để đưa ra ý nghĩa chính có thể mô tả tóm tắt tài
liệu văn bản trong quá trình tổng hợp. Sau đó, người dùng có thể hiểu ý nghĩa
chính của văn bản nhưng không cần thiết phải duyệt toàn bộ văn bản. Đây là
phương pháp đặc biệt được sử dụng trong searching engine, thường cần để
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
đưa ra văn bản trích dẫn [10]. Nhiều searching engines luôn đưa ra những câu
dự đoán trong quá trình tìm kiếm và trả về kết quả, cách tốt nhất để thu được
ý nghĩa chính của một văn bản hoặc tập văn bản chủ yếu bằng việc sử dụng
nhiều thuật toán khác nhau.
- Phân lớp văn bản: Nhiều tài liệu được phân lớp tự động một cách
nhanh chóng và hiệu quả cao. Người ta thường sử dụng phương pháp phân
lớp Navie Bayesian và "K - láng giềng gần nhất" để khai phá thông tin văn
bản. Trong phân lớp văn bản, đầu tiên là phân loại tài liệu. Thứ hai, xác định
đặc trưng thông qua số lượng các đặc trưng của tập tài liệu huấn luyện. Cuối
cùng, tính toán kiểm tra phân lớp tài liệu và độ tương tự của tài liệu phân lớp
bằng thuật toán nào đó. Khi đó các tài liệu có độ tương tự cao với nhau thì
nằm trong cùng một phân lớp. Độ tương tự sẽ được đo bằng hàm đánh giá xác
định trước. Nếu ít tài liệu tương tự nhau thì đưa nó về 0. Nếu nó không giống
với sự lựa chọn của phân lớp xác định trước thì xem như không phù hợp.
- Phân cụm văn bản: Chủ đề phân loại không cần xác định trước nhưng
ta phải phân loại các tài liệu vào nhiều cụm. Trong cùng một cụm thì độ
tương tự thấp hơn. Phương pháp sắp xếp liên kết và phương pháp phân cấp
thường được sử dụng trong văn bản phân cụm.
- Phân tích và dự đoán xu hướng: Thông qua việc phân tích các tài liệu
Web, ta có thể nhận được quan hệ phân phối của các dữ liệu đặc biệt trong
từng giai đoạn của nó và có thể dự đoán được tương lai phát triển.
- Đánh giá chất lượng mẫu: Khai phá dữ liệu Web có thể được xem như
quá trình của machine learning. Kết quả của machine learning là các mẫu tri
thức. Phần quan trọng của machine learning là đánh giá kết quả các mẫu. Ta
thường phân lớp các tập tài liệu vào tập huấn luyện và tập kiểm tra. Cuối
cùng, chất lượng trung bình được dung để đánh giá chất lượng mô hình.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
1.2.2. Bài toán phân cụm tài liệu Web
Nắm bắt những đặc tính của người dung Web là việc rất quan trọng đối
với người thiết kế Website. Thông qua việc khai phá lịch sử các mẫu truy xuất
của người dùng Web, không chỉ thông tin về Web được sử dụng như thế nào
mà còn nhiều đặc tính khác như các hành vi của người dùng có thể được xác
định. Sự điều hướng đường dẫn người dùng Web mang lại giá trị thông tin về
mức độ quan tâm của người dùng đến các Website đó.
Khai phá Web theo sử dụng Web là khai phá truy cập Web để khám phá
các mẫu người dùng truy cập vào Website.
Kiến trúc tổng quát của quá trình khai phá theo sử dụng Web như sau:
Hình 1.3: Kiến trúc tổng quát của khai phá theo sử dụng Web
- Các kỹ thuật được sử dụng trong khai phá sử dụng Web:
+ Luật kết hợp: Để tìm ra những Web thường được truy cập cùng nhau
của người dùng, những lựa chọn cùng nhau của khách hàng trong thương mại
điện tử.
+ Kỹ thuật phân cụm: Phân cụm người dùng dựa trên các mẫu duyệt để
tìm ra sự liên quan giữa người dùng Web và các hành vi của họ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
- Khai phá cấu trúc Web: WWW là hệ thống thông tin toàn cầu, bao gồm
tất cả các Website. Mỗi một trang có thể được liên kết đến nhiều trang. Các
siêu liên kết thay đổi chứa đựng ngữ nghĩa chủ đề của trang. Một siêu liên kết
trỏ tới một trang Web khác có thể được xem như là một chứng thực của trang
Web đó. Do đó, nó rất có ích trong việc sử dụng những thông tin ngữ nghĩa để
lấy được thông tin quan trọng thông qua hân tích liên kết giữa các trang Web.
Mục tiêu của khai phá cấu trúc Web là để phát hiện thông tin cấu trúc về
Web. Nếu như khai phá nội dung Web chủ yếu tập trung vào cấu trúc bên
trong tài liệu thì khai phá cấu trúc Web cố gắng để phát hiện cấu trúc liên kết
của các siêu liên kết ở mức trong của tài liệu. Dựa trên mô hình hình học của
các siêu liên kết, khai phá cấu trúc Web sẽ phân loại các trang Web, tạo ra
thông tin như độ tương tự và mối quan hệ giữa các Website khác nhau. Nếu
trang Web được liên kết trực tiếp với trang Web khác thì ta sẽ muốn phát hiện
ra mối quan hệ giữa các trang Web này.
- Quá trình tìm kiếm và phân cụm tài liệu: Về cơ bản, quá trình phân
cụm kết quả tìm kiếm sẽ diễn ra theo các bước:
+ Tìm kiếm trang Web từ các Website thoả mãn nội dung truy vấn.
+ Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL
tương ứng.
+ Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang
Web thành các cụm, sao cho các trang trong cụm "tương tự" về nội dung với
nhau hơn các trang ngoài cụm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Hình 1.4: Các bước phân cụm kết quả tìm kiếm trên Web
- Tìm kiếm dữ liệu trên Web: Nhiệm vụ chủ yếu của giai đoạn này là dựa
vào tập từ khoá tìm kiếm để tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu
đề, mô tả tóm tắt, URL... tương ứng với các trang đó.
- Tiền xử lý dữ liệu: Quá trình làm sạch dữ liệu và chuyển dịch các tài
liệu thành các dạng biểu diễn dữ liệu thích hợp.
- Chuẩn hoá văn bản: Đây là giai đoạn chuyển hoá văn bản thô về dạng
văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuận tiện, chính
xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả
xử lý.
- Xoá bỏ từ dừng: Trong văn bản có những từ mang ít thông tin quan
trọng trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất
hiện với tần số lớn nhưng không quan trọng trong quá trình xử lý đều được
loại bỏ. Theo một số nghiên cứu gần đây cho thấy việc loại bỏ các từ dừng có
thể giảm bớt được khoảng 20 - 30% tổng số từ trong văn bản.
- Kết hợp các từ có cùng gốc: Hầu hết trong các ngôn ngữ đều có rất
nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự
nhau, do đó để giảm bớt số chiều trong biểu diễn văn bản, ta sẽ kết hợp với
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
các từ có cùng gốc thành một từ. Ví dụ trong tiếng Anh từ user, users, used,
using có cùng từ gốc và sẽ được quy về use.
- Xây dựng từ điển: Việc xây dựng từ điển là một công việc rất quan
trọng trong quá trình vector hoá văn bản, từ điển sẽ gồm các từ/ cụm từ riêng
biệt trong toàn bộ tập dữ liệu. Từ điển sẽ gồm một bảng các từ, chỉ số của nó
trong từ điển và được sắp xếp theo thứ tự.
- Tách từ, số hoá văn bản và biểu diễn tài liệu: Tách từ là công việc hết sức
quan trọng trong việc biểu diễn văn bản, quá trình tách từ, vector hoá tài liệu là
quá trình tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong từ điển.
- Phân cụm tài liệu: Sau khi đã tìm kiếm, trích rút dữ liệu, tiền xử lý và
biểu diễn văn bản chúng ta sử dụng kỹ thuật phân cụm để phân cụm tài liệu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Chương 2: MỘT SỐ THUẬT TOÁN PHÂN CỤM TÀI LIỆU
2.1. Phân cụm dữ liệu không gian và các tiếp cận
Các kỹ thuật áp dụng để giải quyết vấn đề phân cụm dữ liệu đều hướng
tới hai mục tiêu chung: 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ỹ phân cụm dữ liệu có thể phân loại
theo các cách tiếp cận chính [5]:
2.1.1 Phân cụm phân hoạch
Phương pháp phân cụm phân hoạch nhằm phân chia một tập dữ liệu có n
phần tử cho trước thành k nhóm dữ liệu sao cho: mỗi phần tử dữ liệu chỉ
thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu một phần tử dữ
liệu. 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ế người ta
thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một
hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng dẫn
cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường
người ta bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép
ngẫu nhiên hoặc theo heuristic, và liên tục tinh chỉnh nó cho đến khi thu được
một phân hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán
phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính
các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị
này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu
chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm
phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm kiếm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như k-means,
PAM, CLARA, CLARANS… sẽ được trình bày chi tiết ở những chương sau.
2.1.2 Phân cụm dữ liệu phân cấp
Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một cấu trúc có
dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây
phân cụm có thể được xây dựng theo hai phương pháp tổng quát: phương
pháp dưới lên (Bottom up) và phương pháp trên xuống (Top down) [5].
Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu với mỗi
đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành
nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung
tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm
được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến
khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng
chiến lược ăn tham trong quá trình phân cụm.
Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu
S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau :
Bước 0: Mỗi đối tượng dữ liệu được gán cho mỗi cụm tương ứng, đồng
thời xác định tâm D cho mỗi cụm, và tính độ tương tự cho các cặp cụm dữ
liệu trên bằng cách xác định độ tương tự giữa cặp tâm của chúng. Như vậy ta
sẽ có các cụm ban đầu là {a}, {b}, {c}, {d}, {e}.
Bước 1: Xác định ngưỡng µ, các cặp cụm có độ tương tự bé hơn hoặc
bằng ngưỡng µ thì được gộp vào một cụm. Các cặp cụm dữ liệu có độ tương
tự lớn hơn µ thì xếp vào các cụm khác nhau. Trong thí dụ này chỉ có {a} và
{b} là được gộp vào thành một cụm lớn hơn là {a, b}. Các cụm thu được sau
bước này là: {a, b}, {c}, {d}, {e}.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1,
sau bước này ta gộp cụm {d}, {e} thành {d, e}. Các cụm thu được là {a, b},
{c}, {d, e}.
Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1,
sau bước này ta gộp cụm {c} với {d, e} thành {c, d, e}. Các cụm thu được là
{a, b}, {c, d, e}.
Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1,
sau bước này ta gộp cụm hai cụm {c, d, e} với {a, b} thành {a, b, c, d, e}.
Tuy nhiên, trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ
khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực
hiện trên được mô tả trực quan như hình 2.1 dưới đây.
Hình 2.1: Phân cụm phân cấp theo phương pháp “dưới lên”-Bottom Up
Phương pháp “trên xuống” (Top Down): Bắt đầu với trạng thái là tất cả
các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một
cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương
tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện
dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá
trình phân cụm.
Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu
S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau:
Bước 0 Bước 1 Bước 2
Bước 3
Bước 4
b
d
c
e
a
a b
d e
c d e
a b c d e
Bottom up
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
Bước 0: Các đối tượng dữ liệu ban đầu được xếp vào một cụm, ta thu
được cụm {a, b, c, d, e}. Tính độ tương tự giữa các đối tượng dữ liệu trong
cụm {a, b, c, d, e}.
Bước 1: Xác định ngưỡng µ , cụm ban đầu được tách ra thành các cụm
sao cho các đối tượng dữ liệu trong mỗi cụm con tách ra có độ tương tự bé
hơn hoặc bằng µ Sau bước này thì cụm {a, b, c, d, e} chia thành hai cụm {a,
b} và {c, d, e}.
Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1
cho từng cụm con. Với ngưỡng µ, chỉ có cụm con {c, d, e} được tách ra thành
hai cụm con lần lượt là {c} và {d, e}. Các cụm thu được sau bước này là {a,
b}, {c}, {d, e}.
Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1
cho các cụm đã thu được ở bước 2, ở đây chỉ có cụm {d, e} được chia thành 2
cụm con {d}, {e}. Các cụm thu được sau bước này là {a, b}, {c}, {d}, {e}.
Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho
cụm {a, b} và sau bước này ta thu được các cụm: {a}, {b}, {c}, {d}, {e}.
Tuy nhiên trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ
khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực
hiện trên được mô tả trực quan như hình 2.2 dưới đây:
Hình 2.2 : Phân cụm phân cấp theo phương pháp “trên xuống”-Top Down
B Bước 3 Bước 2
Bước 1
Bước 0
b
d
c
e
a
a b
d e
c d e
a b c d e
Top Down
Bước 4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
Thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai phương
pháp phân cụm phân hoạch và phương phân cụm phân cấp, nghĩa là kết quả
thu được của phương pháp phân cấp có thể cải tiến thông quan bước phân
cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương
pháp Phân cụm dữ liệu cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa
trên hai phương pháp này đã được áp dụng phổ biến trong Data Mining.
2.1.3 Phân cụm dữ liệu dựa trên mật độ
Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ
được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo
một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định
thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các
đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác
định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác
định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ.
Tuy vậy, việc xác định các tham số mật độ của thuật toán rất khó khăn, trong
khi các tham số này lại có tác động rất lớn đến kết quả phân cụm dữ liệu. Hình
2.3 dưới đây là một minh hoạ về các cụm dữ liệu với các hình thù khác nhau
dựa trên mật độ được khám phá từ 3 Cơ sở dữ liệu khác nhau.
Hình 2.3 : Một số hình dạng cụm dữ liệu khám phá được bởi kỹ thuật Phân cụm dữ liệu
dựa trên mật độ
CSDL 1 CSDL 2 CSDL 3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27
Một số thuật toán Phân cụm dữ liệu dựa trên mật độ điển hình như
DBSCAN, OPTICS, DENCLUE… sẽ được trình bày chi tiết trong phần tiếp
theo.
2.1.8 Phân cụm dữ liệu dựa trên lưới
Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều
chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân
cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để Phân
cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu
không gian [5]. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình
học của đối tượng trong không gian cùng với các quan hệ, các thuộc tính, các
hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu
thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao
tác Phân cụm dữ liệu làm việc với các đối tượng trong từng Cell này. Cách
tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà
xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong
ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân
cấp nhưng chỉ có điều chúng không trộn các Cell. Do vậy các cụm không dựa
trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu
không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm
của phương pháp Phân cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và
độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là
chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một thí dụ
về cấu trúc dữ liệu lưới chứa các cell trong không gian như hình 2.4 sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
Hình 2.4 : Mô hình cấu trúc dữ liệu lưới
Một số thuật toán Phân cụm dữ liệu dựa trên cấu trúc lưới điển hình
như: STING, WAVECluster, CLIQUE…
2.1.9 Phân cụm dữ liệu dựa trên mô hình
Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số
mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng
chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa
trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà
chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch.
Phương pháp Phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ
liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng
hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô
hình có hai tiếp cận chính: Mô hình thống kê và Mạng Nơron. Phương pháp
này gần giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các
cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng
đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một
khái niệm mật độ cho các cụm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
2.1.10 Phân cụm dữ liệu có ràng buộc
Sự phát triển của phân cụm dữ liệu không gian trên Cơ sở dữ liệu lớn đã
cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lý, tuy nhiên
hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác
định các ràng buộc trong thế giới thực cần phải được thoả mãn trong quá trình
Phân cụm dữ liệu. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên
cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết
hợp các ràng buộc trong thuật toán phân cụm [5].
2.2. Phân cụm dữ liệu dựa vào thuật toán K-means
2.2.1. Tư tưởng thuật toán
K-means là một trong số những phương pháp học không có giám sát cơ
bản nhất thường được áp dụng trong việc giải các bài toán về phân cụm dữ
liệu. Mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2,
…,Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi =
(xi1, xi2, …, xid) ( ni ,1 ), sao cho hàm tiêu chuẩn [5]:
k
i
x iC
mxE
i1
2
đạt
giá trị tối thiểu. Trong đó: mi là trọng tâm của cụm Ci, là khoảng cách giữa
hai đối tượng [2].
Trọng tâm của một cụm là một véc tơ, trong đó giá trị của mỗi phần tử
của nó là trung bình cộng của các thành phần tương ứng của các đối tượng
véc tơ dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm
k, và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ
đo khoảng cách d giữa các đối tượng dữ liệu thường được sử dụng là khoảng
cách Euclide, bởi vì đây là mô hình khoảng cách dễ để lấy đạo hàm và xác
định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được
xác định cụ thể hơn tuỳ vào ứng dụng hoặc các quan điểm của người dùng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
Để dễ hình dung về thuật toán k-means ta xét ví dụ đơn giản sau:
Cho tập dữ liệu bao gồm có 15 phần tử thực trong không gian 1 chiều S=
{1, 4, 8, 5, 10, 15, 16, 23, 25, 27, 13, 37, 2, 18, 20}, người ta cần phân cụm dữ
liệu này ra thành 3 cụm (k=3) theo thuật toán k-means. Các bước thực hiện
của thuật toán được trình bày như sau:
Bước khởi tạo: chọn 3 tâm ngẫu nhiên CL1 = 8, CL2= 16, CL3= 23
Ta thu được phân hoạch ban đầu như sau:
Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8, 10
Cụm 2, với tâm là CL2, gồm có các phần tử: 13, 15, 16, 18
Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 20, 37
(Ở đây độ đo tương tự giữa hai đối tượng được xác định bằng công thức:
d(a, b)=|a-b|)
Như vậy, ta có : E = {(1-8)2 + (2-8)2 + (4-8)2+ (5-8)2+ (8-8)2+ (10 -
8)2} + {(13-16)2 + (15-16)2 + (16-16)2+ (18-16)2}+ {(25-23)2 + (23-23)2 +
(27- 23)2+ (37-23)2+ (20-23)2} = 353.
Bước lặp thứ nhất:
Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8+10)/6 = 5;
Tương tự ta có: CL2=13; CL3=26.4;
Phân hoạch tương ứng với các tâm mới như sau:
Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8
Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18
Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 20, 37
Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 249.2.
Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó
nên ta có bước lặp thứ hai như sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
Bước lặp thứ hai:
Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4;
Tương tự ta có: CL2=14.4; CL3=26.4;
Phân hoạch tương ứng với các tâm mới như sau:
Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8
Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18, 20
Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 37
Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 224.8
Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó
nên ta có bước lặp thứ ba như sau:
Bước lặp thứ ba:
Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4;
Tương tự ta có: CL2=15.33; CL3=28;
Phân hoạch tương ứng với các tâm mới như sau:
Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8
Cụm 2, với tâm là CL2, gồm có các phần tử: 10, 13, 15, 16, 20
Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 37
Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 209.33
Chúng ta thực hiện thuật toán với bước tiếp theo do giá trị của hàm mục
tiêu thu được vẫn bé hơn giá trị trước đó. Ở bước tiếp theo ta thấy thuật tóan
sẽ dừng do tâm mới cập nhật sẽ không bị thay đổi. Như vậy, kết quả phân
cụm ta sẽ xác định giá trị của ba tâm như sau: CL1= 4; CL2=15.33; CL3=28;
2.2.2 Mô tả thuật toán
Input: K, và dữ liệu về n mẫu của 1 Cơ sở dữ liệu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
Output: Một tập gồm K cluster sao cho cực tiểu về tổng sai-số vuông.
Các bước thuật toán:
Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. Coi tâm của cluster
chính là mẫu có trong cluster.
Bước 2: Tìm tâm mới của cluster.
Bước 3: Gán các mẫu vào từng cluster sao cho khoảng cách từ mẫu đó
đến tâm của cluster đó là nhỏ nhất.
Bước 4: Nếu các cluster không có sự thay đổi nào sau khi thực hiện bước
3 thì chuyển sang bước 5, ngược lại sang bước 2.
Bước 5: Dừng thuật toán.
Ví dụ: Trong không gian hai chiều, cho 12 điểm (n = 12) cần phân 12
điểm này thành hai cluster (k=2).
Đầu tiên, chọn hai điểm ngẫu nhiên vào hai cluster (chọn 2 điểm màu đỏ:
(1,3); (9,4))
Coi điểm (1,3) là tâm của cluster 1 và điểm (9,4) là tâm của cluster 2.
Tính toán khoảng cách từ các điểm khác đến hai điểm này và gán được các
điểm còn lại này vào một trong hai cluster, những điểm có màu xanh lơ vào
cluster 1, những điểm có màu xanh đậm vào cluster 2. Hiệu chỉnh lại tâm của
hai cluster, điểm màu đỏ là tâm mới của hai cluster. Tính lại các khoảng cách
các điểm đến tâm mới và gán lại các điểm này. Tiếp tục hiệu chỉnh lại tâm
của hai cluster. Rồi, lặp lại cho đến khi không còn sự thay đổi nữa thì dừng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
Hình 2.5: Minh họa thuật toán K-means
Độ phức tạp của thuật toán này là O(tKn). Trong đó n là số mẫu trong
Cơ sở dữ liệu, K là số cluster, t là số lần lặp. Thông thường t, k << n. Nên
thuật toán này có hiệu quả tương đối với các Cơ sở dữ liệu lớn [2].
2.3 Phân cụm dữ liệu dựa vào thuật toán K-medios
2.3.1. Tư tưởng thuật toán
Để tìm ra k cụm với n đối tượng thì k-medoids chọn ngẫu nhiên k đối
tượng vào k cụm, coi mỗi đối tượng này là tâm của cụm. Phân bổ các đối
tượng còn lại vào cụm mà sự khác nhau của nó với đối tượng tâm của cụm là
gần nhất. Sau đó lặp lại quá trình: Thay đổi đối tượng tâm của mỗi cụm sao
cho chất lượng của cụm được cải thiện. Chất lượng của cụm được lượng giá
bởi một hàm đo sự khác nhau giữa một đối tượng và đối tượng tâm của cụm
chứa nó. Quá trình lặp cho đến khi không còn sự thay đổi nào về lực lượng
cũng như hình dạng của các cụm [2].
Để chọn một đối tượng không là đối tượng tâm Orandom thay thế tốt cho
một đối tượng tâm Oj thì mỗi đối tượng p xét theo 4 trường hợp sau đây:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
Trường hợp 1: p đang thuộc vào cụm có tâm là Oj (từ nay gọi là cụm
Oj). Nếu Oj được thay thế bởi Orandom và p gần nhất với Oi (ij) thì p được
gán lại vào Oi
Trường hợp 2: p đang thuộc vào Oj. Nếu Oj được thay thế bởi Orandom
và p gần nhất với Orandom thì p được gán lại vào Orandom.
Trường hợp 3: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi
Orandom và p vẫn gần nhất với Oi thì không thay đổi gì cả. Tức là p vẫn
thuộc Oi.
Trường hợp 4: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi
Orandom và p gần nhất với Orandom thì p được gán lại vào Orandom.
Hình 2.6: Các trường hợp đối với điểm p
2.3.2. Mô tả thuật toán
Input: Số nguyên k và Cơ sở dữ liệu gồm n đối tượng cần phân cụm.
Output: Một tập gồm k cụm mà tổng giá trị của sự khác nhau của tất cả
các đối tượng đến đối tượng tâm của nhóm chứa nó là nhỏ nhất.
Thuật toán:
Bước 1: Chọn k đối tượng bất kì vào k cụm. Coi mỗi đối tượng này là
tâm của nhóm.
Bước 2: Lặp
Bước 3: Gán mỗi đối tượng còn lại vào một cụm mà nó gần với đối
tượng tâm của cụm nhất.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
Bước 4: Chọn ngẫu nhiên một đối tượng không là đối tượng tâm,
Orandom.
Bước 5: Tính lại giá trị, S, đối với việc đổi Oj với Orandom.
Bước 6: Nếu S<0 thì đổi Oj với Orandom để tạo ra một tập với đối
tượngtâm mới.
Bước 7: Đến khi không có sự thay đổi nào nữa thì dừng.
Ví dụ: Trong không gian hai chiều cho n = 10 điểm, cần chia thành k =2
cụm. Các bước thực hiện của thuật toán k-medoids được chỉ ra:
Hình 2.7: Các bước thực hiện của k-medoids
Đầu tiên, chọn hai điểm bất kì vào hai cụm (điểm màu xanh đậm), rồi xét
các điểm còn lại và đưa chúng vào một trong hai cụm với điểm tâm lần lượt là
hai điểm đã chọn ban đầu.
Tiếp theo, chọn một điểm bất kì khác điểm tâm (điểm màu đỏ). Tính giá
của phép chuyển đổi điểm tâm từ điểm màu xanh -> điểm màu đỏ. Nếu giá
này chất lượng hơn thì coi điểm đỏ là tâm của cụm mới và thực lặp lại quá
trình đó cho đến khi không còn sự thay đổi nào.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
2.3.3 Nhận xét:
Thuật toán k-medoids mạnh hơn thuật toán k-means trong các trường
hợp dữ liệu có nhiễu vì k-medoids chịu ảnh hưởng ít hơn của nhiễu và các giá
trị chênh lệnh so với giá trị trung bình. Tuy nhiên cả hai thuật toán này đều
yêu cầu đưa vào số lượng cụm k [2].
2.4. Phân cụm dữ liệu dựa vào thuật toán BIRCH
2.4.1. Tư tưởng thuật toán
BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies)
là thuật toán phân cụm phân cấp sử dụng chiến lược phân cụm trên xuống
(top down). Ý tưởng của thuật toán là không cần lưu toàn bộ các đối tượng dữ
liệu của các cụm trong bộ nhớ mà chỉ lưu các đại lượng thống kê. Đối với mỗi
dữ liệu, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là số đối tượng
trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm và
SS là tổng bình phương của các giá trị thuộc tính của các đối tượng trong
cụm. Các bộ ba này được gọi là các đặc trưng của cụm (Cluster Features -
CF) và được lưu giữ trong một cây được gọi là cây CF (CF-tree). Người ta đã
chứng minh rằng [5][10], các đại lượng thống kê chuẩn, như là độ đo khoảng
cách, có thể xác định từ cây CF. Hình 2.8 dưới đây biểu thị một ví dụ về cây
CF. Chúng ta thấy rằng, tất cả các nút trong của cây lưu tổng các đặc trưng
cụm CF, của nút con, trong khi đó các nút lá lưu trữ các đặc trưng của các
cụm dữ liệu [4].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
Hình 2.8: Cây CF được sử dụng bởi thuật toán BIRCH
Cây CF là cây cân bằng, nhằm để lưu trữ các đặc trưng của cụm (CF).
Cây CF chứa các nút trong và nút lá, nút trong là nút chứa các nút con và nút
lá thì không có con. Nút trong lưu giữ tổng các đặc trưng cụm (CF) của các
nút con của nó. Một cây CF được đặc trưng bởi hai tham số:
Yếu tố nhánh (Branching Factor -B): Nhằm xác định số tối đa các nút
con của mỗi nút trong của cây.
Ngưỡng (Threshold - T): Khoảng cách tối đa giữa bất kỳ một cặp đối
tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các
cụm con được lưu tại các nút lá.
Hai tham số này có ảnh hưởng đến kích thước của cây CF. Thuật toán
BIRCH thực hiện qua giai đoạn sau:
Giai đoạn 1: BIRCH duyệt tất cả các đối tượng trong Cơ sở dữ liệu và
xây dựng một cây CF khởi tạo. Trong giai đoạn này, các đối tượng lần lượt
được chèn vào nút lá gần nhất của cây CF (nút lá của cây đóng vai trò là cụm
con), sau khi chèn xong thì tất cả các nút trong cây CF được cập nhật thông
tin. Nếu đường kích của cụm con sau khi chèn là lớn hơn ngưỡng T, thì nút lá
được tách. Quá trình này lặp cho đến khi tất cả các đối tượng đều được chèn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
vào trong cây. Ở đây ta thấy rằng, mỗi đối tượng trong cây chỉ được đọc một
lần, để lưu toàn bộ cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước
của cây CF thông qua điều chỉnh ngưỡng T.
Giai đoạn 2: BIRCH lựa chọn một thuật toán Phân cụm dữ liệu (như
thuật toán phân cụm phân hoạch chẳng hạn) để thực hiện Phân cụm dữ liệu
cho các nút lá của cây.
2.4.2 Mô tả thuật toán:
Bước 1: Các đối tượng dữ liệu lần lượt được chèn vào cây CF, sau khi
chèn hết các đối tượng ta thu được cây CF khởi tạo. Một đối tượng được chèn
vào nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn
hơn T thì nút lá được tách. Khi một đối tượng thích hợp được chèn vào nút lá,
tất cả các nút trỏ tới gốc của cây được cập nhật với các thông tin cần thiết.
Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành
cây dựng một cây CF nhỏ hơn: Kích thước của cây CF được điều khiển bởi
tham số T và vì vậy việc chọn một giá trị lớn hơn cho nó sẽ hoà nhập một số
các cụm con thành một cụm, điều này làm cho cây CF nhỏ hơn. Bước này
không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu
chỉnh cây dữ liệu nhỏ hơn.
Bước 3: Thực hiện phân cụm: Các nút lá của cây CF lưu giữ các đại
lượng thống kê của các cụm con. Trong bước này, BIRCH sử dụng các đại
lượng thống kê này để áp dụng một số kỹ thuật phân cụm thí dụ như k-means
và tạo ra một khởi tạo cho phân cụm.
Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối
tượng trọng tâm cho các cụm đã được khám phá từ bước 3: Đây là một bước
tuỳ chọn để duyệt lại tập dữ liệu và gán nhãn lại cho các đối tượng dữ liệu tới
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo
và loại bỏ các đối tượng ngoại lai.
Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện Phân
cụm dữ liệu nhanh và có thể áp dụng đối với tập dữ liệu lớn, đặc biệt, BIRCH
hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH là chỉ
duyệt toàn bộ dữ liệu một lần với một lần quét thêm tuỳ chọn, nghĩa là độ
phức tạp của nó là O(n), với n là số đối tượng dữ liệu. Nhược điểm của nó là
chất lượng của các cụm được khám phá không được tốt. Nếu BIRCH sử dụng
khoảng cách Euclide, nó thực hiện tốt chỉ với các dữ liệu số. Mặt khác, tham
số vào T có ảnh hưởng rất lớn tới kích thước và tính tự nhiên của cụm. Việc
ép các đối tượng dữ liệu làm cho các đối tượng của một cụm có thể là đối
tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút
bởi các cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự
khác. BIRCH không thích hợp với dữ liệu đa chiều [4].
2.5. Cải tiến thuật toán K-means trong phân cụm dữ liệu tự động
2.5.1. Tư tưởng thuật toán
Bài toán thu thập, phân cụm dữ liệu tự động là một bài toán mang tính
thời sự, vì trong thời đại công nghệ thông tin, với sự trợ giúp của máy tính thì
việc áp dụng công nghệ thông tin vào thu thập dữ liệu tự động trên internet,
sau đó phân tích phục vụ cho việc phận cụm và từ đó hình thành các chủ đề
thôn tin với các dữ liệu thu thập tự động từ internet. Trên cơ sở đó, chúng ta
tiến hành phân tích dữ liệu và đưa ra những dự báo trong tương lai với từng
chủ đề khác nhau như: dự báo tốc độ tăng trưởng kinh tế, GDP, chỉ số chứng
khoán, giá cả hàng hoá... Điều này làm cơ sở cho chúng ta có thể đưa ra một
chính sách phát triển kinh tế trong cả nước [2].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
Tuy nhiên, để có được những dữ liệu và phân cụm được những dữ liệu
đó theo các chủ đề khác nhau thì chúng ta phải có các kỹ thuật. Như mục 2.2,
nhóm tác giả đã trình bày thuật toán K-Means, tuy nhiên thuật toán có những
hạn chế nhất định [2]. Do đó, nhóm tác giả cải tiến thuật toán này nhằm khắc
phục những hạn chế của thuật toán K-means.
Cải tiến thuật toán K-means: thay vì chọn số điểm (k) làm trọng tâm,
chúng ta không chọn số điểm (k) làm trọng tâm cho số cụm mà sẽ tăng số
cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ
biến dạng Max và tính lại trọng tâm các cụm.
Với thuật toán K- means bắt đầu bằng cách chọn k cụm và chọn ngẫu
nhiên k điểm làm trung tâm cụm, hoặc chọn phân hoạch ngẫu nhiên k cụm và
tính trọng tâm của từng cụm này. Việc chọn ngẫu nhiên k điểm làm trung tâm
cụm như đã nói ở trên có thể cho ra các kết quả khác nhau tùy vào chọn k
điểm này. Thuật toán cải tiến K-means nhìn chung vẫn dựa trên thuật toán k-
means nhưng sẽ không chọn k điểm làm trọng tâm cho k cụm mà sẽ tăng số
cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ
biến dạng max (tăng số cụm) và tính lại trọng tâm các cụm.
2.5.2. Mô tả thuật toán
Bước 1: Khởi tạo giá trị ban đầu cho K: K=1
Bước 2:
Bước 2.1: Kiểm tra điều kiện K
Nếu K=1: chọn bất kỳ một điểm làm trung tâm của cụm.
Nếu K>1: thêm trung tâm của cụm mới vào cụm có biến dạng max.
Bước 2.2: Gán từng điểm vào cụm có trung tâm gần nhất với điểm đang
xét và cập nhật lại trung tâm cụm
Bước 2.3: Nếu trung tâm cụm không thay đổi, chuyển sang bước 3.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
Ngược lại, quay trở lại bước 2.2 (bước 2).
Bước 3: (Tăng số cụm)
Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở lại bước 2.1 (bước 2).
Ngược lại, thuật toán dừng.
Với thuật toán K-means cải tiến: đưa ra sự khác biệt, đó là mức độ biến
dạng của các cụm (Dựa trên biến dạng để phân cụm).
Mức độ biến dạng của các cụm được tính như sau:
I=S-N (d (w,x ))
Trong đó: w: trung tâm của cụm,
N: Số các thành phần trong cụm.
S: Tổng bình phương khoảng cách giữa các thành phần trong cụm và
trung tâm của không gian Euclidean.
I: Mức độ biến dạng của cụm
d (w,x): là khoảng cách giữa trung tâm w của cụm và trung tâm của
không gian Euclidean x.
2.5.3 Nhận xét:
+ Một cụm có mức độ biến dạng lớn thì trung tâm cụm đó có vị trí
không thích hợp.
+ Việc xác định các cụm cũng như xác định trung tâm của cụm, như vậy
thuật toán chủ yếu tìm trung tâm cụm chính xác và xác định lại các thành
phần trong cụm.
Với thuật toán K-means cải tiến:
+ Bước 2: như K-means nhưng khác là: không xác định trước k điểm mà
tăng k lên dần từ 1. Và chọn cụm có mức độ biến dạng lớn để phân ra 2 cụm
(khi đó 2 cụm này có mức độ biến dạng giảm, nhỏ hơn).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
+ Thuật toán cải tiến K-means có độ phức tạp là O( k 2 nt), như vậy so với
thuật toán K-means có độ phức tạp O(tkn) thì: O( k 2 nt)>O(tkn), nhưng không
bằng K-mendoids, do k<<n. Tuy nhiên ưu điểm của thuật toán là giảm sự
phụ thuộc vào việc khởi tạo các cụm ban đầu nên ta sẽ không phải lập lại
thuật toán với việc chọn các cụm ban đầu khác nhau để tìm ra kết quả tối ưu
như ở K-Means.
2.3.4 Thử nghiệm:
Để đánh giá thuật toán cải tiến K-means, nhóm tác giả sử dụng các dữ
liệu lấy từ các trang Web với các nguồn chính sau:
+ Các trang được lấy tự động từ các website trên internet, việc tìm kiếm
được thực hiện bằng cách dùng Google, chương trình sẽ dựa vào URL để lấy
tài liệu và lưu trữ lại phục vụ cho quá trình tìm kiếm sau này.
+ Tìm kiếm có chọn lọc với các chủ đề tin về "Chứng khoán", khoảng
250 bài; Chủ đề tin về "Tỷ giá hối đoái", khoảng 100 bài; Chủ đề tin về "Giá
vàng", khoảng 150 bài; Chủ đề tin về "Thời tiết", khoảng 50 bài. Các chủ đề
đều có tần số xuất hiện nhiều.
Trên cơ sở thuật toán K-means, thuật toán K-medoids, nhóm tác giả so
sánh kết quả thực hiện phân cụm với các chủ đề tin trên. Kết quả bảng dưới
đây:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43
Số tài
liệu
(Cơ sở
dữ liệu)
Số
cụm
Thời gian phân cụm trung bình (giây)
K-means K-medoids
K-means cải
tiến
250 10 9,756 9,106 8,56
250 15 12,375 11,525 10,972
100 10 2,518 2,218 2,118
100 15 3,719 3,119 3,219
150 10 4,115 4,015 3,005
150 15 5,723 5,110 5,123
50 10 0,957 0,907 0,857
50 15 1,13 1,11 1,00
Với độ phức tạp của các thuật toán trên, nhóm tác giả thấy thời gian
thực hiện thuật toán phụ thuộc vào độ lớn cơ sở dữ liệu và số cụm cần phân
cụm [2].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
Chương 3: ỨNG DỤNG TRONG LẤY TIN TỰ ĐỘNG
3.1. Bài toán Thu thập dữ liệu về kinh tế trên Internet
Trong thời đại bùng nổ thông tin như hiện nay thì việc khai thác, thu thập
và chia sẻ thông tin đóng một vai trò quan trọng. Với một dữ liệu khổng lồ trên
mạng, làm sao ta có thể nắm bắt được thông tin mới nhất, nhanh chóng nhất mà
không phải tốn thời gian xem từng website để đọc và tìm kiếm thông tin.
Trên cơ sở này, hệ thống bóc tách thông tin được xây dựng nhằm phục
vụ cho việc trích xuất thông tin từ các website, rồi tất cả thông tin được hiển
thị trên một website, giúp cho người đọc có thể nắm bắt được thông tin một
cách xúc tích, nhanh chóng và tiết kiệm thời gian.
Đối tượng sử dụng hệ thống là tất cả cộng đồng người sử dụng mạng. Quản
trị viên có thể quản lý tài khoản người dùng, quản lý các đường dẫn (link).
Khảo sát, phân tích và đánh giá yêu cầu
Khảo sát một số chương trình hỗ trợ đọc tin tức RSS
3.1.1 iCA
iCA là tên gọi tắt của "Information Catcher", là phần mềm được xây
dựng dựa trên nền tảng và công nghệ dot NET của Microsoft. Phần mềm iCA
hoạt động với tính năng nhận các thông tin từ Website tổng hợp sau đó hiển
thị đầy đủ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
Hình 3.1: Giao diện của iCA
3.1.2 Google Reader
Google Reader là một sản phẩm của Google dựa trên nền Web Form, có
rất nhiều tính năng nổi trội: lựa chọn số tin tức được hiển thị, chia sẻ tin với
bạn bè, phân nhóm tin tức, tìm kiếm tin tức…..
Hình 3.2: Giao diện trang chủ Google Reader
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
3.1.3 iGoogle
iGoogle là một cổng cá nhân (Personal Portal), sử dụng công nghệ
AJAX và .NET Framework 3.5. Khi người dùng thêm kênh tin từ trang
Google Reader, thì nó sẽ được tự động cập nhật vào trang iGoogle.
Hình 3.3: Giao diện trang chủ của iGoogle
iGoogle còn cung cấp sẵn một directory
Hình 3.4: Giao diện trang Gagdet của iGoogle
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
3.1.4 Trình duyệt Firefox
Hiện nay các trình duyệt phiên bản mới nhất cũng hỗ trợ công nghệ RSS.
Ví dụ như: Internet Explorer 8.0 của Microsoft, Opera, Firefox…
Khi ta vào một website nào đó mà sử dụng công nghệ RSS thì trên trình
duyệt của Firefox có xuất hiện biểu tượng màu da cam, ở giữa có ba chấm
trắng.
Hình 3.5: Giao diện trình duyệt FireFox
Nếu ta muốn lấy tin từ trang tin đó, ta chỉ cần kích vào biểu tượng đó và
nó sẽ tự động chuyển tới trang lấy tin của Google Reader và iGoogle.
Hoặc ta có thể sử dụng Live Bookmark được tích hợp trong trình duyệt
Firefox để lấy tin.
Hình 3.6: Giao diện trang lấy tin RSS
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
3.1.5 Tổng hợp yêu cầu của người dùng
Mục tiêu của đề tài là xây dựng nên một hệ thống hỗ trợ người dùng
chọn kênh tin tức, thu thập tin tức, quản lý các kênh tin, tạo ra một website tin
tức cho chính người dùng mà không phải lướt từng website để đọc tin tức.
Thông qua việc khảo sát một số phần mềm đọc tin tức trong và ngoài nước,
và yêu cầu từ phía người dùng, có thể tóm tắt yêu cầu của người dùng đối với
hệ thống bóc tách thông tin như sau:
- Người dùng có thể tạo ra kênh tin tức cho riêng mình bằng cách chỉ cần
đăng ký một tài khoản và đăng nhập vào nhập đường dẫn link tới địa chị trang
website cần lấy tin.
- Người dùng có thể tổ chức, quản lý kênh tin tức của mình với các chức năng:
- Tạo nhóm tin tức (như: tin giáo dục, xã hội, tin chứng khoán…), sửa
nhóm tin và xoá nhóm tin.
- Lựa chọn số tin tức được hiển thị.
- Người dùng còn có thể tìm kiếm thông tin.
3.1.6 Đánh giá và lựa chọn giải pháp
Thông qua việc khảo sát một số website, phần mềm hỗ trợ đọc tin tức
RSS ở trên, ta thấy có giải pháp để xây dựng hệ thống đó là: Win Form và
Web Form. Sau đây là những thuận lợi hay khó khăn của hai giải pháp trên.
Và cuối cùng sẽ lựa chọn giải pháp cho chương trình của mình.
- Sử dụng Win Form:
+ Ưu điểm:
Hỗ trợ nhiều tính năng
Khả năng chạy không cần mạng (offline)
+ Nhược điểm:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
Người dùng phải mất thời gian cài đặt
Khó khăn trong việc nâng cấp: mỗi khi hệ thống nâng cấp, cập
nhật thêm chức năng mới thì người dùng phải cài lại chương trình.
- Sử dụng Web Form:
+ Ưu điểm:
Tính cơ động: Không cần cài đặt, không cần cấu hình, với
ứng dụng sử dụng Web Forms, người dùng chỉ cần dùng một
trình duyệt web kết nối với mạng Internet là có thể truy cập ở bất
cứ chỗ nào. Đây có thể nói là ưu điểm lớn nhất của các ứng dụng
Web Forms.
Dễ thay đổi: Sử dụng Web Forms đồng nghĩa với tất cả
dữ liệu và chương trình đã nằm trên máy chủ. Chính vì vậy khi
muốn sửa đổi, nâng cấp hệ thống, việc nâng cấp trên Web Forms
có thể diễn ra rất dễ dàng. Người cung cấp dịch vụ chỉ cần cập
nhật trực tiếp lên máy chủ, còn phía người dùng, các công việc
này hoàn toàn trong suốt.
Tính chia sẻ: có thể chia sẻ tin tức.
Sau khi xem xét các khía cạnh, ưu và nhược điểm của các công nghệ cho
thấy Web Form là một giải pháp tối ưu để phát triển hệ thống. Cụ thể ở đây là
công nghệ .NET của Microsoft, sử dụng ngôn ngữ lập trình C# và hệ quản trị
Cơ sở dữ liệu Microsoft SQL Server 2000.
3.2 Phân tích chức năng hệ thống
3.2.1 Biểu đồ Use Case
Biểu đồ Use Case thể hiện sự tương tác giữa người dùng và hệ thống. Từ
đó xác định được hệ thống cần phải làm gì.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
Hình 3.8: Biểu đồ User – case
3.2.2 Đặc tả các Use - case
Đặc tả Use – case đăng nhập
+ Tóm tắt
Use case này mô tả cách đăng nhập vào hệ thống bóc tách thông tin.
+ Dòng sự kiện chính
- Use case này bắt đầu khi một actor (người dùng, quản trị viên)
muốn đăng nhập vào hệ thống.
- Hệ thống yêu cầu các actor nhập tên và mật khẩu.
- Hệ thống kiểm tra tên và mật khẩu mà actor đã nhập. Nếu đúng
hệ thống cho phép actor đăng nhập vào hệ thống.
+ Dòng sự kiện khác
- Tên / mật khẩu sai:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
Nếu trong dòng sự kiện chính các actor nhập tên, mật khẩu sai thì hệ
thống sẽ báo lỗi. Actor có thể quay trở về đầu dòng sự kiện hoặc
huỷ bỏ việc đăng nhập, lúc này use case kết thúc.
+ Các yêu cầu đặc biệt
Không có.
+ Điều kiện tiên quyết
Không có.
+ Post condition
Nếu use case thành công thì người đăng nhập sẽ có các quyền sử
dụng hệ thống tương ứng. Ngược lại trạng thái của hệ thống không đổi.
+ Điểm mở rộng
Không có.
Đặc tả Use-case quản lý tin tức
+ Tóm tắt
Use case này cho phép người sử dụng (đã là đăng nhập thành công)
quản lý tin tức: thêm, sửa, xoá nhóm tin, lựa chọn số tin tức được hiển
thị và thêm, xoá kênh tin.
+ Dòng sự kiện
Use case này bắt đầu khi người dùng đăng nhập vào hệ thống và
thêm kênh tin và nhóm tin.
+ Dòng sự kiện chính
- Hệ thông sẽ liệt kê các nhóm tin, kênh tin của riêng thành viên đó.
- Thêm, sửa, xoá nhóm tin và kênh tin, lựa chọn số tin tức hiển thị.
+ Các yêu cầu đặc biệt
Không có
+ Điểu kiện tiên quyết
Không có
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
+ Post conditions
Nếu use case thành công, thông tin về nhóm tin, kênh tin sẽ được
cập nhật vào cơ sở dữ liệu.
+ Điểm mở rộng
Không có
Đặc tả Use- case quản lý người dùng
+ Tóm tắt
Use case này cho phép quản trị viên thêm, sửa, xoá, tìm kiếm thông
tin về thành viên sử dụng hệ thống. Quản lý trang tin của các thành viên
(thêm, sửa, xoá trang tin của người sử dụng).
+ Dòng sự kiện chính
- Quản trị viên lựa chọn chức năng quản lý người dùng
- Hệ thống nhận thông tin từ quản trị viên.
- Hệ thống kiểm tra thông tin nhập vào
- Hệ thống truy xuất cơ sở dữ liệu.
- Theo từng yêu cầu của quản trị viên hệ thống sẽ thực hiện như sau:
Nếu quản trị viên yêu cầu thêm, sửa, xoá hoặc cập nhật lại thông
tin về trang tin riêng của người sử dụng thì hệ thống sẽ cập nhật
lại cơ sở dữ liệu tương ứng với các yêu cầu.
Nếu quản trị viên yêu cầu tìm kiếm thông tin người sử dụng thì hệ
thống đưa ra những người sử dụng thoả yêu cầu của quản trị viên.
- Hệ thống thông báo thực hiện thành công.
- Use – case kết thúc.
+ Dòng sự kiện phụ
Nếu hệ thống không truy xuất được cơ sở dữ liêu thì sẽ báo lỗi, use
– case kết thúc.
+ Các yêu cầu đặc biệt
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
Không có.
+ Điều kiện tiên quyết
Người quản lý đăng nhập vào hệ thống với quyền quản trị viên trước
khi use – case bắt đầu.
+ Post conditions
Nếu use – case thành công thì thông tin của người sử dụng sẽ được
cập nhật vào hệ thống. Ngược lại trạng thái của hệ thống không thay đổi.
+ Điểm mở rộng
Không có.
Đặc tả Use-case tìm kiếm tin tức
+ Tóm tắt
Use case này cho phép người sử dụng tìm kiếm thông tin mà mình
muốn tìm.
+ Dòng sự kiện
Use case này bắt đầu khi người dùng chọn chức năng tìm kiếm tin tức.
+ Dòng sự kiện chính
- Người dùng nhập thông tin muốn tìm.
- Công cụ Google sẽ tìm kiếm.
- Liệt kê tất cả thông tin thoả yêu cầu.
+ Dòng sự kiện phụ
Nếu không tìm thấy thì thông báo cho người dùng biết là không tìm thấy.
+ Các yêu cầu đặc biệt
Không có.
+ Điều kiện tiên quyết
Không có.
+ Post conditions
Không có.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
3.2.3 Biểu đồ tuần tự (Sequence Diagram)
Hoạt động của hệ thống: Nhìn một cách bao quát, hệ thống gồm những
thao tác cơ bản sau:
Hình 3.9: Biểu đồ tuần tự - Toàn cảnh hệ thống
Đăng ký tài khoản: Để có thể tạo trang tin cá nhân người sử dụng cần
phải đăng ký một tài khoản. Người dùng chỉ cần điền đúng và đầy đủ các
thông tin mà chương trình đưa ra. Server có trách nhiệm cung cấp tài khoản
mới cho người dùng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
Hình 3.10: Biểu đồ tuần tự - Đăng ký tài khoản
Đăng nhập hệ thống: Là hành động người dùng sử dụng tài khoản được
cấp để vào hệ thống. Sau khi nhập các thông tin cần thiết, chương trình sẽ kết
nối và kiểm tra tính hợp lệ. Người dùng sẽ được phản hồi kết quả.
Hình 3.11: Biểu đồ tuần tự - Đăng nhập hệ thống
Thêm đường dẫn: Để lấy thông tin từ website khác, người dùng có thể
nhập trực tiếp đường dẫn tới tập tin RSS, chương trình sẽ tự động trích rút tin
tức và hiện thị lên cho người dùng. Hoặc người dùng có thể nhập đường dẫn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
tới website cung cấp RSS, chương trình sẽ trích rút các đường dẫn tới các tập
tin RSS cho người dùng lựa chọn.
Hình 3.12: Biểu đồ tuần tự - Thêm đường dẫn link
Thêm nhóm tin: Là thao tác mà người dùng thêm mới nhóm để phân loại
tin tức.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
Hình 3.13: Biểu đồ tuần tự - Thêm nhóm tin
Sắp xếp, phân loại nhóm tin:
Hình 3.14: Biểu đồ tuần tự - Sắp xếp nhóm tin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Tìm kiếm tin tức: Trước hết người dùng chọn chế độ tìm kiếm, đó là tìm
kiếm tin tức trong hệ thống hay tìm kiếm trên Google search.
Hình 3.15: Biểu đồ tuần tự - Tìm kiếm thông tin
Quản lý người dùng: Đây là thao tác chỉ dành cho người dùng có quyền
là quản trị. Quản trị viên có thể cung cấp tài khoản mới cho người dùng, có
thể xoá tài khoản người dùng, quản lý trang tin cá nhân của người dùng.
Hình 3.16: Biểu đồ tuần tự - Quản lý người dùng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
3.3 Thiết kế cơ sở dữ liệu
3.3.1 Đặc tả chi tiết các bảng dữ liệu
Bảng Urls: chứa thông tin về địa chỉ website chứa các kênh tin.
Bảng 3.1: Bảng Urls (địa chỉ website)
Bảng Channels: chứa thông tin về các kênh tin tức
Bảng 3.2: Bảng Channels (kênh tin)
Bảng Items: chứa thông tin về những tin tức mà hệ thống bóc tách lấy về.
tblItems
STT Tên trường Kiều dữ liệu Độ dài Ghi chú Diễn giải
1 ItemID int 4 Khoá chính Mã tin tức
2 ChannelID int 4 Khác rỗng Mã kênh tin
3 iLink nvarchar 50 Khác rỗng Đường dẫn tới chi tiết của tin tức
4 iTitle nvarchar 50 Khác rỗng Tiêu đề của tin tức
5 iDescription nvarchar MAX Khác rỗng Nội dung chi tiết của tin tức
6 iPubDate datetime Ngày xuất bản tin
7 iAuthor nvarchar 50 Tác giả viết tin
Bảng 3.3: Bảng Items (tin tức)
tblUrls
STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải
1 UrlID int 4 Khoá chính Mã địa chỉ
2 uLink nvachar 50 Khác rỗng Đường dẫn tới website
3 uTitle nvarchar 50 Tiêu đề của website
4 uDescription nvarchar 50 Đặc tả về website
tblChannels
STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải
1 ChannelID int 4 Khoá chính Mã kênh tin
2 cLink nvachar 50 Khác rỗng Đường dẫn tới file RSS
3 cTitle nvarchar 50 Khác rỗng Tiêu đề của kênh tin
4 cDescription navarchar MAX Khác rỗng Đặc tả chi tiết về kênh tin
5 LastUpdated dateTime Khác rỗng Thời gian cập nhật kênh tin
6 ItemCount int 4 Khác rỗng Số lượng tin tức có trong kênh tin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
Bảng Group: chứa thông tin về nhóm tin của mỗi người sử dụng
Bảng 3.4: Bảng Group (nhóm tin tức)
Bảng User Blog: chứa thông tin về blog tin tức của mỗi người dùng.
Bảng 3.5: Bảng User Blog (kho tin tức của mỗi người dùng)
tblGroup
STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải
1 GroupID int 4 Khoá chính Mã nhóm
2 GroupName nvachar 50 Khác rỗng Tên nhóm
3 UserName nvarchar 50 Khác rỗng Tên đăng nhập của người sử dụng
tblUserBlog
STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải
1 UserBlogID int 4 Khoá chính Mã trang blog tin tức của
mỗi người dùng
2 UserName nvarchar 50 Khác rỗng Tên đăng nhập của người
sử dụng
3 ChannelID int 4 Khác rỗng Mã kênh tin
4 GroupID int 4 Khác rỗng Mã nhóm
5 NumberToShow int 4 Số lượng tin người dùng
chọn trên mỗi kênh tin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
3.3.2 Mô hình quan hệ
Hình 3.17: Mô hình quan hệ dữ liệu giữa các bảng
3.4 Qui trình tự động lấy đường dẫn tới tập tin RSS
Khi người dùng nhập đường dẫn tới website (chẳng hạn:
), thì nhiệm vụ của hệ thống là lấy tất cả những file RSS
mà website đó cung cấp.
Bước 1: Ta phải tải nội dung trang HTML của website đó về.
Bước 2: Ta sử dụng đến biểu thức chính qui (Regular Expression) để lọc
ra những thẻ chứa đường dẫn tới file RSS.
Bước 3: Lọc ra đường dẫn tới file RSS, ta cũng dùng biểu thức chính qui
để match() được href chứa đường dẫn tới file RSS.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
Bước 4: Sau khi đã lấy được đường dẫn tới file RSS, lưu vào Cơ sở dữ
liệu. Tiếp theo, đọc file RSS đó.
3.5 Qui trình đọc tập tin RSS
Người dùng có thể nhập trực tiếp đường dẫn tới file RSS. Nhiệm vụ của
hệ thống là trích rút dữ liệu từ file RSS. Để trích rút dữ liệu ta làm như sau:
Bước 1: Trước tiên là thiết kế lớp RSSItem để chứa các dữ liệu mà ta
trích rút từ file RSS.
Bước 2: Đọc file RSS
3.6 Một số màn hình giao diện đạt được
Hình 3.18: Giao diện trang đăng nhập
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
Hình 3.19: Giao diện trang quản lý người dùng
Hình 3.20: Giao diện blog
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
Hình 3.21: Giao diện thư mục RSS cung cấp sẵn
Hình 3.22: Giao diện trang lấy link RSS tự động
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
Hình 3.23: Giao diện trang tin tức lấy về
Hình 3.24: Giao diện trang quản lý nhóm tin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
PHẦN KẾT LUẬN
Tầm quan trọng của vấn đề lấy tin tự động trên Internet
Với sự phát triển nhanh chóng của Internet như ngày nay, thì mỗi ngày,
tuần, tháng, quý, năm... mỗi con người chúng ta phải xử lý hàng trăm, triệu,
tỷ... thông tin, dữ liệu khác nhau, điều này có nghĩa là chúng ta đã gặp phải
những rắc rối không mong muốn trong thời đại công nghệ số này. Vì vậy, bài
toán tìm kiếm tài liệu Web và phân cụm tài liệu là một bài toán phức tạp và
được ứng dụng trong thực tế, đặc biệt trong các ứng dụng Web. Trên cơ sở
những dữ liệu thu thập được từ internet thì chúng ta cần phải tiến hành phân
loại, nhóm phân cụm thành các cụm khác nhau theo các chủ đề khác nhau từ
đó phục vụ cho việc phân tích dữ liệu và dự báo kinh tế [1].
Hiện nay, có nhiều phương pháp tìm kiếm khác nhau, nhưng nhìn chung
là các cách tiếp cận đều dựa vào các trọng số trang Web (Chỉ số quan trọng
của trang trong tập kết quả), như: Page Bank, HITS...Tức là các trang này chủ
yếu là dựa vào các liên kết để xác định trọng số [16].
Mặt khác, chúng ta có thể dựa vào nội dung các tài liệu để xác định trọng
số, nếu các tài liệu gần nhau về nội dung thì gán cho chúng một trọng số và
khi đó chúng thuộc cùng một nhóm.
Các vấn đề đã được tìm hiểu trong luận văn
Luận văn đã nêu vấn đề cải tiến thuật toán K-means trong phân cụm tài
liệu web, thay vì chọn số điểm làm trọng tâm thì không chọn số điểm làm
trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung
tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các
cụm và đã cài đặt thử nghiệm trên các bộ cơ sở dữ liệu, cho kết quả bước đầu
khá khả quan.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
Hướng nghiên cứu tiếp theo
Tiếp tục nghiên cứu các kỹ thuật phân cụm dữ liệu, trong đó nhấn mạnh
đến kỹ thuật phân cụm K-Means mở rộng, thời gian tuyến tính đáp ứng được
các yêu cầu của bài toán phân cụm tài liệu Web.
Đề xuất ra giải pháp xây dựng quy trình công nghệ và phát triển hệ thống
phần mềm thu thập, đánh giá và phân cụm thông tin tự động trên Internet
phục vụ cho việc nghiên cứu, học tập và giảng dạy ngành Hệ thống thông tin
Kinh tế, và phục vụ cho việc phân tích, tổng hợp, xử lý dữ liệu và dự báo phát
triển kinh tế xã hội của khu vực trung du và miền núi phía Bắc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
68
DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN
ĐẾN LUẬN VĂN
1. Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh
Hà, Nguyễn Thanh Dương (2009), "Tìm kiếm và phân cụm tài liệu Web tự
động", Tập 56, số 8, 2009 - Tạp chí khoa học và công nghệ, Đại học Thái
Nguyên, tr. 60 - 64.
2. Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh Hà
(2009), "Cải tiến thuật toán K-Means và ứng dụng phân cụm dữ liệu tự
động", Báo cáo Hội thảo Khoa học tại ĐH Lạc Hồng, Đồng Nai.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
69
TÀI LIỆU THAM KHẢO
Tài liệu tiếng Việt
[1] Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh
Hà, Nguyễn Thanh Dương (2009), "Tìm kiếm và phân cụm tài liệu Web tự
động", Tập 56, số 8, 2009 - Tạp chí khoa học và công nghệ, Đại học Thái
Nguyên, tr. 60 - 64.
[2] Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh
Hà (2009), "Cải tiến thuật toán K-Means và ứng dụng phân cụm dữ liệu tự
động", Báo cáo Hội thảo Khoa học tại ĐH Lạc Hồng, Đồng Nai.
[3] Lê Thu Trang (2008), "Khai phá dữ liệu bằng phương pháp phân
cụm", Luận văn thạc sĩ Công nghệ thông tin, Khoa Công nghệ thông tin - Đại
học Thái Nguyên.
[4] Hoàng Văn Dũng, "Khai phá dữ liệu web bằng kỹ thuật phân cụm",
[5] Đỗ Văn Đại (2009), "Phân cụm dữ liệu trong không gian có chướng
ngại vật", Đồ án tốt nghiệp Đại học, Khoa Công nghệ thông tin - Đại học
Giao thông vận tải.
Tài liệu tiếng Anh
[6] Athena Vakali (2004), "Web data clustering Current research status
& trends", Aristotle University, Greece.
[7] Raghu Krishnapuram, Anupam Joshi, and Liyu Yi (2001), A Fuzzy
Relative of the K - Medoids Algorithm with Application toWeb Document
and Snippet Clustering.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
[8] Filippo Geraci, Marco Pellegrini, Paolo Pisati, and Fabrizio
Sebastiani (2006), A scalable algorithm for high-quality clustering of Web
Snippets, Italy, ACM.
[9] Hiroyuki Kawano (2004), Applications of Web mining- from Web
search engine to P2P filtering, IEEE.
[10] Raymond and Hendrik (2000), Web Mining Research: A Survey, ACM.
[11] Hua-Jun Zeng, Qi-Cai He, Zheng Chen, Wei-Ying Ma, Jinwen
Ma (2004), Learning to Cluster Web Search Results, ACM.
[12] Lizhen Liu, Junjie Chen, Hantao Song (2002), The research of Web
Mining, IEEE.
[13] Maria Rigou, Spiros Sirmakessis, and Giannis Tzimas (2006), A
Method for Personalized Clustering in Data Intensive Web Applications.
[14] Oren Zamir and Oren Etzioni (1998), Web document Clustering: A
Feasibility Demonstration, University of Washington, USA, ACM.
[15] Periklis Andritsos (2002), Data Clusting Techniques, University
Toronto.
[16] Yitong Wang, Masaru Kitsuregawa (2002), Evaluating Contents-
Link Coupled Web Page Clustering for Web Search Results, ACM.
[17] Zifeng Cui, Xu , Weifeng Zhang, Junling Xu (2005), Web
Documents Clustering with Interest Links, IEEE.
[18] Wenyi Ni (2004), A Survey of Web Document Clustering, Southern
Methodist University.
[19] Bing Liu (2007), Web mining, Springer.
Các file đính kèm theo tài liệu này:
- 27LV09_CNTT_KHMTTruongManhHa.pdf