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 luanvanchat@agmail.com 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 luanvanchat@agmail.com 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 luanvanchat@agmail.com 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 luanvanchat@agmail.com 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.