MỞ ĐẦU Trong những năm ngành công nghệ thông tin đã có những bƣớc phát triển chóng mặt. Do việc ứng dụng công nghệ thông tin vào hầu hết các lĩnh vực trong đời sống nhƣ: giáo dục, văn hóa, kinh tế, giải trí,… và sự tăng nhanh về số lƣợng ngƣời dùng Intenet trên toàn cầu. Đẫn đến việc bùng nổ, sự cập nhật nhanh chóng, liên tục của kh8 dữ liệu số đã đặt ra thách thức về việc khai thác,sử lý thông tin từ kho dữ liệu khổng lồ thành các tri thức có ích một cách nhanh chóng để phục vụ cho việc quản lý, hoạt động kinh doanh,… Để đáp ứng yêu cầu này ngƣời ta đã xây dựng các công cụ tìm kiếm và xử lý thông tin để giúp ngƣời dùng tìm kiếm đƣợc các thông tin cần thiết, nhƣng so với sự rộng lớn về nguồn tài nguyên Web thì dẫn đến sự khó khăn với những kết quả tìm đƣợc. Với các phƣơng pháp khai thác cơ sở dữ liệu truyền thống chƣa đáp ứng đƣợc đầu đủ các yêu cầu từ ngƣời dùng.
Vì vậy một hƣớng đi mới đó là nghiên cứu và áp dụng kỹ thuật khai phá dữ liệu và khám phá tri thức trong môi trƣờng Web. Do đó, việc nghiên cứu các mô hình dữ pháp khai liệu mới và áp dụng các phƣơng phá dữ liệu trong khai phá tài nguyên Web là một xu thế tất yếu vừa có ý nghĩa khoa học vừa mang ý nghĩa thực tiễn cao. Vì vậy, em chọn đề tài đồ án tốt nghiệp “Kết hợp các phƣơng pháp phân cụm trong khai phá dữ liệu Web”. Bố cục đồ án gồm 3 chƣơng: Chƣơng 1: Trình bày các kiến thức cơ bản về khám phá tri thức, khai phá dữ liệu, một số vấn đề về biểu diễn và xử lý dữ liệu văn bản áp dụng trong khai phá dữ liệu.
Chƣơng 2 : Giới thiệu một số thuật toán phân cụm dữ liệu phổ biến và thƣờng đƣợc sử dụng trong lĩnh vực khai phá dữ liệu Web. Chƣơng 3: Trình bày khai phá nội dung Web và tiếp cận theo hƣớng sử dụng các kỹ thuật phân cụm dữ liệu để giải quyết bài toán khai phá dữ liệu Web. Trong phần này cũng trình bày một mô hình áp dụng kỹ thuật phân cụm dữ liệu trong tìm kiếm và phân cụm tài liệu Web. Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 7 CHƢƠNG 1: GIỚI THIỆU VỀ KH I PHÁ LIỆU WEB 1.1 Khai phá dữ liệu và khai phá tri thức 1.1 Khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực mới đƣợc nghiên cứu, nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp,….
từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học cùng những ứng dụng thành công trong KDD cho thấy KPDL là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, đồng thời có ƣu thế hơn hẳn so với các công cụ tìm kiếm phân tích dữ liệu truyền thống. Hiện nay, KPDL đã ứng dụng ngày càng rộng rãi trong các lĩnh vực nhƣ thƣơng mại, tài chính, y học, viễn thông, tin – sinh… Nhƣ vậy, Khai phá dữ liệu là quá trình khai phá, trích xuất, khai thác và sử dụng những dữ liệu có giá trị tiềm ẩn từ bên trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các cơ sở dữ liệu (CSDL), kho dữ liệu, trung tâm dữ liệu… 1.2 Quá trình khám phá tri thức Quá trình khá phá tri thức có thể chia thành 5 bƣớc nhƣ sau [1]: Đánh giá, Trích chọn Biến đổi biểu diễn Dữ liệu Dữ liệu Dữ liệu Các mẫu Tri Dữ liệu lựa chọn tiền xử lý biến đổi thức thô Khai phá Tiền xử lý Hình 1-1: Quy trình khai phá tri thức Quá trình KPDL có thể phân thành các giai đoạn sau: Trích chọn dữ liệu: Đây là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định. Tiền xử lý dữ liệu: Đây là bƣớc làm sạch dữ liệu (loại bỏ dữ liệu không đúng,xử lý dữ liệu thiếu sót,.), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phƣơng pháp nén dữ liệu, sử dụng histograms, lấy mẫu,.), rời rạc hóa dữ liệu (rời rạc hóa dựa Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 8 vào histograms, entropy,.
Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hóa. Biến đổi dữ liệu: Đây là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về cùng một kiểu, dạng thuận lợi nhất nhằm phục vụ quá trình xử lý ở bƣớc sau. Khai phá dữ liệu: Đây là bƣớc áp dụng những kỹ thuật phân tích (nhƣ các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn đƣợc những mẫu dữ liệu, những mối liên hệ đặc biệt trong dữ liệu. Đây đƣợc xem là bƣớc quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc biến đổi và biểu diễn ở một dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,. Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định.3 Khai phá dữ liệu v các l nh vực li n qu n KPDL là một lĩnh vực liên quan tới thống kê, học máy, CSDL, thuật toán, tính toán song song, thu nhận tri thức từ hệ chuyên gia và dữ liệu trừu tƣợng. Đặc trƣng của hệ thống khám phá tri thức là nhờ vào các phƣơng pháp, thuật toán và kỹ thuật từ những lĩnh vực khác nhau để KPDL. Với lĩnh vực học máy và nhận dạng mẫu thì KDD nghiên cứu các lý thuyết và thuật toán của hệ thống để trích ra các mẫu và mô hình từ dữ liệu lớn.
KDD tập trung vào việc mở rộng các lý thuyết và thuật toán cho các vấn đề tìm ra các mẫu đặc biệt (hữu ích hoặc có thể rút ra tri thức quan trọng) trong CSDL lớn. Với lĩnh vực thống kê, hệ thống KDD thƣờng gắn những thủ tục thống kê cho mô hình dữ liệu, đặc biệt là trong lĩnh vực thăm dò (Exploratory Data Analysis - EDA).4 Các kỹ thuật áp dụng trong khai phá dữ liệu Căn cứ vào các bài toán cần giải quyết thì KPDL gồm các kỹ thuật sau [5]: Phân lớp và dự báo: Xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ nhƣ phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định, mạng nơron nhân tạo,.
Phân lớp và dự báo còn đƣợc gọi là học có giám sát. Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nữ giới vào siêu thị nếu mua phấn thì có tới 80% trong số họ sẽ mua thêm son”. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trƣờng chứng khoán,.
Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 9 Phân tích chuỗi theo thời gian: Tƣơng tự nhƣ khai phá luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán vì nó có tính dự báo cao. Phân cụm: Xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên. Phân cụm còn đƣợc gọi là học không có giám sát.
Mô tả và tóm tắt khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khái niệm, ví dụ nhƣ tóm tắt văn bản.5 Những chức năng chính của khai phá dữ liệu KPDL có hai mục tiêu chính là: mô tả và dự báo. Dự báo là dùng một số biến hoặc trƣờng trong CSDL để dự đoán ra các giá trị chƣa biết hoặc sẽ có của các biến quan trọng khác. Việc mô tả tập trung vào tìm kiếm các mẫu mà con ngƣời có thể hiểu đƣợc để mô tả dữ liệu. Trong lĩnh vực KDD, mô tả đƣợc quan tâm nhiều hơn dự báo, nó ngƣợc với các ứng dụng học máy và nhận dạng mẫu mà trong đó việc dự báo thƣờng là mục tiêu chính.
Trên cơ sở mục tiêu chính của KPDL, các chức năng chính của KDD gồm [1]: Mô tả lớp và khái niệm: Dữ liệu có thể đƣợc kết hợp trong lớp và khái niệm. Ví dụ: trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng bao gồm máy tính, máy in,…và khái niệm khách hàng bao gồm khách hàng mua sỉ và khách mua lẻ. Việc mô tả lớp và khái niệm là rất hữu ích cho giai đoạn tổng hợp, tóm lƣợc và chính xác hoá. Mô tả lớp và khái niệm đƣợc bắt nguồn từ đặc trƣng hoá dữ liệu và phân biệt dữ liệu.
Đặc trƣng hoá dữ liệu là quá trình tổng hợp những đặc tính hoặc các thành phần chung của một lớp dữ liệu mục tiêu. Phân biệt dữ liệu là so sánh lớp dữ liệu mục tiêu với những lớp dữ liệu đối chiếu khác. Lớp dữ liệu mục tiêu và các lớp đối chiếu là do ngƣời dùng chỉ ra và tƣơng ứng với các đối tƣợng dữ liệu nhận đƣợc nhờ truy vấn. Phân tích sự kết hợp: Phân tích sự kết hợp là khám phá luật kết hợp thể hiện mối quan hệ giữa các thuộc tính giá trị mà ta nhận biết đƣợc nhờ tần suất xuất hiện cùng nhau của chúng.
Phân lớp và dự báo: Phân lớp là quá trình tìm kiếm một tập các mô hình hoặc chức năng mà nó mô tả và phân biệt nó với các lớp hoặc khái niệm khác. Các mô hình này nhằm mục đích dự báo về lớp của một số đối tƣợng. Việc xây dựng mô hình dựa trên sự phân tích một tập các dữ liệu đƣợc huấn luyện có nhiều dạng thể hiện mô hình nhƣ luật phân lớp (IF-THEN), cây quyết định, công thức toán học hay mạng nơron,. Sự phân lớp đƣợc sử dụng để dự đoán nhãn lớp của các đối tƣợng trong dữ liệu.
Tuy nhiên trong nhiều ứng dụng, ngƣời ta mong muốn dự đoán những giá trị khuyết thiếu Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 10 nào đó. Thông thƣờng đó là trƣờng hợp dự đoán các giá trị của dữ liệu kiểu số. Trƣớc khi phân lớp và dự báo, có thể cần thực hiện phân tích thích hợp để xác định và loại bỏ các thuộc tính không tham gia vào quá trình phân lớp và dự báo. Phân cụm: Không giống nhƣ phân lớp và dự báo, phân cụm phân tích các đối tƣợng dữ liệu khi chƣa biết nhãn của lớp.
