Lập trình

1. Đặt vấn đề

Trong lĩnh vực nghiên cứu về khai phá dữ liệu nói chung cũng như trong nghiên cứu về các thuật toán phân lớp nói riêng, vấn đề xử lý dữ liệu lớn ngày càng trở thành vấn đề cấp thiết và đóng vai trò chủ đạo trong việc giải quyết các bài toán thực tế. Phần lớn các thuật toán phân lớp đã phát triển chỉ có thể giải quyết được với một lượng số liệu giới hạn cũng như với một độ phức tạp dữ liệu biết trước. Trong khi đó lượng dữ liệu mà chúng ta thu thập được ngày càng trở nên phong phú và đa dạng nhờ sự phát triển mạnh mẽ của khoa học kỹ thuật. Mặc dù rất nhiều kỹ thuật khai phá dữ liệu dựa trên một số nền tảng lý thuyết khác nhau đã được phát triển và ứng dụng từ rất lâu, nhưng thực tế cho thấy kết quả phụ thuộc rất nhiều vào đặc tính dữ liệu cũng như khả năng xử lý dữ liệu thô của từng nhóm nghiên cứu. Một điều hiển nhiên là với mỗi phương pháp chỉ có thể đáp ứng và xử lý tốt trên một vài dữ liệu và ứng dụng cụ thể nào đó. Trong khai phá dữ liệu thì phương pháp trích chọn đóng một vai trò quan trọng trong tiền xử lý số liệu. Hướng tiếp cận này làm tăng hiệu năng thu nhận tri thức trong các ngành như tin sinh, xử lý dữ liệu web, xử lý tiếng nói, hình ảnh với đặc tính là có rất nhiều thuộc tích (vài trăm cho đến vài trăm ngàn thuộc tính) nhưng thường chỉ có một số lượng tương đối nhỏ các mẫu dùng để huấn luyện (thường là vài trăm). Phương pháp trích chọn sẽ giúp giảm kích cỡ của không gian dữ liệu, loại bỏ những thuộc tính không liên quan và những thuộc tính nhiễu. Phương pháp này có ảnh hưởng ngay lập tức đến các ứng dụng như tăng tốc độ của thuật toán khai phá dữ liệu, cải thiện chất lượng dữ liệu và vì vậy tăng hiệu suất khai phá dữ liệu, kiểm soát được kết quả của thuật toán. Phương pháp này đã được giới thiệu từ những năm 1970 trong các tài liệu về xác suất thống kê, học máy và khai phá dữ liệu. Những năm trở lại đây, do nhu cầu giảm chiều số liệu ngày càng cao nên có rất nhiều các nghiên cứu về lựa chọn thuộc tính, lĩnh vực này phát triển mạnh mẽ cả về chiều rộng lẫn chiều sâu [1].

2. Cơ sở lý thuyết

2.1 Giới thiệu về trích chọn đặc trưng

Về cơ bản việc bóc tách các thuộc tính đặc trưng bao gồm hai phần là xây dựng các thuộc tính và lựa chọn các thuộc tính đặc trưng. Xây dựng bộ các thuộc tính là một công việc rất quan trọng trong việc xử lý số liệu. Khi xây dựng dữ liệu chúng ta cần phải đảm bảo không để mất nhiều thông tin quá cũng như không quá tốn kém về mặt chi phí. Phần thứ hai có mục tiêu tìm ra những thuộc tính đại diện cho đối tượng, loại bỏ những thuộc tính thừa và gây nhiễu nhằm tăng hiệu suất của các thuật toán khai phá dữ liệu.

Giảm bớt số chiều của mẫu và theo đó còn gọi là nén tập dữ liệu, thông qua trích chọn thuộc tính và lựa chọn thuộc tính. Quá trình này là bước cơ bản nhất trong việc tiền xử lý dữ liệu. Lựa chọn thuộc tính có thể là một phần vốn có của trích chọn thuộc tính ví dụ như phương pháp phân tích thành phần cơ bản hoặc thậm chí là một thiết kế xử lý thuật toán ví dụ như trong thiết kế cây quyết định. Tuy nhiên, lựa chọn thuộc tính thường là một bước cô lập riêng biệt trong một chuỗi xử lý [2].

Có thể định nghĩa lựa chọn thuộc tính là một quá trình tìm ra một tập con các thuộc tính từ M tập thuộc tính của tập dữ liệu N ban đầu, như vậy phải xác định tiêu chuẩn lựa chọn thuộc tính. Theo cách này, kích cỡ của không gian đặc trưng được rút ngắn tối đa theo một tiêu chuẩn định lượng nhất định. Khi kích cỡ của một lĩnh vực được mở rộng, số phần tử của tập N sẽ tăng lên, vì vậy việc tìm ra một tập đại diện tốt nhất thường gặp khó khăn và có nhiều vấn đề liên quan đến tập được chọn. Nhìn chung, một thuật toán trích chọn gồm 4 bước cơ bản: Sinh tập con, lượng giá tập con, điều kiện dừng và xác nhận kết quả.

Quá trình sinh tập con là một thủ tục tìm kiếm, về cơ bản nó sinh ra những tập con dùng cho việc lượng giá. Gọi N là số các đại diện (đặc trưng) của tập dữ liệu gốc ban đầu, thì tổng số các tập con có thể được sinh ra sẽ là 2n. 2n tập này sẽ liệt kê toàn bộ các tập con của không gian. Mỗi tập con được sinh ra bằng thuật toán cần được lượng giá trị bằng một tiêu chuẩn lượng giá trị nhất định và được so sánh với tập con tốt nhất đã tìm được trước nó. Nếu không có điều kiện dừng phù hợp, thuật toán này có thể sẽ chạy mãi không dừng. Điều kiện dừng của một quá trình sinh phải rơi vào một trong số các trường hợp sau:

- Toàn bộ các phần tử của tập hợp đều được chọn.

- Các phần tử chưa chọn bị lặp lại.

- Sinh thêm một tập con nữa cũng không cho kết quả tốt hơn.

- Đã chọn đủ số tập con thoả mãn điều kiện tiêu chuẩn.

Tập con tốt nhất được chọn ra phải được lượng giá trong những trường hợp khác nhau và nó cùng với tập gốc phải biểu diễn được với dữ liệu thực tế.

Lựa chọn các thuộc tính có thể tiến hành theo hai cách: cách thứ nhất là xếp loại các thuộc tính theo một tiêu chuẩn nào đó và lấy ra k thuộc tính đầu tiên, do đó cách này là dựa vào ngưỡng để chọn thuộc tính. Cách thứ hai là chọn ra tập con nhỏ nhất mà không làm giảm đi quá trình học, do đó với cách này tự động xác định số lượng thuộc tính.

Lựa chọn thuộc tính có thể dựa vào các mô hình, các chiến lược tìm kiếm, thước đo chất lượng thuộc tính và ước lượng. Có ba loại mô hình như Filter, Wrapper, 

Embedded. Mô hình Embedded là mô hình tích hợp thuộc tính được lựa chọn khi xây dựng mô hình ví dụ như thuật toán cây quyết định.

Các chiến lược tìm kiếm bao gồm: Forward, Backward, Floating, Branch & Bound, Randomized. Ước lượng của việc chọn lựa thuộc tính bao gồm hai nhiệm vụ: một là so sánh hai giai đoạn: trước và sau khi lựa chọn thuộc tính. Hai là so sánh hai thuật toán lựa chọn thuộc tính [1].

Tóm lại lựa chọn thuộc tính được xem như là sự tổng hợp của ba thành phần chính: tìm kiếm, đánh giá, chọn lựa mô hình. Hình 2.1 dưới đây thể hiện lựa chọn thuộc tính theo 3 thành phần nói trên [3].

Hình 1: Các thành phần chính của việc lựa chọn thuộc tính

2.2 Chiến lược tìm kiếm

Lựa chọn thuộc tính có thể được xem như là một vấn đề tìm kiếm, trong đó mỗi bước trong không gian tìm kiếm xác định ra một tập con thuộc tính liên quan. Giả sử ta có một tập dữ liệu với 3 thuộc tính (A1, A2, A3). Một mảng nhị phân mà mỗi thành phần của mảng được thiết lập là 1 nếu thuộc tính có chỉ số tương ứng trong mảng nhị phân được chọn. Nếu mảng có giá trị (1, 1, 1) có nghĩa là cả 3 thuộc tính được chọn và (1, 0, 0) có nghĩa là chỉ thuộc tính A1 được chọn. Do đó, sẽ có tất cả 2N tập con có thể có, trong đó N là số lượng thuộc tính của tập dữ liệu. Trong trường hợp có 3 thuộc tính sẽ có tất cả 8 trạng thái (tập con). Một tập con tối ưu thường nằm đâu đó giữa điểm đầu và điểm cuối cây. Câu hỏi đặt ra ở đây là: Chúng ta nên bắt đầu tìm kiếm từ đâu. Vấn đề sẽ rất đơn giản nếu không gian tìm kiếm nhỏ. Tuy nhiên, trên thực tế không gian tìm kiếm thường rất lớn (2N), bắt đầu từ câu hỏi “Đâu là điểm tìm kiếm phù hợp” sẽ xuất hiện các câu hỏi khác: Chiến lược tìm kiếm phù hợp là gì ? Trên thực tế chiến lược tìm kiếm lại bị ảnh hưởng bởi hướng tìm kiếm.

Giả sử ban đầu chúng ta chưa có một khái niệm cụ thể nào về tập thuộc tính tối ưu trong không gian tìm kiếm, thì sẽ không có sự khác biệt trong việc xác định điểm 4

xuất phát nên bắt đầu từ đâu (một tập rỗng hay một tập đủ các thuộc tính). Do đó, đối với phần lớn các vấn đề trong tìm kiếm thì trung bình thời gian để tìm ra tập con tối ưu giữa các hướng tìm kiếm khác nhau không có sự khác biệt. Tuy nhiên, hướng tìm kiếm lại có mối liên hệ chặt chẽ trong việc tạo ra tập con thuộc tính. Một phương pháp tìm kiếm là tìm ra tập con tối ưu bắt đầu từ một tập rỗng các thuộc tính (Ví dụ: Sequential Forward Generation), phương pháp còn lại là tìm ra tập con tối ưu bằng cách lần lượt loại bỏ các thuộc tính ít quan trọng từ một tập đủ các thuộc tính ban đầu

(Ví dụ: Sequential Backward Generation).
2.1.2 Tiêu chuẩn lựa chọn

Tất cả các chiến lược tìm kiếm đều có nhu cầu đánh giá một thuộc tính hoặc một tập con thuộc tính để xác định thuộc tính/tập con đó là tốt hay không tốt. Việc đánh giá này thường là phức tạp và có nhiều chiều đánh giá. Ví dụ, đánh giá có thể được đo lường theo những khía cạnh: các thuộc tính được chọn lựa có làm tăng độ chính xác của bộ phân lớp hay không và các thuộc tính được chọn lựa có giúp làm đơn giản các kết quả học do đó sẽ các kết quả này có thể dễ dàng để hiểu hay không… Sau đây là một số đo lường thường được sử dụng trong trích chọn thuộc tính.

a. Đo lường thông tin

Thông tin là một cách đo lường độ không ổn định của người nhận tin khi một người nhận tất cả các tin nhắn. Nếu người nhận tin biết được tin nhắn nào đang đến thì sự ngạc nhiên (uncertainty) của người đó sẽ thấp. Trong trường hợp anh ta hoàn toàn không biết tin nhắn nào đang đến, chúng ta giả sử rằng tất có các tin nhắn có xác suất đến bằng nhau, thì sự ngạc nhiên của anh ta đối với tin nhắn đó là cao. Trong ngữ cảnh của phân lớp, các tin nhắn là các lớp. Giả sử U là một hàm đo lường độ không ổn định của lớp, nếu U có giá trị lớn có nghĩa là mức độ không ổn định cao.

b. Đo lường khoảng cách

Kiểu đo lường này cũng được biết đến như là đo lường khác biệt hoặc đo lường phân biệt. Đo lường này được thực hiện thông qua việc đo khoảng cách giữa các hàm xác suất điều kiện lớp. Ví dụ đối với trường hợp có 2 lớp, D(X) là khoảng cách giữa P(X|c1) và P(X|c2), luật đánh giá thuộc tính xây dựng dựa trên khoảng cách D(X) nói rằng, trong hai thuộc tính X và Y thuộc tính X được chọn nếu D(X) > D(Y). Mục đích của việc chọn lựa này là ta cố gắng tìm ra các thuộc tính sao cho hai lớp được phân chia (khoảng cách giữa 2 lớp) là xa nhất có thể được.

c. Đo lường phụ thuộc

Đo lường này cũng được biết đến như là đo lường mối quan hệ, đo lường mối liên hệ. Đo lường này được thiết kế để lượng hóa mối quan hệ giữa hai biến bằng việc nếu biết được giá trị một biến ta có thể dự đoán được giá trị của biến còn lại. Trong đánh giá thuộc tính, thay bằng việc kiểm tra một thuộc tính thay đổi thông tin thu thập được hoặc thay đổi kỳ vọng xác suất lớp như thế nào, thì chúng ta sẽ xem xét một thuộc tính liên hệ với một lớp như thế nào (mạnh hay yếu). Gọi R(X) là đo lường phụ thuộc giữa thuộc tính X và lớp C, ta chọn thuộc tính X dựa trên đo lường phụ thuộc với thuộc tính Y nếu R(X) > R(Y). Nói một cách khác, chúng ta chọn thuộc tính có mối liên hệ chặt chẽ với lớp C hơn. Nếu X và C là độc lập thống kê thì giữa X và Y sẽ không có mối liên hệ và việc loại bỏ thuộc tính X sẽ  không làm ảnh hưởng đến việc phân lớp các thuộc tính còn lại. Nếu mỗi giá trị của thuộc tính X có mối liên hệ với một giá trị của lớp C, chúng ta kỳ vọng rằng R(X) sẽ có giá trị cực đại và thuộc tính X được chọn thuộc về lớp C.

2.1.3 Các mô hình Filter và Wrapper

Về cơ bản có thể phân loại các phương pháp lựa chọn thuộc tính theo hai cách tiếp cận khác nhau là Filter và Wrapper. Cách sử dụng đơn giản nhất của chọn lựa thuộc tính là sử dụng độ chính xác của bộ phân lớp như một đo lường hiệu quả của bộ phân lớp. Nếu mục đích của chúng ta là để cực tiểu hóa tỷ lệ lỗi của phân lớp và chi phí đo lường đối với mỗi thuộc tính là như nhau thì sử dụng độ chính xác dự báo của lớp như một tiêu chí đo lường hiệu quả là rất khả thi. Do vậy, chúng ta nên xây dựng một bộ phân lớp với mục đích là để có được độ chính xác dự báo cao nhất có thể, sau đó chọn lựa các thuộc tính được sử dụng bởi bộ phân lớp như là các thuộc tính tối ưu. Mô hình này cũng được gọi là mô hình Wrapper. Ngoài phương pháp đo lường trực tiếp ở trên, cũng có một phương pháp đo lường hiệu quả không trực tiếp khác, chủ yếu dựa trên việc đo lường khoảng cách và đo lường thông tin trong việc chọn lựa thuộc tính. Mô hình được xây dựng theo cách này được gọi là mô hình Filter.

a. Mô hình Wrapper

Hình 2: Mô Hình Wrapper

Mối quan tâm chính của khai phá dữ liệu là thu được độ chính xác dự đoán cao. Vấnđề chính ở đây là làm thế nào chúng ta có thể cải thiện được hiệu quả phân lớp dựa trên những tri thức học được từ dữ liệu. Một trong những các phương pháp nhằm cải thiện hiệu quả phân lớp là thông qua chọn lựa thuộc tính, vì thông qua chọn lựa thuộc tính chúng ta sẽ có tập dữ liệu tốt hơn cho phân lớp. Nếu chúng ta có thể chọn được các thuộc tính liên quan và loại bỏ các thuộc tính nhiễu chúng ta có thể nâng cao hiệu quả phân lớp mà cụ thể là độ chính xác của bộ phân lớp [4].

Mô hình chọn lựa thuộc tính Wrapper có thể giúp chúng ta thực hiện được những mong muốn trên. Hình 2.2 thể hiện mô hình Wrapper. Mô hình Wrapper bao gồm 2 giai đoạn: Giai đoạn 1 – chọn lựa tập con thuộc tính, trong giai đoạn này các tập con thuộc tính tốt nhất sẽ được lựa chọn dựa trên tiêu chí độ chính xác lớp (của bộ dữ liệu tập huấn); Giai đoạn 2 – học và kiểm tra (learning and testing), một bộ phân lớp sẽ học các tri thức từ dữ liệu tập huấn thông qua một tập các thuộc tính tốt nhất được chọn lựa, và được kiểm tra lại bằng một bộ dữ liệu kiểm tra. Khi các tập con thuộc tính được tạo ra một cách hệ thống (hướng tìm kiếm), đối với mỗi tập con thuộc tính sẽ có một bộ phân lớp được tạo ra từ dữ liệu bao gồm các thuộc tính đã được chọn lựa. Độ chính xác của bộ phân lớp được ghi lại trong mỗi lần thử nghiệm và tập con thuộc tính với độ chính xác cao nhất sẽ được giữ lại. Khi quá trình chọn lựa kết thúc, tập con thuộc tính với độ chính xác cao nhất sẽ được chọn. Giai đoạn 2 là quá trình học và kiểm tra thông thường, trong giai đoạn này chúng ta sẽ có độ chính xác dự báo trên bộ dữ liệu kiểm tra.

Độ chính xác ước tính của một bộ phân lớp trên dữ liệu tập huấn có thể không phản ánh đúng độ chính xác trên bộ dữ liệu kiểm tra. Do đó, vấn đề đặt ra ở đây là làm thế nào để có được ước lượng độ chính xác tốt nhất trên các bộ dữ liệu kiểm tra. Một trong những cách làm phổ biến là sử dụng kiểm chứng chéo (cross validation)

b. Mô hình Filter

Hình 3: Mô hình Filter

Ngoài cách dựa vào độ chính xác của bộ phân lớp ở trên, chúng ta cũng có thể sử dụng một số cách khác để làm tăng độ chính xác dự đoán của bộ phân lớp như: loại bỏ nhiễu, biến đổi dữ liệu (data reduction). Mặc dù chúng ta biết rằng khả năng xử lý của mô hình Wrapper đối với dữ liệu nhiều chiều bị hạn chế bởi việc chọn lựa bộ phân lớp. Tuy nhiên, trong ngữ cảnh của khai phá dữ liệu thì thông thường bộ dữ liệu thường là rất lớn và không thể dùng trực tiếp một bộ phân lớp để phân lớp dữ liệu cho bộ dữ liệu đó. Do đó, chúng ta cần sử dụng một số phương pháp tiền xử lý (pre-processing) đối với bộ dữ liệu đó trước khi áp dụng phân lớp bộ dữ liệu đó. Thông qua mô hình Wrapper có thể đảm bảo độ chính xác của các thuộc tính được chọn lựa. Tuy nhiên, do những hạn chế của mô hình này như: độ phức tạp thời gian lớn, hạn chế trong việc chọn lựa bộ phân lớp và khả năng xử lý với các bộ dữ liệu có kích cỡ lớn là không tốt. Dưới đây, chúng ta sẽ xem xét mô hình chon lựa thuộc tính Filter, mô hình này có thể khắc phục được một số hạn chế của mô hình Wrapper.

Mô hình Filter cũng bao gồm 2 giai đoạn:

• Giai đoạn 1 – Chọn lựa thuộc tính sử dụng các đo lường như thông tin, khoảng cách, độc lập hoặc độ đồng nhất không sử dụng bất kỳ một giải thuật học nào ở giai đoạn này;
• Giai đoạn 2 – Giai đoạn này tương tự như giai đoạn 2 trong mô hình Wrapper, một bộ phân lớp học các tri thức thông qua các thuộc tính được chọn lựa trên bộ dữ liệu huấn luyện và được kiểm tra lại trên bộ dữ liệu kiểm tra.

Mô hình chọn lựa thuộc tính Filter có một số đặc điểm sau: Mô hình này không chịu ảnh hưởng của một giải thuật học cụ thể, (không áp dụng giải thuật học trong giai đoạn 1) nhưng lại chịu ảnh hưởng của bản chất bộ dữ liệu (sử dụng các đo lường trên bộ dữ liệu). Do đó, các thuộc tính được chọn lựa sau đó có thể được sử dụng cho các giải thuật học khác nhau; Các đo lường như thông tin, khoảng cách, độc lập hoặc độ đồng nhất thường có chi phí “rẻ” hơn so với đo lường độ chính xác của một lớp, vì vậy phương pháp filter có thể cho ra tập thuộc tính được chọn lựa nhanh hơn; và do tính chất giản đơn của các đo lường cũng như độ phức tạp thời gian của các đo lường này thường là thấp, nên phương pháp filter có thể được sử dụng trong việc xử lý các bộ dữ liệu kích cỡ lớn. Tuy nhiên, các thuộc tính được chọn lựa bởi phương pháp fitler không cho phép các giải thuật học hiệu chỉnh lại các sai số (do nó chọn lựa thuộc tính dựa trên một số tiêu chí của bộ dữ liệu mà không dựa trên độ chính xác của kết quả học) do đó kết quả của phân lớp đôi khi có độ chính xác không cao.