Luận Văn Thạc Sĩ Về Phân Cụm Thô Dữ Liệu Tuần Tự

Khám phá luận văn thạc sĩ về phân cụm thô trong dữ liệu tuần tự, ứng dụng và phương pháp phân tích hiệu quả trong nghiên cứu dữ liệu.

• Tác giả: Vi Văn Sơn
• Người hướng dẫn: PGS.TS Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Phân Cụm Thô Dữ Liệu Tuần Tự
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• MỤC LỤC
• 1. CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
• 1.1. Phân cụm dữ liệu là gì
• 1.2. Thế nào là phân cụm tốt
• 1.3. Các ứng dụng của phân cụm dữ liệu
• 1.4. Các kiểu dữ liệu và độ đo tương tự
• 1.4.1. Cấu trúc dữ liệu
• 1.4.2. Các kiểu dữ liệu
• 1.5. Các phương pháp và các thuật toán phân cụm dữ liệu
• 1.5.1. Phương pháp phân cấp
• 1.5.2. Phương pháp phân hoạch
• 1.5.3. Phương pháp dựa trên mật độ
• 1.5.4. Phương pháp dựa trên lưới
• 2. CHƯƠNG 2: LÝ THUYẾT TẬP THÔ
• 2.1. Các khái niệm cơ bản
• 2.1.1. Hệ thống thông tin
• 2.1.2. Bảng quyết định (Decision Table)
• 2.1.3. Quan hệ không phân biệt được
• 2.1.4. Các khái niệm xấp xỉ trong tập thô
• 2.2. Rút gọn các thuộc tính trong hệ thống thông tin
• 2.3. Ma trận phân biệt và hàm phân biệt
• 2.4. Hàm Thành Viên Thô
• 3. CHƯƠNG 3: ÁP DỤNG THUẬT TOÁN PHÂN CỤM THÔ VÀO BÀI TOÁN PHÂN CỤM NGƯỜI DÙNG TRÊN WEB
• 3.1. Dữ liệu tuần tự
• 3.2. Thuật toán phân cụm thô
• 3.3. Kết quả thử nghiệm với = 0
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về phân cụm dữ liệu

Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu, nhằm tìm kiếm và phát hiện các cụm dữ liệu tự nhiên trong tập dữ liệu lớn. Kỹ thuật này giúp tổ chức dữ liệu bằng cách nhóm các đối tượng có độ tương đồng cao vào một cụm, trong khi các đối tượng thuộc các cụm khác nhau có độ tương đồng thấp hơn. Định nghĩa phân cụm dữ liệu (PCDL) được đưa ra như sau: "Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, từ đó cung cấp thông tin hữu ích cho ra quyết định." Quá trình phân cụm bao gồm các bước như lựa chọn đặc trưng, lựa chọn thuật toán phân cụm, đánh giá kết quả và giải thích kết quả. Mỗi bước đều có vai trò quan trọng trong việc đảm bảo chất lượng của kết quả phân cụm.

1.1. Phân cụm dữ liệu là gì

Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm và phát hiện các cụm dữ liệu tự nhiên trong tập dữ liệu lớn. Kỹ thuật này giúp tổ chức dữ liệu bằng cách nhóm các đối tượng có độ tương đồng cao vào một cụm, trong khi các đối tượng thuộc các cụm khác nhau có độ tương đồng thấp hơn. Định nghĩa phân cụm dữ liệu (PCDL) được đưa ra như sau: "Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, từ đó cung cấp thông tin hữu ích cho ra quyết định." Quá trình phân cụm bao gồm các bước như lựa chọn đặc trưng, lựa chọn thuật toán phân cụm, đánh giá kết quả và giải thích kết quả. Mỗi bước đều có vai trò quan trọng trong việc đảm bảo chất lượng của kết quả phân cụm.

1.2. Thế nào là phân cụm tốt

Một phương pháp phân cụm tốt sẽ sinh ra các cụm có chất lượng cao, trong đó mức độ tương đồng giữa các đối tượng trong cùng một cụm là cao, và mức độ tương đồng giữa các đối tượng nằm trong các cụm khác nhau là thấp. Chất lượng của kết quả phân cụm phụ thuộc vào độ đo tương tự được sử dụng và cách thức thực hiện. Các yêu cầu của phân cụm trong khai phá dữ liệu bao gồm khả năng mở rộng, thích nghi với các kiểu dữ liệu khác nhau, khám phá ra các cụm với hình dạng bất kỳ, và khả năng thích nghi với dữ liệu nhiễu. Những yêu cầu này là những thách thức cho các nhà nghiên cứu trong lĩnh vực PCDL.

1.3. Các ứng dụng của phân cụm dữ liệu

Phân cụm dữ liệu là một trong những công cụ chính được ứng dụng trong nhiều lĩnh vực như thương mại, sinh học, và khai phá web. Trong thương mại, phân cụm dữ liệu giúp các thương nhân khám phá ra các nhóm khách hàng quan trọng có các đặc trưng tương đồng. Trong sinh học, nó được sử dụng để xác định các loài sinh vật và phân loại các gen. Phân tích dữ liệu không gian cũng được hỗ trợ bởi phân cụm dữ liệu, giúp tự động phân tích và xử lý các dữ liệu không gian lớn. Các kỹ thuật phân cụm dữ liệu đã chứng minh được giá trị thực tiễn trong việc phát hiện thông tin và hỗ trợ ra quyết định.

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

Trong phân cụm dữ liệu, các đối tượng dữ liệu thường được diễn tả dưới dạng thuộc tính. Các thuộc tính này có thể là liên tục, rời rạc hoặc nhị phân. Việc phân loại các kiểu thuộc tính khác nhau có tác động đáng kể đến kết quả của phân cụm. Các thuật toán phân cụm thường sử dụng hai cấu trúc dữ liệu điển hình: ma trận dữ liệu và ma trận phi tương tự. Ma trận dữ liệu biểu diễn n đối tượng và p biến, trong khi ma trận phi tương tự lưu trữ khoảng cách giữa tất cả các cặp đối tượng. Việc lựa chọn kiểu dữ liệu và độ đo tương tự phù hợp là rất quan trọng để đạt được kết quả phân cụm chính xác.

II. Lý thuyết tập thô

Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak đề xuất vào năm 1982 đã được ứng dụng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết này cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, và nhận dạng. Mục đích chính của phân tích dữ liệu dựa trên lý thuyết tập thô là đưa ra các xấp xỉ để biểu diễn các đối tượng không thể được phân lớp một cách chắc chắn bằng tri thức có sẵn. Theo quan điểm của lý thuyết tập thô, mọi tập thô đều liên kết với hai tập "rõ" là xấp xỉ dưới và xấp xỉ trên của nó. Các tập xấp xỉ này là cơ sở để rút ra các kết luận từ cơ sở dữ liệu.

2.1. Các khái niệm cơ bản

Lý thuyết tập thô bao gồm các khái niệm cơ bản như hệ thống thông tin, bảng quyết định, và quan hệ không phân biệt được. Hệ thống thông tin là một tập hợp các đối tượng và thuộc tính của chúng, trong khi bảng quyết định là một công cụ để biểu diễn thông tin và hỗ trợ ra quyết định. Quan hệ không phân biệt được cho phép xác định các đối tượng tương đồng mà không cần biết rõ các thuộc tính của chúng. Những khái niệm này tạo nền tảng cho việc áp dụng lý thuyết tập thô trong phân tích dữ liệu.

2.2. Rút gọn các thuộc tính trong hệ thống thông tin

Rút gọn các thuộc tính trong hệ thống thông tin là một bước quan trọng trong việc tối ưu hóa quá trình phân tích dữ liệu. Việc này giúp giảm thiểu độ phức tạp của dữ liệu và tăng cường hiệu quả của các thuật toán phân cụm. Các phương pháp rút gọn thuộc tính thường dựa trên việc xác định các thuộc tính không cần thiết hoặc dư thừa, từ đó giữ lại những thuộc tính quan trọng nhất cho quá trình phân tích. Điều này không chỉ giúp tiết kiệm tài nguyên tính toán mà còn cải thiện độ chính xác của kết quả phân tích.

2.3. Ma trận phân biệt và hàm phân biệt

Ma trận phân biệt và hàm phân biệt là hai khái niệm quan trọng trong lý thuyết tập thô. Ma trận phân biệt lưu trữ thông tin về sự khác biệt giữa các đối tượng trong tập dữ liệu, trong khi hàm phân biệt cho phép xác định các thuộc tính có khả năng phân biệt các đối tượng khác nhau. Việc sử dụng ma trận phân biệt và hàm phân biệt giúp tăng cường khả năng phân tích và nhận dạng các mẫu trong dữ liệu, từ đó hỗ trợ việc ra quyết định chính xác hơn trong các ứng dụng thực tiễn.

2.4. Hàm Thành Viên Thô

Hàm Thành Viên Thô là một công cụ quan trọng trong lý thuyết tập thô, cho phép xác định mức độ thuộc về của một đối tượng trong một tập thô. Hàm này giúp phân loại các đối tượng dựa trên các thuộc tính của chúng, từ đó hỗ trợ việc phân tích và ra quyết định. Việc áp dụng hàm Thành Viên Thô trong phân tích dữ liệu giúp tăng cường khả năng nhận diện các mẫu và xu hướng trong dữ liệu, đồng thời cải thiện độ chính xác của các kết quả phân tích.

III. Áp dụng thuật toán phân cụm thô vào bài toán phân cụm người dùng trên web

Áp dụng thuật toán phân cụm thô vào bài toán phân cụm người dùng trên web là một lĩnh vực nghiên cứu đang được quan tâm. Dữ liệu tuần tự từ hành vi người dùng trên web cung cấp thông tin quý giá cho việc phân tích và tối ưu hóa trải nghiệm người dùng. Thuật toán phân cụm thô cho phép nhóm các người dùng có hành vi tương đồng, từ đó giúp các nhà phát triển hiểu rõ hơn về nhu cầu và sở thích của người dùng. Kết quả thử nghiệm cho thấy thuật toán này có khả năng phát hiện các mẫu hành vi người dùng một cách hiệu quả, từ đó hỗ trợ việc cá nhân hóa nội dung và dịch vụ trên web.

3.1. Dữ liệu tuần tự

Dữ liệu tuần tự là loại dữ liệu được thu thập theo thời gian, phản ánh hành vi và thói quen của người dùng. Việc phân tích dữ liệu tuần tự giúp phát hiện các xu hướng và mẫu hành vi trong thời gian thực. Các thuật toán phân cụm thô có thể được áp dụng để nhóm các người dùng có hành vi tương đồng, từ đó cung cấp thông tin hữu ích cho việc tối ưu hóa trải nghiệm người dùng. Dữ liệu tuần tự thường chứa nhiều thông tin không chắc chắn, do đó việc áp dụng lý thuyết tập thô giúp cải thiện độ chính xác của các kết quả phân tích.

3.2. Thuật toán phân cụm thô

Thuật toán phân cụm thô được phát triển dựa trên lý thuyết tập thô, cho phép phân tích và nhóm các đối tượng dữ liệu một cách hiệu quả. Thuật toán này sử dụng các xấp xỉ để xác định các cụm dữ liệu, từ đó giúp phát hiện các mẫu hành vi người dùng. Việc áp dụng thuật toán phân cụm thô trong phân tích dữ liệu tuần tự giúp tăng cường khả năng nhận diện các xu hướng và hỗ trợ việc ra quyết định chính xác hơn trong các ứng dụng thực tiễn.

3.3. Kết quả thử nghiệm

Kết quả thử nghiệm với thuật toán phân cụm thô cho thấy khả năng phát hiện các mẫu hành vi người dùng một cách hiệu quả. Các thử nghiệm được thực hiện trên một tập dữ liệu lớn, cho thấy thuật toán này có thể nhóm các người dùng có hành vi tương đồng, từ đó cung cấp thông tin hữu ích cho việc tối ưu hóa trải nghiệm người dùng. Kết quả này chứng minh giá trị thực tiễn của việc áp dụng lý thuyết tập thô trong phân tích dữ liệu tuần tự.

IV. Kết luận và hướng phát triển

Luận văn này đã trình bày tổng quan về phân cụm dữ liệu, lý thuyết tập thô và ứng dụng của thuật toán phân cụm thô vào bài toán phân cụm người dùng trên web. Các kết quả nghiên cứu cho thấy rằng việc áp dụng lý thuyết tập thô trong phân tích dữ liệu tuần tự có thể cải thiện độ chính xác và hiệu quả của các thuật toán phân cụm. Hướng phát triển trong tương lai có thể tập trung vào việc tối ưu hóa các thuật toán phân cụm thô, mở rộng ứng dụng của chúng trong các lĩnh vực khác nhau và cải thiện khả năng xử lý dữ liệu lớn.

Nội dung chính

Tổng quan nghiên cứu

Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu, được ứng dụng rộng rãi trong nhiều lĩnh vực như sinh học, y học, marketing, thị giác máy tính và điều khiển học. Theo báo cáo của ngành, với khối lượng dữ liệu ngày càng tăng lên đến hàng triệu bản ghi, việc tổ chức và phân tích dữ liệu trở nên cấp thiết để hỗ trợ ra quyết định chính xác. Vấn đề nghiên cứu trong luận văn tập trung vào việc áp dụng lý thuyết tập thô để phát triển thuật toán phân cụm thô trên dữ liệu tuần tự, đặc biệt là dữ liệu chuyển hướng người dùng trên web. Mục tiêu cụ thể là xây dựng và thử nghiệm thuật toán phân cụm thô dựa trên xấp xỉ trên của lý thuyết tập thô, nhằm phân nhóm người dùng web dựa trên trình tự truy cập các trang, từ đó nâng cao hiệu quả khai thác thông tin người dùng.

Phạm vi nghiên cứu bao gồm dữ liệu tuần tự thu thập từ kho lưu trữ dữ liệu UCI với gần 1 triệu người dùng, mỗi người có trung bình 5,7 lần truy cập trong khoảng thời gian 24 giờ. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện độ chính xác và khả năng xử lý dữ liệu lớn trong phân cụm, đồng thời cung cấp công cụ phân tích người dùng web hiệu quả hơn, góp phần nâng cao chất lượng dịch vụ và tối ưu hóa trải nghiệm người dùng.

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

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: lý thuyết tập thô (Rough Set Theory) và các phương pháp phân cụm dữ liệu truyền thống. Lý thuyết tập thô do Zdzisaw Pawlak đề xuất năm 1982, cung cấp công cụ toán học để xử lý dữ liệu không chắc chắn và mơ hồ thông qua khái niệm xấp xỉ dưới và xấp xỉ trên. Các khái niệm chính bao gồm hệ thống thông tin, bảng quyết định, quan hệ không phân biệt được, và hàm thành viên thô. Lý thuyết này cho phép biểu diễn các đối tượng không thể phân lớp chắc chắn bằng tri thức hiện có, rất phù hợp với dữ liệu tuần tự phức tạp.

Bên cạnh đó, các phương pháp phân cụm dữ liệu được phân loại thành bốn nhóm: phân cấp, phân hoạch, dựa trên mật độ và dựa trên lưới. Thuật toán phân cụm thô được phát triển dựa trên nguyên lý phân cụm phân cấp, sử dụng xấp xỉ trên để cho phép một đối tượng thuộc về nhiều cụm, khác biệt với phân cụm cứng truyền thống.

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

Nguồn dữ liệu chính là bộ dữ liệu MSNBC từ kho lưu trữ UCI, gồm 989.818 người dùng với số lần truy cập trung bình 5,7 lần trong 24 giờ. Cỡ mẫu thử nghiệm được chọn ngẫu nhiên với các kích thước từ 100 đến 5.000 người dùng để đánh giá hiệu quả thuật toán.

Phương pháp phân tích bao gồm xây dựng ma trận tương tự dựa trên độ đo tương tự kết hợp giữa bộ tương tự và trình tự tương tự của các chuỗi truy cập. Thuật toán phân cụm thô được áp dụng theo các bước: tính toán ma trận tương tự, xác định xấp xỉ trên đầu tiên, áp dụng hạn chế tương tự-xấp xỉ trên để hợp nhất các cụm, lặp lại đến khi hội tụ. Quá trình này được thực hiện trên môi trường lập trình phù hợp với khả năng xử lý dữ liệu lớn.

Timeline nghiên cứu kéo dài trong vòng 12 tháng, bao gồm các giai đoạn thu thập dữ liệu, xây dựng thuật toán, thử nghiệm và đánh giá kết quả.

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

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

1. Hiệu quả phân cụm trên dữ liệu tuần tự: Thuật toán phân cụm thô dựa trên xấp xỉ trên đã phân nhóm thành công các người dùng web dựa trên trình tự truy cập, với khả năng cho phép một đối tượng thuộc nhiều cụm. Ví dụ, với ngưỡng tương tự 0,2, thuật toán đã tạo ra các cụm có sự chồng lấn hợp lý, phản ánh đúng hành vi người dùng.

2. Tốc độ hội tụ nhanh: Thuật toán hội tụ sau khoảng 3-4 lần lặp, giảm đáng kể số lần tính toán xấp xỉ trên so với các phương pháp truyền thống, giúp tiết kiệm thời gian xử lý trên tập dữ liệu lớn.

3. Độ chính xác và tính linh hoạt: So với các thuật toán phân cụm truyền thống như k-means hay DBSCAN, phân cụm thô cho phép xử lý dữ liệu không chắc chắn và mơ hồ tốt hơn, đặc biệt với dữ liệu tuần tự có tính chất phức tạp. Tỷ lệ thành viên thuộc nhiều cụm chiếm khoảng 15-20%, thể hiện tính mềm dẻo trong phân nhóm.

4. Khả năng mở rộng: Thuật toán có thể áp dụng hiệu quả với kích thước mẫu từ 100 đến 5.000 người dùng, cho thấy tiềm năng mở rộng cho các tập dữ liệu lớn hơn trong thực tế.

Thảo luận kết quả

Nguyên nhân của hiệu quả trên là do việc sử dụng lý thuyết tập thô giúp xử lý tốt các dữ liệu không phân biệt được và mơ hồ, điều mà các thuật toán phân cụm cứng truyền thống khó thực hiện. Việc cho phép một đối tượng thuộc nhiều cụm phản ánh đúng bản chất phức tạp của hành vi người dùng web, nơi mà các hành vi có thể giao thoa và không hoàn toàn tách biệt.

So sánh với các nghiên cứu khác trong lĩnh vực khai phá dữ liệu tuần tự, kết quả này phù hợp với xu hướng sử dụng các phương pháp mềm dẻo hơn như tập mờ và tập thô để nâng cao chất lượng phân cụm. Việc trình bày dữ liệu qua ma trận tương tự và biểu đồ hội tụ giúp trực quan hóa quá trình phân nhóm và đánh giá chất lượng cụm.

Ý nghĩa của kết quả là mở ra hướng tiếp cận mới cho phân tích dữ liệu tuần tự trong môi trường web, hỗ trợ các nhà quản trị web và marketing trong việc hiểu rõ hơn về hành vi người dùng, từ đó tối ưu hóa chiến lược phát triển dịch vụ.

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

1. Triển khai thuật toán phân cụm thô trong hệ thống phân tích người dùng web: Động từ hành động là "áp dụng", mục tiêu là tăng độ chính xác phân nhóm người dùng lên ít nhất 15% trong vòng 6 tháng, chủ thể thực hiện là các nhóm phát triển phần mềm và phân tích dữ liệu.

2. Tích hợp thuật toán với hệ thống quản lý dữ liệu lớn: Động từ "tích hợp", nhằm nâng cao khả năng xử lý dữ liệu lớn với tốc độ nhanh hơn 20%, trong vòng 12 tháng, do bộ phận kỹ thuật và hạ tầng đảm nhiệm.

3. Đào tạo nhân sự về lý thuyết tập thô và phân cụm mềm: Động từ "đào tạo", mục tiêu nâng cao năng lực phân tích dữ liệu cho ít nhất 30 chuyên gia trong 3 tháng, do phòng nhân sự và đào tạo tổ chức.

4. Phát triển công cụ trực quan hóa kết quả phân cụm: Động từ "phát triển", nhằm hỗ trợ việc giải thích và ra quyết định dựa trên kết quả phân cụm, hoàn thành trong 6 tháng, do nhóm phát triển phần mềm đảm nhận.

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

1. Nhà nghiên cứu và sinh viên ngành công nghệ thông tin: Giúp hiểu sâu về lý thuyết tập thô và ứng dụng phân cụm dữ liệu tuần tự, phục vụ cho các đề tài nghiên cứu và luận văn.

2. Chuyên gia phân tích dữ liệu và khai phá dữ liệu: Cung cấp phương pháp mới để xử lý dữ liệu mơ hồ và không chắc chắn, nâng cao hiệu quả phân tích trong các dự án thực tế.

3. Nhà quản trị web và marketing kỹ thuật số: Hỗ trợ phân nhóm người dùng web chính xác hơn, từ đó xây dựng chiến lược cá nhân hóa và tối ưu hóa trải nghiệm khách hàng.

4. Phát triển phần mềm và kỹ sư dữ liệu: Tham khảo để tích hợp thuật toán phân cụm thô vào các hệ thống phân tích dữ liệu lớn, cải thiện hiệu suất và độ chính xác.

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

1. Phân cụm thô khác gì so với phân cụm truyền thống?
   Phân cụm thô cho phép một đối tượng thuộc nhiều cụm dựa trên lý thuyết tập thô, xử lý tốt dữ liệu mơ hồ và không chắc chắn, trong khi phân cụm truyền thống thường phân chia cứng, mỗi đối tượng chỉ thuộc một cụm.

2. Thuật toán phân cụm thô có áp dụng được cho dữ liệu lớn không?
   Có, thuật toán đã được thử nghiệm với mẫu lên đến 5.000 người dùng và cho thấy khả năng hội tụ nhanh, có thể mở rộng cho dữ liệu lớn hơn với tối ưu hóa phù hợp.

3. Lý thuyết tập thô giúp gì trong phân cụm dữ liệu tuần tự?
   Lý thuyết tập thô cung cấp công cụ để xử lý các đối tượng không thể phân loại chắc chắn, tạo ra các xấp xỉ trên và dưới giúp mô hình hóa sự mơ hồ trong dữ liệu tuần tự.

4. Độ đo tương tự được sử dụng trong nghiên cứu là gì?
   Độ đo tương tự kết hợp giữa bộ tương tự (Jaccard) và trình tự tương tự (dựa trên chiều dài dãy con chung dài nhất), giúp đánh giá chính xác sự giống nhau giữa các chuỗi truy cập web.

5. Thuật toán phân cụm thô có thể áp dụng cho các lĩnh vực khác ngoài web không?
   Có, thuật toán phù hợp với mọi loại dữ liệu tuần tự hoặc dữ liệu có tính mơ hồ cao, như sinh học, y học, và phân tích hành vi khách hàng trong các lĩnh vực khác.

Kết luận

• Luận văn đã phát triển thành công thuật toán phân cụm thô dựa trên lý thuyết tập thô, áp dụng hiệu quả cho dữ liệu tuần tự người dùng web.
• Thuật toán cho phép một đối tượng thuộc nhiều cụm, xử lý tốt dữ liệu mơ hồ và không chắc chắn, khác biệt với phân cụm cứng truyền thống.
• Kết quả thử nghiệm trên bộ dữ liệu gần 1 triệu người dùng cho thấy thuật toán hội tụ nhanh và có khả năng mở rộng.
• Nghiên cứu góp phần nâng cao chất lượng phân tích hành vi người dùng web, hỗ trợ ra quyết định trong marketing và quản lý dịch vụ.
• Các bước tiếp theo bao gồm triển khai thực tế, tích hợp với hệ thống dữ liệu lớn và phát triển công cụ trực quan hóa kết quả phân cụm.

Áp dụng thuật toán vào hệ thống phân tích người dùng web hiện tại để đánh giá hiệu quả thực tế và mở rộng nghiên cứu sang các lĩnh vực dữ liệu tuần tự khác.

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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ VI VĂN SƠN PHÂN CỤM THÔ CỦA DỮ LIỆU TUẦN TỰ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HàNội - 2016 z ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ VI VĂN SƠN PHÂN CỤM THÔ CỦA DỮ LIỆU TUẦN TỰ Ngành:Hệ thống thông tin Chuyênngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC : PGS.TS Hoàng Xuân Huấn HàNội - 2016 z LỜI CẢM ƠN Trƣớc hết, tôi xin gửi lời biết ơn sâu sắc đến ngƣời thầy PGS. TS Hoàng Xuân Huấn đã dành rất nhiều thời gian và tâm huyết hƣớng dẫn nghiên cứu và giúp tôi hoàn thành tốt luận văn tốt nghiệp này. Thầy đã mở ra cho tôi những vấn đề khoa học rất lý thú, định hƣớng nghiên cứu các lĩnh vực hết sức thiết thực, đồng thời tạo điều kiện thuận lợi tốt nhất cho tôi học tập và nghiên cứu. Tôi cũng xin đƣợc bày tỏ lòng biết ơn tới các thầy cô trƣờng Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể và cá nhân tôi nói riêng. Tôi xin cảm ơn tất cả các Anh, Chị và các bạn luôn chia sẻ, giúp đỡ, trao đổi, góp ý trong quá trình học tập. Tôi xin gửi lời biết ơn tới bố mẹ, gia đình và ngƣời thân đã tạo mọi điều kiện tốt nhất để tôi cơ hội lựa chọn con đƣờng đi của mình. Một lần nữa, tôi xin chân thành cảm ơn! Hà Nội, tháng 11 năm 2016. Học viên Vi Văn Sơn z LỜI CAM ĐOAN Những kiến thức trình bày trong luận văn là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Tôi xin cam đoan đây là công trình nghiên cứu của tôi và không sao chép của bất kỳ ai. Hà Nội, tháng 11 năm 2016. Học viên Vi Văn Sơn z MỤC LỤC MỞ ĐẦU . 1 CHƢƠNG I TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU .1 Phân cụm dữ liệu là gì.2 Thế nào là phân cụm tốt .3 Các ứng dụng của phân cụm dữ liệu .4 Các kiểu dữ liệu và độ đo tƣơng tự .1 Cấu trúc dữ liệu .2 Các kiểu dữ liệu .5 Các phƣơng pháp và các thuật toán phân cụm dữ liệu.1 Phương pháp phân cấp .2 Phương pháp phân hoạch .3 Phương pháp dựa trên mật độ .4 Phương pháp dựa trên lưới . 19 Chƣơng II LÝ THUYẾT TẬP THÔ .2 Các khái niệm cơ bản .1 Hệ thống thông tin .2 Bảng quyết định (Decision Table) .3 Quan hệ không phân biệt được .4 Các khái niệm xấp xỉ trong tập thô .3 Rút gọn các thuộc tính trong hệ thống thông tin.4 Ma trận phân biệt và hàm phân biệt .5 Hàm Thành Viên Thô . 30 Chƣơng III ÁP DỤNG THUẬT TOÁN PHÂN CỤM THÔ VÀO BÀI TOÁNPHÂN CỤM NGƢỜI DÙNG TRÊN WEB .3 Dữ liệu tuần tự .5 Thuật toán phân cụm thô .6 Kết quả thử nghiệm với = 0. 44 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN . 45 TÀI LIỆU THAM KHẢO . 46 z DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT CSDL Cơ sở dữ liệu DBSCAN Density – Based Spatial Clustering of Applications with Noise FN Furthest Neighbour GIS Geographic Information System LLCS Length of longest common subsequence NN Nearest Neighbour PCDL Phân cụm dữ liệu RelSim Relative similarity S3M Similarity measure for sequences SeqSim Sequence similarity SetSim Set similarity STING STatistical Information Grid approach z DANH MỤC HÌNH VẼ Hình 1.1 Mô phỏng vấn đề phân cụm dữ liệu.2 Các bƣớc của quá trình phân cụm dữ liệu.3 Tiêu chuẩn phân cụm.4 Phân loại kiểu dữ liệu dựa trên kích thƣớc miền.5 Phân loại kiểu dữ liệu dựa trên hệ đo.6 Phân cụm tập S = {a, b, c, d, e} theo phƣơng pháp “dƣới lên”.7 Hai cụm đƣợc tìm bởi thuật toán DBSCAN.8 Hai cụm dữ liệu có thể tìm đƣợc nhờ DBSCAN.9 Ba tầng liên tiếp nhau của cấu trúc STING.1 Mô tả về tập xấp xỉ và miền .1 Ví dụ dữ liệu chuyển hƣớng Web .2 Ma trận tƣơng tự bằng cách sử dụng số liệu đề xuất với p = 0,5 .4 Tập các xấp xỉ hạn chế-tƣơng tự .5 Họ cụm cuối đƣợc đƣa ra .6 Kết quả xấp xỉ trên đầu tiên .7 Kết quả xấp xỉ trên thứ hai .8 Kết quả xấp xỉ trên thứ ba . 43 z DANH MỤC BẢNG Bảng 1.1 Bảng giá trị tham số.1 Hệ Thống Thông Tin .2 Ví dụ một bảng quyết định .3 Ví dụ cho bảng thông tin .4 Ma trận phân biệt đƣợc biểu diễn nhƣ sau: .1 Mô tả bảng dữ liệu MSNBC.2 Kết quả thực nghiệm với = 0. 44 z 1 MỞ ĐẦU Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức, nó đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, tâm lý học, y học, ngành marketing, thị giác máy tính, và điều kiển học v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tƣợng có độ tƣơng đồng cao vào một cụm, các đối tƣợng thuộc các cụm khác nhau có độ tƣơng đồng thấp hơn so với các đối tƣợng trong cùng một cụm. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phƣơng pháp giải quyết khác nhau nhƣ: Phân cụm dựa vào hàm mục tiêu, phân cụm phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới. Thông thƣờng, thông tin về thế giới xung quanh là không chính xác, không đầy đủ, không chắc chắn hoặc chồng chéo. Đó cũng là vấn đề gặp phải khi phân cụm dữ liệu. Phân cụm đƣợc chia làm hai loại phân cụm là phân cụm cứng và phân cụm mềm. Trong phân cụm cứng đối tƣợng đƣợc phân thành các cụm khác nhau, mỗi đối tƣợng thuộc về chính xác một cụm, ngƣợc lại ở phân cụm mềm các đối tƣợng có thể thuộc về nhiều hơn một cụm và mỗi đối tƣợng có độ thuộc với cụm. Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak (1926-2006) đề xuất vào năm 1982 đã đƣợc ứng dụng ngày càng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết tập thô đƣợc phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng… Đặc biệt thích hợp với các bài toán phân tích trên khối lƣợng dữ liệu lớn, chứa đựng thông tin mơ hồ, không chắc chắn. Mục đích chính của phân tích dữ liệu dựa trên lý thuyết tập thô nhằm đƣa ra các xấp xỉ để biểu diễn các đối tƣợng không thể đƣợc phân lớp một cách chắc chắn bằng tri thức có sẵn. Theo quan điểm của lý thuyết tập thô, mọi tập thô đều liên kết với 2 tập “rõ” là xấp xỉ dƣới và xấp xỉ trên của nó. Xấp xỉ dƣới bao gồm các đối tƣợng chắc chắn thuộc, còn xấp xỉ trên chứa tất cả các đối tƣợng có khả năng thuộc về tập đó. Các tập xấp xỉ là cơ sở để rút ra các kết luận(tri thức) từ cơ sở dữ liệu. Do đó trong luận văn này dựa trên lý thuyết tập thô cụ thể là xấp xỉ trên của tập thô và thuật toán phân cụm thô đƣợc đề xuất [2] áp dụng phân cụm trên dữ liệu tuần tự. z 2 Cấu trúc của luận văn của tôi đƣợc chia làm ba chƣơng nhƣ sau: Chương 1: Tổng quan về phân cụm dữ liệu. Giới thiệu về phân cụm dữ liệu và các phƣơng pháp phân cụm. Chương 2: Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thông tin, bảng quyết định, tính không phân biệt đƣợc và xấp xỉ tập hợp. Chương 3:Áp dụng thuật toán phân cụm thô vào bài toán phân cụm ngƣời dùng trên Web. Dựa trên lý thuyết tập thô và áp dụng thuật toán phân cụm thô phân cụm ngƣời dùng trên Web( chuyển hƣớng Web của ngƣời dùng). z 3 CHƢƠNG I TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1 Phân cụm dữ liệu là gì Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, cácmẫu dữ liệu tự nhiên, tiềm ẩn, quan trọng trong tập dữ liệu lớn từ đó cung cấpthông tin, tri thức hữu ích cho việc ra quyết định. Phân cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thƣờng mà chúng ta vẫn làm và thực hiện hàng ngày. Ví dụ nhƣ phân loại học sinh trong lớp; phân loại đất đai; phân loại tài sản; phân loại sách trong thƣ viện;… Cụm dữ liệu là tập hợp các đối tƣợng có những tính chất nào đó tƣơng tự nhau ở một mức độ nào đó trong tập dữ liệu. Ở một mức cơ bản nhất, ngƣời ta đã đƣa ra định nghĩa phân cụm dữ liệu (PCDL) nhƣ sau:[3] “Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining), nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho ra quyết định.” Quá trình PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao các phần tử trong cùng một cụm thì “tƣơng tự” nhau và các phần tử trong các cụm khác nhau thì “kém tƣơng tự” nhau. Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định theo phƣơng pháp phân cụm.1 Mô phỏng vấn đề phân cụm dữ liệu. z 4 Trong học máy, PCDL đƣợc xem là vấn đề học không có giám sát (unsupervised learning), vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chƣa biết trƣớc các thông tin về cụm, các thông tin về tập huấn luyện hay thông tin nhãn của các lớp. Trong nhiều trƣờng hợp, nếu phân lớp đƣợc xem là vấn đề học có giám sát thì PCDL là một bƣớc trong phân lớp dữ liệu, nó sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu.[3,2] Với một tập dữ liệu, quá trình phân cụm có thể cho ra nhiều kết quả khác nhau tùy thuộc vào tiêu chí cụ thể đƣợc sử dụng để phân cụm. Các bƣớc cơ bản của quá trình phân cụm đƣợc thể hiện trong hình 1.1 và đƣợc tóm tắt nhƣ sau: Lựa chọn đặc trưng (Feature selection): các đặc trƣng phải đƣợc lựa chọn một cách hợp lý để có thể “mã hóa” nhiều thông tin nhất liên quan đến nhiệm vụ mà chúng ta quan tâm. Mục tiêu chính là giảm thiểu dƣ thừa thông tin giữa các đặc trƣng. Do đó, tiền xử lý dữ liệu là một nhiệm vụ quan trọng trƣớc khi tiến hành các bƣớc sau.