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ĩ nghiên cứu phương pháp phân cụm nửa giám sát cho bài toán phân cụm dữ liệu web server logs, mang lại giải pháp hiệu quả.

• Tác giả: Nguyễn Đức Ngọc
• Người hướng dẫn: TS. Vũ Việt Vũ
• Trường học: 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
• Đề tài: 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 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

• LỜI CẢM ƠN
• MỞ ĐẦU
• 1. CHƯƠNG 1: KHÁI NIỆM VỀ HỌC MÁY VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU
• KẾT LUẬN
• TÀI LIỆU THAM KHẢO
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

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 có giá trị 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 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 dữ liệu chưa được gán nhãn, từ đó nâng cao hiệu quả phân tích và ra quyết định.

II. Vấn Đề 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 khối lượng dữ liệu lớn và tính không đồng nhất của dữ liệu. Những vấn đề này có thể dẫn đến khó khăn trong việc trích xuất thông tin có giá trị. 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 những vấn đề này một cách hiệu quả.

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

Khối lượng dữ liệu từ web server logs có thể lên đến hàng terabyte, gây khó khăn trong việc xử lý và phân tích. 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ỉ tập trung vào các mẫu quan trọng.

2.2. Tính Không Đồng Nhất Của Dữ Liệu

Dữ liệu từ web server logs thường không đồng nhất, với nhiều định dạng và kiểu dữ liệu khác nhau. Phân cụm nửa giám sát có thể giúp nhận diện và phân loại các mẫu dữ liệu khác nhau, từ đó cải thiện độ chính xác trong 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, SSDBSCAN và SSGC. Mỗi phương pháp có ưu điểm và nhược điểm riêng, phù hợp với các loại dữ liệu khác nhau. 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 giữa các điểm dữ liệu và trọng tâm của cụm. Phương pháp này đơn giản và hiệu quả cho các tập dữ liệu lớn.

3.2. Thuật Toán SSDBSCAN

SSDBSCAN là một biến thể của DBSCAN, sử dụng mật độ để xác định các cụm. Phương pháp này có khả năng phát hiện các cụm có hình dạng bất kỳ và có thể xử lý tốt các điểm nhiễu trong dữ liệu.

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, từ đó tối ưu hóa nội dung và trải nghiệm người dùng trên website.

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

Bằng cách phân tích các cụm người dùng, các nhà quản lý có thể tối ưu hóa nội dung trên website để phù hợp với nhu cầu và sở thích của người dùng, từ đó tăng cường trải nghiệm người dùng.

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

Phân cụm nửa giám sát giúp nhận diện các mẫu hành vi của người dùng, từ đó cung cấp thông tin quý giá cho các chiến lược marketing và phát triển sản phẩm.

V. Kết Luận Và Tương Lai Của 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ứa hẹn trong việc phân tích dữ liệu web server logs. Với sự phát triển của công nghệ và các thuật toán học máy, phương pháp này sẽ ngày càng trở nên hiệu quả hơn trong việc khai thác thông tin từ dữ liệu lớn.

5.1. Hướng Phát Triển Tương Lai

Trong tương lai, việc kết hợp phân cụm nửa giám sát với các công nghệ mới như học sâu có thể mở ra nhiều cơ hội mới trong việc phân tích dữ liệu và khai thác thông tin.

5.2. Tầm Quan Trọng Của Phân Cụm Nửa Giám Sát

Phân cụm nửa giám sát sẽ tiếp tục đóng vai trò quan trọng trong việc phân tích dữ liệu, giúp các tổ chức và doanh nghiệp đưa ra quyết định chính xác hơn dựa trên thông tin từ dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên chuyển đổi số và bùng nổ dữ liệu lớn, các hệ thống máy chủ mạng mỗi ngày phải tiếp nhận hàng triệu lượt tương tác, tạo ra khối lượng cơ sở dữ liệu khổng lồ lên tới hàng trăm Gigabyte hoặc Terabyte. Việc khai phá dữ liệu vết truy cập của người dùng (Web Usage Mining) trở thành nhiệm vụ cốt lõi nhằm phát hiện hành vi, thói quen và nhu cầu thông tin của khách hàng. 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 hạn chế nghiêm trọng: nhạy cảm với việc khởi tạo tâm cụm ngẫu nhiên, dễ rơi vào cực trị địa phương và hoạt động kém hiệu quả trên các tập dữ liệu có mật độ phân bố phức tạp.

Đề tài tập trung nghiên cứu, hệ thống hóa và đánh giá các phương pháp phân cụm nửa giám sát tiên tiến bao gồm COP-KMeans, Seed K-Means, SSDBSCAN và SSGC, từ đó ứng dụng giải quyết bài toán phân nhóm hành vi người dùng trên dữ liệu nhật ký máy chủ. Phạm vi nghiên cứu thực nghiệm được triển khai trên tập dữ liệu máy chủ của một trường đại học thu thập vào ngày 03 tháng 4 năm 2018, bao gồm 4.745 địa chỉ IP người dùng duy nhất và 255 ký hiệu chỉ mục phân bố trên 24 chuyên mục nội dung chính.

Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc nâng cao chất lượng cấu trúc hóa website. Bằng cách tích hợp tri thức chuyên gia dưới dạng dữ liệu hạt giống (seeds), phương pháp giúp tăng độ ổn định của thuật toán lên 100% qua các lần lặp và tối ưu hóa chỉ số đo lường Rand Index từ 0 đến 1. Kết quả nghiên cứu cung cấp cơ sở định lượng vững chắc giúp các nhà quản trị mạng bố trí giao diện thông minh, tối ưu hóa lưu lượng tải trang và tăng trải nghiệm người dùng trong môi trường giáo dục điện tử cũng như thương mại số.

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 xây dựng trên nền tảng lý thuyết khai phá dữ liệu web, tập trung vào khai phá dữ liệu người dùng web kết hợp với lý thuyết học máy nửa giám sát (Semi-supervised Learning). Ba mô hình phân cụm nền tảng được khảo sát gồm: phân cụm phân hoạch K-Means (xuất hiện từ những năm 1950), phân cụm dựa trên mật độ DBSCAN (năm 1996) và phân cụm dựa trên lý thuyết đồ thị Graph Clustering (năm 1973).

Các khái niệm then chốt cấu thành mô hình nghiên cứu bao gồm:

1. Thông tin bổ trợ (Side Information): Tri thức định hướng do người dùng cung cấp dưới dạng các cặp ràng buộc (Must-link, Cannot-link) hoặc tập các điểm dữ liệu hạt giống đã được gán nhãn sẵn đại diện cho từng cụm.
2. Khoảng cách tiếp cận mật độ tương đối (rDist) và cây khung nhỏ nhất (MST): Cơ chế mở rộng cụm của thuật toán SSDBSCAN cho phép phát hiện các cụm có mật độ khác nhau mà chỉ cần duy nhất một tham số lân cận.
3. Đồ thị k láng giềng gần nhất (k-NNG) và điều kiện cắt liên thông: Cấu trúc cơ sở của thuật toán SSGC giúp phân tách đồ thị tự động dựa trên nguyên tắc mỗi thành phần liên thông chỉ chứa tối đa một loại hạt giống.
4. Chỉ số Rand Index: Thước đo thống kê chuẩn hóa từ 0 đến 1 để đánh giá mức độ tương đồng giữa kết quả phân cụm thực nghiệm với phân bố nhãn thực tế của dữ liệu.

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

Nghiên cứu sử dụng nguồn dữ liệu thứ cấp trích xuất trực tiếp từ tệp nhật ký máy chủ web vào ngày 03 tháng 4 năm 2018. Toàn bộ 4.745 địa chỉ IP người dùng thực tế được thu thập qua phương pháp chọn mẫu xác suất toàn phần từ các phiên truy cập hợp lệ trong ngày.

Quy trình phân tích dữ liệu trải qua ba giai đoạn chặt chẽ:

1. Tiền xử lý dữ liệu: Trích xuất địa chỉ IP, đường dẫn URL và thời gian truy cập; chuyển đổi và gộp 255 mã chỉ mục kỹ thuật thành 24 chuyên mục nội dung then chốt như Đào tạo, Tuyển sinh, Khoa học công nghệ, Tin tức sự kiện và Sinh viên.
2. Vector hóa ma trận: Biểu diễn hành vi người dùng thành ma trận số học nhị phân kích thước 4.745 dòng tương ứng với 4.745 người dùng và 24 cột đại diện cho 24 chiều chuyên mục (giá trị 1 nếu có truy cập và 0 nếu không truy cập).
3. Phân cụm và đánh giá: Áp dụng thuật toán Seed K-Means để phân chia tập 4.745 vector thành 6 cụm hành vi đặc trưng tương ứng với 6 hạt giống định hướng. Lý do lựa chọn Seed K-Means xuất phát từ khả năng kiểm soát tâm cụm ngay từ pha khởi tạo, giúp thuật toán có độ phức tạp tính toán thấp ở mức tuyến tính O(nk) nhưng vẫn bảo đảm loại bỏ hoàn toàn tính ngẫu nhiên của thuật toán K-Means cổ điển. Quá trình thực nghiệm diễn ra trong khung thời gian 6 tháng của năm 2018.

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 toán học đã mang lại các phát hiện định lượng then chốt:

1. Rút gọn chiều không gian hiệu quả: Thống kê từ 255 chỉ mục ban đầu xuống 24 chiều chuyên mục giúp giảm hơn 90% độ thưa thớt của ma trận dữ liệu mà không làm mất đi các đặc trưng truy cập cốt lõi của 4.745 người dùng.
2. Sự hình thành 6 phân khúc hành vi rõ rệt: Thuật toán Seed K-Means đã gom toàn bộ 4.745 người dùng vào 6 cụm riêng biệt. Trong đó, khoảng 68% tổng lượng người dùng tập trung mạnh mẽ vào 4 chuyên mục chính gồm Tin tức sự kiện, Tuyển sinh, Đào tạo và Sinh viên; trong khi các chuyên mục chuyên sâu như Nghiên cứu mới hay Hợp tác phát triển chỉ thu hút khoảng 12% lượt truy cập.
3. Độ ổn định thuật toán đạt mức tuyệt đối: Việc tích hợp 6 điểm dữ liệu hạt giống ban đầu đã giúp thuật toán Seed K-Means hội tụ chính xác chỉ sau duy nhất 1 lần chạy, khắc phục hoàn toàn hiện tượng phân tán kết quả vốn làm sai lệch từ 15% đến 30% cấu trúc cụm trong phương pháp K-Means ngẫu nhiên.
4. Hiệu năng vượt trội của thuật toán đồ thị: Phân tích so sánh lý thuyết chỉ ra thuật toán SSGC đạt tốc độ xử lý nhanh hơn thuật toán SSDBSCAN khoảng 20 lần trên các tập dữ liệu có mật độ không đồng nhất, nhờ việc tận dụng cấu trúc đồ thị k-NNG với độ phức tạp giảm về mức O(n log n).

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự cải thiện vượt bậc về chất lượng phân cụm là sự can thiệp hợp lý của tri thức con người vào quá trình máy học. Trong K-Means truyền thống, việc gán tâm ngẫu nhiên thường khiến thuật toán rơi vào các cực trị cục bộ. Ngược lại, 6 hạt giống được chọn lọc cẩn trọng đã đóng vai trò làm điểm tựa định hướng không gian vector 24 chiều, hướng quá trình tối ưu hóa hàm mục tiêu về đúng cấu trúc thực tế của đối tượng truy cập.

Khi so sánh với các nghiên cứu của Wagstaff năm 2001 về COP-KMeans hay Basu năm 2002 về Seed K-Means trên các tập dữ liệu chuẩn quốc tế như Soybean hay Newsgroups, kết quả trên tập dữ liệu web server logs tại Việt Nam tái khẳng định rằng dữ liệu bán giám sát luôn mang lại chỉ số Rand Index vượt trội so với phân cụm thuần túy không giám sát.

Về mặt hiển thị trực quan, toàn bộ kết quả phân bổ của 4.745 người dùng có thể được biểu diễn trực quan qua bảng ma trận trọng số và đồ thị nhiệt 24 chiều. Đồng thời, biểu đồ radar 6 trục có thể minh họa mức độ quan tâm vượt trội của từng nhóm người dùng đối với các nhóm chuyên mục, giúp ban quản trị nhận diện ngay các cụm người dùng tiềm năng và những điểm nghẽn truy cập trên website.

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

Dựa trên kết quả nghiên cứu thực nghiệm, bốn giải pháp chiến lược được đề xuất nhằm tối ưu hóa hệ thống máy chủ và cấu trúc website:

1. Tái cấu trúc thanh điều hướng và giao diện website: Ban biên tập và Quản trị viên website cần tiến hành sắp xếp lại 24 chuyên mục theo mức độ tương quan của 6 cụm hành vi người dùng. Mục tiêu hướng tới là nâng cao 25% tỷ lệ nhấp chuột vào các liên kết hữu ích và rút ngắn 30% thời gian tìm kiếm thông tin của người dùng trong vòng 3 tháng đầu triển khai.
2. Tích hợp mô-đun gợi ý thông minh thời gian thực: Đội ngũ kỹ sư phần mềm cần lập trình tích hợp thuật toán phân cụm nửa giám sát Seed K-Means vào hệ thống máy chủ để tự động nhận dạng vector hành vi của địa chỉ IP ngay trong phiên truy cập. Mục tiêu đề ra là giảm 35% tỷ lệ thoát trang và kéo dài thời gian lưu lại trang web thêm ít nhất 45 giây trong lộ trình 6 tháng.
3. Tối ưu hóa hạ tầng lưu trữ và bộ nhớ đệm máy chủ: Bộ phận công nghệ thông tin cần ưu tiên phân bổ tài nguyên bộ nhớ đệm cho nhóm 4 chuyên mục chiếm 68% lưu lượng truy cập cao nhất. Giải pháp này giúp cải thiện tốc độ tải trang thêm 40%, hạn chế tối đa nguy cơ nghẽn mạng trong các đợt cao điểm tuyển sinh trước quý IV hàng năm.
4. Xây dựng quy trình tự động cập nhật dữ liệu hạt giống: Các nhà nghiên cứu và quản trị cơ sở dữ liệu cần thiết lập cơ chế định kỳ trích xuất tối thiểu 10 đến 15 mẫu truy cập đặc trưng mỗi tháng để hiệu chỉnh lại tập hạt giống. Điều này đảm bảo mô hình phân cụm thích ứng liên tục với sự biến động hành vi của người dùng qua từng năm học.

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

Công trình nghiên cứu mang giá trị tham khảo học thuật và ứng dụng thực tiễn cao cho 4 nhóm đối tượng chính:

1. Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính: Cung cấp tài liệu hệ thống hóa toàn diện về mặt toán học và thuật toán đối với các phương pháp phân cụm nửa giám sát kinh điển như Seed K-Means, COP-KMeans, SSDBSCAN và SSGC, cùng cách sử dụng độ đo Rand Index để đánh giá mô hình.
2. Kỹ sư dữ liệu và chuyên viên Machine Learning: Tiếp cận phương pháp luận chuẩn xác trong việc xử lý tệp nhật ký máy chủ thực tế, từ bước lọc nhiễu 4.745 địa chỉ IP, rút gọn 255 chỉ mục thành 24 chiều đặc trưng đến kỹ thuật chuyển đổi ma trận nhị phân phục vụ huấn luyện mô hình.
3. Quản trị viên cổng thông tin điện tử và chuyên gia UI/UX: Ứng dụng mô hình 6 cụm hành vi để thấu hiểu luồng di chuyển của người truy cập, từ đó tái thiết kế kiến trúc thông tin trang web khoa học và gia tăng chỉ số tương tác tổng thể.
4. Doanh nghiệp thương mại điện tử và tiếp thị số: Khai thác nguyên lý phân cụm nửa giám sát để tự động phân đoạn khách hàng mục tiêu, tối ưu hóa các chiến dịch tiếp thị cá nhân hóa và gia tăng tỷ lệ chuyển đổi đơn hàng lên khoảng 15% đến 20%.

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

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 bổ sung một lượng nhỏ thông tin định hướng từ chuyên gia, bao gồm các điểm dữ liệu hạt giống đã gán nhãn hoặc các ràng buộc Must-link và Cannot-link. Sự bổ trợ này giúp thuật toán định hình ranh giới cụm chính xác hơn và loại bỏ tính bất định của các phương pháp không giám sát cổ điển.

Tại sao tác giả lựa chọn thuật toán Seed K-Means cho bài toán thực nghiệm?

Thuật toán Seed K-Means sở hữu độ phức tạp tính toán thấp ở mức tuyến tính O(nk), rất phù hợp với tập dữ liệu lớn gồm 4.745 dòng. Việc đưa 6 hạt giống đại diện vào pha khởi tạo giúp thuật toán hội tụ cố định chỉ sau 1 lần chạy, mang lại kết quả ổn định và tiết kiệm tài nguyên tính toán.

Tập dữ liệu gồm 4.745 địa chỉ IP có bảo đảm tính đại diện thống kê không?

Cỡ mẫu 4.745 địa chỉ IP duy nhất được thu thập đầy đủ trong một ngày đại diện cho toàn bộ các luồng truy cập đa dạng từ sinh viên, giảng viên đến khách vãng lai. Sau khi chuẩn hóa thành 24 chiều chuyên mục, dữ liệu bảo đảm đầy đủ các phân bố thống kê cần thiết để thuật toán phân cụm chính xác.

Làm thế nào để xác định chính xác các điểm hạt giống đại diện cho từng cụm?

Hạt giống được xác định dựa trên sự kết hợp giữa phân tích thống kê tần suất truy cập và tri thức chuyên gia quản trị mạng. Mỗi hạt giống là một vector nhị phân 24 chiều điển hình, thể hiện rõ nét hành vi truy cập đặc trưng của từng nhóm đối tượng mục tiêu trên website.

Thuật toán SSGC có ưu thế gì nổi bật so với SSDBSCAN?

Thuật toán SSGC giải quyết phân cụm dựa trên cấu trúc đồ thị k láng giềng gần nhất với cơ chế cắt ngưỡng liên thông tự động. Thực nghiệm cho thấy SSGC có tốc độ xử lý nhanh hơn SSDBSCAN khoảng 20 lần và xử lý rất tốt các tập dữ liệu có mật độ phân bố không đồng đều.

Kết luận

1. Hệ thống hóa thành công cơ sở lý thuyết vững chắc về các thuật toán phân cụm nửa giám sát hiện đại gồm COP-KMeans, Seed K-Means, SSDBSCAN và SSGC.
2. Xây dựng hoàn chỉnh quy trình tiền xử lý và vector hóa dữ liệu nhật ký máy chủ từ 255 ký hiệu chỉ mục thành ma trận nhị phân 24 chiều chuẩn mực.
3. Thực nghiệm thành công việc phân chia 4.745 người dùng thành 6 nhóm hành vi truy cập rõ rệt với độ ổn định tuyệt đối nhờ thuật toán Seed K-Means.
4. Chứng minh tính ưu việt của việc tích hợp tri thức hạt giống giúp tăng tốc độ hội tụ và nâng cao độ chính xác của mô hình phân tích dữ liệu web.
5. Định hình phương hướng mở rộng nghiên cứu sang việc kết hợp cả hai loại thông tin bổ trợ là hạt giống và ràng buộc, đồng thời ứng dụng kỹ thuật học sâu để trích chọn đặc trưng tự động.

Đóng góp lớn nhất của luận văn là đã thu hẹp khoảng cách giữa lý thuyết phân cụm bán giám sát phức tạp và bài toán tối ưu hóa hệ thống thông tin thực tế. Trong giai đoạn 12 tháng tới, các đơn vị vận hành công nghệ thông tin nên ứng dụng ngay khung phân tích này vào máy chủ sản xuất để xây dựng hệ thống gợi ý trang web thông minh, nâng cao hiệu quả quản trị và tạo bước đột phá trong trải nghiệm người dùng số.

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

Chương 1. 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 LUAN VAN CHAT LUONG download : add [e-mail] 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

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. LUAN VAN CHAT LUONG download : add [e-mail] 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

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 LUAN VAN CHAT LUONG download : add [e-mail] 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. Ví dụ về dữ liệu log server webs Sau khi có các dữ liệu như bảng trên chúng ta phải chuyển sang dạng các vector dạng số dựa trên các trang của website.

Giả sử có 5 người sử dụng (users) và 5 trang kí hiệu là A, B, C, D, E. Dữ liệu sau khi chuyển đổi có dạng như bảng sau. Các số trong bảng thể hiện thời gian truy cập vào các trang tương ứng của người sử dụng. Bài toán phân cụm sẽ thực hiện với dữ liệu trên bảng này.

LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ví dụ về dữ liệu sau khi chuyển đổi thành vector A B C D E User 1 0 8 3 0 10 User 2 10 3 0 2 6 User 3 0 12 67 4 0 User 4 12 9 0 9 1 User 5 3 0 2 10 9 Kết quả của quá trình phân cụm sẽ là các cụm trong đó các phần tử trong mỗi cụm sẽ cho biết nhóm khách hàng hay vào truy xuất, các nhóm chủ đề của website hay được xem cùng nhau,. Nếu như thực hiện phân cụm với dữ liệu này trên các website khác nhau thì các cụm sẽ cho biết nhóm người truy cập website theo các chủ đề gì, vào các website nào,… Điều này có ý nghĩa trong việc bố trí cấu trúc của các nội dung website cũng như biết được mối liên hệ giữa các website mà người dùng hay truy cập. Một số phương pháp phân cụm dữ liệu cơ bản Bài toán phân cụm (clustering) là một dạng của phương pháp học không giám sát (unsupervised learning) được phát biểu như sau: Cho tập X gồm n đối tượng, hãy phân rã tập X ra thành k (k ≤ n) cụm (cluster) sao cho các đối tượng trong cùng một cụm thì tương tự nhau và các đối tượng ở các cụm khác nhau thì không tương tự nhau theo một tiêu chuẩn nào đó.5 minh họa về tập dữ liệu trong không gian hai chiều với các cụm tương ứng.

Chúng ta có thể thấy các cụm có thể có phân bố Gaussian hoặc có hình dạng bất kỳ (hình 1. Mục đích của quá trình phân cụm dữ liệu giúp cho chúng ta hiểu rõ cấu trúc phân bố của dữ liệu cũng như mối quan hệ giữa các đối tượng trong tập dữ liệu, thậm chí có thể phát hiện các dị thường trong dữ liệu (các phần từ không thuộc cụm nào sau khi phân cụm). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.5 Ví dụ về phân cụm dữ liệu Hình 1. Minh họa thuật toán K-Means LUAN VAN CHAT LUONG download : add [e-mail] 11 Các thuật toán phân cụm được nghiên cứu và giới thiệu từ những năm 50 của thế kỷ XX.

Một số thuật toán phân cụm dữ liệu cơ bản gồm K-Means, Fuzzy C-Means, thuật toán phân cụm dựa trên đồ thị, thuật toán phân cụm dựa trên mật độ (DBCSAN), thuật toán phân cụm kiểu thứ bậc. Mỗi phương pháp có ưu và nhược điểm riêng và sẽ phù hợp với các loại dữ liệu cho các ứng dụng khác nhau. Phương pháp phân cụm K-Means Thuật toán phân cụm K-Means là một trong những thuật toán được giới thiệu sớm nhất (vào những năm 50 của thế kỷ XX). Ý tưởng của phương pháp K-Means như sau: Giả sử ta cần phân tách tập dữ liệu X gồm n phần tử thành k cụm.