Nghiên Cứu Phương Pháp Phân Cụm Nửa Giám Sát Ứng Dụng Cho Dữ Liệu Web Server Logs

Luận văn thạc sĩ toán học phân tích nghiên cứu một số phương pháp phân cụm nửa giám sát ứng dụng cho bài toán phân cụm dữ liệu web, đánh giá thực trạng, chỉ ra hạn chế, đề xuất

• Tác giả: Nguyễn Đức Ngọc
• Người hướng dẫn: TS. Vũ Việt Vũ
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phương Pháp Phân Cụm Nửa Giám Sát Cho Dữ Liệu Web Server Logs
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• 1. MỞ ĐẦU
• 1.1. Khái niệm về học máy và bài toán phân cụm dữ liệu
• 1.2. Nội dung nghiên cứu của luận văn
• 1.3. Một số phương pháp phân cụm dữ liệu cơ bản
• 1.3.1. Phương pháp phân cụm K-Means
• 1.3.2. Phương pháp phân cụm DBSCAN
• 1.3.3. Phương pháp phân cụm dựa trên đồ thị (GC)
• 1.4. Ứng dụng của phân cụm dữ liệu
• 2. MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT CƠ BẢN
• 2.1. Tổng quan về phân cụm nửa giám sát
• 2.2. Thuật toán phân cụm nửa giám sát dựa trên K-Means
• 2.2.1. Thuật toán COP-KMeans
• 2.2.2. Thuật toán Seed K-Means
• 2.3. Thuật toán phân cụm nửa giám sát dựa trên mật độ: SSDBSCAN
• 2.4. Thuật toán phân cụm nửa giám sát dựa trên đồ thị (SSGC)
• 3. KẾT QUẢ THỰC NGHIỆM
• 3.1. Giới thiệu về dữ liệu web server logs
• 3.2. Tiền xử lý dữ liệu
• 3.3. Phương pháp đánh giá chất lượng phân cụm
• 3.4. Thuật toán phân cụm
• 3.5. Kết quả phân cụm trên tập web server logs
• KẾT LUẬN
• Những kết quả đã đạt được
• Hướng phát triển tiếp theo của đề tài
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phương Pháp Phân Cụm Nửa Giám Sát

Phương pháp phân cụm nửa giám sát là một kỹ thuật quan trọng trong lĩnh vực học máy, đặc biệt là trong việc phân tích dữ liệu từ các dữ liệu web server logs. Kỹ thuật này kết hợp giữa học có giám sát và không giám sát, giúp cải thiện độ chính xác trong việc phân loại và phân cụm dữ liệu. Việc áp dụng phương pháp này cho phép khai thác thông tin từ các tập dữ liệu lớn mà không cần phải gán nhãn cho tất cả các điểm dữ liệu.

1.1. Khái Niệm Về Phân Cụm Nửa Giám Sát

Phân cụm nửa giám sát là một phương pháp học máy, trong đó một phần dữ liệu được gán nhãn và phần còn lại không. Điều này giúp cải thiện khả năng phân loại và phân cụm, đặc biệt trong các bài toán như phân tích dữ liệu từ web server logs.

1.2. Lợi Ích Của Phương Pháp Này

Phương pháp phân cụm nửa giám sát giúp tiết kiệm thời gian và công sức trong việc gán nhãn dữ liệu. Nó cũng cho phép khai thác thông tin từ các tập dữ liệu lớn mà không cần phải gán nhãn cho tất cả các điểm dữ liệu, từ đó nâng cao hiệu quả phân tích.

II. Thách Thức Trong Phân Tích Dữ Liệu Web Server Logs

Phân tích dữ liệu web server logs gặp nhiều thách thức, bao gồm việc xử lý khối lượng dữ liệu lớn và đa dạng. Các vấn đề như dữ liệu không đồng nhất, thiếu thông tin và nhiễu có thể ảnh hưởng đến kết quả phân tích. Việc áp dụng phương pháp phân cụm nửa giám sát có thể giúp giải quyết một số vấn đề này.

2.1. Khối Lượng Dữ Liệu Lớn

Dữ liệu từ web server logs thường rất lớn và đa dạng, điều này gây khó khăn trong việc phân tích và xử lý. Phân cụm nửa giám sát giúp giảm thiểu khối lượng dữ liệu cần xử lý bằng cách chỉ sử dụng một phần dữ liệu đã được gán nhãn.

2.2. Dữ Liệu Không Đồng Nhất

Dữ liệu từ các nguồn khác nhau có thể không đồng nhất về định dạng và cấu trúc. Phân cụm nửa giám sát cho phép xử lý các loại dữ liệu khác nhau một cách hiệu quả hơn, từ đó cải thiện độ chính xác của phân tích.

III. Phương Pháp Phân Cụm Nửa Giám Sát Hiệu Quả

Có nhiều phương pháp phân cụm nửa giám sát khác nhau, bao gồm K-Means, DBSCAN và các thuật toán dựa trên đồ thị. Mỗi phương pháp có ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả tốt nhất trong phân tích dữ liệu.

3.1. Thuật Toán K Means

K-Means là một trong những thuật toán phân cụm phổ biến nhất. Nó hoạt động bằng cách phân chia dữ liệu thành k cụm dựa trên khoảng cách đến các trọng tâm. Phương pháp này đơn giản và hiệu quả, nhưng có thể gặp khó khăn với các cụm có hình dạng phức tạp.

3.2. Thuật Toán DBSCAN

DBSCAN là một thuật toán phân cụm dựa trên mật độ, cho phép phát hiện các cụm có hình dạng bất kỳ. Nó có khả năng xử lý nhiễu và không yêu cầu số lượng cụm k phải được xác định trước.

IV. Ứng Dụng Thực Tiễn Của Phân Cụm Nửa Giám Sát

Phân cụm nửa giám sát có nhiều ứng dụng thực tiễn trong việc phân tích dữ liệu web server logs. Nó giúp xác định các nhóm người dùng có cùng sở thích và xu hướng truy cập, từ đó tối ưu hóa nội dung trên website.

4.1. Tối Ưu Hóa Nội Dung Website

Bằng cách phân tích dữ liệu từ web server logs, các nhà quản lý có thể xác định các nhóm người dùng và tối ưu hóa nội dung để đáp ứng nhu cầu của họ. Điều này giúp cải thiện trải nghiệm người dùng và tăng cường hiệu quả kinh doanh.

4.2. Phân Tích Hành Vi Người Dùng

Phân cụm nửa giám sát cho phép phân tích hành vi người dùng từ các vết truy cập trên website. Điều này giúp các nhà quản lý hiểu rõ hơn về cách người dùng tương tác với nội dung và cải thiện chiến lược tiếp thị.

V. Kết Luận Về Phân Cụm Nửa Giám Sát

Phân cụm nửa giám sát là một phương pháp mạnh mẽ trong việc phân tích dữ liệu web server logs. Nó không chỉ giúp cải thiện độ chính xác trong phân tích mà còn tiết kiệm thời gian và công sức trong việc gán nhãn dữ liệu. Tương lai của phương pháp này hứa hẹn sẽ mang lại nhiều ứng dụng mới trong lĩnh vực học máy.

5.1. Tương Lai Của Phân Cụm Nửa Giám Sát

Với sự phát triển không ngừng của công nghệ và dữ liệu lớn, phương pháp phân cụm nửa giám sát sẽ ngày càng trở nên quan trọng. Nó sẽ tiếp tục được nghiên cứu và cải tiến để đáp ứng nhu cầu ngày càng cao trong phân tích dữ liệu.

5.2. Các Hướng Nghiên Cứu Tiếp Theo

Các nghiên cứu tiếp theo có thể tập trung vào việc cải thiện các thuật toán phân cụm nửa giám sát, cũng như áp dụng chúng vào các lĩnh vực khác nhau như y tế, tài chính và thương mại điện tử.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của công nghệ thông tin và làn sóng chuyển đổi số trong kỷ nguyên Cách mạng công nghiệp 4.0 đã dẫn đến sự tích lũy khổng lồ của dữ liệu máy chủ với quy mô hàng trăm Gigabyte và Terabyte mỗi ngày. Trong bối cảnh hàng triệu cơ sở dữ liệu vận hành liên tục, việc khai thác tri thức từ nhật ký truy cập máy chủ web (web server logs) trở thành bài toán cấp thiết nhằm thấu hiểu hành vi người dùng và tối ưu hóa hệ thống thông tin. Tuy nhiên, các kỹ thuật phân cụm không giám sát truyền thống như K-Means hay DBSCAN bộc lộ nhiều điểm nghẽn nghiêm trọng, đặc biệt là sự nhạy cảm với việc chọn tâm ngẫu nhiên ban đầu và khó khăn khi xử lý cụm có hình dạng hay mật độ phức tạp.

Nghiên cứu của học viên Nguyễn Đức Ngọc, dưới sự hướng dẫn khoa học của Tiến sĩ Vũ Việt Vũ tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên (chuyên ngành Khoa học máy tính, mã số 8480101, năm 2018), tập trung giải quyết bài toán này thông qua phương pháp phân cụm nửa giám sát (semi-supervised clustering). Đề tài đặt mục tiêu nghiên cứu và làm chủ các mô hình phân cụm nửa giám sát tiêu biểu gồm Seed K-Means, SSDBSCAN và thuật toán phân cụm dựa trên đồ thị SSGC, từ đó ứng dụng trực tiếp vào việc phân tích dữ liệu web log thực tế.

Phạm vi thực nghiệm của công trình được triển khai trên tập dữ liệu gồm 4.745 địa chỉ IP truy cập độc lập vào hệ thống cổng thông tin giáo dục điện tử thu thập trong ngày 03 tháng 4 năm 2018. Ý nghĩa khoa học và thực tiễn của nghiên cứu được đo lường cụ thể qua việc phân tách thành công 6 cụm hành vi người dùng chuyên biệt, ứng dụng chỉ số Rand Index (RI) đạt giá trị tiệm cận tối ưu nhằm hỗ trợ các nhà quản trị mạng tái cấu trúc website, nâng cao khoảng 20% đến 30% hiệu suất tìm kiếm thông tin của người truy cập.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng của hai trụ cột lý thuyết vững chắc: Lý thuyết Khai phá dữ liệu web (Web Mining) và Lý thuyết Học máy nửa giám sát (Semi-supervised Learning). Khai phá dữ liệu web được chia thành 3 phân nhánh chính: khai phá nội dung (web content mining), khai phá cấu trúc (web structure mining) và khai phá hành vi người dùng (web usage mining). Luận văn đi sâu vào phân nhánh khai phá hành vi nhằm phát hiện các mẫu tương tác ẩn thông qua các vết truy cập máy chủ.

Các khái niệm then chốt được áp dụng xuyên suốt bao gồm:

1. Thông tin bổ trợ (Side Information): Dữ liệu tri thức ngoài do chuyên gia cung cấp dưới dạng các mẫu gán nhãn đại diện ban đầu (seed) hoặc các cặp ràng buộc.
2. Ràng buộc Must-link và Cannot-link: Tập quy tắc xác định hai điểm dữ liệu bắt buộc phải thuộc cùng một cụm hoặc bắt buộc phải thuộc hai cụm khác nhau.
3. Đồ thị k-láng giềng gần nhất (k-NN Graph): Cấu trúc đồ thị vô hướng có trọng số thể hiện mối quan hệ tương đồng cục bộ giữa các đối tượng dữ liệu dựa trên số lượng láng giềng chung.
4. Cây khung nhỏ nhất (Minimum Spanning Tree - MST): Giải thuật được tích hợp trong SSDBSCAN để mở rộng cụm từ các điểm hạt giống dựa trên khoảng cách tiếp cận mật độ rDist.

Phương pháp nghiên cứu

Nguồn dữ liệu thực nghiệm được trích xuất trực tiếp từ tệp nhật ký máy chủ web của một trường đại học lớn vào ngày 03 tháng 4 năm 2018. Sau giai đoạn làm sạch và loại bỏ các truy cập không hợp lệ từ máy chủ tìm kiếm tự động, tập dữ liệu đạt cỡ mẫu 4.745 địa chỉ IP người dùng duy nhất. Dữ liệu thô ban đầu trải rộng trên 255 ký hiệu chỉ mục truy cập đã được chuẩn hóa và thu gọn thành 24 trường chuyên mục chính thống (như Tin tức sự kiện, Tuyển sinh, Đào tạo, Khoa học công nghệ, Sinh viên, Hợp tác phát triển).

Phương pháp chọn mẫu áp dụng là phương pháp lấy mẫu toàn bộ nhật ký trong khung thời gian cố định (census log sampling) kết hợp chọn mẫu có chủ đích để xác định 6 điểm hạt giống (seed) ban đầu đại diện cho 6 phân nhóm hành vi. Lý do lựa chọn thuật toán Seed K-Means và SSGC làm phương pháp phân tích trọng tâm nằm ở khả năng kiểm soát độ phức tạp tính toán: Seed K-Means duy trì độ phức tạp mức tuyến tính O(nk) nhưng triệt tiêu hoàn toàn sự dao động kết quả nhờ gán tâm hạt giống cố định; trong khi đó SSGC giảm độ phức tạp thời gian từ mức O(nN^2) của SSDBSCAN xuống O(n^2) hoặc O(nlogn), mang lại tốc độ thực thi vượt trội trên các tập dữ liệu quy mô lớn. Đánh giá độ chính xác của mô hình được thực hiện định lượng thông qua chỉ số Rand Index với thang điểm chuẩn hóa từ 0 đến 1.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đối chiếu mô hình đã mang lại 4 phát hiện quan trọng:

Thứ nhất, việc tiền xử lý và chuyển đổi dữ liệu nhật ký web sang ma trận vector nhị phân kích thước 4.745 hàng và 24 cột đã giúp cô đọng 255 chỉ mục ban đầu, giảm hơn 90,5% không gian chiều dữ liệu mà vẫn bảo toàn đầy đủ các đặc trưng tương tác cốt lõi của người dùng.

Thứ hai, thuật toán Seed K-Means đã khắc phục triệt để nhược điểm lớn nhất của K-Means truyền thống. Với 6 hạt giống đại diện được chỉ định cho 6 cụm, thuật toán hội tụ và cho ra kết quả phân cụm duy nhất, chính xác ngay sau 1 lần thực thi duy nhất, loại bỏ hoàn toàn sự phụ thuộc vào bước khởi tạo ngẫu nhiên vốn có thể làm sai lệch 15% đến 25% độ chính xác giữa các lần chạy.

Thứ ba, thuật toán phân cụm nửa giám sát dựa trên đồ thị (SSGC) chứng minh hiệu năng vượt trội khi so sánh với thuật toán SSDBSCAN. Kết quả đo đạc tốc độ xử lý cho thấy SSGC thực thi nhanh hơn khoảng 20 lần so với SSDBSCAN trên cùng tập dữ liệu chuẩn, đồng thời giải quyết triệt để bài toán nhận dạng các cụm có hình dạng tùy ý và mật độ chênh lệch.

Thứ tư, 4.745 người dùng truy cập được phân tách rõ nét thành 6 cụm riêng biệt: Cụm 1 tập trung người dùng tra cứu văn bản đào tạo và đề cương môn học (chiếm khoảng 32% lưu lượng); Cụm 2 chuyên biệt về tin tức tuyển sinh và chỉ dẫn hồ sơ; các cụm còn lại phân bố vào hợp tác quốc tế, nghiên cứu khoa học và hoạt động sinh viên.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp các mô hình nửa giám sát đạt hiệu quả vượt trội là việc tích hợp tri thức tiền nghiệm (prior knowledge) từ chuyên gia thông qua các hạt giống (seed). Trong K-Means thông thường, các trọng tâm khởi tạo ngẫu nhiên dễ rơi vào các cực tiểu cục bộ (local minima). Ngược lại, Seed K-Means sử dụng vector hạt giống để cố định tâm ban đầu, dẫn dắt thuật toán hội tụ trực tiếp về các nhóm hành vi thực tế. Đối với dữ liệu phức tạp, thuật toán SSGC sử dụng cơ chế ngưỡng phân cắt thích ứng trên đồ thị k-NN, cho phép nhận diện biên cụm chính xác mà không cần người dùng can thiệp tinh chỉnh thủ công các tham số bán kính lân cận phức tạp như trong DBSCAN.

Trong thực tế triển khai, các kết quả này có thể được trực quan hóa sinh động thông qua biểu đồ phân tán hai chiều (2D Scatter Plot) kết hợp phân tích thành phần chính (PCA) để thể hiện sự phân rã của 6 cụm hành vi. Đồng thời, bảng ma trận đối sánh thời gian thực thi (Execution Time Table) và đồ thị đường biểu diễn chỉ số Rand Index sẽ minh chứng rõ nét tính ưu việt của mô hình SSGC và Seed K-Means so với các phương pháp không giám sát cổ điển.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu, tác giả đề xuất 4 nhóm giải pháp kỹ thuật có tính ứng dụng cao:

1. Tái cấu trúc kiến trúc thông tin website: Bộ phận Quản trị cổng thông tin và Kỹ sư giao diện cần tiến hành sắp xếp lại các liên kết trên trang chủ dựa theo 6 nhóm chuyên mục đã được phân cụm, hướng tới mục tiêu giảm 25% số lần nhấp chuột thừa của người dùng trong thời gian 3 tháng tới.
2. Tích hợp module gợi ý liên kết thông minh: Đội ngũ Kỹ sư phát triển phần mềm cần triển khai thuật toán Seed K-Means trực tiếp vào hệ thống quản trị nội dung (CMS) nhằm tự động gợi ý các bài viết liên quan dựa trên chuyên mục mà người dùng đang truy cập, đặt mục tiêu tăng 30% thời gian lưu trang (time on site) trong vòng 6 tháng.
3. Tự động hóa quy trình phân tích nhật ký máy chủ: Nhóm Vận hành hạ tầng dữ liệu cần thiết lập luồng xử lý tự động trích xuất file log hàng ngày thành ma trận vector 24 chiều, giúp giảm 50% thời gian xử lý dữ liệu thủ công định kỳ trong quý 1 tới.
4. Nghiên cứu mở rộng thuật toán SSGC trên nền tảng dữ liệu lớn: Nhóm Nghiên cứu trí tuệ nhân tạo cần thử nghiệm cài đặt thuật toán SSGC trên các khung tính toán phân tán như Apache Spark để xử lý các tệp nhật ký quy mô hàng triệu bản ghi, hướng tới tối ưu hóa 20 lần tốc độ xử lý log thời gian thực trong vòng 12 tháng.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị tham khảo thiết thực cho 4 nhóm đối tượng cụ thể:

1. Học viên cao học và sinh viên chuyên ngành Khoa học máy tính, Công nghệ thông tin: Tài liệu là nguồn tham khảo mẫu mực về quy trình thực hiện một đề tài nghiên cứu từ lý thuyết giải thuật học máy (K-Means, DBSCAN, SSGC) đến xây dựng mô hình thực nghiệm chi tiết.
2. Kỹ sư dữ liệu và chuyên gia Khai phá dữ liệu web (Data Engineers & Web Mining Specialists): Cung cấp phương pháp luận thực chiến về kỹ thuật tiền xử lý dữ liệu log máy chủ thô, chuyển đổi địa chỉ IP và mã chỉ mục thành không gian vector nhị phân phục vụ phân tích chuyên sâu.
3. Chuyên gia thiết kế trải nghiệm người dùng và Quản trị viên cổng thông tin (UX/UI Designers & Webmasters): Cung cấp cơ sở khoa học định lượng để thấu hiểu luồng di chuyển của khách truy cập, từ đó bố trí layout, danh mục điều hướng website hợp lý và tối ưu hóa chuyển đổi.
4. Giảng viên và nhà nghiên cứu trong lĩnh vực Trí tuệ nhân tạo: Sử dụng làm tài liệu giảng dạy chuyên đề về Học máy nửa giám sát và các biến thể nâng cao của thuật toán gom cụm trên đồ thị.

Câu hỏi thường gặp

1. Phân cụm nửa giám sát khác biệt như thế nào so với phân cụm không giám sát truyền thống? Phân cụm nửa giám sát kết hợp một lượng nhỏ thông tin bổ trợ như các điểm dữ liệu đã gán nhãn ban đầu (seed) hoặc các cặp ràng buộc (must-link, cannot-link) vào quá trình phân nhóm. Việc bổ sung tri thức này giúp định hướng thuật toán phân tách chính xác hơn, tránh rơi vào các cụm cục bộ sai lệch mà phương pháp không giám sát thuần túy thường gặp phải.

2. Tại sao thuật toán Seed K-Means lại được ưu tiên sử dụng trong thực nghiệm log web của luận văn? Thuật toán Seed K-Means giải quyết triệt để điểm yếu chí mạng của K-Means truyền thống là tính bất định khi chọn tâm ngẫu nhiên. Bằng cách gán trực tiếp các điểm hạt giống đại diện cho từng chuyên mục, thuật toán đạt kết quả phân cụm chính xác và cố định chỉ sau 1 lần thực hiện, duy trì độ phức tạp tính toán thấp ở mức O(nk).

3. Việc thu gọn 255 ký hiệu chỉ mục thành 24 chuyên mục có làm mất mát thông tin quan trọng không? Phương pháp thống kê gộp 255 mã chỉ mục về 24 chuyên mục chính giúp loại bỏ các biến phụ trùng lặp và hiện tượng bùng nổ số chiều. Thao tác này giúp ma trận dữ liệu nhị phân 4.745 x 24 giữ trọn vẹn đặc trưng hành vi cốt lõi của người dùng, đồng thời tối ưu hóa tài nguyên tính toán và nâng cao độ chính xác phân cụm.

4. Chỉ số Rand Index (RI) được tính toán như thế nào để đánh giá chất lượng phân cụm? Chỉ số Rand Index đo lường mức độ tương đồng giữa kết quả phân cụm mô hình với nhãn thực tế dựa trên tỷ lệ các cặp điểm dữ liệu được gán đúng cùng cụm hoặc khác cụm. Giá trị RI dao động từ 0 đến 1; chỉ số càng tiệm cận 1 chứng minh thuật toán phân cụm có độ chính xác và độ tin cậy càng cao.

5. Thuật toán SSGC có ưu thế gì vượt trội so với SSDBSCAN khi xử lý cụm có mật độ khác nhau? Thuật toán SSGC xây dựng đồ thị k-láng giềng gần nhất kết hợp cơ chế lan truyền nhãn tự động, giúp nhận diện chính xác các cụm có hình dạng tùy ý và mật độ bất kỳ. Đặc biệt, các kiểm chứng thực nghiệm đã chứng minh SSGC đạt tốc độ xử lý nhanh hơn khoảng 20 lần so với SSDBSCAN.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về học máy nửa giám sát và các thuật toán phân cụm hiện đại gồm Seed K-Means, SSDBSCAN và SSGC.
• Đề xuất quy trình tiền xử lý chuẩn hóa tệp web server logs thô thành ma trận nhị phân 24 chiều trên tập mẫu 4.745 địa chỉ IP người dùng thực tế.
• Chứng minh tính hiệu quả của giải thuật Seed K-Means trong việc loại bỏ tính bất định của K-Means và ghi nhận tốc độ vượt trội gấp 20 lần của SSGC so với SSDBSCAN.
• Phân tách thành công 6 cụm hành vi người dùng trực quan, tạo cơ sở định lượng vững chắc cho bài toán tối ưu hóa cấu trúc website trường đại học.
• Kế hoạch phát triển trong 6 đến 12 tháng tới tập trung mở rộng tích hợp đồng thời ràng buộc must-link/cannot-link vào mô hình đồ thị và thử nghiệm trên tập dữ liệu lớn.

Quý độc giả, nhà nghiên cứu và kỹ sư dữ liệu quan tâm đến lĩnh vực khai phá dữ liệu web hãy áp dụng ngay phương pháp phân cụm nửa giám sát để nâng cao hiệu năng phân tích hành vi người dùng trong hệ thống của mình!

Trích đoạn nội dung tài liệu

MỞ ĐẦU Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng, phần mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế - xã hội nói riêng. Việc thu thập thông tin cũng như nhu cầu lưu trữ thông tin càng ngày càng lớn. Bên cạnh đó việc tin học hoá một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu Cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý., trong đó có nhiều Cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte.

Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kĩ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật Khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền Công nghệ thông tin thế giới hiện nay. Một vấn đề được đặt ra là phải làm sao trích chọn được những thông tin có ý nghĩa từ tập dữ liệu lớn để từ đó có thể giải quyết được các yêu cầu của thực tế như trợ giúp ra quyết định, dự đoán,… và Khai phá dữ liệu (Data mining) đã ra đời nhằm giải quyết các yêu cầu đó. Khai phá dữ liệu được định nghĩa là: Quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các Cơ sở dữ liệu, kho dữ liệu….

Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như: Khai phá tri thức từ Cơ sở dữ liệu (knowlegde mining from databases), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredging). Nhiều người coi khai phá dữ liệu và một thuật ngữ thông dụng khác là khám phá tri thức trong Cơ sở dữ 2 liệu(Knowlegde Discovery in Databases – KDD) là như nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình Khám phá tri thức trong Cơ sở dữ liệu. Ngay từ những ngày đầu khi xuất hiện, Data mining đã trở thành một trong những xu hướng nghiên cứu phổ biến trong lĩnh vực học máy tính và công nghệ tri thức.

Nhiều thành tựu nghiên cứu của Data mining đã được áp dụng trong thực tế. Data mining có nhiều hướng quan trọng và một trong các hướng đó là phân cụm dữ liệu (Data Clustering ). Phân cụm dữ liệu là quá trình tìm kiếm để phân ra các cụm dữ liệu, các mẫu dữ liệu từ tập Cơ sở dữ liệu lớn. Phân cụm dữ liệu là một phương pháp học không giám sát.

Trong những năm trở lại đây, do phương pháp phân cụm dữ liệu không giám sát còn một số hạn chế vì vậy dựa trên học không giám sát và học có giám sát đã ra đời một phương pháp phân cụm dữ liệu mới đó là phương pháp phân cụm dữ liệu nửa giám sát. Phương pháp phân cụm nửa giám sát không phải là một phương pháp phân cụm hoàn thiện nhưng nó đã phần nào khắc phục được những hạn chế và phát huy ưu điểm của phương pháp phân cụm không giám sát. Khái niệm về học máy và bài toán phân cụm dữ liệu Học máy (Machine Learning) là một nhánh nghiên cứu của Trí tuệ nhân tạo nhằm xây dựng các thuật toán thực hiện trên hệ thống máy tính có thể học được qua các dữ liệu mẫu thống kê có sẵn. Trí tuệ nhân tạo (artificial intelligence) gồm rất nhiều lĩnh vực nghiên cứu [1].1 minh họa các hướng nghiên cứu trong lĩnh vực trí tuệ nhân tạo.

Chúng ta có thể kể đến học máy, học sâu, nhận dạng đối tượng, các hệ thống tự động, xử lý ngôn ngữ tự nhiên, trợ lý ảo,… Trí tuệ nhân tạo là một trong ba trụ cột của cuộc cách mạng công nghiệp 4.0 cùng với dữ liệu lớn (Big Data) và Internet vận vật. Các hướng nghiên cứu của Trí tuệ nhân tạo [1] Trên thực tế có 4 dạng học cơ bản bao gồm: - Học có giám sát: Máy tính được học một số mẫu gồm đầu vào (Input) và đầu ra (Output) tương ứng trước. Sau khi học xong các mẫu này, máy tính 4 quan sát một đầu vào mới và tính toán, suy diễn ra kết quả tương ứng cho đầu vào đó. Đối với loại học này sẽ có hai pha là pha huấn luyện (training) và pha kiểm thử (testing).

- Học không giám sát: Máy tính chỉ được xem các mẫu thu thập được không có nhãn tương ứng, sau đó máy tính phải tự tìm cách phân loại các mẫu này (clustering – phân cụm) hoặc tìm ra mối quan hệ giữa các mẫu (association rule – luật kết hợp), các điểm dị thường của tập mẫu (outlier), giảm số chiều của tập mẫu (PCA),… - Học nửa giám sát: Một dạng lai giữa hai nhóm học trên. Trong trường hợp này hệ thống sẽ được cung cấp một lượng nhỏ các mẫu và tùy từng mục tiêu bài toán chúng ta phát triển các phương pháp phân lớp nửa giám sát (semi-supervised classification) hoặc phân cụm nửa giám sát (semi- supervised clustering). - Học tăng cường: Máy tính đưa ra quyết định hành động (action) và nhận kết quả phản hồi (response/reward) từ môi trường (environment). Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành động của mình.

Ngoài ra trong khoảng 10 năm trở lại đây nghiên cứu về học sâu hay học đa lớp (Deep learning) đã được quan tâm rất nhiều. Học sâu bản chất là dựa trên mạng Nơ ron nhiều lớp. Dựa vào sự phát triển rất mạnh mẽ của công nghệ và các hệ thống tính toán đã đáp ứng được với khối lượng phép tính khổng lồ của các hệ thống học sâu. Tuy nhiên chất lượng của học sâu đã chứng minh là tốt hơn hẳn các phương pháp học khác cho một số bài toán như nhận dạng đối tượng trên ảnh, xử lý ngôn ngữ tự nhiên,… Học sâu cũng được ứng dụng cho bài toán trích chọn đặc trưng, một dạng bài toán học không giám sát.

Các lĩnh vực liên quan với học máy Hình 1.2 trình bày các lĩnh vực liên quan đến học máy, chúng ta thấy để nghiên cứu vấn đề học máy cần có có kiến thức về lĩnh vực như xác suất, đại số tuyến tính, tối ưu hóa, lý thuyết học thống kê,… Học máy có ứng dụng rộng khắp các ngành khoa học/ sản xuất, đặc biệt là đối với những ngành cần phân tích khối lượng dữ liệu khổng lồ. Một số ứng dụng phổ biến của học máy là: - Xử lý ngôn ngữ tự nhiên (Natural Language Processing): Xử lý văn bản, giao tiếp người – máy, … - Nhận dạng (Pattern Recognition): Nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy (Computer Vision) … - Tìm kiếm (Search Engine) - Chẩn đoán trong y tế: Phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động. 6 - Tin sinh học: Phân loại chuỗi gene, quá trình hình thành gene/protein. - Vật lý: Phân tích ảnh thiên văn, tác động giữa các hạt … - Phát hiện gian lận tài chính (financial fraud): Gian lận thẻ tín dụng.

- Phân tích thị trường chứng khoán (stock market analysis) - Chơi trò chơi: Tự động chơi cờ, hành động của các nhân vật ảo,. Robot là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/ bộ não của người máy. Nội dung nghiên cứu của luận văn Với các khái niệm như đã trình bày, học máy là một lĩnh vực có nhiều vấn đề cần nghiên cứu cũng như rất nhiều các ứng dụng thực tế. Trong luận văn của mình tác giả mong muốn tìm hiểu và nghiên cứu các vấn đề sau đây: - Nghiên cứu và tìm hiểu các thuật toán phân cụm dữ liệu cơ bản.

- Nghiên cứu và nắm bắt một số thuật toán phân cụm nửa giám sát bao gồm thuật toán phân cụm nửa giám sát K-Means, thuật toán SSDBSCAN, và thuật toán phân cụm nửa giám sát dựa trên đồ thị SSGC. - Lập trình ứng dụng cho bài toán phân cụm dữ liệu web server logs – dữ liệu ghi các truy xuất của khách hàng đến các website. Bài toán phân cụm dữ liệu người sử dụng web có ý nghĩa rất quan trọng trong việc xác định các nhóm người sử dụng có cùng sở thích, có cùng xu hướng truy cập thông tin giúp cho các nhà quản lý bố trí các nội dung trên web cho tối ưu; chẳng hạn như các trang thương mại điện tử hiện nay thì việc phân tích dữ liệu khách hàng khi truy cập vào website là không thể bỏ qua. Các bài toán khai phá dữ liệu trên web (web mining) [2] Các bài toán khai phá dữ liệu trên web gồm khai phá nội dung web, khai phá dữ liệu người dùng web và khai phá dữ liệu cấu trúc web (xem hình 1.

Với các vấn đề này chúng ta có thể sử dụng các công cụ học máy như phân cụm, phân lớp, phương pháp luật kết hợp. Bài toán khai phá nội dung web (web content mining) nhằm mục đích khai phá các dữ liệu từ các trang web. Dữ liệu thường là văn bản, video,… Hiện nay số lượng website là rất lớn vấn đề đặt ra là phân loại, trích chọn thông tin, tìm các thông tin quý là một nhu cầu rất thiết yếu. Bài toán khai phá dữ liệu cấu trúc website (web structure mining) nhằm mục đích tìm các mối liên hệ giữa các cấu trúc website.

Các loại dữ liệu này thường biểu diễn dưới dạng đồ thị. Và bài toán khai phá dữ liệu đồ thị là một trong những lớp bài toán được quan tâm rất nhiều trong nghiên cứu và ứng dụng. Bài toán khai phá dữ liệu người dùng web (web usage mining) nhằm mục đích tìm ra các mẫu, các quy luật của người dùng từ các vết truy nhập 8 website của người sử dụng. Quá trình truy nhập website của người dùng sẽ được ghi lại trên máy chủ và gọi là web server logs.

Các thông tin cơ bản được lưu trữ lại như địa chỉ IP, thời gian truy nhập, tên đường liên kết của website,… Trong luận văn của mình tôi chọn nghiên cứu tìm hiểu bài toán phân cụm cho dữ liệu người dùng website. Cấu trúc của các dữ liệu web server logs như sau: TT Nội dung web server logs 2006-02-01 00:08:43 1.4 - GET /classes/cs589/papers.6 - GET /classes/cs480/announce.1;+SV1) http://maya.edu/~classes/cs480/ 2006-02-02 19:34:45 3.6 - GET/classes/cs480/header.1;+SV1) http://maya.edu/~classes/cs480/announce.