Lập trình

Các thuật toán trích chọn thuộc tính được xét dưới góc độ chiến lược tìm kiếm nào được sử dụng trong giải thuật đó: Tìm kiếm toàn bộ, Tìm kiếm theo kinh nghiệm và Tìm kiếm xác suất.

3.1 Tìm kiếm toàn bộ

a. Phương pháp Focus

Phương pháp này do Almuallim và Dietterich đưa ra vào năm 1991. Phương pháp này xem xét tất cả các kết hợp có thể của N các thuộc tính, bắt đầu từ một tập con rỗng các thuộc tính: là tập con thứ nhất, là tập con thứ hai,…. Khi Focus tìm ra một tập con thỏa mãn tiêu chí đo lường độ ổn định, giải thuật sẽ dừng lại. Bỏ qua độ phức tạp thời gian của giải thuật khi kiểm tra độ ổn định, giải thuật Focus cần tạo ra Σ tập con nhằm mục đích tìm ra tập con m thuộc tính bé nhất thỏa mãn tiêu chí ổn định. Khi m không nhỏ (Ví dụ m>N/2), thì chi phí thời gian chạy giải thuật là rất lớn. Dưới đây là mã giả của phương pháp Focus. Phương pháp tìm kiếm này thích hợp với tập dữ liệu có số thuộc tính vừa và không quá lớn. Do đó Focus thường được áp dụng trong các bài toán với các dữ liệu về các đối tượng có số lượng các thuộc tính vừa phải nhằm giảm bớt độ phức tạp cho chi phí xây dựng hệ thống. Giả sử đối với bài toán tìm ra các đặc điểm các dịch vụ trong các ngân hàng hấp dẫn và thu hút khách hàng, áp dụng thuật toán Focus để tìm các các đặc điểm quan trọng nhất của các dịch vụ đó. Áp dụng phương pháp này sẽ không quá phức tạp cho hệ thống cũng như các nhà quản lý.

b. Phương pháp AAB

Được Liu đưa ra năm 1998, ABB là viết tắt của cụm từ Automated Branch and Bound algorithm. Chữ tự động (automated) ở đây có nghĩa là cận (bound) được xác định một cách tự động, điều này không giống như giải thuật nhánh và cận cổ điển, cận phải được xác định trước. Dưới đây thể hiện mã giả của giải thuật ABB.

Giải thuật ABB bắt đầu với một tập tất cả các thuộc tính, ABB thực hiện chiến lược tìm kiếm theo chiều rộng. Tại mỗi bước giải thuật lần lượt loại bỏ một thuộc tính cho đến khi không còn một thuộc tính nào có thể được loại bỏ mà vẫn thỏa mãn tiêu chí độ ổn định. ABB thực hiện việc mở rộng không gian tìm kiếm cũng giống như là việc cắt tỉa một cây. Một nhánh bị “tỉa” khi nó không thể phát triển thêm được nữa do việc vi phạm tiêu chí ổn định. Khi một nhánh không thể phát triển thêm được nữa thì gốc của nhánh có thể là một trong những “ứng cử viên” cho kết quả của giải thuật. Cuối cùng, một tập với số lượng các thuộc tính nhỏ nhất được chọn lựa nếu nó thỏa mãn tiêu chí đo lường U. Phương pháp AAB nên được áp dụng trong các bài toán xử lý và phân tích dữ liệu với tiêu chí đánh giá được xác định một cách tự động. Ví dụ trong bài toán tìm ra các nhân tố ảnh hưởng đến doanh thu của doanh nghiệp hay tổ chức trực tiếp sản xuất ra sản phẩm, tập các nhân tố ảnh hưởng sẽ được liệt kê đầy đủ và chúng sẽ được chọn lọc phù hợp với chi phí bỏ ra thu mua nguyên liệu đầu vào của từng năm. Số lượng nguyên liệu đầu vào thay đổi theo từng năm và biến đổi theo cả tiêu chí mong muốn của các khách hàng nữa. Khi đó các nhân tố ảnh hưởng sẽ dễ dàng nhận biết phục vụ cho công việc điều hành và quản lý của các nhà lãnh đạo cấp cao.

3.2 Tìm kiếm theo kinh nghiệm

Có rất nhiều phương pháp chọn lựa thuộc tính theo kinh nghiệm. Nhìn chung, các phương pháp này đều là sự đánh đổi việc tìm ra một tập con tốt nhất, với việc tìm ra một tập con tốt có thể chấp nhận được ở chừng mực nào đó nhưng có thời gian thực hiện nhanh hơn. Mặc dù, mục đích của các phương pháp tìm kiếm theo kinh nghiệm vẫn là tìm ra một tập con tối ưu.

Phương pháp đơn giản nhất trong các phương pháp tìm kiếm theo kinh nghiệm là “trích” ra một bộ phân lớp và thực hiện việc chọn lựa các thuộc tính bằng cách sử dụng bộ phân lớp được tạo ra trước đó. Dưới đây là mã giả của phương pháp tìm kiếm theo kinh nghiệm Wrap1:

Trong phương pháp Wrap1, từ một tập dữ liệu N thuộc tính chúng ta áp dụng một giải thuật học trên bộ dữ liệu đó nhằm tìm ra một bộ phân lớp (các tham số) có kết quả phân lớp tốt nhất. Sau đó, áp dụng bộ phân lớp này đối với tất cả các thuộc tính trong bộ dữ liệu cần phân lớp.

Phương pháp này có thời gian thực hiện nhanh hơn phương pháp tìm kiếm toàn bộ. Do đó đối với các bài toán có tiêu chí đánh giá cụ thể thì nên sử dụng phương pháp tìm kiếm kinh nghiệm. Ví dụ để tìm ra các đặc điểm của trường đại học thu hút nhiều sinh viên nhất dựa vào tiêu chí đánh giá chẳng hạn là tổng số điểm đầu vào cao nhất. Sử dụng thuật toán này với tiêu chí như vậy sẽ nhanh chóng phát hiện ra các đặc điểm về trường đại học hấp dẫn nhiều thí sinh đến dự thi nhất.

3.3 Tìm kiếm xác suất

Có thể nói rằng phương pháp tìm kiếm theo xác suất là kết quả của việc các nhà nghiên cứu tiếp tục theo đuổi mục đích tìm kiếm tập con tối ưu mà không muốn thực hiện việc tìm kiếm toàn bộ trong không gian tìm kiếm. Không giống như hai phương pháp tìm kiếm theo kinh nghiệm và tìm kiếm toàn bộ được trình bày ở trên, các thuộc tính không tuần tự được loại bỏ/thêm vào từ một tập các thuộc tính cho trước. Phương pháp tìm kiếm theo xác suất cho phép tìm kiếm các tập con thuộc tính mà ở đó các tập con này được tạo ra một cách ngẫu nhiên. Phương pháp LVF (Las Vegas algorithm for Filter feature selection). Phương pháp LVF được Liu và Setiono đưa ra vào năm 1996, phương pháp LVF bao gồm một thủ tục có thể tạo ra tạo ra các tập con thuộc tính một cách ngẫu nhiên và một thủ tục nhằm đánh giá xem mỗi tập con được tạo ra có thỏa mãn tiêu chuẩn chọn lựa hay không. Dưới đây thể hiện mã giả của phương pháp LVF. Kết quả của hai thủ tục trong giải thuật LVF là một tập con thuộc tính tối ưu. Đo lường được sử dụng để đánh giá trong LVF là tỷ lệ lỗi (inconsistency). Giải thuật LVF này có hai tham số quan trọng đó là: Tỷ lệ lỗi của dữ liệu khi sử dụng tất cả các thuộc tính, Số lượng tối đa các tập con thuộc tính được tạo ra ngẫu nhiên.

Trong mã giả của giải thuật LVF ở trên maxTries là một hằng số liên quan đến số lượng các thuộc tính có trong tập dữ liệu ban đầu, bằng trực quan chúng ta nhận thấy rằng dữ liệu càng có nhiều thuộc tính thì càng khó phân lớp. Thông thường maxTries = c x N, trong đó c là một hằng số (c<=N). Giá trị maxTries càng lớn có nghĩa là số lần lặp của giải thuật càng lớn và kết quả của giải thuật cũng tốt hơn. Một cách khác để xác định giá trị maxTries trong LVF đó là xác định giá trị maxTries theo không gian tìm kiếm mà người sử dụng muốn LVF thực hiện. Chúng ta biết rằng không gian tìm kiếm là 2N, nếu người sử dụng muốn LVF thực hiện việc tìm kiếm trong p% của không gian tìm kiếm thì maxTries=2N x p%. Hàm randomSet() yêu cầu một bộ sinh ngẫu nhiên tốt để thực hiện việc phân ngẫu nhiên các tập con thuộc tính khác nhau. Có một bộ sinh số ngẫu nhiên tốt cũng có nghĩa là có ít hơn các tập con giống nhau được tạo ra.

Phương pháp tìm kiếm theo xác suất được áp dụng trong các trường hợp muốn tìm kiếm một cách công bằng và khách quan nhất. Ví dụ trong trường hợp muốn tìm ra các yếu tố quan trọng chi phối đến đời sống của con người sống trên các châu lục trên thế giới. Tập các yếu tố ảnh hưởng tương đối lớn, vậy muốn tìm ra những yếu tố nào là chính và ảnh hưởng, chi phối đến đời sống con người một cách khách quan nhất thì nên sử dụng phương pháp tìm kiếm theo xác suất sẽ giúp hệ thống làm việc nhanh hơn và hiệu quả hơn.

4. Kết luận

Như vậy để thực hiện được các thuật toán trích chọn, chúng ta cần phải thực hiện một số công việc sau: Trước tiên lựa chọn phương pháp để sinh ra tập thuộc tính đặc trưng có thể hiểu tương ứng với các chiến lược tìm kiếm; Sau đó phải định nghĩa hàm đánh giá (đưa ra các tiêu chí để có thể xác định một thuộc tính hay nhóm thuộc tính là tốt hay không tốt). Cuối cùng phải ước lượng hàm đánh giá đó tức là kiểm chứng lại xem hàm đánh giá có thực sự phù hợp và hiệu quảvới bộ dữ liệu

Tài liệu tham khảo

[1]. Huan Liu and Hiroshi Motoda, Computational Methods of Feature Selection, Chapman & Hall/CRC, 2008

[2]. Luis Carlos Molina, Luis Belanche, Àngela Nebot: Feature Selection Algorithms, A Survey and Experimental Evaluation, Technical report, Universitat Politècnica de Catalunya Departament de Llenguatges i Sistemes Informátics, France, 2002

[3]. Luis Carlos Molina et at, Feature Selection for Algorithms: A Survey and Experimental Evaluation, 2000

[4]. Ron Kohavi and George H. John, Wrapper for Feature Subset Selection, AIJ special issuse on relevance, 1996