Luận Văn Thạc Sĩ Khoa Học Máy Tính: Phương Pháp Khai Thác Tập Hiếm Từ Phát Hiện Đến Mở Rộng

Luận văn thạc sĩ khoa học máy tính tập trung khai thác các tập hiếm, từ phát hiện đến mở rộng, ứng dụng trong phân tích dữ liệu hiệu quả.

• Tác giả: Trần Thanh Phương
• Người hướng dẫn: PGS. Quản Thanh Thơ
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai thác các tập hiếm: Từ phát hiện đến mở rộng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu và giới hạn của đề tài
• 1.3. Đối tượng và phạm vi
• 1.4. Phương pháp tiến hành
• 1.5. Những đóng góp của đề tài
• 1.6. Cấu trúc của luận văn
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Mô hình học tích cực active learning và mô hình học máy có tương tác
• 2.2. Các phương pháp phát hiện thể loại hiếm cần biết trước thông tin về tập dữ liệu
• 2.3. Các phương pháp phát hiện thể loại hiếm không cần biết trước thông tin
• 2.4. Hướng tiếp cận của đề tài
• 3. CHƯƠNG 3: CÁC KỸ THUẬT ĐƯỢC SỬ DỤNG
• 3.1. Giải thuật Biclustering
• 3.2. Các cấu trúc Bicluster
• 3.3. Đánh giá kết quả biclustering
• 3.4. Các giải thuật biclustering
• 3.5. Kd-tree và giải thuật tìm kiếm k-NN trên cây kd-tree
• 3.6. Minh họa cách hiện thực kd-tree
• 3.7. Giải thuật tìm kiếm NN
• 3.8. Giải thuật tìm kiếm k-NN
• 4. CHƯƠNG 4: MÔ HÌNH KHAI THÁC CÁC TẬP HIẾM TỪ PHÁT HIỆN ĐẾN MỞ RỘNG ĐƯỢC ĐỀ XUẤT
• 4.1. Ý tưởng xây dựng mô hình
• 4.2. Case study minh họa
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Tạo tập thí nghiệm
• 5.2. Kết quả chạy thí nghiệm
• 5.3. Đánh giá độ chính xác và tốc độ của hệ thống
• 6. CHƯƠNG 6: KẾT LUẬN VÀ ĐỀ XUẤT
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu

Luận văn thạc sĩ này tập trung vào lĩnh vực Khoa học máy tính, cụ thể là Khai thác tập hiếm từ Phát hiện tập hiếm đến Mở rộng tập hiếm. Nghiên cứu này nhằm mục đích phát triển các thuật toán khai thác dữ liệu hiệu quả để phát hiện và mở rộng các tập dữ liệu hiếm, đặc biệt trong bối cảnh xử lý dữ liệu lớn và tối ưu hóa thuật toán. Phương pháp khai thác được đề xuất kết hợp các kỹ thuật như biclustering, time series, và tìm kiếm k-NN trên kd-tree để đạt được độ phức tạp thời gian thấp.

1.1 Lý do chọn đề tài

Phát hiện thể loại hiếm là một lĩnh vực mới nổi trong khai phá dữ liệu, với ứng dụng rộng rãi trong các lĩnh vực như y tế, tài chính, và an ninh. Các thể loại hiếm thường xuất hiện trong các dữ liệu bất thường, và việc phát hiện chúng có thể dẫn đến những khám phá quan trọng. Ví dụ, trong y tế, việc phát hiện các triệu chứng hiếm gặp có thể giúp chẩn đoán bệnh hiếm. Trong tài chính, phát hiện các giao dịch gian lận là một ứng dụng thiết thực của khai thác tập hiếm.

1.2 Mục tiêu và giới hạn của đề tài

Mục tiêu chính của nghiên cứu là phát triển một thuật toán prior-free để phát hiện các thể loại hiếm mà không cần biết trước thông tin về tập dữ liệu. Điều này đặc biệt hữu ích trong các ứng dụng thực tế, nơi thông tin về dữ liệu thường không đầy đủ. Nghiên cứu cũng hướng đến việc mở rộng thuật toán để khám phá tất cả các mẫu dữ liệu thuộc về một thể loại hiếm đã được phát hiện.

II. Tổng quan

Chương này khảo sát các công trình nghiên cứu liên quan đến phát hiện thể loại hiếm và khai thác dữ liệu. Các mô hình học tích cực và học máy có tương tác được đề cập như những phương pháp hiệu quả để xử lý các dữ liệu bất thường. Các mô hình này yêu cầu sự tham gia của con người để phân loại dữ liệu, giúp tăng độ chính xác trong việc phát hiện các thể loại hiếm.

2.1 Mô hình học tích cực và học máy có tương tác

Mô hình học tích cực của D. Moore [10] đề xuất việc sử dụng chuyên gia để phân loại các dữ liệu bất thường, giúp loại bỏ các sai sót do nhiễu dữ liệu. Mô hình học máy có tương tác của Theiler [3] cũng tương tự, nhưng tập trung vào việc tối ưu hóa mô hình dữ liệu thông qua sự tương tác của người dùng. Cả hai mô hình đều nhấn mạnh tầm quan trọng của việc tích hợp tri thức con người vào quá trình phân tích dữ liệu.

III. Các kỹ thuật được sử dụng

Chương này đi sâu vào các kỹ thuật được sử dụng trong nghiên cứu, bao gồm biclustering, time series, và tìm kiếm k-NN trên kd-tree. Biclustering là một phương pháp hiệu quả để phân cụm dữ liệu đa chiều, trong khi time series giúp xử lý các dữ liệu có yếu tố thời gian. Tìm kiếm k-NN trên kd-tree được sử dụng để tối ưu hóa quá trình tìm kiếm các mẫu dữ liệu tương tự.

3.1 Giải thuật Biclustering

Biclustering là một kỹ thuật quan trọng trong phân tích dữ liệu, đặc biệt là trong việc phát hiện các thể loại hiếm. Tuy nhiên, các giải thuật biclustering hiện tại thường có độ phức tạp cao và kết quả không chính xác. Nghiên cứu này đề xuất việc kết hợp biclustering với tìm kiếm k-NN trên kd-tree để cải thiện độ chính xác và hiệu quả.

3.2 Tìm kiếm k NN trên kd tree

Tìm kiếm k-NN trên kd-tree là một phương pháp hiệu quả để tìm các mẫu dữ liệu tương tự trong không gian đa chiều. Kỹ thuật này giúp giảm độ phức tạp thời gian và tăng tốc độ xử lý dữ liệu, đặc biệt trong các tập dữ liệu lớn.

IV. Mô hình khai thác các tập hiếm

Chương này trình bày mô hình khai thác các tập hiếm được đề xuất, từ phát hiện đến mở rộng. Mô hình này kết hợp các kỹ thuật biclustering, time series, và tìm kiếm k-NN trên kd-tree để đạt được độ phức tạp thời gian thấp và hiệu quả cao. Một case study được đưa ra để minh họa cho mô hình này.

4.1 Ý tưởng xây dựng mô hình

Mô hình được xây dựng dựa trên ý tưởng kết hợp các kỹ thuật biclustering và tìm kiếm k-NN trên kd-tree để phát hiện và mở rộng các thể loại hiếm. Biclustering giúp phát hiện các cụm dữ liệu bất thường, trong khi tìm kiếm k-NN trên kd-tree giúp khám phá tất cả các mẫu dữ liệu thuộc về một thể loại hiếm đã được phát hiện.

V. Thực nghiệm

Chương này trình bày các kết quả thực nghiệm của mô hình được đề xuất. Các thí nghiệm được thực hiện trên các tập dữ liệu biểu diễn gen, và kết quả cho thấy mô hình đạt được độ chính xác cao và thời gian xử lý thấp. Các đánh giá về độ chính xác và tốc độ của hệ thống cũng được đưa ra.

5.1 Kết quả thí nghiệm

Các thí nghiệm cho thấy mô hình đề xuất đạt được độ chính xác cao trong việc phát hiện và mở rộng các thể loại hiếm. Thời gian xử lý cũng được tối ưu hóa đáng kể nhờ việc sử dụng tìm kiếm k-NN trên kd-tree.

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

Nghiên cứu này đã đề xuất một mô hình hiệu quả để khai thác các tập hiếm từ phát hiện đến mở rộng. Mô hình kết hợp các kỹ thuật biclustering, time series, và tìm kiếm k-NN trên kd-tree để đạt được độ phức tạp thời gian thấp và hiệu quả cao. Các hướng phát triển trong tương lai bao gồm việc áp dụng mô hình này vào các lĩnh vực khác như phân tích thống kê và quản lý dữ liệu.

6.1 Hướng phát triển

Trong tương lai, nghiên cứu có thể mở rộng bằng cách áp dụng mô hình này vào các lĩnh vực khác như phân tích thống kê và quản lý dữ liệu. Việc tích hợp thêm các kỹ thuật học máy và trí tuệ nhân tạo cũng là một hướng phát triển tiềm năng.

Nội dung chính

Tổng quan nghiên cứu

Phát hiện và khai thác các tập hiếm là một lĩnh vực nghiên cứu mới nổi trong khoa học máy tính, bắt nguồn từ khai phá dữ liệu truyền thống nhằm phát hiện các thể loại hiếm trong các tập dữ liệu bất thường. Theo ước tính, các lớp hiếm thường chiếm tỷ lệ rất nhỏ trong tổng thể dữ liệu, nhưng lại có ý nghĩa quan trọng trong nhiều ứng dụng thực tế như chẩn đoán y tế, phát hiện gian lận tài chính, an ninh mạng và thậm chí là phát hiện tội phạm. Ví dụ, trong y học, các triệu chứng hiếm có thể là dấu hiệu của bệnh mới hoặc chưa được biết đến, trong khi trong tài chính, các giao dịch gian lận thường là các trường hợp hiếm nhưng có tác động lớn.

Mục tiêu chính của luận văn là nghiên cứu và phát triển một giải thuật phát hiện các tập hiếm không cần biết trước thông tin về tập dữ liệu (prior-free) với độ phức tạp thời gian thấp, đồng thời mở rộng để khám phá toàn bộ các mẫu dữ liệu thuộc về các tập hiếm đã phát hiện. Nghiên cứu tập trung trên dữ liệu biểu diễn gen, trong phạm vi thời gian thực hiện từ năm 2013 tại Trường Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh.

Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp một phương pháp hiệu quả, có thể áp dụng cho các tập dữ liệu đa chiều, có yếu tố thời gian, giúp giảm thiểu thời gian xử lý và tăng độ chính xác trong phát hiện các thể loại hiếm. Điều này góp phần nâng cao hiệu quả trong các lĩnh vực ứng dụng như y tế, tài chính, an ninh mạng và khoa học dữ liệu lớn.

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 và mô hình chính:

1. Mô hình phân bố dữ liệu của Pelleg và Moore: Giả định các lớp hiếm tồn tại trong các tập nhỏ của các bất thường có tính chất tương tự, thường được nhóm lại thành các cụm nhỏ gọn trong không gian đặc trưng. Các lớp bình thường có phân bố Gaussian với phương sai lớn, trong khi các lớp hiếm có phương sai thấp hơn và phân bố cục bộ không đồng đều. Đặc điểm này giúp phân biệt các lớp hiếm với các điểm ngoại lai rời rạc.

2. Mô hình học tích cực (Active Learning) và học máy có tương tác: Mô hình này cho phép sự tham gia của chuyên gia để phân loại các điểm dữ liệu bất thường, giúp nâng cao độ chính xác và giảm thiểu số lần truy vấn dữ liệu. Người dùng tương tác với mô hình để cung cấp tri thức miền, loại bỏ dữ liệu nhiễu và nhập nhằng, từ đó tối ưu hóa mô hình dữ liệu.

Các khái niệm chính bao gồm:

• Biclustering: Phương pháp gom cụm dữ liệu đồng thời trên hàng và cột của ma trận dữ liệu, đặc biệt hữu ích với dữ liệu biểu diễn chuỗi thời gian.
• Chuỗi thời gian (Time Series): Dữ liệu có thứ tự thời gian, yêu cầu các bicluster phải có các cột liên tiếp nhau.
• Tìm kiếm k-NN trên kd-tree: Kỹ thuật tìm kiếm k điểm lân cận gần nhất trong không gian đa chiều với độ phức tạp thời gian thấp, giúp mở rộng khám phá các mẫu dữ liệu thuộc tập hiếm.

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

Nguồn dữ liệu sử dụng là tập dữ liệu biểu diễn gen, không có thông tin phân loại trước về số lượng lớp hay tỷ lệ phân bố. Phương pháp nghiên cứu gồm các bước chính:

• Tiền xử lý dữ liệu: Biến đổi dữ liệu gốc thành dạng rời rạc hóa theo chuỗi thời gian, lọc nhiễu và chuẩn hóa để phù hợp với giải thuật biclustering.
• Phát hiện thể loại hiếm: Áp dụng giải thuật biclustering CCC-Biclustering và e-CCC-Biclustering để tìm các bicluster cực đại với mẫu biểu thị xấp xỉ, giới hạn trong các cột liên tiếp nhằm giảm độ phức tạp tính toán.
• Mở rộng khám phá: Sử dụng cấu trúc kd-tree để xây dựng cây phân vùng không gian đa chiều, kết hợp giải thuật tìm kiếm k-NN nhằm xác định tất cả các mẫu dữ liệu tương tự với các mẫu bất thường đã phát hiện.
• Tương tác chuyên gia: Cho phép chuyên gia lĩnh vực tham gia đánh giá và xác nhận các mẫu dữ liệu bất thường, đảm bảo tính chính xác và thực tiễn của kết quả.

Cỡ mẫu nghiên cứu được lựa chọn dựa trên tập dữ liệu biểu diễn gen với số chiều lên đến khoảng 20, phù hợp với khả năng xử lý của các giải thuật biclustering và kd-tree. Phương pháp chọn mẫu là không giám sát, không cần biết trước thông tin về số lượng lớp hay phân bố dữ liệu. Thời gian nghiên cứu kéo dài trong năm 2013, với các giai đoạ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ả của giải thuật biclustering trên dữ liệu chuỗi thời gian: Giải thuật e-CCC-Biclustering cho phép phát hiện các bicluster cực đại với mẫu biểu thị xấp xỉ, giúp phát hiện các tập hiếm có tính chặt chẽ và liên tục trên các cột dữ liệu. Thời gian thực thi giảm đáng kể so với các giải thuật biclustering truyền thống, với độ phức tạp đa thức theo kích thước ma trận.

2. Khả năng mở rộng khám phá bằng tìm kiếm k-NN trên kd-tree: Việc sử dụng kd-tree giúp giảm độ phức tạp tìm kiếm các điểm lân cận gần nhất xuống còn O(k), trong khi tìm kiếm tuyến tính có độ phức tạp O(N). Kết quả thí nghiệm cho thấy, với số lượng điểm dữ liệu lớn, thời gian tìm kiếm giảm hơn 50% so với phương pháp truyền thống.

3. Tính không phụ thuộc tham số và prior-free: Thuật toán không yêu cầu biết trước số lượng lớp hay tỷ lệ phân bố, phù hợp với các tập dữ liệu thực tế không có nhãn. Điều này giúp tăng tính ứng dụng trong các lĩnh vực như y tế, tài chính, và an ninh mạng.

4. Tương tác chuyên gia nâng cao độ chính xác: Việc cho phép chuyên gia tham gia đánh giá kết quả giúp loại bỏ các điểm bất thường giả, tăng độ tin cậy của hệ thống. Thời gian xử lý tổng thể được rút ngắn nhờ giảm số lần truy vấn dữ liệu không cần thiết.

Thảo luận kết quả

Nguyên nhân chính dẫn đến hiệu quả của phương pháp là sự kết hợp giữa biclustering giới hạn trên chuỗi thời gian và tìm kiếm k-NN trên cấu trúc kd-tree, tận dụng đặc điểm phân bố dữ liệu của các lớp hiếm. So với các nghiên cứu trước đây yêu cầu biết trước thông tin về tập dữ liệu hoặc có độ phức tạp tính toán cao, phương pháp này mang lại sự cân bằng giữa độ chính xác và hiệu quả tính toán.

Kết quả cũng phù hợp với các nghiên cứu về mô hình học tích cực và học máy có tương tác, nhấn mạnh vai trò của con người trong việc xác nhận dữ liệu bất thường. Biểu đồ so sánh thời gian thực thi giữa các giải thuật biclustering truyền thống và e-CCC-Biclustering, cùng với biểu đồ hiệu suất tìm kiếm k-NN trên kd-tree, minh họa rõ ràng sự cải thiện về mặt hiệu quả.

Tuy nhiên, phương pháp vẫn còn hạn chế khi số chiều dữ liệu quá lớn, do đó cần nghiên cứu thêm về kỹ thuật giảm chiều và chọn đặc trưng đồng thời để nâng cao hiệu quả trên dữ liệu đa chiều cao.

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

1. Phát triển giao diện tương tác trực quan cho chuyên gia: Thiết kế hệ thống có giao diện dễ sử dụng, cho phép chuyên gia dễ dàng đánh giá và phân loại các mẫu dữ liệu bất thường, giảm thiểu thời gian và công sức trong quá trình phân tích. Thời gian triển khai dự kiến trong 6 tháng, do nhóm phát triển phần mềm thực hiện.

2. Tối ưu hóa thuật toán biclustering cho dữ liệu đa chiều cao: Nghiên cứu và áp dụng các kỹ thuật giảm chiều như PCA hoặc co-selection để xử lý hiệu quả các tập dữ liệu có số chiều lớn hơn 20, nhằm mở rộng phạm vi ứng dụng. Thời gian nghiên cứu và thử nghiệm khoảng 1 năm, do nhóm nghiên cứu khoa học máy tính đảm nhiệm.

3. Mở rộng ứng dụng sang các lĩnh vực thực tế khác: Áp dụng phương pháp vào các lĩnh vực như giám sát an ninh mạng, phát hiện gian lận tài chính, và phân tích dữ liệu viễn thám để đánh giá tính khả thi và hiệu quả. Thời gian thử nghiệm 6-12 tháng, phối hợp với các chuyên gia ngành liên quan.

4. Nâng cao khả năng xử lý dữ liệu thời gian thực: Tích hợp giải thuật tìm kiếm k-NN xấp xỉ và tối ưu hóa cấu trúc kd-tree để xử lý các luồng dữ liệu lớn và liên tục trong thời gian thực, phục vụ các ứng dụng đòi hỏi phản hồi nhanh. Thời gian phát triển dự kiến 9 tháng, do nhóm kỹ thuật phần mềm thực hiệ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 khoa học máy tính: Có thể áp dụng các kỹ thuật biclustering, kd-tree và k-NN trong nghiên cứu về khai phá dữ liệu, học máy và xử lý dữ liệu đa chiều.

2. Chuyên gia phân tích dữ liệu trong y tế và sinh học: Sử dụng phương pháp để phát hiện các mẫu hiếm trong dữ liệu biểu diễn gen, hỗ trợ chẩn đoán bệnh và nghiên cứu y sinh.

3. Chuyên viên an ninh mạng và tài chính: Áp dụng để phát hiện các hành vi bất thường, gian lận hoặc tấn công mạng dựa trên phân tích dữ liệu lớn và phức tạp.

4. Nhà phát triển phần mềm và hệ thống thông tin: Tham khảo để xây dựng các hệ thống phát hiện bất thường hiệu quả, có khả năng mở rộng và tương tác với người dùng.

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

1. Phương pháp này có thể áp dụng cho dữ liệu không phải chuỗi thời gian không?
   Phương pháp chủ yếu thiết kế cho dữ liệu chuỗi thời gian với biclustering trên các cột liên tiếp. Tuy nhiên, có thể điều chỉnh để áp dụng cho dữ liệu không theo thứ tự thời gian bằng cách thay đổi ràng buộc bicluster, nhưng sẽ tăng độ phức tạp tính toán.

2. Làm thế nào để xác định số lượng k trong tìm kiếm k-NN?
   Số lượng k được xác định dựa trên đặc điểm dữ liệu và mục tiêu phân tích. Trong nghiên cứu, k được chọn sao cho đủ để mở rộng khám phá toàn bộ tập hiếm mà không làm tăng quá nhiều thời gian tính toán.

3. Phương pháp có yêu cầu dữ liệu phải được chuẩn hóa không?
   Dữ liệu cần được tiền xử lý, bao gồm lọc nhiễu và chuẩn hóa để đảm bảo tính nhất quán và hiệu quả của biclustering và tìm kiếm k-NN, đặc biệt khi sử dụng khoảng cách Euclide làm thước đo.

4. Có thể áp dụng phương pháp cho dữ liệu có số chiều rất lớn không?
   Hiện tại, phương pháp hiệu quả với dữ liệu có số chiều tối đa khoảng 20. Với số chiều lớn hơn, cần kết hợp kỹ thuật giảm chiều để tránh giảm hiệu suất và tăng thời gian tính toán.

5. Vai trò của chuyên gia trong mô hình học tích cực là gì?
   Chuyên gia giúp phân loại và xác nhận các điểm bất thường, loại bỏ dữ liệu nhiễu và nhập nhằng, từ đó nâng cao độ chính xác của mô hình và giảm số lần truy vấn dữ liệu không cần thiết.

Kết luận

• Đã phát triển thành công giải thuật prior-free kết hợp biclustering và tìm kiếm k-NN trên kd-tree để phát hiện và khai thác các tập hiếm với độ phức tạp thời gian thấp.
• Giải thuật biclustering e-CCC-Biclustering cho phép phát hiện các bicluster cực đại trên dữ liệu chuỗi thời gian với mẫu biểu thị xấp xỉ, giảm thiểu sai số và tăng hiệu quả tính toán.
• Tìm kiếm k-NN trên cấu trúc kd-tree giúp mở rộng khám phá toàn bộ các mẫu dữ liệu thuộc tập hiếm đã phát hiện, tiết kiệm thời gian so với tìm kiếm tuyến tính.
• Mô hình học tích cực và học máy có tương tác được tích hợp để tăng độ chính xác và tính thực tiễn của hệ thống thông qua sự tham gia của chuyên gia.
• Hướng phát triển tiếp theo bao gồm tối ưu hóa cho dữ liệu đa chiều cao, mở rộng ứng dụng thực tế và nâng cao khả năng xử lý dữ liệu thời gian thực.

Đề nghị các nhà nghiên cứu và chuyên gia trong lĩnh vực khai phá dữ liệu, y sinh, tài chính và an ninh mạng tiếp cận và ứng dụng phương pháp để nâng cao hiệu quả phân tích dữ liệu phức tạp.

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

Chương 1: Giới thiệu Chương 2: Tổng quan Chương 2: TONG QUAN Trong chương nay chung tôi sé khảo sat các công trình đã đăng tai có liên quan, sau đó giới thiệu phương pháp và hướng tiếp cận của đề tai.1 Mo hình học tích cực active learning và mo hình học máy có tương tác Phát hiện thể loại hiếm dựa vào phát hiện các bất thường, tuy nhiên bất thường có thể là do sai sót nhập dữ liệu, hoặc là dữ liệu bị nhiễu nên tác giả D. Moore [10] đã dé xuất một mô hình hoc tích cực mà trong đó các bất thường sẽ được phân loại một cách chủ quan bởi người dùng. Tác giả đã đưa ra 2 giả định, đầu tiên có rất ít các dị thường hữu ích trong một tập dữ liệu lớn. Thứ hai, các di thường hữu ich và không hữu ich đôi khi có thể ton tại trong một lớp nhỏ các dữ liệu tương tự.

Thách thức là làm sao nhận dạng các thể loại hiễm trong một tập hợp đữ liệu bị nhiễu với sự trợ giúp của chuyên gia về lĩnh vực dit liệu đó. Sau đây là đề xuất mô hình học tích cực của tác giả. Tập dữ Hỏi chuyên Đưa ra các liệu ngẫu » gia để phân < dt liệu “quan nhién loại một sô trọng” đữ liệu A V Xây dung mô Duyệt qua tât hình từ dữ liệu | cả dữ liệu và các nhãn thông qua mô phân loại hình Hình 2.1: Mo hình học tích cực [10, tr.2] Chương 2: Tổng quan Mô hình trên là mô hình học bán giám sát, thực hiện truy van di liệu va hỏi chuyên gia dé phan loại di liệu có phải là bất thường hay không, kết qua phân loại sẽ được dùng để nâng cấp mô hình dữ liệu và lặp lại quá trình truy van dit liệu. cho tới khi xác định được tất cả các thể loại hiếm.

Theiler [3] cũng dé xuất mô hình tương tự, mô hình học máy có tương tác là kỹ thuật mô hình hướng dữ liệu và hướng tri thức nhằm biến đổi dữ liệu gốc trực quan hơn để trình bày được tới người sử dụng. Người dùng sẽ tương tác với mô hình để cung cấp thêm tri thức, tính toán để loại bỏ nhập nhằng và dữ liệu nhiễu nếu có. Sự tương tác của người dùng chứa thông tin về độ ưu tiên và tri thức miền có giá trị. Sự tương tác được lưu lại va bién đối mô hình dữ liệu có sử dụng các kỹ thuật mô hình hướng dữ liệu và hướng tri thức.

Theo thời gian, và với sự tham gia của người dùng, mô hình người dùng cung cấp một công cụ có giá trị để tối ưu hóa mô hình dé liệu, dẫn tới sự gia tăng trực quan hóa dữ liệu cụ thể hơn, và thu hẹp khoảng cách ngữ nghia giữa người sử dụng và ứng dụng. Mô hình của | Truy vân va © Dữ liệu người dùng an hồi Trình bày tới người dùng Mô hình dữ Nhận dạng dữ liệu liệu hữu ích Hình 2.2: Mo hình học máy có tương tác [3, tr.2| Chương 2: Tổng quan Mô hình học tích cực và mô hình học máy có tương tác đều có điểm chung là có sự tham gia, trợ giúp của con người để phân loại dữ liệu hữu ích. Vấn đề còn lại là mô hình dữ liệu, chiến lược lấy mẫu, thiết kế giải thuật như thế nào để số lần truy vẫn dữ liệu và lẫy thông tin phản hồi của người dùng là ít nhất có thé dé xác định được tất cả các thé loại hiếm trong tập dữ liệu.2 Các phương pháp phát hiện thé loại hiếm cần biết trước thông tin về tập dữ liệu Các tác giả D. Moore [10] giả định mô hình hỗn hợp mixture model phù hop với sự phân bố dữ liệu và chọn lựa phan tử khác biệt nhất để phân loại.

Tác giả đã liệt kê một loạt các chiến lược lây mẫu như chọn lựa các điểm có khả năng thấp, chọn lựa các điểm mơ hỗ, hoặc kết hợp các điểm có kha năng thấp và mơ hồ, hoặc dùng chiến lược đan xen. Tuy nhiên việc giả định mô hình hỗn hợp đòi hỏi các lớp bình thường và lớp hiém phải tách biệt nhau. Điều này là không khả thi với các tập dữ liệu thực tế. Một hướng tiếp cận khác theo phương pháp phân loại classification, các tác gia J.

Chen [4] tìm cách giải quyết van dé phát hiện thé loại hiém trên tập dữ liệu không cân bang. Bang cách thực hiện phân chia các lớp lớn thành các vùng nhỏ hơn (local clustering) với kích thước tương đối cân bằng. Sau đó, áp dụng các thuật toán học truyền thong có giám sát như Support Vector Machines (SVMs) dé phân loại. Xét trường hợp tập dữ liệu là không tuyến tính tách rời, có thể cản trở việc thực hiện phân loại tuyến tính.

Tuy nhiên bằng cách chia nhỏ vùng không khả tách tuyến tính thành các vùng nhỏ hơn khả tách tuyến tính, phân loại tuyến tính truyền thông van có thê làm việc tot. 10 Chương 2: Tổng quan Scenario ll x ) ® ; 8 ey pani 0.5 li-t: "Pure" SVMs lI-II: COG Hình 2.3 : So sánh phương pháp phân loại bang SVM truyền thống và phương pháp kết hợp phân cụm clustering và phân loại SVM (COG) |4.4| Scenario Ill HN. ae rnin 7 Ae i Se VN o 0 0.5 1 0 05 1 ili-t COG IIF-|i: OS III-11!: COG-OS Hình 2.4: Tích hợp kỹ thuật lấy mẫu over-sampling vào chương trình COG cho kết quả dự đoán các lớp hiếm tốt hon trong tập dữ liệu cực kỳ không cân bằng.4] Các phương pháp trên chưa xem xét tầm quan trọng của các thuộc tính dữ liệu đặc biệt trong những thể loại khác nhau. Ví dụ khi xem xét về tội phạm, các thuộc tính như vi trí, nạn nhân là những ai, hung khí là gi.

đóng vai trò quan trọng trong việc tìm kiếm các trường hợp phạm tội tương tự của cùng thủ phạm vi tội phạm có khuynh hướng phạm tội gần giống như những vụ án khác trong quá khứ. Do vậy các thuộc tính đặc biệt trong từng thể loại khác nhau có tầm quan trọng hay trọng số cao hơn các thuộc tính khác. Tính toán độ lợi thông tin của các thuộc tính còn lại và đánh trọng số cho các thuộc tính này. Giai đoạn 2: áp dụng thuật toán K-Mean dé xác định K nhóm tương tự.

Một hướng tiếp cận khác, các tác giả J. Carbonell [6] đã phát triển một phương pháp phát hiện thể loại hiếm băng một chiến lược lẫy mẫu không giám sát dựa trên sự khác biệt về mật độ cục bộ. Phương pháp này không dựa trên sự giả định các lớp bình thường và các lớp bất thường là tách biệt với nhau. Mà các lớp này có thể chồng lên hoặc phủ lên nhau.

Cho biết trước số lượng các lớp hiém và xác xuất phân bố của các lớp này, ta có thé ước lượng được số mẫu K của mỗi lớp hiếm. Với mỗi phan tử, tính khoảng cách gần nhất tới K phần tử lân cận (Kth nearest neighbor) ta có thể xác định được khoảng cách nhỏ nhất giữa 2 phần tử r trong tập hợp. Kế tiếp ta vẽ đường tròn có bán kính lar trên mỗi điểm và đếm tong số phần tử n nam trong đường tròn này. Ta gọi giá trị n này là mật độ cục bộ của mỗi phần tử.

Nếu lay mật độ cục bộ cua phần tử 1 trừ đi mật độ cục bộ của phần tử J là một trong K điểm lân cận của phần tử i. Giá trị lớn nhất phản ánh sự thay đôi mật độ cục bộ nhiều nhất có khả năng là phan tử biên của lớp hiếm. Vì lớp hiém có khuynh hướng tập trung trong một vùng nhỏ còn hàm phân bồ xác xuất của lớp bình thường là trơn cục bộ. Hơn thế nữa, bán kính r là khoảng cách nhỏ nhất của K điểm lân cận nên nó sẽ không quá lớn dé làm trơn đi sự thay đổi mật độ cục bộ.

Tiếp tục tang dần giá tri bán kính r, ta có thé xác định được tat cả các điểm nằm trong vùng bất thường. Lawrence [8] cũng dựa trên chiến lược lay mẫu từ các vùng mà mật độ thay đôi nhiều nhất, phương pháp đề xuất sử dụng ma trận tương tự toàn cục được tạo bởi thuật toán xếp hạng đa dạng và nó cũng loại trừ giả thiết các lớp bình thường và các lớp hiếm là tách rời 12 Chương 2: Tổng quan nhau. So sánh với phương pháp [6]. phương pháp [8] cũng cần thông tin về xác suất hoặc cận trên xác suất của các lớp hiếm.

Các phương pháp dựa vào mật độ cục bộ chỉ hiệu quả thật sự khi mật độ cục bộ của các lớp hiếm cao hơn han mật độ cục bộ của các lớp bình thường. Để tránh bị ảnh hưởng bởi mật độ cục bộ, các tác giả H. Ma [9] đã đề xuất một phương pháp cải tiễn sử dụng nghịch đảo khoảng cách nhỏ nhất của K phần tử lân cận RKNN dé ước lượng mức độ biên của các điểm dit liệu. Điểm nao có mức độ biên cao hơn thì có xác suất cao hơn là phần tử biên của các lớp hiếm.

Nhìn chung phương pháp cũng dựa vào mật độ và phải biết trước tông số các lớp khác nhau trong tập dữ liệu. Rõ ràng trong thực tế, chúng ta không thể biết trước dữ liệu khảo sát sẽ có bao nhiêu lớp, nên cần phải nghiên cứu thêm về các phương pháp không cần tham số truyền vào, không cần biết trước thông tin về tập dữ liệu.3 Các phương pháp phát hiện thể loại hiếm không cần biết trước thông tin prior-free Vẫn là hướng tiếp cận dựa vào mật độ cục bộ, các tác giả J. Carbonell [7] xác định các phan tử biên của các lớp hiếm. Tuy nhiên phương pháp sử dụng không cần biết trước thông tin về số lượng các lớp, xác suất phân bố của các lớp.

Phương pháp ngầm định thực hiện ước lượng mật độ bán tham số và lựa chọn các mẫu có độ dốc lớn nhất dé phân loại. Bằng cách nay, nó tập trung vào những vùng có sự thay đôi tối đa trong mật độ cục bộ. Ví dụ hình sau cho thấy có sự thay doi đột ngột ở các điểm nhọn cho thấy có khả năng các điểm nay là phan tử biên của lớp hiếm. Ngoài ra, các điểm tạo thành đường cong trơn là các điểm thuộc lớp bình thường thỏa mãn phân bố xác Suât Gausian.

15 Chương 2: Tổng quan 0.5: Lớp bình thường có phân bố Gaussian với phương sai lớn trong khi 2 lớp hiếm tương ứng với hai đỉnh phương sai thấp hơn.Wong [11] trình bày phương pháp phát hiện thé loại hiém dựa trên sự chuyển dịch điểm trung vị theo phan cap.