›
›

Đồ án Bài toán khai thác thông tin về sản phẩm từ Web - Nguyễn Văn Huy

pdf 58 trang huongle 1620
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Bài toán khai thác thông tin về sản phẩm từ Web - Nguyễn Văn Huy", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_bai_toan_khai_thac_thong_tin_ve_san_pham_tu_web_nguyen.pdf

Nội dung text: Đồ án Bài toán khai thác thông tin về sản phẩm từ Web - Nguyễn Văn Huy

  1. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng MỤC LỤC MỤC LỤC 1 DANH SÁCH CÁC HÌNH 3 GIỚI THIỆU 6 CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 8 1.1CÁC KHÁI NIỆM CƠ BẢN 8 1.2 KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU 9 1.3 CÁC KỸ THUẬT ÁP DỤNG TRONG KHAI PHÁ DỮ LIỆU 11 1.3.1 Các kỹ thuật tiếp cận trong Khai phá dữ liệu 11 1.3.2 Các dạng dữ liệu có thể khai phá 12 1.4TÌM KIẾM THÔNG TIN TRÊN INTERNET 12 1.5 PHÂN LOẠI THÔNG TIN TÌM KIẾM 15 1.6TỔ CHỨC LƢU TRỮ THÔNG TIN TÌM KIẾM 17 1.7XỬ LÝ THÔNG TIN 17 CHƢƠNG 2: KHAI PHÁ VÀ TỔNG HỢP DỮ LIỆU 19 2.1 PHÂN CỤM DỮ LIỆU 19 2.2 CÁC ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU 20 2.3 CÁC KIỂU DỮ LIỆU VÀ ĐỘ ĐO TƢƠNG TỰ 21 2.3.1 Phân loại các kiểu dữ liệu dựa trên kích thƣớc miền 21 2.3.2 Phân loại các kiểu dữ liệu dựa trên hệ đo 21 2.4 CÁC YÊU CẦU CẦN THIẾT CHO TẠO DỤNG KỸ THUẬT PCDL 22 2.5 MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐIỂN HÌNH 24 2.5.1 Họ các thuật toán phân hoạch 24 2.5.2 Các thuật toán phân cụm phân cấp 28 2.5.3 Các thuật toán phân cụm dựa trên mật độ 31 CHƢƠNG 3: HỆ THỐNG ĐÁNH GIÁ THÔNG TIN SẢN PHẨM 35 3.1 Phát biểu bài toán 35 3.2 Xác định mô hình nghiệp vụ 36 3.2.1 Các chức năng nghiệp vụ 36 3.2.2 Biểu đồ Use Case tổng quan 37 3.2.3 Mô tả khái quát các hệ con 38 3.2.4 Các mô hình ca sử dụng chi tiết 39 3.3 Phân tích hệ thống 43 3.3.2 Phân tích gói ca sử dụng “Cập nhật các danh mục” 43 3.3.3 Phân tích gói ca sử dụng “Tìm kiếm” 49 3.3.4 Phân tích gói ca sử dụng “Báo cáo” 51 3.4 Thiết kế hệ thống 52 3.5 Thiết kế chƣơng trình 53 3.5.1 Giao diện chính của chƣơng trình 53 3.5.2 Giao diện cập nhật sản phẩm 53 3.5.3 Giao diện cập nhật loại sản phẩm 54 3.5.4 Giao diện cập nhật nhóm sản phẩm 55 3.5.5 Giao diện tìm kiếm thông tin sản phẩm 56 3.5.6 Kết quả của chƣơng trình minh họa 56 KẾT LUẬN 57 Nguyễn Văn Huy – CT1301 1
  2. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng TÀI LIỆU THAM KHẢO 58 Nguyễn Văn Huy – CT1301 2
  3. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng DANH SÁCH CÁC HÌNH Hình 1.1:Các bƣớc thực hiện trong quá trình khám phá tri thức 10 Hình 1.2 Các lĩnh vực liên quan đến Khám phá tri thức trong CSDL 11 Hình 1.3: Sơ đồ khối Khối truy vấn 13 Hình1.4: Sơ đồ khối Đánh chỉ mục 14 Hình2.1:Hình minh họa phân cụm dữ liệu 19 Hình2.2: Hình dạng cụm dữ liệu khám phá đƣợc bởi k-means 25 Hình 2.3:Cây CF đƣợc sử dụng bởi thuật toán BIRCH 28 Hình 2.4:Các cụm dữ liệu đƣợc khám phá bởi CURE 30 Hình 2.5: Hình minh họa phân cụm OPTICS 33 Hình 2.6:Hình minh họa DENCLUE với hàm phân phối Gaussian 34 Hình 3.1: Biểu đồ Use Case tổng quan 37 Hình 3.2: Biểu đồ ca sử dụng gói “Cập nhật” 39 Hình 3.3: Biểu đồ ca sử dụng gói “Tìm kiếm” 39 Hình 3.4: Biểu đồ ca sử dụng gói “Báo cáo” 41 Hình 3.5: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật nhóm sản phẩm” 44 Hình 3.6: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật nhóm sản phẩm” 44 Hình 3.7: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật loạisản phẩm” 45 Hình 3.8: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật loạisản phẩm” 45 Hình 3.9: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật sản phẩm” 46 Hình 3.10: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật sản phẩm” 46 Hình 3.11: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật Search Engine” 47 Hình 3.12: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật Search Engine” 47 Hình 3.13: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật thông số tìm kiếm” 48 Hình 3.14: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật thông số tìm kiếm” 48 Hình 3.15: Mô hình phân tích gói ca “Cập nhật” 49 Hình 3.16: Biểu đồ tuần tự thực thi ca sử dụng “Tìm kiếm” 49 Hình 3.17: Biểu đồ cộng tác thực thi ca sử dụng “Tìm kiếm” 50 Hình 3.18: Mô hình phân tích gói ca”Tìm kiếm” 50 Hình 3.19: Biểu đồ tuần tự thực thi ca sử dụng “Lập báo cáo” 51 Hình 3.20: Biểu đồ cộng tác thực thi ca sử dụng “Báo cáo” 51 Hình 3.21: Mô hình phân tích gói ca”Báo cáo” 51 Hình 3.22: Mô hình lớp thiết kế hệ thống 52 Hình 3.23 Giao diện chính của chƣơng trình 53 Hình 3.24: Giao diện cập nhật sản phẩm 53 Hình 3.25: Giao diện cập nhật loại sản phẩm 54 Hình 3.26: Giao diện cập nhật nhóm sản phẩm 55 Nguyễn Văn Huy – CT1301 3
  4. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 3.27: Giao diện tìm kiếm thông tin sản phẩm 56 Nguyễn Văn Huy – CT1301 4
  5. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng DANH SÁCH BẢNG BIỂU Bảng 3.1: Bảng xác định các chức năng nghiệp vụ của hệ thống 36 Bảng 3.2: Bảng xác định tác nhân của hệ thống 37 Bảng 3.3: Bảng mô tả các ca sử dụng và tác nhân 38 Bảng 3.4: Bảng mô tả ca sử dụng cập nhật nhóm sản phẩm 39 Bảng 3.5: Bảng mô tả ca sử dụng cập nhật loại sản phẩm 40 Bảng 3.6: Bảng mô tả ca sử dụng cập nhật sản phẩm 40 Bảng 3.7: Bảng mô tả ca sử dụng câp nhật Search Engine 41 Bảng 3.8: Bảng mô tả ca sử dụng cập nhật thông số tìm kiếm 41 Bảng 3.9: Bảng mô tả ca sử dụng tìm kiếm 42 Bảng 3.10: Bảng mô tả ca sử dụng báo cáo 43 Nguyễn Văn Huy – CT1301 5
  6. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng GIỚI THIỆU Web là kho tài nguyên dữ liệu khổng lồ, không ngừng tăng trƣởng với tốc độ cao. Ngày càng nhiều thông tin trong cuộc sống đƣợc đƣa lên Internet. Trong đó, Internet chứa nhiều thông tin có giá trị liên quan đến cộng đồng nói chung, và các hoạt động sản xuất kinh doanh nói riêng.Xuất phát từ thực tế đó, vậy có phƣơng pháp nào? Chúng ta có thể khai thác thông tin từ Internet để phục vụ cuộc sống. Hiện nay có nhiều công trình nghiên cứu các phƣơng pháp khai thác thông tin từ Internet. Xuất phát từ bài toán thực tế trong hoạt động kinh doanh thƣơng mại, liệu có phƣơng pháp nào đánh giá thông tin về sản phẩm thông qua các nhận xét của ngƣời dùng trên Internet? Đây là một bài toán khó cần kết hợp nhiều kiến thức để giải quyết bài toán này. Do đó em chọn đề tài: “Bài toán khai thác thông tin về sản phẩm từ Web”.Khóa luận tập trung tìm hiểu các lý thuyết liên quan nhằm phần nào giải quyết đƣợc vấn đề đặt ra. Một hệ thống tổng hợp thông tin từ Internet cho phép ngƣời dùng đƣa vào các thông tin cần đánh giá về sản phẩm đƣợc quan tâm. Sau đó, hệ thống đƣa đƣợc ra các thông tin liên quan đến sản phẩm để có thể hỗ trợ các doanh nghiệp có thêm một kênh thông tin về các sản phẩm trên thị trƣờng. Hệ thống đƣợc mô tả nhƣ sau: 1. Nhập thông tin sản phẩm:Ngƣời dùng nhập các thuật ngữ về thông tin sản phẩm vào ô thông tin sản phẩm cần đánh giá. Hệ thống trả về các thông tin sản phẩm mà hệ thống khai thác, phân loại, thống kê đƣợc thông qua máy tìm kiếm 2. Tìm kiếm thông tin:Hệ thống dựa vào các thông tin sản phẩm đƣợc nhập vào và gửi vào máy tìm kiếm để tìm các Ý kiến người dùng sản phẩmhoặc Xu hướng. 3. Hỗ trợ đánh giá:Kết quả trả về từ máy tìm kiếm đƣợc đem phân loại, thống kê các thông tin cần thiết về sản phẩm nhằm đánh giá cảm nhận của người tiêu dùng đối với sản phẩm đƣợc đƣa vào đánh giá. 4. Báo cáo:Hệ thống đƣa ra các bản báo cáo về ý kiến của ngƣời sử dụng sản phẩm bằng các số liệu theo chuyên môn. Nguyễn Văn Huy – CT1301 6
  7. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 5. Giao diện hệ thống:Hệ thống có giao diện thân thiện, thuận lợi cho ngƣời dùng và ngƣời quản lý. Qua cách đặt vấn đề trên, khóa luận được trình bày như sau: Giới thiệu: Giới thiệu chung về bài toán và phạm vi của khóa luận. Chƣơng 1:Trình bày cơ sở lý thuyết để thục hiện khóa luận. Chƣơng 2:Trình bày các kiến thức liên quan đến bài toán tìm kiếm thông tin trên Internet dùng để trợ giúp các hoạt động trong kinh doanh. Chƣơng 3:Trình bày phần phân tích thiết kế một ứng dụng mang tính chất thử nghiệm. Kết luận Tài liệu tham khảo Nguyễn Văn Huy – CT1301 7
  8. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 1.1CÁC KHÁI NIỆM CƠ BẢN Khai phá dữ liệu là một hƣớng nghiên 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 Cơ sở dữ liệu,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, theo [1] khái niệm Khai phá dữ liệu nhƣ sau: “Khai phá dữ liệu là một quá trình tìm kiếm, phân tích, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn.” Trong lĩnh vực khai phá dữ liệu, có nhiều hƣớng nghiên cứu đƣợc đƣa ra trong đó có một số hƣớng chính đƣợc nhiều nhà nghiên cứu quan tâm. Khai phá dữ liệu văn bản,Web, Trích chọn thông tin, Phân tích mạng xã hội, khai phá quan điểm, Phân tích dữ liệu kinh tế - tài chính, Khai phá dữ liệu sinh học, y tế, Khóa luận này hƣớng đến việc tìm hiểu và xây dựng hệ thống thống nhằm khai thác thông tin các sản phẩm mà ngƣời tiêu dùng đã đánh giá trên Internet, cụ thể là các trang web. Ngƣời tiêu dùng có mua, sử dụng các sản phẩm và họ đã có cảm nhận và suy nghĩ về sản phẩm đó. Đôi lúc họ đƣa những cảm nhận về sản phẩm nào đó lên các trang web cá nhân, các diễn đàn, trên Internet. Bài toán mà khóa luận này tìm cách giải quyết là tìm cách khai thác các thông tin về một sản phẩm cụ thể nào đó trên Internet, thống kê để phục vụ cho công tác khảo sát và đánh giá sản phẩm trên thị trƣờng. Sau đây là một số khái niệm đƣợc sử dụng. Thông tin sản phẩm: Là thông tin mô tả về nguồn gốc, tính năng kỹ thuật, tính chất lý hóa tính, công dụng chính, giá thành, màu sắc, hình dáng, kích thƣớc, của sản phẩm. Nguyễn Văn Huy – CT1301 8
  9. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ý kiến ngƣời dùng sản phẩm: Là các thông tin ngƣời dùng phản ánh về sản phẩm đƣợc thể hiện qua các từ đánh giá về ƣu điểm nhƣ: Tốt, thuận tiện, tiết kiệm, bền, rẻ, đẹp, phong phú, đa dạng, mƣợt mà, mịn, hoặc đƣợc đánh giá nhƣợc điểm: Xấu, kém, mau hỏng, hàng giả, hàng nhái, hoặc đƣợc thể hiện mong muốn về sản phẩm qua các từ nhƣ: giá nhƣ, giá mà, cần, phải, để tốt hơn, Xu hƣớng: Là các từ liên quan đến các mong muốn của ngƣời dùng về sản phẩm. Đƣợc chi thành xu hƣớng tốt hoặc xấu hoặc không thiện cảm. + Xu hƣớng tốt: Xu hƣớng đánh giá thông tin sản phẩm tốt + Xu hƣớng xấu: Xu hƣớng đánh giá thông tin sản phẩm xấu + Xu hƣớng không thiện cảm: Xu hƣớng không khen, không chê sản phẩm. Ngƣời tiêu dùng: Là ngƣời mua hoặc ngƣời sử dụng sản phẩm hoặc ngƣời có ý định mua hay sử dụng sản phẩm có gửi thông tin lên Internet. Ngƣời dùng: Ngƣời có tƣơng tác với hệ thống. Ngƣời quản trị: Ngƣời có nhiệm vụ quản lý hệ thống. Máy tìm kiếm:Các cỗ máy tìm kiếm thông tin trên Internet: Google, Yahoo, Bing, Sản phẩm: Là tất cả các mặt hàng đang đƣợc tiêu thụ trên thị trƣờng bao gồm thị trƣờng trong nƣớc và nƣớc ngoài. 1.2 KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU Khai phá dữ liệu là lĩnh vực có liên quan đến nhiều ngành khác nhau nhƣ: thống kê, học máy, tính toán phân tán,cơ sở dữ liệu, thuật toán, mô hình hóa dữ liệu, Mục tiêu của khai phá dữ liệu là khám phá tri thức từ đó dùng hỗ trợ ra quyết định, trong lĩnh vực hẹp này có thể đƣợc chia thành một số giai đoạn [3][4]: . Trích chọn dữ liệu: bƣớc này trích những bộ dữ liệu cần đƣợc khám phá từ các hệ thống dữ liệu (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định. Nguyễn Văn Huy – CT1301 9
  10. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng . Tiền xử lý dữ liệu:Bƣớc này làm sạch dữ liệu (xử lý những dữ liệu dƣ thừa, nhiễu, .v.v.), rút gọn dữ liệu (áp dụng các thuật toán lấy mẫu, .v.v.), rời rạc hóa dữ liệu. Kết quả là 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 dữ liệu, tinh chỉnh dữ liệu để đƣa dữ liệu về dạng chuẩn để giúp kỹ thuật khai phá dữ liệu ở bƣớc sau. . Khai phá dữ liệu: Áp dụng những kỹ thuật phân tích nhằm để trích chọn thông tin, những mối liên hệ đặc biệt của dữ liệu. Bƣớc này rất quan trọng và cần nhiều tài nguyên nhất của toàn bộ quá trình khai phá trin thức. . Đánh giá và biểu diễn tri thức: Các mẫu tin và quan hệ giữa chúng đã đƣợc rút trích ở bƣớc trên đƣợc mã hóa và biểu diễn theo dạng dễ quan sát nhƣ đồ thị, cây, bảng biểu, luật, .v.v. Bƣớc này cung cấp thông tin cho các nhà quản trị ra quyết định. Các giai đoạn trong KDD đƣợc thể hiện trực quan nhƣ hình 1 dƣới đây: Hình 1.1:Các bước thực hiện trong quá trình khám phá tri thức Nguyễn Văn Huy – CT1301 10
  11. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 1.3 CÁC KỸ THUẬT ÁP DỤNG TRONG KHAI PHÁ DỮ LIỆU 1.3.1 Các kỹ thuật tiếp cận trong Khai phá dữ liệu Khai phá tri thức 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 1.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 Dựa trên quan điểm của học máy thì các kỹ thuật trong Khai phá dữ liệu, bao gồm: . Học có giám sát: 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. . Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tƣơng tự nhau mà chƣa biết trƣớc các thông tin về lớp hay tập các ví dụ huấn luyện. . Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trƣớc. Theo lớp các bài toán cần giải quyết, thì Khai phá dữ liệu bao gồm các kỹ thuật áp dụng sau: . Phân lớp và dự đoán(classification and prediction): xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ: phân lớp các bệnh nhân dữ liệu trong hồ sơ bệnh án. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định (decision tree), mạng nơ ron nhân Nguyễn Văn Huy – CT1301 11
  12. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng tạo (neural network), .v.v. Phân lớp và dự đoán còn đƣợc gọi là học có giám sát. . Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản. Ví dụ: “60 % nữ giới vào siêu thị nếu phấn thì có tới 80% trong số họ sẽ mua thêm son”. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trƣờng chứng khoán, .v.v. . Phân tích chuỗi theo thời gian (sequential/ temporal patterns): tƣơng tự nhƣ khai phá luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán vì nó có tính dự báo cao. . Phân cụm (clustering/ segmentation): xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên. Phân cụm còn đƣợc gọi là học không có giám sát ( 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.3.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 trên nhiều lĩnh vực có thể làm việc với rất nhiều kiểu dữ liệu khác nhau. Ví dụ: Cơ sở dữ liệuquan hệ, dữ liệu đa chiều, Cơ sở dữ liệu quan hệ - hướng đối tượng, Cơ sở dữ liệu có thuộc tính không gian và thời gian, Cơ sở dữ liệu chuỗi thời gian, Cơ sở dữ liệu đa phương tiện, 1.4TÌM KIẾM THÔNG TIN TRÊN INTERNET Theo [thụy1] máy tìm kiếm là một hệ thống phần mềm đƣợc xây dựng nhằm tiếp nhận yêu cầu tìm kiếm của ngƣời dùng, sau đó phân tích yêu cầu này và tìm kiếm thông tin trong cơ sở dữ liệu đƣợc tải xuống từ Internet và đƣa ra kết quả là danh sách các trang Web lên quan với yêu cầu ngƣời dùng. Về cơ bản, mọi kỹ thuật tập trung vào máy tìm kiếm (Searche engine). Hiện nay trên thế giới có rất nhiều máy tìm kiếm, điển hình là Google, Bing, Yahoo, ,và một số máy tìm kiếm có cách thực hiện rất đặc biệt không chỉ đƣa ra kết quả tìm kiếm là các địa chỉ chứa thông tin mà tìm kiếm và tổng hợp tri thức nhƣ Nguyễn Văn Huy – CT1301 12
  13. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Wolframanpha, máytìm kiếm này còn biết cách trả lời các vấn đề mang tính chất đặc thù chuyên ngành nhƣ toán học, lý, hóa, lịch sử, địa lý, Kiến trúc cơ bản của máy tìm kiếm gồm các khối nhƣ truy vấn dữ liệu, đánh chỉ mục, phân loại dữ liệu .Nói chung, máy tìm kiếm thực hiện một số thao tác cơ bản sau: Bước 1: Phân tích các yêu cầu của người dùng, phân loại và đánh chỉ mục các yêu cầu này, lưu vào hệ thống. Bước 2:Các kết quả tìm kiếm cũng được phân tích, đánh chỉ mục và lưu vào hệ thống. Bước 3: Khi có yêu cầu tìm kiếm thông tin, máy tìm kiếm so khớp yêu cầu với các yêu cầu đã có sẵn nếu phù hợp sẽ đưa kết quả ra luôn, nếu yêu cầu này chưa có thì sẽ tìm thông tin rồi thao tác lại bước 1. Đối với kết quả tìm kiếm mới sẽ bổ sung như bước 2. Sau đây là sơ đồ kiến trúc chung của một số khối trong máy tìm kiếm [2]. Khối Truy vấn Hình 1.3: Sơ đồ khối Khối truy vấn Khối truy vấn nhận thông tin từ ngƣời dùng theo dạng văn bản. Từ đó phân loại, xác định yêu cầu của câu truy vấn xem thuộc nhóm nào? Đánh giá và phân tích câu. Tìm kiếm trong cơ sở dữ liệu chỉ mục rồi trả lại kết quả tìm kiếm cho ngƣời dùng. Nguyễn Văn Huy – CT1301 13
  14. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Khối Đánh chỉ mục Hình1.4: Sơ đồ khối Đánh chỉ mục Trong khóa luận này máy tìm kiếm Google đƣợc sử dụng làm công cụ để lấy thông tin. Do đó, phần sau sẽ khảo sát kỹ hơn về máy tìm kiếm của Google. Tên gọi của máy tìm kiếm Google có nguồn gốc từ chữ “Googol”. Sau một thời gian không lâu máy tìm kiếm này trở nên nổi tiếng vì đáp ứng tốt yêu cầu ngƣời dùng. Google đã áp dụng những kỹ thuật tiên tiến để nâng cao khả năng sản phẩm của họ nhƣ: . Công nghệ crawling có tốc độ cao khi thu thập tài liệu và cập nhật chúng. . Hệ thống lưu trữ không những lưu trữ chỉ số mà lưu trữ toàn bộ nội dung tài liệu. . Hệ thống đánh chỉ số hiệu quả khi làm việc trên hàng trăm tetrabyte dữ liệu. . Câu hỏi cần được tiếp nhận và đáp úng nhanh theo cỡ hàng trăm nghìn câu hỏi trong một giây. Máy tìm kiếm này có một số đặc trƣng - Boolean: việc cho phép ngầm định các phép toán logic(and, or, not, (),+,-) trong câu hỏi tìm kiếm và thực hiện. - Default:Phép toán logic được thi hành ngầm định. - Proxymity:Thực hiện tìm theo cụm từ. - Truncation: Tiến hành tìm kiếm theo từ gốc,cho phép có kí hiệu đại diện trong câu hỏi. Nguyễn Văn Huy – CT1301 14
  15. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng - Fields: Cho phép đặt tham số tìm kiếm theo một số trường theo tiêu đề, địa chỉ URL, liên kết, miền/site, kiểu file, - Limits: Cho phép đưa ra một số hạn chế về thời gian, lĩnh vực , nội dung, đa phương tiện - Stop(stop word): Cho phép loại bỏ từ dừng, một số trường hợp không tiến hành tìm kiếm từ quá thông dụng. - Sorting: Sắp xếp kết quả tìm kiếm theo độ liên quan, phân cụm theo địa chỉ web, sắp theo thứ tự thời gian, kích thước. 1.5 PHÂN LOẠI THÔNG TIN TÌM KIẾM Bài toán phâncụm thông tinlà một trong những bài toán quan trọng nhất trong lĩnh vực khai phá dữ liệu. Phân cụm dữ liệu là dựa vào các mục tiêu tức là cụ thể các tiêu chí phân cụm để tự động sinh ra các lớp(cụm) thông tin. Khi áp dụng các thuật toán phân cụm dữ liệu nhằm mục đích quan trọng là khai phácác cấu trúc của mẫu dữ liệu để từ đó tạo ra các cụm dữ liệu từ kho dữ liệu gốc, theo đó, cho phép phân tích, nghiên cứu cho từng cụm dữ liệu để khám phá và trích xuất các thông tin tiềm ẩn, có ích hỗ trợ ra quyết định. Ví dụ: Sau khi tìm kiếm các văn bản trên Internet về các thông tin sản phẩm, hệ thống được xây dựng phải khám phá ra các thông tin về sự đánh giá của người tiêu dùng về sản phẩm đó là “tốt” hay “xấu” hoặc xu hướng mong muốn về sản phẩm cảu người tiêu dùng. Nhƣ vậy, phân cụm dữ liệu là phƣơng thức xử lý thông tin 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.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, khóa luận sẽ đề cập đến các hƣớng phân cụm dữ iệu, đây là phần quan trọng trong lĩnh vực khai phá dữ liệu. Các hƣớng giải quyết phân cụm: Theo [thụy1], có một số cách phân cụm nhƣ sau: Nguyễn Văn Huy – CT1301 15
  16. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng - Phương pháp phân cụm theo mô hìnhvà phân vùng (partitioning): Phƣơng pháp thứ nhất tạo ra các mô hình biểu diễn các cụm; phƣơng pháp thứ hai chỉ đơn giản là tập hợp các phần tử dữ liệu vào các cụm. - Phân cụm đơn định và phân cụm xác suất: Trong phân cụm đơn định, mỗi một phần tử dữ liệu (thông tin trên trang Web) chỉ phụ thuộc vào một cụm. Có thể xem xét việc gán thông tin d thuộc cụm i nhƣ là việc đặt một giá trị trong mảng hai chiều Z Boolean Zd,ilà l. Trong phân cụm xác suất. mỗi phần tử dữ liệu sẽ có xác suất nào đó đối với mỗi cụm. Trong ngữ cảnh này, Zd,i có giá trị là một số thực trongkhoảng[0,1]. Tức là, giá trị trong bảng là một ánh xạ z: S S [0, 1] và các vector ci, làm cực tiểu hóa hoặc cực đại hóa . - Phân cụm phẳng và phân cụm phân cấp: Phân cụm phẳng chỉ đơn giản là chia tập dữ liệu thành một số tập con. Còn phân cụm phân cấp tạo ra một cây phân cấp của các cụm. Việc phân hoạch có thể thực hiện theo hai cách,a) cách thứ nhất bắt đầu bằng việc cho mỗi mẫu tin vào một cụm của nó và tiến hành kết hợp các cụm lại với nhau cho đến khi số các cụm là phù hợp, cách này đƣợc gọi là phân cụm từ dƣới lên (bottom - up). b) Cách thứ hai bắt đầu bằng việc khai báo các cụm nguyên thủy và sau đó gán các mẫu tin vào các cụm, cách này dƣợc gọi là phân cụm từ trên xuống (top - down). Nhƣ vậy, có thể xem xét kỹ thuật phân cụm bottom - up dựa vào quá trình lặp lại việc trộn các cụm tƣơng tự nhau cho đến khi đạt đƣợc sổ cụm mongmuốn; kỹ thuật phân cụm top - down làm mịn dần bằng cách gán các mẫu tin vào các cụm đƣợc thiết đặt trƣớc. Kỹ thuật bottom - up thƣờng chậm hơn, nhƣng có thể đƣợc dùng trộn một tập nhỏ các mẫu có trƣớc để khởi tạo các cụm nguyên thủy trƣớc khi tiến hành kỹ thuật từ trên xuống. - Phân cụm theo lô và phân cụm gia tăng: Trong phân theo lô, toàn bộ tập dữ liệu đƣợc sử dụng để tạo ra các cụm. Trong phân cụm gia tăng. giải thuật phân cụm lấy từng phần tử dữ liệu và cập nhật các cụm để phân vào cụm thích hợp. Trong khóa luận này, các mẫu tin đƣợc phân cụm theo các tiêu chí đem vào tìm kiếm. Nghĩa là, các tiêu chí tìm kiếm bao gồm tên sản phẩm, các thuộc tính của sản phẩm. Các sản phẩm đƣợc phân loại theo loại sản phẩm. Các loại sản phẩm Nguyễn Văn Huy – CT1301 16
  17. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng thuộc một nhóm sản phẩm nào đó. Các tiêu chí này đƣợc gán một mã xác định(mã tìm kiếm) nhằm phân biệt các tiêu chí khác nhau, dễ dàng cho việc phân cụm. 1.6 TỔ CHỨC LƢU TRỮ THÔNG TIN TÌM KIẾM Khi có kết quả tìm kiếm các hệ thống cần lƣu trữ theo một định dạng nào đó để phục vụ các nghiệp vụ tiếp theo. Hiện nay ngƣời ta thƣờng dùng hệ quản trị cơ sở dữ liệu lớn để lƣu trữ nhƣ: SQL server, MySQL, Postgre, Oracle, Đặc biệt hiện nay định dạng XML là một trong những chuẩn dữ liệu đƣợc dùng phổ biến. Khóa luận này sử dụng hệ quản trị cơ sở dữ liệu SQL server để lƣu trữ. Dữ liệu khai thác về đƣợc phân loại theo các tiêu chí tìm kiếm, các thông tin từ các trang web khi lấy về đƣợc đánh mã để phân biệt cho mỗi lần lấy kết quả. Các thông tin này đƣợc gắn với mã tìm kiếm. Các url chính xác của từng bản tin cũng đƣợc lƣu trữ để thuận tiện cho việc lấy lại nội dung sau này. Ví dụ: Lƣu trữ thông tin sau khi tìm kiếm: WebsiteID SearchID Url Content 97 26 Vanphongphamt2.com WebsiteID là mã của trang Web chứa bản tin thỏa mãn tiêu chí tìm kiếm có mã SearchID là 26 (chứa các từ khóa về sản phẩm các loại bút bi) . Thuộc tính Url chứa địa chỉ của Website có chứa thông tin về bút bi, Thuộc tính Contentchứa các văn bản về thông tin các loại bút bị có trong Website Vanphongphamt2.com, đôi khi còn có lẫn các thẻ định dạng HTML của trang Web đó. Dữ liệu này mới chỉ là dữ liệu thô. Các bản tin đƣợc nhóm theo mục tiêu tìm kiếm (phụ thuộc vào nội dung của khóa tìm kiếm) do vậy các bản tin thƣờng chứa các thông tin về một loại sản phẩm cụ thể. 1.7XỬ LÝ THÔNG TIN Các bản tin nhận đƣợc từ các máy tìm kiếm đƣợc lƣu trữ trong hệ quản trị cơ sở dữ liệu SQL Server. Các dữ liệu này đƣợc gọi là dữ liệu thô. Về mặt hình thức văn bản này đƣợc coi là văn bản phi cấu trúc, trong đó các đối tƣợng đƣợc diễn tả Nguyễn Văn Huy – CT1301 17
  18. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng bằng các danh từ và các thuộc tính của đối tƣợng đƣợc mô tả bằng các tính từ, trạng từ, Khi xử lý thông tin đƣợc máy tìm kiếm trả về, dựa vào bộ từ khóa tìm kiếm SearchKeystrong bảng SearchTable theo hình sau: SearchID SearchKeys ProductID SearchEngineID Bút + bi + ngoại + 26 Giá + tiền + Bền + 10 www.google.com Rẻ Dữ liệu đƣợc phân cụm theo mã sản phẩm ProductID = 10và các thuộc tính của sản phẩm này. Hệ thống phân tích các thông tin rồi phân cụm chúng theo các tiêu chí đƣợc lƣu trong SearchKeys đối với sản phẩm có mã ProductID = 10. Nguyễn Văn Huy – CT1301 18
  19. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 2: KHAI PHÁ VÀ TỔNG HỢP DỮ LIỆU Chƣơng này khóa luận trình bày một số kiến thức cơ bản liên quan đến thống kê và khai phá dữ liệu, theo đó làm sáng tỏ cách thức tổng hợp thông tin từ các mẫu tin khai thác đƣợc 2.1 PHÂN CỤM DỮ LIỆU Phân cụm dữ liệu áp dụng nhiều kiến thức trong các ngành học máy, thống kê, nhận dạng, Có rất nhiều khái niệm khác nhau về phân cụm, tuy nhiên có khái niệm chung nhất về phân cụm [2]. "Phân cụm dữ liệu là một phương pháp trong khai phá dữ liệu, 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, hấp dẫn trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho người sử dụng." Thật vậy, phân cụm dữ liệu là quá trình phân chiatập dữ liệu thành các khần khác nhau dựa trên một tập các tiêu chí cho trƣớc. Phƣơng pháp phân cụm có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định bằng phƣơng pháp phân cụm. Hình2.1:Hình minh họa phân cụm dữ liệu Ở hình trên, khi áp dụng phƣơng pháp phân cụm dù thủ công hay tự động, sẽ thu đƣợc các cụm trong đó các phần tử "gần nhau" hay là "tương tự" thì chúng thuộc về các cụm khác nhau. Phân cụm dữ liệu phải giải quyết đó là hầu hết các dữ liệu chứa dữ liệu "nhiễu" (noise) do các bƣớc lấy mẫu chƣa đầy đủ hoặc thiếu chính xác, do đó cần phải lập kế hoạch chiến lƣợc ngay tại bƣớc tiền xử lý dữ liệu để loại bỏ "nhiễu" Nguyễn Văn Huy – CT1301 19
  20. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng trƣớc khi đƣa vào giai đoạn tiếp theo. Khái niệm "nhiễu" đƣợc hiểu là thông tin về các đối tƣợng chƣa chính xác, hoặc là khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối tƣợng "nhiễu" bằng giá trị thuộc tính tƣơng ứng của đối tƣợng dữ liệu gần nhất. Do vậy, phân cụm dữ liệu cần giải quyết một số vấn đề sau: . Xây dụng hàm tính độ đo tương tự . Xây dựng tập các tiêu chí phân cụm . Thiết lập các cấu trúc dữ liệu cho cụm dữ liệu . Xây dựng thuật toán phân cụm dữ liệu . Xây dựng hệ thống phân tích và đánh giá kết quả Ngày nay, chƣa có một phƣơng pháp phân cụm nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu. 2.2 CÁC ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU Phân cụm dữ liệu đƣợc ứng dụng trong nhiều lĩnh vực kinh tế, y học, thƣơng mại, khoa học, Các phƣơng pháp phân cụm đƣợc áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau: . Thương mại: Trong thƣơng mại, các hệ thống thông tin áp dụng phƣơng pháp phân cụm dữ liệu có thể giúp các doanh nhân có đủ thông tin về nhóm khách hàng quan trọng có các đặc trƣng tƣơng đồng nhau và từ đó ra quyết định chính xác hơn. . Khoa học tự nhiên: Các lĩnh vực nhƣ sinh học, môi trƣờng, địa lý, toán học, các phƣơng pháp phân cụm giúp cho các nhà nghiên cứu cô lập đƣợc các thông tin đặc thù của từng đối tƣợng để phục vụ cho nghiên cứu. . Nghiên cứu trái đất: Phân cụm để theo dõi các hoạt động của các vùng trên trái đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm. . Khai phá dữ liệu Web: Phân cụm dữ liệu có thể khai phá các nhóm dữ liệu có nhiều ý nghĩa trong môi trƣờng Web, nhƣ khai thác quan điểm ngƣời dùng, xu hƣớng tiếp cận và giải quyết vấn đề. Nguyễn Văn Huy – CT1301 20
  21. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2.3 CÁC KIỂU DỮ LIỆU VÀ ĐỘ ĐO TƢƠNG TỰ Khi phân cụm dữ liệu cần có một “thƣớc đo” nào đó để đo các sự vật. Nhƣ vậy với các đối tƣợng khác nhau thì cần “thƣớc đo” cũng khác nhau. Sau đây là cách phân lớp dựa trên hai đặc trƣng là: kích thƣớc miền và hệ đo. Cho một Cơ sở dữ liệuD chứa nphần tử trong không gian k chiều, trong đó x,y,z là các phần tử thuộc D: x=(x1,x2, ,xk);y=(y1,y2, ,yk);z=(z1,z2, ,zk), trong đó xi, yi, zi với i 1,k là các thuộc tính tƣơng ứng của các đối tƣợng x,y,z. Vì vậy, hai khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” đƣợc xem là tƣơng đƣơng với nhau, nhƣ vậy, chúng ta sẽ có các kiểu dữ liệu sau [2]. 2.3.1 Phân loại các kiểu dữ liệu dựa trên kích thƣớc miền . Thuộc tính liên tục (Continuous Attribute): Thuộc tính này có miền giá trị là vô hạn không đếm đƣợc, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ nhƣ trƣờng số thực. . Thuộc tính rời rạc (DiscretteAttribute): Miền giá trị của thuộc tính này là đếm đƣợc. Thí dụ nhƣ số nguyên. Lớp các thuộc tính nhị phân là trƣờng hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử đƣợc diễn tả nhƣ:Yes/No hoặc Nam/Nữ, False/true, 2.3.2 Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tƣợng x, y và các thuộc tính xi, yi tƣơng ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu nhƣ sau: . Thuộc tính định danh(nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tƣợng thuộc tính thì chỉ có thể xác định là x y hoặc x=y. Thí dụ nhƣ thuộc tính về nơi sinh hoặc thuộc tính các đội bóng chơi cho giải vô địch quốc gia Việt Nam. . Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhƣng chúng không đƣợc định lƣợng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x y hoặc x=y hoặc x>y hoặc x<y. Thí dụ nhƣ thuộc tính Huy chương của vận động viên thể thao. Nguyễn Văn Huy – CT1301 21
  22. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng . Thuộc tính khoảng (Interval Scale): Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trƣớc hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi>yi thì ta nói x cách y một khoảng xi – yi tƣơng ứng với thuộc tính thứ i. Một thí dụ về thuộc tính khoảng nhƣ thuộc tính số Serial của một đầu sách trong thƣ viện hoặc thuộc tính số kênh trên truyền hình. . Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhƣng đƣợc xác định một cách tƣơng đối so với điểm mốc đầy ý nghĩa, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), trong khi đó thì thuộc tính khoảng và thuộc tính tỉ lệ đƣợc gọi là thuộc tính số (Numeric). Ngƣời ta còn đặc biệt quan tâm đến dữ liệu không gian (Spatial Data). Đây là loại dữ liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tƣợng, thí dụ nhƣ thông tin về hình học, Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc: . Dữ liệu không gian rời rạc: có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định đƣợc khoảng cách giữa các đối tƣợng dữ liệu trong không gian. . Dữ liệu không gian liên tục: bao chứa một vùng trong không gian. Thông thƣờng, các thuộc tính số đƣợc đo bằng các đơn vị xác định nhƣ là kilogams hay là centimeter. Tuy nhiên, các đơn vị đo có ảnh hƣởng đến các kết quả phân cụm. Thí dụ nhƣ thay đổi độ đo cho thuộc tính cân nặng từ kilogams sang Pound có thể mang lại các kết quả khác nhau trong phân cụm. Để khắc phục điều này ngƣời ta phải chuẩn hoá dữ liệu, tức là sử dụng các thuộc tính dữ liệu không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hoá phụ thuộc vào ứng dụng và ngƣời dùng, thông thƣờng chuẩn hoá dữ liệu đƣợc thực hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các trọng số cho các thuộc tính. 2.4 CÁC YÊU CẦU CẦN THIẾT CHO TẠO DỤNG KỸ THUẬT PCDL Dựa vào mục đích của ứng dụng thực tế hoặc yêu cầu về chất lƣợng số liệu mà các phƣơng pháp phân cụm có thể khác nhau. Đây là bƣớc quan trọng cho việc Nguyễn Văn Huy – CT1301 22
  23. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng giải quyết vấn đề phân cụm. Các phƣơng pháp đều thóa mãn tiêu chuẩn chung nhƣ sau: . Có khả năng mở rộng (Scalability): Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ ( khoảng 200 bản ghi dữ liệu ) nhƣng không hiệu quả khi áp dụng cho tập dữ liệu lớn (Khoảng 1 triệu bản ghi). . Thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau nhƣ dữ liệu kiểu số, kiểu nhị phân, dữ liệu kiểu hạng mục, và thích nghi với kiểu dữ liệu hỗn hợp giữa các dữ liệu đơn trên. . Khám phá ra các cụm với hình thù bất kỳ: do hầu hết các CSDL có chứa nhiều cụm dữ liệu với các hình thù khác nhau nhƣ: hình lõm, hình cầu, hình que, Vì vậy, để khám phá đƣợc các cụm có tính tự nhiên thì các thuật toán phân cụm cần phải có khả năng khám phá ra các cụm có hình thù bất kỳ. . Tối thiểu lượng tri thức cần cho xác định các tham số vào: do các giá trị đầu vào thƣờng rất ảnh hƣởng đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các CSDL lớn. . Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu, khi đƣa vào xử lý cho thuật toán PCDL với các thứ tự vào của các đối tƣợng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hƣởng lớn đến kết quả phân cụm. . Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm trong Data Mining đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác. Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất lƣợng phân cụm thấp do nhạy cảm với nhiễu. . Ít nhạy cảm với các tham số đầu vào: Nghĩa là giá trị của các tham số đầu vào khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm. . Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau. . Dễ hiểu, cài đặt và khả dụng. Các yêu cầu này đồng thời là các tiêu chí để đánh giá hiệu quả của các phƣơng pháp phân cụm dữ liệu, đây là các thách thức cho các nhà nghiên cứu trong lĩnh vực PCDL. Các yêu cầu này sẽ đƣợc đề cập đến cụ thể hơn khi đi vào khảo cứu chi tiết một số thuật toán PCDL đƣợc trình bày ở các chƣơng sau. Nguyễn Văn Huy – CT1301 23
  24. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2.5 MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐIỂN HÌNH Có rất nhiều thuật toán đƣợc áp dụng trong phân cụm dữ liệu. Do đo trong phần này khóa luận trình bày một số thuật toán cơ bản, rất kinh điển trong phân cụm dữ liệu. Các thuật toán này đƣợc chia thành các họ thuật toán: Họ các thuật toán phân cụm phân hoạch (Patitional), họ các thuật toán phân cụm phân cấp (Hierachical), họ các thuật toán phân cụm dựa trên lƣới và các thuật toán PCDL đặc thù khác nhƣ: các thuật toán phân cụm dựa trên mật độ, các thuật toán phân cụm dựa trên mô hình, 2.5.1 Họ các thuật toán phân hoạch Họ các thuật toán phân cụm phân hoạch bao gồm các thuật toán đề xuất đầu tiên trong lĩnh vực Data Mining cũng là các thuật toán đƣợc áp dụng nhiều trong thực tế nhƣ k-means, PAM (Partioning Around Medoids), CLARA (Clustering LARge Applications), CLARANS (Clustering LARge ApplicatioNS). Trƣớc hết chúng ta đi khảo cứu thuật toán k-means, đây là một thuật toán kinh điển đƣợc kế thừa sử dụng rộng rãi. 2.5.1.1 Thuật toán k-means Thuật toán phân hoạch K-means do MacQeen đề xuất trong lĩnh vực thống kê năm 1967, 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) ( k i 1, n ), sao cho hàm tiêu chuẩn: E 2 (x ) đạt giá trị tối thiểu. x D mi i 1 C i Trong đó:mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tƣợng. 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 vectơ 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 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 Nguyễn Văn Huy – CT1301 24
  25. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng hoặc các quan điểm của ngƣời dùng. Thuật toán k-means bao gồm các bƣớc cơ bản nhƣ sau: k InPut: Số cụm k và các trọng tâm cụm {mj} j=1 ; OutPut: Các cụm Ci (i 1, k ) và hàm tiêu chuẩn E đạt giá trị tối thiểu; Begin Bƣớc 1: Khởi tạo: k d Chọn k trọng tâm {mj} j=1 ban đầu trong không gian R (d là số chiều của dữ liệu) . Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm. Bƣớc 2: Tính toán khoảng cách: Đối với mỗi điểm Xi (1<=i<=n), tính toán khoảng cách của nó tới mỗi trọng tâm mj j=1,k. Và sau đó tìm trọng tâm gần nhất đối với mỗi điểm. Bƣớc 3: Cập nhật lại trọng tâm: Đối với mỗi j=1,k, cập nhật trọng tâm cụm mj bằng các xác định trung bình cộng của các vectơ đối tƣợng dữ liệu. Bƣớc 4: Điều kiện dừng Lặp các bƣớc 2 và 3 cho đến khi các trọng tâm của cụm không thay đối. End. Hình sau minh họa về một số hình dạng cụm dữ liệu khám phá đƣợc bởi k- means: Hình2.2: Hình dạng cụm dữ liệu khám phá được bởi k-means 2.5.1.2 Thuật toán CLARA CLARA (Clustering LARge Application) đƣợc Kaufman đề xuất năm 1990, thuật toán này nhằm khắc phục nhƣợc điểm của thuật toán PAM trong trƣờng hợp giá trị của k và n là lớn. CLARA tiến hành trích mẫu cho tập dữ liệu có n phần tử, nó áp dụng thuật toán PAM cho mẫu này và tìm ra các các đối tƣợng tâm medoid cho mẫu đƣợc trích từ dữ liệu này. Ngƣời ta thấy rằng, nếu mẫu dữ liệu đƣợc trích theo cách ngẫu nhiên, thì các medoid của nó xấp xỉ với các medoid của toàn bộ tập dữ liệu ban đầu. Để tiến tới một xấp xỉ tốt hơn, CLARA đƣa ra nhiều cách lấy mẫu và thực hiện phân cụm cho mỗi trƣờng hợp và tiến hành chọn kết quả phân cụm tốt Nguyễn Văn Huy – CT1301 25
  26. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng nhất khi thực hiện phân cụm trên các mẫu này. Để cho chính xác, chất lƣợng của các cụm đƣợc đánh giá thông độ phi tƣơng tự trung bình của toàn bộ các đối tƣợng dữ liệu trong tâp đối tƣợng ban đầu. Kết quả thực nghiệm chỉ ra rằng, 5 mẫu dữ liệu có kích thƣớc 40+2k cho các kết quả tốt. Các bƣớc thực hiện của thuật toán CLARA nhƣ hình sau: Bƣớc 1. Duyệt dãy i = 1 đến i= 5 Bƣớc 2. Lấy một mẫu có 40 + 2k đối tƣợng dữ liệu ngẫu nhiên từ tập dữ liệu và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối tƣợng medoid đại diện cho các cụm. Bƣớc 3. Đối với mỗi đối tƣợng Oj trong tập dữ liệu ban đầu, xác định đối tƣợng medoid tƣơng tự nhất trong số k đối tƣợng medoid. Bƣớc 4. Tính độ phi tƣơng tự trung bình cho phân hoạch các đối tƣợng dành ở bƣớc trƣớc, nếu giá trị này bé hơn giá trị tối thiểu hiện thời thì sử dụng giá trị này thay cho giá trị tối thiếu ở trạng thái trƣớc, nhƣ vậy, tập k đối tƣợng medoid xác định ở bƣớc này là tốt nhất cho đến thời điểm này. Bƣớc 5. Quay về bƣớc 1. Độ phức tạp tính toán của nó là O(k(40+k)2 + k(n-k)), và CLARA có thể thực hiện đối với tập dữ liệu lớn. Chú ý đối với kỹ thuật tạo mẫu trong PCDL: kết quả phân cụm có thể không phụ thuộc vào tập dữ liệu khởi tạo nhƣng nó chỉ đạt tối ƣu cục bộ. Thí dụ nhƣ: Nếu các đối tƣợng medoid của dữ liệu khởi tạo không nằm trong mẫu, khi đó kết quả thu đƣợc không đảm bảo là tốt nhất đƣợc. 2.5.1.4 Thuật toán CLARANS Thuật toán CLARANS nhằm để cải tiến cho chất lƣợng cũng nhƣ mở rộng áp dụng cho tập dữ liệu lớn. CLARANS cũng sử dụng các đối tƣợng trung tâm medoids làm đại diện cho các cụm dữ liệu. Ý tƣởng cơ bản của CLARANS là không xem xét tất cả các khả năng có thể thay thể các đối tƣợng tâm medoids bởi một đối tƣợng khác, nó ngay lập tức thay thế các đối tƣợng tâm này nếu việc thay thế này có tác động tốt đến chất lƣợng phân cụm chứ không cấn xác định cách thay thể tối ƣu nhất. Một phân hoạch cụm phát hiện đƣợc sau khi thay thế đối tƣợng trung tâm đƣợc gọi là một láng giềng (Neighbor) của phân hoạch cụm trƣớc đó. Số các láng giềng đƣợc hạn chế bởi tham số do ngƣời dùng đƣa vào là Maxneighbor, quá trình lựa chọn các láng giềng này là hoàn toàn ngẫu nhiên. Tham số Numlocal cho phép ngƣời dùng xác định số vòng lặp tối ƣu cục bộ đƣợc tìm kiếm. Không phải Nguyễn Văn Huy – CT1301 26
  27. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng tất các các láng giềng đƣợc duyệt mà chỉ có Maxneighbor số láng giềng đƣợc duyệt. Thuật toán chi tiết CLARANS nhƣ biểu diễn nhƣ sau: Input: O, k, dist, numlocal, and maxneighbor; Output: k cụm dữ liệu; CLARANS (int k, function dist, int numlocal, int maxneighbor) BEGIN for (i = 1; i <= numlocal; i++) { current.create_randomly(k); j = 1; while (j < maxneighbor) { current.select_randomly(old, new); diff = current.calculate_distance_difference(old, new); if (diff < 0) { current.exchange(old, new); j = 1; } else j++; // end if } // end while dist = current.calculate_total_distance(); if (dist < smallest_dist) { best = current; smallest_dist = dist; } // end if } // end for END; Trong đó: Create_Randomly(k): tạo ngẫu nhiên k cụm dữ liệu, nghĩa là thuật toán lựa chọn ngẫu nhiên k đối tƣợng medoid từ n đối tƣợng dữ liệu. Select_randomly(old, new): Thay thế một đối tƣợng tâm cụm medoid old bởi đối tƣợng khác new. Calculate_distance_difference(old, new): Tính toán sự khác nhau về tổng khoảng cách giữa phân hoạch hiện thời và láng giềng của nó. Exchange(old, new): Hoán đối giữa đối tƣợng tâm cụm medoid old với đối tƣợng không phải là medoid new, sau khi hoán đổi vai trò của chúng cũng đƣợc hoán đổi. Calculate_total_distance(): Tính tổng khoảng cách cho mỗi phân hoạch. Nguyễn Văn Huy – CT1301 27
  28. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Nhƣ vậy, quá trình hoạt động của CLARANS tƣơng tự với quá trình hoạt động của thuật toán CLARA. Tuy nhiên, ở giai đoạn lựa chọn các trung tâm medoid của cụm dữ liệu, CLARANS lựa chọn một giải pháp tốt hơn bằng cách lấy ngẫu nhiên một đối tƣợng của k đối tƣợng trung tâm medoid của cụm và cố gắng thay thế nó với một đối tƣợng đƣợc chọn ngẫu nhiên trong (n-k) đối tƣợng còn lại, nếu không có giải pháp nào tốt hơn sau một số cố gắng lựa chọn ngẫu nhiên xác định, thuật toán dùng và cho kết quả phân cụm tối ƣu cục bộ. 2.5.2 Các thuật toán phân cụm phân cấp 2.5.2.1 Thuật toán BIRCH 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, BRICH 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). Hình dƣới đây biểu thị một ví dụ về cây CF. Hình 2.3: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ó Nguyễn Văn Huy – CT1301 28
  29. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 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, và . 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 CSDL 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 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 hai: BIRCH lựa chọn một thuật toán PCDL ( nhƣ thuật toán phân cụm phân hoạch chẳng hạn ) để thực hiện PCDL cho các nút lá của cây. Tƣ tƣởng thuật toán BIRCH đƣợc minh họa nhƣ sau: 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. 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. Nguyễn Văn Huy – CT1301 29
  30. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 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. 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 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. 2.5.2.2 Thuật toán CURE Việc chọn một cách biểu diễn cho các cụm có thể nâng cao chất lƣợng phân cụm. Thuật toán CURE (Clustering Using REpresentatives) là thuật toán sử dụng chiến lƣợc dƣới lên (Bottom up) của kỹ thuật phân cụm phân cấp.CURE sử dụng nhiều đối tƣợng để diễn tả cho mỗi cụm dữ liệu. Các đối tƣợng đại diện cho cụm này ban đầu đƣợc lựa chọn rải rác đều ở các vị trí khác nhau, sau đó chúng đƣợc di chuyển bằng cách co lại theo một tỉ lệ nhất định. Tại mỗi bƣớc của thuật toán, hai cụm có cặp đối tƣợng đại diện gần nhất (đối tƣợng thuộc về mỗi cụm) sẽ đƣợc trộn lại thành một cụm. Với cách thức sử dụng nhiều hơn một điểm đại diện cho các cụm, CURE có thể khám phá đƣợc các cụm có các dạng hình thù và kích thƣớc khác nhau trong CSDL lớn. Việc co các đối tƣợng đại diện lại có tác dụng làm giảm tác động của các phần tử ngoại lai, vì vậy, CURE có khả năng xử lý đối với các phần tử ngoại lai. Hình 17 dƣới đây là thí dụ về các dạng và kích thƣớc cụm dữ liệu đƣợc khám phá bởi CURE: Hình 2.4:Các cụm dữ liệu được khám phá bởi CURE Nguyễn Văn Huy – CT1301 30
  31. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Để áp dụng với CSDL lớn, CURE sử dụng lấy mẫu ngẫu nhiên và phân hoạch. Mẫu dữ liệu đƣợc xác định ngẫu nhiên là phân hoạch đầu tiên, CURE tiến hành phân cụm trên mỗi phân hoạch. Quá trình này lặp lại cho đến khi ta thu đƣợc phân hoạch đủ tốt. Các cụm thu đƣợc sau đó lại đƣợc phân cụm nhằm để thu đƣợc các cụm con cần quan tâm. Thuật toán CURE đƣợc thực hiện qua các bƣớc cơ bản nhƣ sau: 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu; 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thƣớc bằng nhau: Ý tƣởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thƣớc của mỗi phân hoạch là n'/p (n' là kích thƣớc của mẫu) ; 3. Phân cụm các điểm của mỗi nhóm: chúng ta thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm đƣợc phân thành n'/pq cụm (với q>1); 4. Loại bỏ các phần tử ngoại lai: Trƣớc hết, khi các cụm đƣợc hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trƣờng hợp các phần tử ngoại lai đƣợc lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thụât toán sẽ tự động loại bỏ các nhóm nhỏ. 5. Phân cụm các cụm không gian: Các đối tƣợng đại diện cho các cụm di chuyển về hƣớng trung tâm cụm, nghĩa là chúng đƣợc thay thế bởi các đối tƣợng gần trung tâm hơn. 6. Đánh dấu dữ liệu với các nhãn tƣơng ứng Độ phức tạp tính toán của thuật toán CURE là O(n2log(n)). CURE là thụât toán tin cậy trong việc khám phá các cụm với hình thù bất kỳ và có thể áp dụng tốt đối trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số nhƣ là tham số các đối tƣợng đại diện, tham số co của các phần tử đại diện. Nhìn chung thì BIRCH tốt hơn so với CURE về độ phức tạp, nhung kém về chất lƣợng phân cụm. Các hai thuật toán này có thể xử lý các phần tử ngoại lai tốt. 2.5.3 Các thuật toán phân cụm dựa trên mật độ Các cụm có thể đƣợc xem nhƣ các vùng có mật độ cao, đƣợc tách ra bởi các vùng không có hoặc ít mật độ. Khái niệm mật độ ở đây đƣợc xem nhƣ là các số các đối tƣợng láng giềng. Nguyễn Văn Huy – CT1301 31
  32. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2.5.3.1 Thuật toán DBSCAN Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN (Density - Based Spatial Clustering of Applications with noise). Thuật toán đi tìm các đối tƣợng mà có số đối tƣợng láng giềng lớn hơn một ngƣỡng tối thiểu. Tìm tất cả các đối tƣợng mà các láng giềng của nó thuộc về lớp các đối tƣợng đã xác định ở trên, một cụm đƣợc xác định bằng một tập tất cả các đối tƣợng liên thông mật độ với các láng giềng của nó. DBSCAN có thể tìm ra các các cụm với hình thù bất kỳ, trong khi đó tại cùng một thời điểm ít bị ảnh hƣởng bởi thứ tự của các đối dữ liệu nhập vào. Khi có một đối tƣợng đƣợc chèn vào chỉ tác động đến một láng giềng xác định. Mặt khác, DBSCAN yêu cầu ngƣời dùng xác định bán kính Eps của các láng giềng và số các láng giềng tối thiểu Minpts, các tham số này khó mà xác định đƣợc tối ƣu, thông thƣờng nó đƣợc xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm. Ngƣời ta áp dụng chỉ số không gian để giúp xác định các láng giềng của một đối tƣợng dữ liệu do vậy độ phức tạp của DBSCAN đã đƣợc cải tiến là O(nlogn) so với dộ phức tạp của DBSCAN là O(n2) trong trƣờng hợp nếu không áp dụng cấu trúc chỉ số. Khoảng cách Euclide đƣợc sử dụng để đo sự tƣơng tự giữa các đối tƣợng nhƣng không hiệu quả đối với dữ liệu đa chiều. { Mô đun chƣơng trình chính } SetOfPoints.changeClIds(seeds,ClId); DBSCAN (SetOfPoints, Eps, MinPts) seeds.delete(Point); // SetOfPoints is UNCLASSIFIED WHILE seeds = MinPts THEN IF ExpandCluster(SetOfPoints, Point, FOR i FROM 1 TO result.size DO ClusterId, Eps, MinPts) THEN resultP:= result.get(i); ClusterId:= nextId(ClusterId) IF resultP.ClId END IF IN {UNCLASSIFIED, NOISE} THEN END IF IF resultP.ClId = UNCLASSIFIED THEN Nguyễn Văn Huy – CT1301 32
  33. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng END FOR seeds.append(resultP); END; // DBSCAN END IF; { Thủ tục Expand } SetOfPoints.changeClId(resultP,ClId); ExpandCluster(SetOfPoints, Point, ClId, Eps, END IF; // UNCLASSIFIED or NOISE MinPts): Boolean; END FOR; seeds:=SetOfPoints.regionQuery(Point,Eps); END IF; // result.size >= MinPts IF seeds.size Empty RETURN False; RETURN True; ELSE // all points in seeds are density- END IF // reachable from Point END; // ExpandCluster { End } 2.5.3.2 Thuật toán OPTICS Đây là thuật toán mở rộng cho thuật toán DBSCAN, bằng cách giảm bớt các tham số đầu vào. OPTICS (Ordering Points To Identify the Clustering Structure) sắp xếp các cụm theo thứ tự tăng dần nhằm tự động phân cụm dữ liệu. Thứ Chƣa đánh dấu tự này diễn tả cấu trúc dữ liệu phân cụm dựa trên mật độ chứa thông tin Khoảng cách đến tƣơng đƣơng với phân cụm dựa trên đƣợc mật độ mật độ với một dãy các tham số đầu vào. OPTICS xem xét bán kính tối thiểu nhằm xác định các láng giềng Thƣ tự của các cụm dữ liệu phù hợp với thuật toán. DBSCAN và OPTICS tƣơng tự với nhau về cấu trúc và có cùng độ phức tạp: O(nLogn) (N là Hình 2.5: Hình minh họa phân cụm OPTICS kích thƣớc của tập dữ liệu). Nguyễn Văn Huy – CT1301 33
  34. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2.5.3.3. Thuật toán DENCLUE DENCLUE (DENsity - Based CLUstEring) là thuật toán PCDL dựa trên một tập các hàm phân phối mật độ. Ý tƣởng chính của thuật toán này nhƣ sau: . Sự tác động của một đối tƣợng tới láng giềng của nó đƣợc xác định bởi hàm ảnh hƣởng (Influence Function). . Mật độ toàn cục của không gian các đối tƣợng đƣợc mô hình nhƣ là tổng tất cả các hàm ảnh hƣởng của các đối tƣợng. . Các cụm đƣợc xác định bởi các đối tƣợng mật độ cao (density attactors), các đối tƣợng nàylà các điểm cực đại của hàm mật độ toàn cục. Tập Phân cụm Hìnhdữ li 2.6ệu :Hình minh họa DENCLUEvới Gauss với hàm phân phối Gaussian Chúng ta thấy rằng, DENCLUE phụ thuộc nhiều vào ngƣỡng nhiễu  (Noise Threshold) và tham số mật độ  , nhƣng DENCLUE có các ƣu điểm sau: . Có cơ sở toán học vững chắc . Có khả năng xử lý các phần tử ngoại lai. . Cho phép khám phá ra các cụm với hình thù bất kỳ ngay cả đối với các dữ liệu đa chiều Độ phức tạp tính toán của DENCLUE là O(nlogn). Các thuật toán dựa trên mật độ không thực hiện kỹ thuật phân mẫu trên tập dữ liệu nhƣ trong các thụât toán phân cụm phân hoạch, vì điều này có thể làm tăng thêm độ phức tạp do có sự khác nhau giữa mật độ của các đối tƣợng trong mẫu với mật độ của toàn bộ dữ liệu. Nguyễn Văn Huy – CT1301 34
  35. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 3: HỆ THỐNG ĐÁNH GIÁ THÔNG TIN SẢN PHẨM Trong chƣơng này, khóa luận trình bày mô tả về bài toán, bản phân tích thiết kế bài toán. Sau đó tiến hành cài đặt chƣơng trình sử dụng công cụ visual studio 2010 bằng ngôn ngữ lập trình C#. Sau khi cài đặt chƣơng trình ta sẽ đánh giá thử nghiệm hệ thống có phù hợp với yêu cầu hay không. 3.1 Phát biểu bài toán Một phần mềm cho phép ngƣời dùng đăng nhập vào để tìm kiếm thông tin về một sản phẩm đƣợc mô tả cụ thể nhƣ sau: Hệ thống cho phép ngƣời dùng nhập thông tin về sản phẩm cần tìm. + Thông tin về sản phẩm: Sản phẩm đƣợc phân chia làm nhiều nhóm sản phẩm,mỗi nhóm sản phẩm có nhiều loại sản phẩm. Thông tin nhóm sản phẩm miêu tả nhƣ sau: Mã nhóm sản phẩm, Tên nhóm sản phẩm. Thông tin về loại sản phẩm: Mã loại sản phẩm, Tên loại sản phẩm. Trong loại sản phẩmthì có nhiều sản phẩm. Thông tin về sản phẩmgồm có: Mã sản phẩm, Tên sản phẩm. Khi ngƣời dùng đăng nhập vào hệ thông thì kê khai sản phẩm mà mình cần tìm kiếm. Thông tin sản phẩm gồm có: Mã sản phẩm Tên sản phẩm Mô tả hoạt động của hệ thống: Ngƣời dùng đăng nhập vào hệ thống để nhập thông tin sản phẩm cần tìm kiếm. Nguyễn Văn Huy – CT1301 35
  36. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hệ thống cung cấp chức năng tụ động tìm kiếm sản phẩm trên mạng Internet thông qua các máy tìm kiếm. Hệ thống có giao diện hợp lý, thuận lợi cho ngƣời dùng. Có báo cáo kết quả tìm kiếm. 3.2 Xác định mô hình nghiệp vụ 3.2.1 Các chức năng nghiệp vụ Ta có thể xác định các chức năng nghiệp vụ hệ thống nhƣ sau: Tham chiếu Chức năng R1 Cập nhật các danh mục R11 Cập nhật thông tin nhóm sản phẩm R12 Cập nhật thông tin loại sản phẩm R13 Cập nhật thông tin sản phẩm R14 Cập nhật thông tin Search Engine R15 Cập nhật thông số tìm kiếm R2 Tìm kiếm R3 Báo cáo Bảng 3.1: Bảng xác định các chức năng nghiệp vụ của hệ thống Các tác nhân hệ thống Tác nhân là một bộ phận bên ngoài hệ thống nhƣng có tƣơng tác với hệ thống. Nó chính là đối tƣợng mà hệ thống phục vụ hoặc cần cung cấp dữ liệu. Hệ thống gồm các tác nhân sau: Nguyễn Văn Huy – CT1301 36
  37. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Tác nhân Vai trò Ngƣời dùng Là một tổ chức hoặc cá nhân đăng nhập vào hệ thống Máy tìm kiếm Là máy tìm kiếm trên mạng. Cụ thể là Google. Bảng 3.2: Bảng xác định tác nhân của hệ thống. 3.2.2 Biểu đồ Use Case tổng quan Hình 3.1: Biểu đồ Use Case tổng quan Chƣơng trình thử nghiệm tìm kiếm xác định đƣợc các ca sử dụng và tác nhân nhƣ sau: Nguyễn Văn Huy – CT1301 37
  38. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Gói ca sử dụng Các ca sử dụng chi tiết Tác nhân 1.Cập nhật UC1. Cập nhật thông tin nhóm sản phẩm UC2. Cập nhật thông tin loại sản phẩm Ngƣời dùng UC3. Cập nhật thông tin sản phẩm UC4.Cập nhật thông tin Search Engine UC5. Cập nhật thông số tìm kiếm 2.Tìm kiếm UC6. Tìm kiếm Ngƣời dùng Máy tìm kiếm 3.Báo cáo UC7. Lập báo cáo Ngƣời dùng Bảng 3.3: Bảng mô tả các ca sử dụng và tác nhân 3.2.3 Mô tả khái quát các hệ con Hệ thống gồm ba hệ con: Cập nhật: Có tác nhân là ngƣời dùng. Có tác dụng cập nhật các thông tin đầu vào nhƣ: Nhóm sản phẩm, loại sản phẩm, sản phẩm, thông tin tìm kiếm. Tìm kiếm: có tác nhân là máy tìm kiếm. Máy tìm kiếm nhận lệnh từ hệ thống và trả lại các kết quả tìm kiếm là các đƣờng link Báo cáo: Có các tác nhân là ngƣời dùng. Có tác dụng lập báo cáo và in báo cáo về các kết quả tìm kiếm, đánh giá. Nguyễn Văn Huy – CT1301 38
  39. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.2.4 Các mô hình ca sử dụng chi tiết 3.2.4.1 Gói ca sử dụng “Cập nhật” Hình 3.2: Biểu đồ ca sử dụng gói “Cập nhật” + Mô tả chi tiết ca sử dụng Ca sử dụng “Cập nhật nhóm sản phẩm” Tên ca sử dụng Cập nhật nhóm sản phẩm Tác nhân Ngƣời dùng Mục đích Cập nhật nhóm sản phẩm Mô tả khái quát Ngƣời dùng cập nhật thông tin các nhóm sản phẩm Các tham chiếu R11 Bảng 3.4: Bảng mô tả ca sử dụng cập nhật nhóm sản phẩm Nguyễn Văn Huy – CT1301 39
  40. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ca sử dụng “Cập nhật loại sản phẩm” Tên ca sử dụng Cập nhật loại sản phẩm Tác nhân Ngƣời dùng Mục đích Cập nhật loại sản phẩm Mô tả khái quát Ngƣời dùng cập nhật thông tin loại sản phẩm Các tham chiếu R12 Bảng 3.5: Bảng mô tả ca sử dụng cập nhật loại sản phẩm Ca sử dụng “Cập nhật sản phẩm” Tên ca sử dụng Cập nhật sản phẩm Tác nhân Ngƣời dùng Mục đích Cập nhật sản phẩm Mô tả khái quát Ngƣời dùng cập nhật thông tin các sản phẩm Các tham chiếu R13 Bảng 3.6: Bảng mô tả ca sử dụng cập nhật sản phẩm Nguyễn Văn Huy – CT1301 40
  41. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ca sử dụng “Cập nhật search engine” Tên ca sử dụng Cập nhật search engine Tác nhân Ngƣời dùng Mục đích Cập nhật search engine Mô tả khái quát Ngƣời dùng cập nhật thông tin các search engine Các tham chiếu R14 Bảng 3.7: Bảng mô tả ca sử dụng câp nhật Search Engine Ca sử dụng “Cập nhật thông số tìm kiếm” Tên ca sử dụng Cập nhật thông số tìm kiếm Tác nhân Ngƣời dùng Mục đích Cập nhật các thông số cho việc tìm kiếm Ngƣời dùng cập nhạt các thông số giúp cho việc Mô tả khái quát tìm kiếm đạt kết quả mong muốn Các tham chiếu R15 Bảng 3.8: Bảng mô tả ca sử dụng cập nhật thông số tìm kiếm Nguyễn Văn Huy – CT1301 41
  42. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.2.4.2 Gói ca sử dụng “Tìm kiếm” Hình 3.3: Biểu đồ ca sử dụng gói “Tìm kiếm” + Mô tả chi tiết ca sử dụng Ca sử dụng “Tìm kiếm” Tên ca sử dụng Nhận lệnh tìm kiếm Tác nhân Máy tìm kiếm, ngƣời dùng Mục đích Tìm kiếm thông tin Mô tả khái quát Máy tìm kiếm nhận các lệnh tìm kiếm và tiến hành tìm kiếm trên Internet Các tham chiếu R2 Bảng 3.9: Bảng mô tả ca sử dụng tìm kiếm Nguyễn Văn Huy – CT1301 42
  43. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.2.4.3 Gói ca sử dụng “Báo cáo” Hình 3.4: Biểu đồ ca sử dụng gói “Báo cáo” + Mô tả chi tiết ca sử dụng Ca sử dụng “Báo cáo” Tên ca sử dụng Lập báo cáo Tác nhân Ngƣời dùng Mục đích Tổng hợp các kết quả tìm kiếm, tạo báo cáo Mô tả khái quát Hệ thống tổng hợp các kết quả tìm kiếm, tạo báo cáo cho ngƣời dùng Các tham chiếu R3 Bảng 3.10: Bảng mô tả ca sử dụng báo cáo 3.3 Phân tích hệ thống 3.3.2 Phân tích gói ca sử dụng “Cập nhật các danh mục” 3.3.2.1 Ca sử dụng “Cập nhật nhóm sản phẩm” Biểu đồ tuần tự thực thi ca sử dụng Nguyễn Văn Huy – CT1301 43
  44. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 3.5: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật nhóm sản phẩm” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.6: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật nhóm sản phẩm” Nguyễn Văn Huy – CT1301 44
  45. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.3.2.2 Ca sử dụng “Cập nhật loại sản phẩm” Biểu đồ tuần tự thực thi ca sử dụng Hình 3.7: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật loạisản phẩm” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.8: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật loạisản phẩm” 3.3.2.3 Ca sử dụng “Cập nhật sản phẩm” Biểu đồ tuần tự thực thi ca sử dụng Nguyễn Văn Huy – CT1301 45
  46. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 3.9: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật sản phẩm” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.10: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật sản phẩm” Nguyễn Văn Huy – CT1301 46
  47. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.3.2.4 Ca sử dụng “Cập nhật Search engine” Biểu đồ tuần tự thực thi ca sử dụng Hình 3.11: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật Search Engine” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.12: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật Search Engine” Nguyễn Văn Huy – CT1301 47
  48. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.3.2.5 Ca sử dụng “Cập nhật thông số tìm kiếm” Biểu đồ tuần tự thực thi ca sử dụng Hình 3.13: Biểu đồ tuần tự thực thi ca sử dụng “Cập nhật thông số tìm kiếm” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.14: Biểu đồ cộng tác thực thi ca sử dụng “Cập nhật thông số tìm kiếm” Nguyễn Văn Huy – CT1301 48
  49. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.3.2.6 Mô hình phân tích gói ca sử dụng “Cập nhật” Hình 3.15: Mô hình phân tích gói ca “Cập nhật” 3.3.3 Phân tích gói ca sử dụng “Tìm kiếm” 3.3.3.1 Ca sử dụng “Nhận lệnh tìm kiếm” Biểu đồ tuần tự thực thi ca sử dụng Hình 3.16: Biểu đồ tuần tự thực thi ca sử dụng “Tìm kiếm” Nguyễn Văn Huy – CT1301 49
  50. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Biểu đồ cộng tác thực thi ca sử dụng Hình 3.17: Biểu đồ cộng tác thực thi ca sử dụng “Tìm kiếm” 3.3.3.2 Mô hình phân tích gói ca sử dụng “Tìm kiếm” Hình 3.18: Mô hình phân tích gói ca”Tìm kiếm” Nguyễn Văn Huy – CT1301 50
  51. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.3.4 Phân tích gói ca sử dụng “Báo cáo” 3.3.4.1 Ca sử dụng “Lập báo cáo” Biểu đồ tuần tự thực thi ca sử dụng Hình 3.19: Biểu đồ tuần tự thực thi ca sử dụng “Lập báo cáo” Biểu đồ cộng tác thực thi ca sử dụng Hình 3.20: Biểu đồ cộng tác thực thi ca sử dụng “Báo cáo” 3.3.4.2 Mô hình phân tích gói ca sử dụng “Báo cáo” Hình 3.21: Mô hình phân tích gói ca”Báo cáo” Nguyễn Văn Huy – CT1301 51
  52. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.4 Thiết kế hệ thống Hình 3.22: Mô hình lớp thiết kế hệ thống Nguyễn Văn Huy – CT1301 52
  53. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.5 Thiết kế chƣơng trình Chƣơng trình viết bằng ngôn ngữ lập trình C# Chƣơng trình sử dụng hệ quản trị cơ sở dũ liệu SQL 2008. 3.5.1 Giao diện chính của chƣơng trình Hình 3.23 Giao diện chính của chương trình Giao diện cung cấp thông tin của chƣơng trình và menu thực hiện công việc. 3.5.2 Giao diện cập nhật sản phẩm Hình 3.24: Giao diện cập nhật sản phẩm Giao diện này đƣợc mở từ menu “Sản phẩm” trên giao diện chính. Nguyễn Văn Huy – CT1301 53
  54. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Khi cập nhật sản phẩm cần chọn tên nhóm từ ô “tên nhóm”, tên loại sản phẩm từ ô “tên loại”, nhập tên sản phẩm vào ô “tên sản phẩm”, nhập đặc điểm sản phẩm vào ô “đặc điểm”. Nút “lƣu” để lƣu thông tin. Nhấn nút “thêm” để nhập sản phẩm mới. Nhấn chuột phải vào loại sản phẩm , chọn “Xóa” nếu muốn xóa sản phẩm, chọn “Sửa” nếu muốn sửa sản phẩm 3.5.3 Giao diện cập nhật loại sản phẩm Hình 3.25: Giao diện cập nhật loại sản phẩm Giao diện này đƣợc gọi từ menu “Loại sản phẩm ” trên giao diện chính. Khi cập nhật loại sản phẩm cần chọn tên nhóm sản phẩm từ ô “tên nhóm”, nhập tên loại sản phẩm vào ô “loại sản phẩm”. Nhấn nút “Lƣu” để lƣu thông tin. Nút thêm để thêm một loại mới. Nhấn chuột phải vào loại sản phẩm , chọn “Xóa” nếu muốn xóa nhóm sản phẩm, chọn “Sửa” nếu muốn sửa loại sản phẩm Nguyễn Văn Huy – CT1301 54
  55. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.5.4 Giao diện cập nhật nhóm sản phẩm Hình 3.26: Giao diện cập nhật nhóm sản phẩm Giao diện này đƣợc gọi từ menu “Nhóm SP” từ giao diện chính. Khi cập nhật nhóm sản phẩm cần nhập tên nhóm vào ô “tên nhóm”. Nút lƣu để lƣu thông tin. Nhấn nút “Thêm” để thêm nhóm mới. Nhấn chuột phải vào nhóm sản phẩm , chọn “Xóa” nếu muốn xóa nhóm sản phẩm, chọn “Sửa” nếu muốn sửa nhóm sản phẩm Nguyễn Văn Huy – CT1301 55
  56. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.5.5 Giao diện tìm kiếm thông tin sản phẩm Hình 3.27: Giao diện tìm kiếm thông tin sản phẩm Ô “Số KQ Google” dung để nhập số kết quả tìm kiếm mong muốn. Chọn nhóm sản phẩm từ ô “Tên nhóm”, chọn tên loại sản phẩm từ ô “Tên loại”, chọn sản phẩm từ ô “Tên sản phẩm”, tích chọn đặc điểm trong ô đặc điểm. Nút “ ” để sửa sản phẩm đã chọn. Nhấn “Tim kiếm” để bắt đâu tìm kiếm. Chọn chuỗi tìm kiếm trong ô “Chuỗi tìm kiếm”, nhấn nút “Thống kê” để xem kết quả thống kê cho chuỗi tìm kiếm. Nút “Thoát” để thoát khỏi giao diện này trở về giao diện chính 3.5.6 Kết quả của chƣơng trình minh họa - Chƣơng trình đã giải quyết đƣợc vấn đề cơ bản mà bài toán đƣa ra là tìm kiếm đƣợc các đánh giá vế sản phẩm trên web. - Chƣơng trình đã xây dựng đƣợc các chức năng cơ bản mà bài toán đƣa ra Cập nhật, thêm mới, xóa lƣu các thông tin về sản phẩm, chuỗi tìm kiếm, kết quả tìm kiếm Cho phép tìm kiếm các đánh giá tự động Có chức năng hiển thị số lƣợng các đánh giá. Nguyễn Văn Huy – CT1301 56
  57. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng KẾT LUẬN Đề tài tìm kiếm thông tin sản phẩm trên Web là một công việc rất thú vị. Nó thể hiện rất rõ việc áp dụng công nghệ thông tin vào các lĩnh vực khác sẽ đem lại kết quả cao. Khóa luận đã đạt một số kết quả nhƣ sau: 1. Trình bày các khái niệm cơ bản trong lĩnh vực khai phá dữ liệu từ đó giúp cho việc hiểu rõ bài toán cần đƣợc giải quyết nhƣ thế nào. 2. Khóa luận tổng hợp một số thuật toán liên quan đến lĩnh vực khai phá dữ liệu. và phân tích,thiết kế, xây dựng chƣơng trình minh họa ứng dụng tìm kiếm thông tin sản phẩm trên Web, nhằm giúp các nhà quản lý ra quyết định tốt hơn về sản phẩm hoặc nhóm sản phẩm họ định triển khai trên thị trƣờng. Với cách trình bày từ khái niệm cơ bản đến cách thức xây dựng hệ thống tìm kiếm thông tin sản phẩm trên Web đã giúp cho em bổ sung nhiều kiến thức liên quan đến thực tế nghề nghiệp. Nguyễn Văn Huy – CT1301 57
  58. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng TÀI LIỆU THAM KHẢO Tiếng Việt [1]. Hà Quang Thụy, Phan Xuân Hiếu - Đoàn Sơn - Nguyên Trí Thành Nguyễn Thu Trang - Nguyễn Cầm Tú, Giáo trình khai phá dữ liệu web, NXBGDVN, 2009, 313 tr. [2] Lê Văn Phùng, Quách Xuân Trƣởng, Khai phá dữ liệu, NXB TT-TT, 2012, 320 tr. Tiếng Anh [3] W. Bruce Croft,Donald Metzler,Trevor Strohman, Search Engines: Information Retrieval in Practice,Addison-Wesley, 2008,524p. [4] Alan Rea, Data Mining – An Introduction. The Parallel Computer Centre, Nor of The Queen’s University of Belfast, 1995. [5] Jiawei Han and Micheline Kamber, Data Mining:Concepts andTechniques, Hacours Science and Technology Company, USA, 2005. [6] Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, and Ramasamy Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press- The MIT Press, 1996. [7] Jiawei Han and Micheline Kamber (2001), Data Mining: Concepts and Techniques, Hacours Science and Technology Company, USA. [8] J.Han, M.Kamber and A.K.H. Tung (2002), Spatial Clustering Methods in Data mining: A Survey, Simon Fraster University, Canada. Nguyễn Văn Huy – CT1301 58