Luận văn kết hợp các phương pháp phân cụm trong khai phá dữ liệu web

GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU WEB

Khai phá dữ liệu và khai phá tri thức

Khai phá dữ liệu (KPDL) là một lĩnh vực nghiên cứu mới, nhằm tự động khai thác thông tin và tri thức hữu ích từ các cơ sở dữ liệu lớn, giúp các tổ chức, doanh nghiệp nâng cao khả năng sản xuất và cạnh tranh Các nghiên cứu khoa học và ứng dụng thành công trong KPDL cho thấy đây là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và triển vọng vượt trội 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 đã được áp dụng rộng rãi trong nhiều lĩnh vực như thương mại, tài chính, y học, viễn thông và tin sinh học.

Khai phá dữ liệu là quá trình trích xuất và sử dụng những thông tin quý giá ẩn chứa trong khối lượng lớn dữ liệu lưu trữ tại các cơ sở dữ liệu, kho dữ liệu và trung tâm dữ liệu.

1.1.2 Quá trình khám phá tri thức

Quá trình khá phá tri thức có thể chia thành 5 bước như sau [1]:

Quá trình KPDL có thể phân thành các giai đoạn sau:

Trích chọn dữ liệu là quá trình lựa chọn các tập dữ liệu cần khai phá từ những tập dữ liệu lớn ban đầu dựa trên các tiêu chí cụ thể.

Tiền xử lý dữ liệu là bước quan trọng trong quá trình phân tích, bao gồm làm sạch dữ liệu bằng cách loại bỏ thông tin sai lệch và xử lý dữ liệu thiếu sót Ngoài ra, nó còn bao gồm việc rút gọn dữ liệu thông qua các phương pháp như sử dụng hàm nhóm, tính tổng, nén dữ liệu và lấy mẫu Cuối cùng, rời rạc hóa dữ liệu cũng là một phần của quá trình này, giúp biến đổi dữ liệu thành các dạng dễ xử lý hơn.

Dữ liệu tiền xử lý

Các mẫu Tri thức Trích chọn

Khai phá Đánh giá, biểu diễn

Hình 1-1: Quy trình khai phá tri thức

Cao Hữu Hải, sinh viên lớp CT1601 ngành Công nghệ Thông tin 9, đã thực hiện các bước xử lý dữ liệu bao gồm việc sử dụng histograms, entropy và các phương pháp khác Qua đó, dữ liệu trở nên nhất quán, đầy đủ, được rút gọn và rời rạc hóa hiệu quả.

Biến đổi dữ liệu là quá trình chuẩn hóa và làm mịn dữ liệu, giúp đưa dữ liệu về cùng một kiểu và dạng thuận lợi nhất để phục vụ cho các bước xử lý tiếp theo.

Khai phá dữ liệu là giai đoạn quan trọng trong quy trình KDD, nơi áp dụng các kỹ thuật phân tích, bao gồm học máy, để trích xuất mẫu dữ liệu và mối liên hệ đặc biệt Đây là bước tốn nhiều thời gian nhất, giúp khám phá thông tin quý giá Sau đó, đánh giá và biểu diễn tri thức được thực hiện để biến đổi các mẫu thông tin này thành dạng dễ hiểu như đồ thị, cây, bảng biểu hay luật, đồng thời đánh giá tri thức khám phá theo các tiêu chí cụ thể.

1.1.3 Khai phá dữ liệu v các l nh vực li n qu n

KPDL là lĩnh vực kết hợp thống kê, học máy, cơ sở dữ liệu và các thuật toán để khám phá tri thức từ dữ liệu lớn Hệ thống khám phá tri thức sử dụng các phương pháp và kỹ thuật từ nhiều lĩnh vực khác nhau để KPDL hiệu quả KDD nghiên cứu lý thuyết và thuật toán nhằm trích xuất mẫu và mô hình từ dữ liệu lớn, tập trung vào việc phát hiện các mẫu đặc biệt có giá trị Ngoài ra, KDD thường áp dụng các thủ tục thống kê cho mô hình dữ liệu, đặc biệt trong phân tích dữ liệu thăm dò (EDA).

1.1.4 Các kỹ thuật áp dụng trong khai phá dữ liệu

Căn cứ vào các bài toán cần giải quyết thì KPDL gồm các kỹ thuật sau [5]:

Phân lớp và dự báo: Xếp một đối tượng vào một trong những lớp đã biết trước

Phân lớp dữ liệu bệnh nhân trong hồ sơ bệnh án là một phương pháp quan trọng trong y học, thường áp dụng các kỹ thuật học máy như cây quyết định và mạng nơron nhân tạo Phương pháp này thuộc về học có giám sát, cho phép phân loại và dự đoán thông tin từ dữ liệu đã được gán nhãn.

Luật kết hợp là một loại luật thể hiện tri thức một cách đơn giản, ví dụ như: "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." Loại luật này được áp dụng rộng rãi trong các lĩnh vực như kinh doanh, y học, tin sinh, tài chính và thị trường chứng khoán.

Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 10

Phân tích chuỗi theo thời gian kết hợp yếu tố thứ tự và thời gian, tương tự như khai phá luật kết hợp Phương pháp này được áp dụng rộng rãi trong lĩnh vực tài chính và thị trường chứng khoán nhờ khả năng dự đoán chính xác.

Phân cụm: Xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên Phân cụm còn đƣợc gọi là học không có giám sát

Mô tả và tóm tắt khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khái niệm, ví dụ nhƣ tóm tắt văn bản

1.1.5 Những chức năng chính của khai phá dữ liệu

KPDL có hai mục tiêu chính là mô tả và dự báo Dự báo sử dụng các biến trong cơ sở dữ liệu để dự đoán các giá trị chưa biết của các biến quan trọng khác Trong khi đó, mô tả tập trung vào việc tìm kiếm các mẫu dễ hiểu để thể hiện dữ liệu Trong lĩnh vực KDD, mô tả thường được chú trọng hơn so với dự báo, điều này trái ngược với các ứng dụng học máy, nơi dự báo là mục tiêu chính Dựa trên những mục tiêu này, các chức năng chính của KDD bao gồm nhiều khía cạnh quan trọng.

Mô tả lớp và khái niệm là quá trình quan trọng trong việc tổ chức dữ liệu, giúp phân loại và xác định các nhóm dữ liệu khác nhau Chẳng hạn, trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng như máy tính và máy in được phân loại, trong khi khái niệm khách hàng được chia thành khách hàng mua sỉ và khách mua lẻ Việc mô tả này hỗ trợ giai đoạn tổng hợp và chính xác hóa thông tin Đặc trưng hóa dữ liệu, tức là tổng hợp các đặc tính chung của lớp dữ liệu mục tiêu, và phân biệt dữ liệu, so sánh lớp dữ liệu mục tiêu với các lớp dữ liệu đối chiếu, là hai bước thiết yếu trong quy trình này Các lớp dữ liệu này được xác định bởi người dùng và liên quan đến các đối tượng dữ liệu thu được qua truy vấn.

Phân tích sự kết hợp là quá trình khám phá các luật kết hợp, thể hiện mối quan hệ giữa các thuộc tính giá trị thông qua tần suất xuất hiện cùng nhau của chúng.

Phân lớp và dự báo là quá trình tìm kiếm các mô hình hoặc chức năng để phân biệt và mô tả các lớp hoặc khái niệm khác nhau Mục tiêu của các mô hình này là dự báo lớp của các đối tượng cụ thể Việc xây dựng các mô hình này dựa trên phân tích một tập dữ liệu huấn luyện đa dạng, bao gồm các dạng thể hiện như luật phân lớp (IF-THEN), cây quyết định, công thức toán học và mạng nơron.

Phương pháp phân cụm dữ liệu

1.2.1 Giới thiệu về kỹ thuật phân cụm

PCDL là quá trình phân chia dữ liệu thành các cụm, giúp các đối tượng trong cùng một cụm trở nên tương tự nhau Đây là một kỹ thuật trong KPDL, nhằm phát hiện các cụm và mẫu dữ liệu tự nhiên, quan trọng trong tập dữ liệu lớn Mục tiêu chính của PCDL là khám phá cấu trúc mẫu dữ liệu, từ đó hình thành các nhóm dữ liệu, tạo điều kiện cho việc phân tích sâu hơn và cung cấp thông tin hữu ích cho quyết định.

Sinh viên Cao Hữu Hải, lớp CT1601 ngành Công nghệ Thông tin, nghiên cứu các cụm dữ liệu để khám phá thông tin tiềm ẩn, hữu ích cho quyết định Ví dụ, có thể xác định "nhóm khách hàng có khả năng trả nợ cao" Phân cụm dữ liệu (PCDL) là một phương pháp quan trọng và phổ biến, giúp 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.

Hình 1-2: Mô phỏng sự phân cụm

Trong quá trình phân cụm dữ liệu, các phần tử tương tự được sắp xếp vào cùng một nhóm, trong khi những phần tử có định nghĩa hoặc khái niệm gần gũi cũng được gom lại Một số vấn đề phổ biến trong phân cụm dữ liệu là dữ liệu "nhiễu" và "phần tử ngoại lai" Dữ liệu "nhiễu" thường là các đối tượng không chính xác hoặc thiếu thông tin, và một kỹ thuật xử lý hiệu quả là thay thế giá trị thuộc tính của đối tượng nhiễu bằng giá trị tương ứng của đối tượng gần nhất Trong khi đó, "phần tử ngoại lai" là những phần tử có sự khác biệt rõ rệt so với các phần tử khác, có thể được xác định thông qua khoảng cách hoặc các mô hình phân phối thống kê mà các phần tử cần tuân theo.

“Phần tử ngoại lai” là những yếu tố không tuân theo các quy luật chung Để xác định chúng, cần phân tích độ khác biệt, trong đó các phần tử này sẽ thể hiện những đặc trưng cơ bản khác biệt rõ rệt so với các phần tử còn lại trong cụm.

Những v n đ cần gi i qu t hi

- Xây dựng hàm tính độ tương tự

- Xây dựng các tiêu chuẩn phân cụm

- Xây dựng mô hình cho cấu trúc cụm dữ liệu

- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo

- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm

1.2.2 Ứng dụng của phân cụm dữ liệu

PCDL là công cụ quan trọng trong KPDL, được ứng dụng rộng rãi trong các lĩnh vực như thương mại và khoa học Các kỹ thuật PCDL đã được áp dụng hiệu quả trong nhiều ứng dụng tiêu biểu, góp phần nâng cao chất lượng và hiệu suất công việc.

PCDL giúp thương nhân nhận diện các nhóm khách hàng quan trọng với những đặc trưng tương đồng, thông qua việc phân tích mẫu mua bán trong cơ sở dữ liệu khách hàng Ngoài ra, PCDL còn hỗ trợ trong việc phát hiện và dự đoán các giao dịch gian lận.

PCDL là công cụ quan trọng trong sinh học, giúp phân cụm các loại sinh vật và phân loại các gen có chức năng tương đồng Phương pháp này cho phép thu được các cấu trúc trong mẫu, đồng thời phát hiện và dự đoán các biến dị.

Lập quy hoạch đô thị yêu cầu nhận dạng các nhóm nhà ở dựa trên kiểu dáng và vị trí địa lý, nhằm cung cấp thông tin thiết yếu cho quy hoạch Địa lý cũng đóng vai trò quan trọng trong việc phân lớp động vật và thực vật, từ đó đưa ra các đặc trưng của chúng theo vị trí địa lý.

Khai phá Web thông qua PCDL cho phép xác định các nhóm tài liệu quan trọng và có ý nghĩa trong môi trường trực tuyến Những lớp tài liệu này hỗ trợ việc khám phá tri thức từ dữ liệu Web, giúp phát hiện mẫu truy cập của khách hàng và nhận diện các cộng đồng trực tuyến.

1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu

Việc lựa chọn thuật toán phân cụm phù hợp là yếu tố quan trọng trong quá trình giải quyết vấn đề phân cụm Quyết định này phụ thuộc vào đặc điểm của dữ liệu cần phân tích, mục tiêu ứng dụng thực tiễn, cũng như sự ưu tiên giữa chất lượng các cụm và tốc độ thực hiện thuật toán.

Những u cầu để phát triển thuật toán PC [5]:

Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ

(khoảng 200 bản ghi dữ liệu) nhƣng không hiệu quả khi áp dụng cho tập dữ liệu lớn (khoảng 1 triệu bản ghi)

Thuật toán phân cụm có khả năng thích nghi với nhiều kiểu dữ liệu khác nhau, bao gồm dữ liệu số, dữ liệu nhị phân, dữ liệu định danh và dữ liệu hạng mục Điều này cho phép thuật toán xử lý hiệu quả các tập dữ liệu hỗn hợp, mang lại kết quả phân cụm chính xác và đáng tin cậy.

Khám phá các cụm dữ liệu với hình thù đa dạng là cần thiết, vì nhiều cơ sở dữ liệu chứa các cụm có hình dạng khác nhau như hình lõm, hình cầu, hay hình que Để nhận diện các cụm một cách tự nhiên, các thuật toán phân cụm cần có khả năng phát hiện các hình thù bất kỳ của dữ liệu.

Để xác định các tham số đầu vào cho thuật toán phân cụm, cần có một lượng tri thức tối thiểu, vì giá trị đầu vào có ảnh hưởng lớn đến kết quả Việc xác định giá trị đầu vào phù hợp cho các cơ sở dữ liệu lớn là rất phức tạp Hơn nữa, thuật toán phân cụm ít nhạy cảm với thứ tự của dữ liệu đầu vào; cùng một tập dữ liệu, nếu được xử lý với các thứ tự khác nhau trong các lần thực hiện, sẽ không gây ảnh hưởng lớn đến kết quả phân cụm.

Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm trong

KPDL thường chứa dữ liệu lỗi, dữ liệu không đầy đủ và dữ liệu rác, điều này có thể ảnh hưởng đến chất lượng phân cụm Thuật toán phân cụm không chỉ hiệu quả trong việc xử lý dữ liệu nhiễu mà còn giảm thiểu tác động tiêu cực từ chúng, giúp duy trì chất lượng phân cụm cao Hơn nữa, thuật toán này ít nhạy cảm với các tham số đầu vào, nghĩa là sự thay đổi nhỏ trong giá trị tham số đầu vào không gây ra biến động lớn trong kết quả phân cụm.

Thích nghi với dữ liệu đ chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau

Dễ hiểu, dễ cài đặt và khả thi

1.2.4 Các kiểu dữ liệu v độ đo tương tự

Trong phân tích dữ liệu lớn (PCDL), các đối tượng cần phân tích bao gồm con người, nhà cửa, tiền lương và các thực thể phần mềm, thường được mô tả qua các thuộc tính của chúng Phân loại các kiểu thuộc tính khác nhau là vấn đề quan trọng để nhận diện sự khác biệt giữa các phần tử dữ liệu Có hai phương pháp phân lớp dựa trên hai đặc trưng của dữ liệu: kích thước miền và hệ đo.

1.2.4.1 Phân loại kiểu dữ liệu dựa trên ích thước mi n

Khai phá Web

1.3.1 Các kiểu dữ liệu Web

Sơ đồ phân loại dữ liệu Web :

Các đối tượng của khai phá Web bao gồm[4] : Server logs, Web pages, Web hyperlink structures, dữ liệu thị trường trực tuyến và các thông tin khác

Dữ liệu đăng nhập Web, bao gồm server logs, error logs và cookie logs, được tạo ra khi người dùng duyệt Web Phân tích các loại dữ liệu này giúp khám phá thông tin truy cập của người dùng trên Website.

Web pages: Hầu hết các phương pháp KPDL Web được sử dụng trong Web pages là theo chuẩn HTML

Cấu trúc siêu liên kết web là yếu tố quan trọng giúp kết nối các trang web với nhau, từ đó khai thác thông tin hiệu quả Các siêu liên kết này không chỉ tạo ra mạng lưới thông tin phong phú mà còn là nguồn tài nguyên đáng tin cậy.

Dữ liệu thị trường trực tuyến: Như lưu trữ thông tin thương mại điện tử trong các site thương mại điện tử

Các thông tin khác: Chủ yếu bao gồm các đăng ký người dùng, nó có thể giúp cho việc khai phá tốt hơn

Dữ liệu cấu trúc Web

Dữ liệu sử dụng Web

Dữ liệu động Hình ảnh, video

Dữ liệu XML Văn bản tự do

Hình 1-3: Phân loại dữ liệu Web

1.3.2 Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web

Văn bản là tài liệu quan trọng, được sử dụng rộng rãi trong mọi hoạt động của con người, đặc biệt trong môi trường truyền thông số và Internet Do đó, các bài toán xử lý văn bản đã được đặt ra từ sớm và vẫn thu hút sự quan tâm của nhiều nhà nghiên cứu Một số vấn đề nổi bật trong lĩnh vực này bao gồm tìm kiếm và trích dẫn văn bản, cũng như biểu diễn và phân loại văn bản.

S văn n có thể chia làm 2 loại chính [6] :

Dữ liệu không có cấu trúc là những tài liệu văn bản thông thường mà chúng ta sử dụng hàng ngày, thường xuất hiện trên sách, báo và internet Đây là dạng dữ liệu phản ánh ngôn ngữ tự nhiên của con người và không tuân theo bất kỳ khuôn mẫu cố định nào.

Dạng nửa cấu trúc là những văn bản được tổ chức theo cách lỏng lẻo nhưng vẫn truyền đạt nội dung chính một cách rõ ràng, ví dụ như văn bản HTML và email.

1.3.3 Một số vấn đề trong xử lý dữ liệu văn bản

Trong xử lý dữ liệu văn bản, mỗi văn bản được biểu diễn dưới dạng vector Boolean hoặc vector số Các vector này được phân tích trong không gian đa chiều, với mỗi chiều tương ứng với một từ mục riêng biệt trong tập văn bản.

- ột s ưu hi iểu đi n văn n ng h ng gian v ctor:

- Không gian vector: là một tập hợp bao gồm các từ

Một từ được định nghĩa là một chuỗi các ký tự, bao gồm chữ cái và chữ số, nhưng không bao gồm khoảng trống, ký tự xuống dòng hoặc dấu câu như dấu chấm, phẩy, hay dấu chấm phẩy Để đơn giản hóa quá trình xử lý, người ta thường chuyển tất cả các ký tự về dạng chữ thường, không phân biệt giữa chữ hoa và chữ thường.

Gộp từ đồng nghĩa là quá trình sử dụng từ gốc hoặc biến thể của nó để giảm số lượng từ trong văn bản, giúp tối ưu hóa không gian ngôn ngữ Mặc dù việc này có thể làm giảm đáng kể số từ, nhưng việc cắt bỏ các từ lại có thể gây khó khăn trong việc hiểu nội dung.

Trong phương pháp biểu diễn dữ liệu văn bản bằng không gian vector, chiều của vector thường rất lớn do số lượng từ khác nhau trong tập hợp từ Do đó, cần phải tìm cách giảm số chiều của vector mà vẫn đảm bảo hiệu quả trong quá trình xử lý.

Cao Hữu Hải, sinh viên lớp CT1601 ngành Công nghệ Thông tin, đã nghiên cứu về việc cải thiện độ chính xác của văn bản Để giải quyết vấn đề này, một số phương pháp được đề xuất bao gồm việc loại bỏ từ dừng và áp dụng định luật Zipf.

Trong ngôn ngữ hàng ngày, có nhiều từ chỉ đóng vai trò cấu trúc câu mà không truyền đạt nội dung, như giới từ và từ nối Những từ này thường xuất hiện trong văn bản nhưng không liên quan đến chủ đề chính, được gọi là từ dừng Do đó, việc loại bỏ từ dừng giúp giảm số chiều của vector trong biểu diễn văn bản.

Sau đây là ví dụ về tần số xuất hiện cao của một số từ (tiếng Anh) trong 336,310 tài liệu gồm tổng cộng 125.720.891 từ, 508.209 từ riêng biệt

Number of Occurrences Percentage of

The 7,398,934 5.9 of 3,893,790 3.1 to 3,364,653 2.7 and 3,320,687 2.6 in 2,311,785 1.8 is 1,559,147 1.2 for 1,313,561 1.0

Bảng 1-2: Thống kê các tần số xuất hiện cao

(Thống kê của B Croft, UMass)

1.3.3.2 Định luật Zipf Định luật đƣợc đƣa ra bởi Zipf năm 1949 đƣợc hiểu là: Trong văn bản có một số từ có tần số xuất hiện thấp thì ảnh hưởng đến ngữ nghĩa và lượng thông tin có trong văn bản, không cần thiết cho quá trình xử lý, cho nên ta có thể loại bỏ chúng để giảm số chiều của vector biểu diễn văn bản

Năm 1958 Luhn đề xuất những từ “phổ biến” và “hiếm” và không cần thiết cho quá trình xử lý nhƣ sau:

Hình 1-4: Đồ thị thống kê tần số của từ theo định luật Zipf

Tiểu kết chương 1

Chương 1 trình bày những kiến thức cơ bản về khai phá dữ liệu và khám phá tri thức trong CSDL, các kỹ thuật phân cum trong khai phá dữ liệu, những chức năng chính, ứng dụng của nó trong xã hội,

Chương này tập trung vào nghiên cứu và ứng dụng phân cụm dữ liệu, bao gồm tổng quan về kỹ thuật phân cụm, ứng dụng của nó, yêu cầu kỹ thuật, các loại dữ liệu, và phương pháp đo lường sự tương đồng.

MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU

Thuật toán k-means

Thuật toán phân cụm k-means, được MacQueen giới thiệu vào năm 1967 trong lĩnh vực thống kê, nhằm mục tiêu tạo ra k cụm dữ liệu {C1, C2,…, Ck} từ một tập dữ liệu ban đầu gồm n đối tượng trong không gian d chiều.

,…, ), i=(1,n), sao cho hàm tiêu chuẩn: ∑ ∑ đạt giá trị tối thiểu Trong đó: mi là trọg tâm của cụm C i , D là khoảng cách giữa hai đối tƣợng

Trọng tâm của một cụm được xác định bởi một vector, trong đó mỗi phần tử là giá trị trung bình cộng của các thành phần tương ứng từ các đối tượng vector dữ liệu trong cụm Thuật toán yêu cầu đầu vào là số cụm k và tập dữ liệu gồm n phần tử, trong khi đầu ra là các trọng tâm của các cụm dữ liệu Để phân nhóm dữ liệu, độ đo khoảng cách được sử dụng để xác định sự tương đồng giữa các đối tượng.

Khoảng cách Euclidean là phương pháp phổ biến để đo lường sự tương đồng giữa các đối tượng dữ liệu, nhờ vào khả năng dễ dàng 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à cách đo khoảng cách có thể được điều chỉnh tùy thuộc vào ứng dụng cụ thể hoặc quan điểm của người dùng.

Thuật toán k-means được chứng minh là hội tụ với độ phức tạp tính toán là O(nkdτ), trong đó n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều, τ là số vòng lặp, và thời gian thực hiện một phép tính cơ bản như nhân, chia, v.v.

Thuật toán k-means bao gồm các ước cơ n như sau

INPUT: Một CSDL gồm n đối tƣợng và số các cụm k

OUTPUT: Các cụm C i (i=1, ,k) sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu

Chọn k đối tƣợng m j (j=1 k) là trọng tâm ban đầu của k cụm từ tập 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 giữa mỗi đối tượng x_i và các trọng tâm m_j (j=1, ,k) Đầu tiên, xác định khoảng cách từ từng đối tượng đến từng trọng tâm, sau đó tìm trọng tâm gần nhất cho mỗi đối tượng.

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ách xác định trung bình cộng của các vector đố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

Hình 2-1: Hình dạng cụm dữ liệu đƣợc khám phá bởi k-means

Thuật toán k-means là một phương pháp phân cụm đơn giản, phù hợp với các tập dữ liệu lớn Tuy nhiên, nó có một số hạn chế, bao gồm việc chỉ áp dụng cho dữ liệu có thuộc tính số và hình dạng cầu, đồng thời nhạy cảm với nhiễu và các điểm ngoại lai Chất lượng phân cụm của k-means phụ thuộc nhiều vào các tham số đầu vào như số cụm k và các trọng tâm khởi tạo Nếu các trọng tâm khởi tạo quá lệch so với các cụm tự nhiên, kết quả phân cụm sẽ không chính xác, dẫn đến việc khám phá các cụm dữ liệu không phản ánh đúng thực tế.

Hiện nay có rất nhiều thuật toán kế thừa tư tưởng của thuật toán k-means để KPDL ma có CSDL rất lớn nhƣ: k-medoid, PAM, CLARA, CLARANS, …

Thuật toán PAM

Thuật toán PAM (Partitioning Around Medoids) được đề xuất bởi Kaufman và Rousseeuw vào năm 1987, là một phiên bản mở rộng của thuật toán k-means, giúp xử lý hiệu quả dữ liệu nhiễu và các phần tử ngoại lai Khác với k-means, PAM sử dụng các đối tượng medoid để đại diện cho các cụm dữ liệu, giúp giảm thiểu ảnh hưởng từ những điểm xa trung tâm Ban đầu, PAM chọn k đối tượng medoid và phân phối các đối tượng còn lại vào các cụm dựa trên sự tương đồng với medoid tương ứng Sau mỗi bước, thuật toán cố gắng hoán chuyển giữa các đối tượng medoid để tối ưu hóa cấu trúc của các cụm.

Om và một đối tượng Op không phải là medoid, miễn là việc hoán chuyển này nhằm cải thiện chất lượng phân cụm Quá trình này sẽ dừng lại khi chất lượng phân cụm không còn thay đổi Chất lượng phân cụm được đánh giá thông qua hàm tiêu chuẩn, với chất lượng tốt nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu Để quyết định có hoán chuyển hai đối tượng hay không, thuật toán PAM sử dụng giá trị tổng chi phí hoán chuyển làm căn cứ.

: Là đối tƣợng medoid hiện thời cần đƣợc thay thế

: Là đối tƣợng medoid mới thay thế cho

: Là đối tƣợng dữ liệu (không phải là medoid) có thể đƣợc di chuyển sang cụm khác

: Là đối tƣợng medoid hiện thời khác với mà gần đối tƣợng nhất

Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 28 u đây là trường hợp tính để làm căn cứ hoán chuyển h i đối tượng medoid:

Trong trường hợp Oj thuộc về cụm với đại diện là Om và Oj tương tự với hơn (d( , ) d( , )), đối tượng medoid tương tự xếp thứ 2 sẽ được thay thế bởi đối tượng medoid mới Kết quả là Oj sẽ thuộc về cụm có đối tượng đại diện là Do đó, giá trị hoán chuyển được xác định như sau:

– Giá trị C jmp là không âm

Trong trường hợp 2, O j hiện tại thuộc về cụm đại diện O m, nhưng O j lại ít tương tự với O m,2 hơn so với O p (d(O j ,O p ) < d(O j ,O m,2 ) Khi thay thế O m bằng O p, O j sẽ thuộc về cụm có đại diện O p Do đó, giá trị C jmp được xác định theo công thức sau: ( ) Giá trị C jmp có thể là âm hoặc dương.

Hình 2-3 : ( ) có thể âm hoặc dương

Trường hợp 3: Giả sử O j hiện thời không thuộc về cụm có đối tượng đại diện là

O m thuộc về cụm có đại diện là O m,2 Nếu O j tương tự với O m,2 hơn so với O p, thì khi O m được thay thế bởi O p, O j vẫn sẽ giữ vị trí trong cụm đại diện O m,2.

Trong trường hợp 4, O j hiện tại thuộc về cụm có đại diện O m,2, nhưng mức độ tương tự của O j với O m,2 lại thấp hơn so với O p Do đó, việc thay thế O m bằng O p sẽ dẫn đến việc O j chuyển từ cụm này.

O m,2 sang cụm O p Do đó, giá trị hoán chuyển C jmp đƣợc xác định là: C jmp = (O j ,O p )- d(O j , O m,2 ) C jmp ở đây luôn âm

Hình 2-5: Trường hợp C jmp = (O j ,O p )- d(O j , O m,2 ) C jmp luôn âm

Hình 2 1 Trường hợp Cjmp= (Oj,Op)- d(Oj, Om,2) luôn âm

- Kết hợp cả bốn trường hợp trên, tổng giá trị hoán chuyển Om bằng Op được xác định nhƣ sau: T Cmp = ∑

Thuật toán P M b o gồm các bước s u:

INPUT: Tập dữ liệu có n phần tử, số cụm k

OUTPUT: k cụm dữ liệu sao cho chất lƣợng phân hoạch là tốt nhất

Bước 1: Chọn k đối tƣợng medoid bất kỳ

Bước 2: Tính T Cmp cho tất cả các cặp đối tƣợng O m , O p Trong đó O m là đối tƣợng medoid và O p là đối tƣợng không phải là modoid

Bước 3: Với mỗi cặp đối tƣợng O m và O p Tính min(O m ), min(O p ), T Cmp Nếu

T Cmp là âm, thay thế O m bởi O p và quay lại bước 2 Nếu T Cmp dương, chuyển sang bước 4

Trong bước 4 của thuật toán PAM, cần xác định đối tượng medoid tương tự nhất cho mỗi đối tượng không phải medoid và gán nhãn cụm cho chúng Độ phức tạp tính toán của PAM là O(i k (n-k)), trong đó i là số vòng lặp Thuật toán này phải duyệt tất cả k(n-k) cặp O m và O p, đồng thời kiểm tra n-k đối tượng để tính toán T Cmp Do đó, PAM trở nên kém hiệu quả về thời gian tính toán khi giá trị của k và n lớn.

Thuật toán PAM không chỉ kế thừa những ưu điểm của k-means mà còn khắc phục được vấn đề xử lý dữ liệu nhiễu và các phần tử ngoại lai Tuy nhiên, thời gian tính toán của PAM trở nên kém hiệu quả khi làm việc với cơ sở dữ liệu lớn và số lượng medoid nhiều.

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 được đề xuất bởi Tian Zhang, Ramesh M S Amakrishnan và Michael Livny vào năm 1996, sử dụng chiến lược Top down Thuật toán này không yêu cầu lưu trữ toàn bộ đối tượng dữ liệu trong bộ nhớ, mà chỉ cần lưu các đại lượng thống kê Đối với mỗi cụm, BIRCH lưu trữ một bộ ba (n, LS, SS), trong đó n là số đối tượng, LS là tổng các giá trị thuộc tính và SS là tổng bình phương 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 trưng cụm (Cluster Features - CF) và được lưu trong một cấu trúc cây gọi là cây CF Tất cả các nút trong cây lưu tổng các đặc trưng CF của nút con, trong khi các nút lá lưu trữ đặc trưng của các cụm dữ liệu.

CF 6 child 6 prev CF 1 CF 2 … CF 6 Next prev CF 1 CF 2 … CF 6 Next

Hình 2-6: Câ CF đƣợc tạo bởi BIRCH

Cây CF là loại cây cân bằng được sử dụng để lưu trữ các đặc trưng của cụm Cấu trúc của cây CF bao gồm các nút trong và nút lá, trong đó nút trong chứa tổng các đặc trưng của các nút con Đặc điểm của cây CF được xác định bởi hai tham số chính.

- Yếu tố nhánh (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 (T) là khoảng cách tối đa giữa bất kỳ cặp đối tượng nào trong nút lá của cây, thường được gọi là đường kính của các cụm con được lưu trữ tại các nút lá.

INPUT: CSDL gồm n đối tƣợng, ngƣỡng T

Bước đầu tiên trong quá trình xây dựng cây CF là duyệt qua tất cả các đối tượng trong cơ sở dữ liệu (CSDL) và tạo ra một cây CF khởi tạo Mỗi đối tượng sẽ được chèn vào nút lá gần nhất, hình thành nên một cụm con Nếu đường kính của cụm con này vượt quá ngưỡng T, nút lá sẽ bị tách ra Khi một đối tượng phù hợp được chèn vào nút lá, tất cả các nút liên kết với gốc của cây sẽ được cập nhật thông tin cần thiết.

Nếu cây CF hiện tại thiếu bộ nhớ trong, hãy xây dựng một cây CF nhỏ hơn bằng cách điều chỉnh tham số T Việc tăng T sẽ giúp hoà nhập các cụm con thành một cụm lớn hơn, từ đó làm giảm kích thước của cây CF Bước này không yêu cầu phải đọc lại dữ liệu từ đầu nhưng vẫn đảm bảo hiệu chỉnh cho cây dữ liệu nhỏ hơn.

Bước 3 trong quy trình phân cụm là thực hiện phân cụm, trong đó 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 Tại 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 như k-means, từ đó tạo ra một khởi tạo cho phân cụm hiệu quả.

Bước 4 trong quá trình phân tích dữ liệu là phân phối lại các đối tượng bằng cách sử dụng các trọng tâm của các cụm đã được khám phá ở bước 3 Đây là bước tùy chọn, giúp 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 Mục đích của bước này là 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.

Thuật toán BIRCH nổi bật với tốc độ thực hiện nhanh trong phân cụm dữ liệu lớn, đặc biệt hiệu quả với các tập dữ liệu có sự tăng trưởng theo thời gian Với độ phức tạp thấp, BIRCH đảm bảo khả năng xử lý nhanh chóng, làm cho nó trở thành lựa chọn lý tưởng trong các ứng dụng phân tích dữ liệu lớn.

Nhược điểm: BIRCH khám phá các cụm có chất lƣợng đƣợc không đƣợc tốt

BIRCH chỉ hiệu quả với dữ liệu số và phụ thuộc vào thứ tự của dữ liệu Ngưỡng T có ảnh hưởng lớn đến việc hình thành cụm, trong khi BIRCH không phù hợp với dữ liệu đa chiều.

Thuật toán DBSCAN

Thuật toán DBSCAN (Density Based Spatial Clustering of Applications with Noise) do Martin Ester và các tác giả khác đề xuất là một phương pháp phân cụm dựa trên mật độ, rất hiệu quả cho cơ sở dữ liệu lớn và có khả năng xử lý nhiễu Ý tưởng chính của thuật toán là xác định vùng lân cận của mỗi đối tượng trong cụm có số lượng đối tượng vượt quá ngưỡng tối thiểu Hình dạng của vùng lân cận phụ thuộc vào hàm khoảng cách giữa các đối tượng; ví dụ, nếu sử dụng khoảng cách Manhattan trong không gian 2 chiều, vùng lân cận sẽ có hình chữ nhật, trong khi khoảng cách Euclidean sẽ tạo ra vùng lân cận hình tròn Định nghĩa lân cận của một điểm P với ngưỡng Eps, ký hiệu N Eps(p), được xác định như sau: N Eps(p) = {q D | khoảng cách Dist(p,q) ≤ Eps}, với D là tập dữ liệu đã cho.

Hình 2-7: Lân cận của một điểm p với ngƣỡng Eps

Một điểm p muốn nằm trong một cụm C nào đó thì N Eps(p) phải có tối thiểu

Trong phân tích cụm, MinPts là số lượng điểm tối thiểu cần thiết để xác định một cụm Chỉ những điểm thực sự nằm trong cụm mới đáp ứng điều kiện trở thành điểm thuộc cụm, trong khi các điểm nằm ở biên cụm không thỏa mãn điều này Điều này xảy ra vì lân cận với ngưỡng Eps của điểm biên thường ít hơn so với lân cận với ngưỡng Eps của điểm nhân.

Mật độ-đến được trực tiếp (Directly Density-reachable) là khái niệm quan trọng trong công nghệ thông tin, đặc biệt trong phân tích dữ liệu Một điểm p được xem là mật độ-đến được trực tiếp từ điểm q nếu nó thỏa mãn hai điều kiện: nằm trong khoảng cách Eps và có ít nhất MinPts điểm lân cận trong tập đối tượng D Việc hiểu rõ định nghĩa này giúp sinh viên ngành Công nghệ Thông tin áp dụng hiệu quả trong các nghiên cứu và dự án liên quan đến phân tích dữ liệu.

1) p N Eps(q) Với N Eps(q) là tập con của D

2) ||N Eps(q) || ≥ MinPts Điều kiện đối tƣợng nhân

Hình 2-8: Mật độ-đến đƣợc trực tiếp

Nếu p và q đều là đối tượng nhân, quan hệ mật độ - đến được trực tiếp (Directly Density-reachable) có tính đối xứng, nghĩa là p có thể đến được trực tiếp từ q theo mật độ và ngược lại.

Nếu trong một không gian p, q có một đối tượng nhân và một đối tượng biên, chỉ đối tượng biên mới có thể tiếp cận trực tiếp từ đối tượng nhân theo mật độ, mà không có chiều ngược lại, thể hiện tính bất đối xứng Định nghĩa về Mật độ - đến được (Density - Reachable) chỉ ra rằng một điểm p được coi là mật độ-đến được từ điểm q nếu tồn tại một chuỗi liên kết giữa chúng, với điều kiện có hai tham số Eps và MinPts, sao cho mỗi điểm trong chuỗi đều có thể tiếp cận trực tiếp từ điểm trước đó.

Hình 2-9: Mật độ - đến đƣợc

Hai điểm p,q đến đƣợc với nhau, vì p,q không là điểm nhân và tồn tại điểm nhân trong cụm mà hai điểm p,q có thể đến đƣợc nó

Mật độ - liên thông (Density - Connected) là khái niệm trong công nghệ thông tin, trong đó một đối tượng p được coi là mật độ - liên thông với điểm q nếu tồn tại một đối tượng o sao cho cả hai đối tượng p và q đều có thể tiếp cận o theo các tham số Eps và MinPts.

Mật độ-liên thông trong CSDL D được xác định bởi cụm C thỏa mãn các điều kiện Eps và MinPts Cụm C sẽ được coi là tập con hác rỗng của D nếu nó đáp ứng hai điều kiện cần thiết.

1) Cực đại: Với p,q D, nếu p C và q là mật độ- đến được p theo Eps và MinPts thì q C

2) Với p,q C, p là mật độ-liên thông với q theo Eps và MinPts

Mọi đối tƣợng không thuộc cụm nào cả thì gọi là nhiễu

Hình 2-11: Các đối tƣợng nhiễu

C h i b đề trong thuật toán SC N:

Bổ đ 1: Giả sử p là một đối tƣợng trong D, trong đó ||N Eps(p) || ≥ MinPts, tập O =

Mật độ điểm được xác định bởi các tham số Eps và MinPts, tạo thành một cụm C Mặc dù cụm C không hoàn toàn độc nhất, nhưng mỗi điểm trong cụm đều có vai trò quan trọng trong việc xác định cấu trúc dữ liệu.

C đến đƣợc mật độ từ bất cứ một điểm nhân nào của C, vì vậy C chứa đúng một số điểm liên thông với điểm nhân tuỳ ý

Bổ đ 2: Giả sử C là một cụm được xác định bởi các tham số Eps và MinPts, trong đó p là một điểm bất kỳ thuộc C với số lượng điểm lân cận ||N Eps(p) || lớn hơn hoặc bằng MinPts Khi đó, cụm C sẽ trùng với tập O, bao gồm các điểm o mà o có độ mật độ có thể tiếp cận từ p theo các tham số Eps và MinPts.

Các bước của thuật toán SC N như s u:

OUTPUT: Các cụm dữ liệu sau khi đƣợc khám phá

Bước 1: Chọn một đối tƣợng p tuỳ ý

Để xác định các đối tượng mật độ, bước đầu tiên là lấy tất cả các điểm xung quanh điểm p với khoảng cách Eps và số lượng điểm tối thiểu MinPts Nếu điểm p được xác định là điểm nhân, thì sẽ tiến hành tạo ra một cụm dựa trên các thông số Eps và MinPts đã chỉ định.

Bước 4: Nếu p là một điểm biên, không có điểm nào là mật độ - đến được từ p và

DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu

Bước 5: Quá trình tiếp tục cho đến khi tất cả các đối tƣợng đƣợc xử lý

DBSCAN sử dụng các tham số Eps và MinPts để gộp hai cụm thành một khi mật độ của chúng tương đương Thuật toán này có khả năng phát hiện các cụm với hình dáng đa dạng và ít bị ảnh hưởng bởi thứ tự của dữ liệu đầu vào Điều này cũng mang lại lợi ích cho việc cập nhật dữ liệu, vì việc thêm đối tượng mới chỉ ảnh hưởng đến một láng giềng cụ thể.

Chương này trình bày một số thuật toán phân cụm dữ liệu phổ biến như: k- means, PAM, DBSCAN

Thuật toán k-means và PAM bắt đầu bằng việc tạo ra k cụm ngẫu nhiên, sau đó thực hiện lặp lại nhiều lần để phân bổ lại các đối tượng dữ liệu giữa các cụm, từ đó nâng cao chất lượng phân cụm.

Thuật toán BIRCH dựa trên ý tưởng cây phân cấp để phân cụm dữ liệu theo top- down hoặc botton-up

Thuật toán DBSCAN căn cứ vào hàm mật độ của các đối tƣợng dữ liệu để xác định cụm cho các đối tƣợng.

KHAI PHÁ DỮ LIỆU WEB

Khai phá nội dung Web

Khai phá nội dung Web là quá trình tập trung vào việc phân tích và xử lý các loại nội dung trên trang Web, bao gồm văn bản, âm thanh và hình ảnh Trong lĩnh vực này, khai phá nội dung Web được coi là một kỹ thuật quan trọng trong việc phát hiện các mẫu tri thức từ kho dữ liệu không cấu trúc có trong tài liệu Web Nhiều tài liệu Web có dạng nửa cấu trúc như HTML hoặc dữ liệu cấu trúc như bảng, nhưng phần lớn dữ liệu văn bản lại là không cấu trúc, điều này tạo ra những thách thức phức tạp cho việc khai phá nội dung Web.

Khai phá nội dung web có nhiều phương pháp khác nhau, tuy nhiên trong bài viết này, chúng ta sẽ tập trung vào hai khía cạnh chính: khai phá kết quả tìm kiếm và khai phá nội dung từ trang HTML.

Hình 3-1: Phân loại khai phá Web

Dữ liệu cấu trúc Web

Dữ liệu sử dụng Web

Theo dõi sử dụng của người dùng

Theo dõi mẫu tru cập

Dữ liệu tìm kiếm Web

3.1.1 Khai phá kết quả tìm kiếm

Hiện nay, việc sử dụng công cụ Web Searching Engine để phân loại tự động tài liệu Web đang phát triển mạnh mẽ nhờ khả năng đánh trọng số cho các trang Web Quá trình này bắt đầu bằng việc tải dữ liệu từ các Website, sau đó trích xuất thông tin chỉ mục mô tả cùng với URL để lưu trữ trong Web Search Engine Cuối cùng, các phương pháp KPDL được áp dụng để phân lớp tự động, giúp tổ chức và phân loại các trang Web một cách hiệu quả thông qua cấu trúc siêu liên kết.

Trực quan hoá kết quả tìm kiếm giúp cải thiện hiệu quả phân loại tài liệu bằng cách phân tích và phân cụm các thông tin liên quan Bằng cách nhóm các tài liệu có nội dung tương tự vào một nhóm và phân loại các tài liệu không tương tự vào các nhóm khác, người dùng có thể dễ dàng tìm kiếm theo từng tiêu chí cụ thể Việc này không chỉ nâng cao trải nghiệm tìm kiếm mà còn giúp người dùng tiết kiệm thời gian trong việc tìm kiếm thông tin cần thiết.

3.1.2 Kh i phá văn bản Web

KPVB là việc áp dụng kỹ thuật KPDL để khai thác tri thức tiềm ẩn từ các tập văn bản Nó liên quan đến các công nghệ như xử lý ngôn ngữ tự nhiên và tìm kiếm thông tin Đối tượng của KPVB bao gồm dữ liệu có cấu trúc, không cấu trúc và nửa cấu trúc Kết quả của quá trình KPVB là xác định trạng thái trung của mỗi tài liệu và phân loại tài liệu cho các mục đích cụ thể Quá trình KPVB diễn ra theo các bước nhất định để đạt được hiệu quả cao nhất.

Tiền xử lý Biểu diễn dữ liệu

Sử dụng các kỹ thuật khai phá dữ liệu để xử lý

Trích rút các mẫu Đánh giá biểu diễn tri thức

Hình 3-2: Quá trình kh i phá văn bản Web

Nguồn dữ liệu Web bao gồm văn bản cục bộ trên các trang Web, được định dạng và tích hợp thành các tài liệu theo yêu cầu Những tài liệu này sau đó được khai thác và phân phối qua nhiều dịch vụ Web thông qua kỹ thuật truy xuất thông tin.

3.1.2.2 Ti n xử lý dữ liệu

Tiền xử lý là quá trình quan trọng nhằm làm rõ và chính xác hóa dữ liệu, loại bỏ những thông tin hỗn độn và dư thừa để phục vụ cho khai phá dữ liệu Các bước cơ bản bao gồm: đầu tiên, xác định yêu cầu của người dùng và tìm hiểu mối quan hệ giữa các tri thức trong dữ liệu Sau đó, tiến hành làm sạch, chuẩn hóa và sắp xếp lại các tri thức này Kết quả cuối cùng là một bảng hai chiều chứa các đặc trưng cần thiết.

- 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

- 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

KPVB Web giúp khai thác các tập tài liệu HTML, yêu cầu chúng ta phải chuyển đổi và biểu diễn dữ liệu một cách phù hợp cho quá trình xử lý Chúng ta có thể tiến hành xử lý và lưu trữ dữ liệu này trong mảng.

Dữ liệu có thể phản ánh đặc trưng của tài liệu qua hai chiều, thường sử dụng mô hình TF-IDF để vector hóa Tuy nhiên, việc này tạo ra số chiều vector lớn, do đó cần lựa chọn các đặc trưng quan trọng để đảm bảo chúng trở thành khóa và ảnh hưởng trực tiếp đến hiệu quả của KPVB.

Để tối ưu hóa nội dung, trước tiên cần loại bỏ các từ dừng theo định luật Zipf, tức là loại bỏ những từ có tần suất xuất hiện cao nhưng ít thông tin như "và", "hoặc", "hay" Đồng thời, cũng cần loại bỏ các từ có tần suất thấp để giảm thiểu dữ liệu nhiễu Sau đó, tiến hành chọn lọc và phân lớp các từ còn lại nhằm mô tả các đặc trưng của tài liệu một cách hiệu quả.

3.1.2.4 Trích rút các từ đặc trưng

Rút ra các đặc trưng là một phương pháp hiệu quả để xử lý số chiều vector đặc trưng lớn do kỹ thuật KPVB mang lại Quá trình này dựa trên hàm trọng số nhằm tối ưu hóa việc trích xuất thông tin.

Phư ng pháp tính trọng số tần xuất logarit (TF:term-frequency):

TF của một từ t trong tài liệu d đƣợc tính nhƣ sau:

Điểm số cho một cặp tài liệu-truy vấn (document-query) được xác định bằng tổng trọng số của từ t trong cả tài liệu d và truy vấn Nếu từ truy vấn không xuất hiện trong tài liệu, điểm số sẽ bằng 0.

Phư ng pháp tính trọng số nghịch đảo văn bản:

Trong việc tính toán trọng số tần suất (TF), các từ có tần suất xuất hiện cao sẽ được đánh giá với điểm số cao hơn Tuy nhiên, những từ hiếm lại chứa đựng nhiều ý nghĩa sâu sắc hơn, do đó cần có một phương pháp đánh giá khác dành cho các từ này.

Trọng số idf t của từ t: (

: Tổng số tài liệu mà d xuất hiện

Lưu ý rằng IDF không ảnh hưởng đến việc xếp hạng tài liệu khi chỉ có một từ khóa, mà chỉ giúp phân loại tài liệu IDF chỉ tác động đến xếp hạng tài liệu khi truy vấn có ít nhất hai từ.

3.1.2.5 Khai phá dữ liệu văn n

Sau khi thu thập và lựa chọn các văn bản để xác định các đặc trưng cơ bản, chúng ta có thể xây dựng cơ sở dữ liệu cho KPDL Từ đó, có thể thực hiện các bước như trích xuất, phân loại, phân cụm, phân tích và dự đoán thông tin.

Khai phá theo sử dụng Web

Khai phá theo sử dụng Web là quá trình thiết kế các trang Web dựa trên mẫu truy xuất của người dùng, nhằm phục vụ tốt nhất cho nhu cầu của đa số người dùng internet Bên cạnh đó, việc này còn cho phép khai thác thông tin về hành vi và sự quan tâm của người dùng đối với trang Web, giúp tối ưu hóa trải nghiệm trực tuyến.

Khai phá theo sử dụng Web là quá trình phân tích các mẫu truy cập của người dùng vào Website thông qua việc khảo sát và ghi nhận quy tắc truy cập Điều này không chỉ giúp xác thực khách hàng trong thương mại điện tử mà còn nâng cao chất lượng dịch vụ thông tin trên Internet và cải thiện hiệu suất của các hệ thống Web Bên cạnh đó, việc phân tích các mẫu truy xuất của người dùng còn hỗ trợ phát triển Website và xây dựng các dịch vụ Web cá nhân hóa, đáp ứng tốt hơn nhu cầu của từng người dùng.

- Cải tiến hiệu suất hệ thống phục vụ của các máy chủ Web

- Cá nhân dịch vụ Web thông quan việc phân tích các đặc tính cá nhân người dùng

- Tìm ra những khách hàng tiềm năng trong thương mại điện tử

- Chính phủ điện tử (e-Gov), giáo dục điện tử (e-Learning)

- Xác định những quảng cáo tiềm năng

- Cải tiến thiết kế Web thông qua việc phân tích thói quen duyệt Web và phân tích các mẫu nội dung trang quy cập của người dùng

- Phát hiện gian lận và xâm nhập bất hợp lệ trong dịch vụ thương mại điện tử và các dịch vụ Web khác

- Nâng cao chất lƣợng truyền tải của các dịch vụ thông tin Internet đến người dùng

- Thông qua việc phân tích chuỗi truy cập của người dùng để có thể dự báo những hành vi của người dùng trong quá trình tìm kiếm thông tin

3.2.1 Các kỹ thuật đƣợc sử dụng trong khai phá theo sử dụng Web

Luật kết hợp là một phương pháp quan trọng giúp xác định các trang web mà người dùng thường xuyên truy cập cùng nhau, từ đó phân tích những lựa chọn của khách hàng trong lĩnh vực thương mại điện tử.

Kỹ thuật phân cụm người dùng là phương pháp phân tích các mẫu duyệt web nhằm xác định mối liên hệ giữa người dùng và hành vi trực tuyến của họ Bằng cách này, các nhà nghiên cứu có thể hiểu rõ hơn về sự tương tác của người dùng với nội dung trên mạng.

3.2.1.1 Những v n đ trong khai khá theo sử dụng Web

Khai thác dữ liệu từ Web bao gồm hai bước chính: đầu tiên, cần làm sạch, định nghĩa, tích hợp và biến đổi Web log Sau khi hoàn thành các bước này, chúng ta có thể tiến hành phân tích và khai thác thông tin hiệu quả.

- Cấu trúc vật lý các Website khác nhau từ những mẫu người dùng truy xuất

- Rất khó có thể tìm ra những người dùng, các phiên làm việc, các giao tác

Vấn đề chứng thực phiên người dùng và truy cập Web:

Các phiên chuyển hướng của người dùng là tập hợp các hành động mà người dùng thực hiện từ khi truy cập vào website cho đến khi rời khỏi Những hành động này được ghi lại và lưu trữ trong file đăng nhập, chứa thông tin như địa chỉ IP của máy khách, ngày, thời gian tiếp nhận yêu cầu, các đối tượng yêu cầu, cũng như các thông tin khác như giao thức và kích thước đối tượng.

3.2.2 Quá trình khai phá theo sử dụng Web

Khai phá sử dụng Web có 3 pha [6]: Tiền xử lý, khai phá và phân tích đánh giá, biểu diễn dữ liệu

Chứng thực người dùng và hoạt động truy nhập là những yếu tố quan trọng trong việc xử lý thông tin web Trong giai đoạn này, thông tin đăng nhập sẽ được chuyển đổi thành các mẫu giao tác để phục vụ cho các lĩnh vực khác nhau Đồng thời, cần loại bỏ các file không cần thiết như gif, jpg và bổ sung hoặc xóa bỏ dữ liệu khuyết thiếu từ cache cục bộ và dịch vụ proxy Việc xử lý thông tin từ Cookie, thông tin đăng ký người dùng kết hợp với địa chỉ IP, tên trình duyệt và dữ liệu tạm thời cũng rất quan trọng Cuối cùng, chứng thực giao tác giúp xác thực các phiên người dùng và các giao tác diễn ra.

Sử dụng các phương pháp KPDL trong nhiều lĩnh vực như luật kết hợp, phân tích, thống kê, phân tích đường dẫn, phân lớp và phân cụm giúp khám phá các mẫu hành vi của người dùng một cách hiệu quả.

Phân tích đường dẫn là quá trình nghiên cứu cấu trúc các trang web, trong đó mỗi nút đại diện cho một trang và mỗi cạnh là liên kết giữa các trang Qua việc phân tích này, chúng ta có thể hiểu rõ hơn về mối quan hệ giữa các đường dẫn mà người dùng truy cập, từ đó tối ưu hóa trải nghiệm người dùng và cải thiện hiệu suất của trang web.

Luật kết hợp: Sự tương quan giữa các tham chiếu đến các file khác nhau có trên dịch vụ nhờ việc sử dụng luật kết hợp

Chuỗi các mẫu là tập hợp các phần tử được thu thập từ các giao tác trong một chuỗi thời gian Nó thể hiện sự liên kết giữa các phân tử theo thứ tự thời gian của các giao tác, giúp phân tích và hiểu rõ hơn về mối quan hệ giữa chúng.

Quy tắc phân loại thứ sáu cho rằng profile của các phần tử trong một nhóm riêng biệt dựa trên các thuộc tính chung, như thông tin cá nhân hoặc mẫu truy cập Việc sử dụng profile này giúp phân loại các phần tử dữ liệu mới khi được thêm vào cơ sở dữ liệu.

Phân tích phân cụm: Nhóm các khách hàng lại cùng nhau hoặc các phần tử dữ liệu có các đặc tính tương tự nhau

Khai thác việc sử dụng Web hỗ trợ phát triển và triển khai các chiến lược tiếp thị khách hàng, cả trực tuyến và không trực tuyến Một trong những ứng dụng hiệu quả là hệ thống trả lời tự động cho nhóm khách hàng mục tiêu, giúp tạo ra sự linh hoạt và cá nhân hóa cho từng trang web, đáp ứng tốt hơn nhu cầu của từng khách hàng.

Mô hình phân tích [6] bao gồm thống kê, tìm kiếm tri thức và tác nhân thông minh, nhằm đánh giá tính khả thi và truy vấn dữ liệu phục vụ nhu cầu tiêu dùng của con người Việc trực quan hóa thông tin được thực hiện thông qua Web, sử dụng lược đồ đường dẫn Web để tạo ra đồ thị có hướng OLAP.

Khai phá cấu trúc Web

WWW là mạng lưới thông tin toàn cầu, bao gồm tất cả các trang web có thể liên kết với nhau thông qua các siêu liên kết, giúp người dùng dễ dàng truy cập và tìm kiếm thông tin.

Sinh viên Cao Hữu Hải, lớp CT1601, ngành Công nghệ Thông tin, nhấn mạnh rằng siêu liên kết dẫn đến một trang web khác có thể được xem như một chứng thực cho trang đó Việc sử dụng thông tin ngữ nghĩa rất hữu ích trong việc khai thác thông tin quan trọng thông qua phân tích mối liên kết giữa các trang web.

Khai phá cấu trúc Web nhằm phát hiện thông tin cấu trúc liên kết của các siêu liên kết trong tài liệu, khác với khai phá nội dung Web chỉ tập trung vào cấu trúc bên trong Quá trình này phân loại các trang Web dựa trên mô hình hình học của siêu liên kết, từ đó tạo ra thông tin về độ tương tự và mối quan hệ giữa các Website Khi một trang Web liên kết trực tiếp với trang khác, việc khám phá mối quan hệ giữa chúng giúp xác định sự tương đồng về nội dung hoặc dịch vụ, có thể do cùng một người tạo ra Ngoài ra, khai phá cấu trúc Web cũng khám phá sự phân cấp tự nhiên của các siêu liên kết trong Website của một miền cụ thể, tạo ra luồng thông tin giúp xử lý truy vấn dễ dàng và hiệu quả hơn.

3.3.1 Tiêu chuẩn đánh giá độ tương tự

Khám phá ra một nhóm các trang Web giống nhau để khai phá, ta phải chỉ ra sự giống nhau của hai nút theo một tiêu chuẩn nào đó

Tiêu chuẩn 1(Quan hệ trực tiếp): Đối với mỗi trang Web d 1 và d 2 Ta nói d 1 và d 2 quan hệ với nhau nếu có một liên kết từ d 1 đến d 2 hoặc từ d 2 đến d 1

Tiêu chuẩn 2(Đồng trích dẫn): Độ tương tự giữa d 1 và d 2 được đo bởi số trang dẫn tới cả d 1 và d 2 d d d 1 d 2

Hình 3-3: Quan hệ trực tiếp giữa 2 trang

Tiêu chuẩn 3(Tư ng tự chỉ mục): Độ tương tự giữa d 1 và d 2 được đo bằng số trang mà cả d 1 và d 2 đều trở tới

3.3.2 Khai phá và quản lý cộng đồng Web

Cộng đồng Web là tập hợp các trang Web liên quan đến một lĩnh vực cụ thể Việc nhận diện và hiểu rõ sự phát triển cũng như đặc trưng của các cộng đồng này rất quan trọng Xác định và quản lý các cộng đồng Web có thể được coi là một hình thức khai thác thông tin trên Internet.

- Các trang Web trong cùng một cộng đồng sẽ “tương tự” với nhau hơn các trang Web ngoài cộng đồng

- Mỗi cộng đồng Web sẽ tạo thành một cụm các trang Web

- Các cộng đồng Web được xác định một cách rõ ràng, tất cả mọi người đều biết, nhƣ các nguồn tài nguyên đƣợc liệt kê bởi Yahoo

- Cộng đồng Web đƣợc xác định hoàn chỉnh: Chúng là những cộng đồng bất ngờ xuất hiện

Khai phá cộng đồng Web đang ngày càng được chú trọng và ứng dụng rộng rãi trong thực tiễn Nghiên cứu các phương pháp khám phá cộng đồng mang lại ý nghĩa lớn, đặc biệt trong việc phân tích đồ thị Web để phát hiện các cộng đồng ẩn Một số phương pháp chứng thực cộng đồng Web hiệu quả bao gồm thuật toán HITS, luồng cực đại và nhát cắt cực tiểu, cùng với thuật toán PageRank.

Hình 3-4: Độ tương đồng trích dẫn

Hình 3-5: Độ tương tự chỉ mục

Áp dụng thuật toán trong tìm kiếm và phân cụm tài liệu Web

Sự phát triển của các công cụ tìm kiếm trên Web đã giúp người dùng dễ dàng tìm kiếm thông tin, nhưng không phải lúc nào cũng cho ra kết quả chính xác Để cải thiện trải nghiệm tìm kiếm, chúng ta có thể phân loại kết quả theo từng chủ đề, giúp người dùng nhanh chóng tìm thấy thông tin cần thiết Bài viết này sẽ khám phá kỹ thuật phân cụm tài liệu Web dựa trên kho dữ liệu đã được tìm kiếm và lưu trữ.

3.4.1 Tìm hiểu kỹ thuật phân cụm tài liệu Web

Ngày nay, có nhiều phương pháp đánh giá độ quan trọng của trang web như PageRank và HITS, chủ yếu dựa vào các liên kết để xác định trọng số Một cách tiếp cận khác là đánh giá mức độ quan trọng dựa vào nội dung của tài liệu; nếu các tài liệu có nội dung tương đồng, chúng sẽ có trọng số tương đương và thuộc về cùng một nhóm.

Giả sử có một tập S bao gồm các trang web, nhiệm vụ là tìm ra những trang chứa nội dung câu hỏi truy vấn tạo thành tập R Áp dụng thuật toán phân cụm dữ liệu, chúng ta chia tập R thành k cụm (k đã được xác định) sao cho các phần tử trong cùng một cụm tương đồng nhất, trong khi các phần tử thuộc các cụm khác nhau thì khác biệt Từ tập S-R, các phần tử sẽ được phân loại vào một trong k cụm đã thiết lập Những phần tử nào tương đồng với trọng tâm của cụm (dựa trên một ngưỡng xác định) sẽ được đưa vào cụm đó, còn những phần tử không đáp ứng sẽ bị loại khỏi kết quả Cuối cùng, chúng ta đánh trọng số cho các cụm và các trang trong tập kết quả theo một thuật toán cụ thể.

INPUT: tập dữ liệu D chứa các trang gồm k cụm và k trọng tâm

OUTPUT: trọng số của các trang

Mỗi cụm dữ liệu m và trọng tâm C m được gán một trọng số ts m Đối với bất kỳ hai trọng tâm C i và C j, nếu t i tương tự với truy vấn hơn t j, thì trọng số ts i sẽ lớn hơn trọng số ts j.

Trong một cụm m, trọng số của mỗi trang p được xác định là pw m Đối với bất kỳ hai trọng số pw i và pw j, nếu pw 1 gần trọng tâm hơn pw 2, thì luôn có pw 1 > pw 2.

Như vậy, theo cách tiếp cận này ta sẽ giải quyết được các vấn đề sau:

Kết quả tìm kiếm được phân loại thành các cụm theo các chủ đề khác nhau, giúp người dùng dễ dàng xác định và tìm kiếm thông tin theo nhu cầu cụ thể của mình.

- Quá trình tìm kiếm và xác định trọng số cho các trang chủ yếu tập trung vào nội dung của trang hơn là dựa vào các liên kết trang

- Giải quyết đƣợc vấn đề từ/cụm từ đồng nghĩa trong câu truy vấn của người dùng

- Có thể kết hợp phương pháp phân cụm trong lĩnh vực khai phá dữ liệu với các phương pháp tìm kiếm đã có

3.4.2 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 được thể hiện nhƣ sau :

- Tìm kiếm các trang Web từ các Website thỏa 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 để tự động nhóm các trang web thành các cụm, đảm bảo rằng các trang trong cùng một cụm có nội dung tương tự nhau hơn so với các trang bên ngoài cụm.

3.4.2.1 Tìm ki m dữ liệu trên Web

Giai đoạn này tập trung vào việc sử dụng tập từ khóa tìm kiếm để truy xuất và cung cấp toàn văn tài liệu, tiêu đề, mô tả tóm tắt và URL tương ứng Để cải thiện tốc độ xử lý, các tài liệu này được tìm kiếm và lưu trữ trong kho dữ liệu, tương tự như các công cụ tìm kiếm web như Yahoo và Google Mỗi phần tử bao gồm toàn văn tài liệu, tiêu đề, đoạn mô tả nội dung và URL.

Quá trình làm sạch dữ liệu và chuyển đổi tài liệu thành các dạng biểu diễn dữ liệu thích hợp bao gồm nhiều công việc quan trọng Một trong những bước đầu tiên là chuẩn hóa văn bản, giúp chuyển đổi văn bản thô thành dạng dễ xử lý, từ đó cải thiện độ chính xác và hiệu quả trong các giai đoạn xử lý tiếp theo Việc này bao gồm xóa bỏ các từ dừng, kết hợp các từ có cùng gốc, và số hóa văn bản để đảm bảo rằng dữ liệu được chuẩn bị một cách tối ưu cho các phân tích sau này.

- Xóa các thẻ HTML và các loại thẻ khác để trích ra các từ/cụm từ

- Chuyển các ký tự hoa thành các ký tự thường

- Xóa bỏ các dấu câu, xoá các ký tự trắng dƣ thừa,

Tìm kiếm và trích rút dữ

Biểu diễn dữ Áp dụng thuật toán

Hình 3-6: Các bước phân cụm kết quả tìm kiếm trên Web

Sinh viên: Cao Hữu Hải-Lớp: CT1601-Ngành: Công nghệ Thông tin 51 b Xóa bỏ các từ dừng

Trong quá trình xử lý văn bản, những từ mang ít thông tin và có tần suất xuất hiện thấp hoặc cao nhưng không quan trọng sẽ bị loại bỏ Nghiên cứu cho thấy việc loại bỏ các từ này có thể giảm khoảng 20-30% tổng số từ trong văn bản Các từ như "a", "an", "the", "of", "and", "to", "on", "by" trong tiếng Anh và "thì", "mà", "là", "và", "hoặc" trong tiếng Việt thường không hữu ích cho phân cụm dữ liệu Để đơn giản hóa quy trình, có thể tổ chức một danh sách từ dừng dựa trên định luật Zipf để loại bỏ các từ có tần suất xuất hiện quá thấp hoặc quá cao.

Trong quá trình vector hóa văn bản, việc xây dựng từ điển đóng vai trò quan trọng Từ điển này bao gồm một bảng các từ cùng với chỉ số của chúng, được sắp xếp theo thứ tự.

3.4.2.4 Tách từ, s hóa văn n và biểu di n tài liệu

Tách từ là quá trình xác định và thay thế các từ trong văn bản bằng chỉ số từ điển tương ứng Các mô hình phổ biến để tính toán chỉ số từ bao gồm TF, IDF và TF-IDF Trong bài viết này, chúng ta sẽ sử dụng mô hình TF-IDF để biểu diễn văn bản một cách hiệu quả.

Chúng ta sử dụng mảng W (trọng số) hai chiều kích thước m x n, trong đó n đại diện cho số lượng tài liệu và m là số từ trong từ điển Mỗi hàng thứ j trong mảng W là một vector biểu diễn cho tài liệu thứ j trong cơ sở dữ liệu, trong khi mỗi cột thứ i tương ứng với thuật ngữ thứ i trong từ điển Giá trị W ij thể hiện trọng số của từ i đối với tài liệu j.

Trong giai đoạn này, chúng ta tiến hành thống kê tần số xuất hiện của từ t i trong tài liệu d j và số lượng tài liệu chứa từ t i Dựa trên thông tin này, bảng trọng số của ma trận W được xây dựng theo công thức đã định.

Tần số xuất hiện của từ t i trong tài liệu d j được ký hiệu là Tf ij, trong khi nghịch đảo tần số xuất hiện của từ t i trong tài liệu d j được ký hiệu là idf ij Số lượng tài liệu mà từ t i xuất hiện được gọi là h i, và n là tổng số tài liệu.

Thực nghiệm

Sử dụng phần mềm Orange data mining để thực hiện phân cụm dữ liệu

Dữ liệu ban đầu bao gồm 100 file text được đặt tên từ file001 đến file100 Sau đó, dữ liệu này được chuẩn hóa theo các cụm chủ đề như Kinh tế, Chính trị, Khoa học, Công nghệ, Giáo dục, Giải trí và Y tế, sử dụng file CSV trong Excel để lưu trữ.

- Dữ liệu đã đƣợc phân cụm bằng Orange

Quá trình phân cụm dữ liệu bằng Orange :

Hình 3-7: Mô hình phân cụm dữ liệu trên Orange

Hình 3-8: Đƣ dữ liệu chuẩn hóa và mô hình

Hình 3-10: Do khoảng cách bằng Euclidean

Hình 3-11: Phân cụm dữ liệu theo phương pháp phân cụm phân cấp

Hình 3-12: Dữ liệu sau khi phân cụm phân cấp

Hình 3-13: Phân cụm bằng k-means

 Đo khoảng cách bằng Euclidean, cho thấy 8 cụm thì thuật toán là tối ƣu nhất

Hình 3-14: Biểu diễn dữ liệu sau khi phân cụm k-means

Chương này giới thiệu các phương pháp khai phá Web, bao gồm khai phá dữ liệu toàn văn từ tài liệu Web, khai phá cấu trúc Web và khai phá hành vi sử dụng Web Bên cạnh đó, tác giả cũng đề cập đến một số thuật toán hiện đang được áp dụng trong lĩnh vực khai phá Web.

Trong phần này, chúng tôi sẽ trình bày quy trình phân cụm dữ liệu sử dụng phương pháp phân cụm phân cấp và thuật toán k-means, thông qua phần mềm mô hình hóa Orange Data.

Định dạng
Số trang	69
Dung lượng	2,59 MB