Áp dụng máy học để tìm ra các đặc trưng tối ưu trong các bài toán xử lý số liệu lớn
Áp dụng máy học để tìm ra các đặc trưng tối ưu trong các bài toán xử lý số liệu lớn
Xem bên trong

Áp dụng máy học để tìm ra các đặc trưng tối ưu trong các bài toán xử lý số liệu lớn

62 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin — Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2011
Tổng quan về bài toán cần giải quyết: khai phá dữ liệu và trích chọn thuộc tính, lựa chọn thuộc tính và bài toán phân lớp, Phương pháp dự kiến thực hiện. Trình bày một số kỹ thuật lựa chọn thuộc tính: Phương pháp lựa chọn thuộc tính, một số thuật toán lựa chọn thuộc tính. Phân tích cơ sở lý thuyết thuật giải di truyền và mạng nơron nhân tạo: Thuật toán di truyền, mạng nơron nhân tạo. Kết hợp giải thuật di truyền và mạng nơron để giảm chiều số liệu: Giới thiệu, kiến trúc hệ thống, hoạt động của hệ thống
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
————

NGÔ THÙY LINH

ÁP DỤNG MÁY HỌC ĐỂ TÌM RA CÁC ĐẶC TRƯNG
TỐI ƯU TRONG CÁC BÀI TOÁN XỬ LÝ SỐ LIỆU LỚN

LUẬN VĂN THẠC SĨ

Hà nội – 2011

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
————

NGÔ THÙY LINH

ÁP DỤNG MÁY HỌC ĐỂ TÌM RA CÁC ĐẶC TRƯNG
TỐI ƯU TRONG CÁC BÀI TOÁN XỬ LÝ SỐ LIỆU LỚN

Ngành : Công nghệ thông tin
Chuyên ngành : Hệ thống thông tin
Mã số : 60 48 05

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hà Nam

Hà nội – 2011
3

Mục lục
LỜI CAM ĐOAN ………………………………………………………………………………………….. 1
Lời cảm ơn …………………………………………………………………………………………………… 2
Mục lục ……………………………………………………………………………………………………….. 3
Danh mục các hình vẽ …………………………………………………………………………………….. 5
Danh mục các bảng biểu …………………………………………………………………………………. 6
Chương 1: Tổng quan về bài toán cần giải quyết…………………………………………………. 7
1.1 Giới thiệu …………………………………………………………………………………………….. 7
1.2 Khai phá dữ liệu và trích chọn thuộc tính …………………………………………………… 7
1.3. Lựa chọn thuộc tính và bài toán phân lớp………………………………………………….. 9
1.4 Phương pháp dự kiến thực hiện……………………………………………………………… 11
Chương 2: Một số kỹ thuật lựa chọn thuộc tính ………………………………………………… 12
2.1 Phương pháp lựa chọn thuộc tính là gì? …………………………………………………… 12
2.1.1 Chiến lược tìm kiếm ……………………………………………………………………….. 13
2.1.2 Tiêu chuẩn lựa chọn ……………………………………………………………………….. 14
2.2 Một số thuật toán lựa chọn thuộc tính ……………………………………………………… 18
2.2.1 Tìm kiếm toàn bộ …………………………………………………………………………… 18
2.2.2 Tìm kiếm theo kinh nghiệm ……………………………………………………………… 19
2.2.3 Tìm kiếm xác suất ………………………………………………………………………….. 20
Chương 3: Cơ sở lý thuyết thuật giải di truyền và mạng nơron nhân tạo ………………. 22
3.1 Thuật toán di truyền ……………………………………………………………………………… 22
3.1.1. Chọn lọc ………………………………………………………………………………………. 24
3.1.2 Lai ghép ……………………………………………………………………………………….. 25
3.1.3 Đột biến………………………………………………………………………………………… 26
3.2 Mạng nơron nhân tạo ……………………………………………………………………………. 28
3.2.1 Giới thiệu ……………………………………………………………………………………… 28
3.2.2 Mô hình phân lớp tổng quát ……………………………………………………………… 28
3.2.3 Mạng Back propagation …………………………………………………………………… 30
Chương 4: Kết hợp giải thuật di truyền và mạng nơron để giảm chiều số liệu ………… 35
4.1 Giới thiệu …………………………………………………………………………………………… 35
4.2 Kiến trúc hệ thống ……………………………………………………………………………….. 36
4.3 Hoạt động của hệ thống ………………………………………………………………………… 37
4

4.4 Sơ đồ khối phương pháp học máy …………………………………………………………… 41
4.5 Phương pháp đề xuất tìm bộ thuộc tính tối ưu nhất ……………………………………. 42
Chương 5: Kết quả thực nghiệm …………………………………………………………………….. 45
5.1 Môi trường thực nghiệm ……………………………………………………………………….. 45
5.2 Bộ dữ liệu Stomach Cancer …………………………………………………………………… 45
5.2.1 Mô tả bộ dữ liệu …………………………………………………………………………….. 45
5.2.2 Kết quả thực nghiệm ………………………………………………………………………. 46
5.2.3 Nhận xét ……………………………………………………………………………………….. 49
5.3 Bộ dữ liệu Lung Cancer ………………………………………………………………………… 50
5.3.1 Mô tả bộ dữ liệu Lung Cancer ………………………………………………………….. 50
5.3.2 Kết quả thực nghiệm ………………………………………………………………………. 51
5.3.3 Nhận xét ……………………………………………………………………………………….. 54
Kết luận ……………………………………………………………………………………………………… 56
Tài liệu tham khảo ……………………………………………………………………………………….. 57
Phụ lục……………………………………………………………………………………………………….. 58

5

Danh mục các hình vẽ

Hình 2.1: Các thành phần chính của lựa chọn thuộc tính ……………………………………. 13
Hình 2.2: Mô Hình Wrapper …………………………………………………………………………. 16
Hình 2.3: Mô hình Filter ………………………………………………………………………………. 17
Hình 3.1: Kỹ thuật bánh xe quay ……………………………………………………………………. 25
Hình 3.2: Hệ thống phân lớp tổng quát …………………………………………………………… 29
Hình 3.3: Cấu trúc mạng Back propagation 3 lớp ……………………………………………… 30
Hình 3.4: Sơ đồ khối cho thuật toán Back – propagation ……………………………………. 34
Hình 4.1: Mô hình GA wrapper …………………………………………………………………….. 35
Hình 4.2: Kiến trúc cơ bản của hệ thống …………………………………………………………. 36
Hình 4.3: Mô tả kiểm chứng chéo ………………………………………………………………….. 38
Hình 4.4: Hàm Sigmoid đơn cực ……………………………………………………………………. 39
Hình 4.5: Hoạt động hệ thống ……………………………………………………………………….. 41
Hình 5.1: Biểu đồ tổng hợp 10 lần kiểm tra ……………………………………………………… 47
Hình 5.2: So sánh kết quả thực nghiệm các bộ cột tìm được ………………………………. 49
Hình 5.3: Kết quả thực nghiệm của hai phương pháp trên bộ dữ liệu Stomach Cancer
…………………………………………………………………………………………………………………. 50
Hình 5.4: Biểu đồ 20 lần kiểm tra ………………………………………………………………….. 52
Hình 5.5: Kết quả thực nghiệm của các tỷ lệ chọn khác nhau trên bộ dữ liệu Lung
Cancer ………………………………………………………………………………………………………. 53
Hình 5.6: Kết quả thực nghiệm của hai phương pháp trên bộ dữ liệu Lung Cancer … 54

6

Danh mục các bảng biểu

Bảng 4.1: Bảng kết quả sau quá trình chọn lọc …………………………………………………. 40
Bảng 5.1: Mô tả bộ dữ liệu Stomach Cancer ……………………………………………………. 45
Bảng 5.2: Giá trị của 10 lần kiểm tra với bộ thuộc tính vừa tìm được ở trên ………….. 47
Bảng 5.3: Giá trị trung bình và độ lệch chuẩn của bộ vừa tìm được …………………….. 47
Bảng 5.4: Kết quả 11 lần thử nghiệm với bộ các cột khác nhau …………………………… 48
Bảng 5.5: Bảng giá trị trung bình và độ lệch chuẩn của bộ các cột ………………………. 49
Bảng 5.6: So sánh kết quả phân lớp trên bộ dữ liệu Stomach Cancer …………………… 50
Bảng 5.7: Mô tả bộ dữ liệu Lung Cancer ………………………………………………………… 51
Bảng 5.8: Kết quả kiểm tra 20 lần của bộ thuộc tính tìm được ở phần 1 ……………….. 51
Bảng 5.9: Kết quả thu được của 20 lần kiểm tra ……………………………………………….. 52
Bảng 5.10: Bảng tổng hợp các lần kiểm thử với tỷ lệ chọn khác nhau ………………….. 53
Bảng 5.11: Bảng so sánh kết quả của các tỷ lệ chọn khác nhau …………………………… 54
Bảng 5.12: So sánh kết quả thu được của 2 phương pháp trên bộ dữ liệu Lung Cancer
…………………………………………………………………………………………………………………. 55

7

Chương 1: Tổng quan về bài toán cần giải quyết
1.1 Giới thiệu
Ngày nay nhờ sự phát triển mạnh mẽ của khoa học kỹ thuật mà chúng ta phải
tiếp nhận và giải quyết với khối dữ liệu ngày càng lớn, có thể lên tới hàng nghìn tỷ các
đối tượng và hàng nghìn các thuộc tính. Câu hỏi đặt ra ở đây là liệu có phải “càng
nhiều có nghĩa là càng tốt?”. Câu trả lời cũng có thể là “Đúng” và cũng có thể là “Sai”.
Trả lời là “Đúng” là vì ít nhất thì chúng ta cũng có thể nhận được những gì mà chúng
ta mong muốn. Còn câu trả lời là “Sai” vì khi có sự hiện diện của quá nhiều dữ liệu thì
cũng tương đương với việc là “không có dữ liệu” nếu việc truy nhập dữ liệu không
hiệu quả. Như vậy thì “nhiều” cũng có thể là “ít”. Dữ liệu trong mọi lĩnh vực như kinh
tế, xã hội… sẽ trở thành vô nghĩa nếu không có phương pháp xử lý đồng nghĩa với
không khai thác được các thông tin quan trọng của nó. Bởi vì sự tích lũy dữ liệu đã trở
thành thói quen nên phải có kỹ thuật lựa chọn dữ liệu phù hợp với tốc độ thu thập dữ
liệu. Hơn thế nữa, với khối lượng lớn dữ liệu được sinh ra từ các máy tính hoặc từ các
thiết bị khác tương đương, phải được xử lý một cách tự động để chúng ta có thể kiểm
soát và chế ngự được chúng.
Số lượng bản ghi cũng như kích thước của từng bản ghi được lưu trữ rất nhanh
và lớn gây khó khăn trong việc lưu trữ và xử lý,… nên người ta đã đưa ra một số giải
pháp như: xử lý song song, tìm ra các mẫu đặc trưng, tìm ra các thuộc tính đặc trưng.
Hướng nghiên cứu của luận văn là tìm ra các thuộc tính đặc trưng hay còn gọi là lựa
chọn thuộc tính (feature selection). 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, trong cả bài
toán nhận dạng mẫ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. Bằng chứng là chúng ta có thể tìm thấy trong rất nhiều bài
báo, tạp chí hoặc trong các hội thảo gần đây. Các nghiên cứu bắt đầu từ lựa chọn thuộc
tính giám sát cổ điển mở rộng đến lựa chọn thuộc tính không giám sát và bán giám sát,
cả đến việc lựa chọn các kiểu thuộc tính khác như thuộc tính “nguyên nhân” và “cấu
trúc”. Một số nghiên cứu xét đến các loại dữ liệu khác như high-throughput, văn bản
hoặc ảnh và có cả ước lượng lựa chọn thuộc tính… [1].
1.2 Khai phá dữ liệu và trích chọn thuộc tính
Khai phá dữ liệu là một khái niệm ra đời từ những cuối những năm 80 của thế kỷ
trước. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có giá trị tiềm
ẩn trong tập các dữ liệu lớn. Về bản chất, khai phá dữ liệu liên quan đến việc phân tích
8

các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập
dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện
tri thức trong cơ sở dữ liệu (Kownledge Discovery in Database – KDD) để chỉ toàn bộ
quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu
là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết
xuất ra các mẫu hay các mô hình từ dữ liệu.
Trong khai phá dữ liệu thì phương pháp trích chọn thuộc tính đóng một vai trò
quan trọng trong tiền xử lý số liệu. Phương pháp trích chọn sẽ giúp giảm kích cỡ của
không gian dữ liệu đặc trưng, loại bỏ những thuộc tính không liên quan và những
thuộc tính nhiễu. Phưong pháp này có ảnh hưởng ngay lập tức đến các ứng dụng như
thuật toán tăng tốc độ 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.
Khai phá dữ liệu chủ yếu tập trung vào 3 nhiệm vụ chính sau:
Giảm chiều dữ liệu: Giảm chiều dữ liệu là việc làm giảm chiều của không gian tìm
kiếm dữ liệu, giảm chi phí thu thập và lưu trữ dữ liệu, nâng cao hiệu quả của việc khai
phá dữ liệu và làm đơn giản hóa các kết quả khai phá dữ liệu. Trong nhiệm vụ làm
giảm chiều dữ liệu chúng ta cần phân biệt hai khái nhiệm sau:
Trích chọn thuộc tính (Feature Extraction): Trích chọn thuộc tính là việc tìm ra
một tập thuộc tính mới từ tập thuộc tính ban đầu nhằm nâng cao hiệu suất tính
toán và độ chính xác phân lớp. Các kỹ thuật trích chọn thuộc tính thường liên
quan đến các phép biến đổi phi tuyến (non-linear). Linear discriminant analysis
(LDA) và principal components analysis (PCA) là hai kỹ thuật phổ biến dùng
trong trích chọn thuộc tính.
Chọn lựa thuộc tính (Feature Selection): Chọn lựa thuộc tính là việc chọn ra
một tập thuộc tính con từ tập thuộc tính ban đầu sao cho các tập thuộc tính con
này thể thể hiện tốt nhất chức năng của một hệ thống quy nạp, chẳng hạn như
một hệ thống phân lớp. Việc tìm kiếm một tập con thuộc tính tối ưu thường là
rất khó và rất nhiều các vấn đề của chọn lựa thuộc tính là thuộc về lớp các bài
toán NP-hard. Tuy nhiên, chọn lựa thuộc tính lại được sử dụng rộng rãi trong
giảm chiều dữ liệu vì các kết quả dựa trên các thuộc tính được chọn lựa từ tập
thuộc tính ban đầu thường dễ dàng lý giải hơn so với một tập các thuộc tính
được biến đổi từ tập thuộc tính ban đầu.
Phân cụm và phân lớp: Phân lớp và phân cụm là hai nhiệm vụ có mối quan hệ
tương đối gần nhau trong khai phá dữ liệu. Một lớp là một tập các đối tượng có cùng
một số đặc điểm hoặc mối quan hệ nào đó, tất cả các đối tượng trong lớp này được
9

phân vào trong cùng một lớp tên nhằm mục đích là để phân biệt với các lớp khác. Một
cụm là một tập các đối tượng tương tự nhau về mặt vị trí. Các cụm thường được tạo ra
nhằm mục đích để sau đó tiến hành phân lớp các đối tượng.
Trích chọn luật: Trích chọn luật tìm kiếm và đưa ra dữ liệu bằng cách tất cả
các dữ liệu được đưa ra dựa trên các suy diễn/các quyết định mà các suy diễn/quyết
định này được xây dựng từ các tri thức thu thập được từ dữ liệu đó. Đối với người sử
dụng các kết quả của khai phá dữ liệu họ chỉ mong muốn có một cách giải thích đơn
giản là tại sao có các kết quả phân lớp đó, thuộc tính nào ảnh hưởng đến kết quả khai
phá dữ liệu…Tuy nhiên, bằng các tham số phân lớp rất khó để có thể diễn giải các tri
thức đó theo cách mà người sử dụng có thể dễ dàng hiểu được. Do đó, trích chọn ra
các luật IF-THEN để đưa ra các thông tin có giá trị là một cách diễn giải đơn giản và
dễ hiểu nhất đối với người sử dụng.
1.3. Lựa chọn thuộc tính và bài toán phân lớp
Nhiệm vụ cơ bản của việc phân lớp là phân chia một tập các đối tượng thành n-hữu
hạn lớp đã biết trước. Tập đối tượng cần phân lớp được đặc trưng bởi một tập các
thuộc tính chứa các thông tin cần thiết liên quan đến các lớp, trong đó mỗi tập các
thuộc tính được đại diện bởi một tập các thuộc tính – giá trị. Với một tập dữ liệu bao
gồm một tập các đối tượng đã được phân lớp (thường gọi là tập tập huấn) nhiệm vụ đặt
ra là từ tập huấn luyện cho trước xây dựng một bộ phân lớp cho các dữ liệu tương tự.
Vấn đề đặt ra đối với bài toán phân lớp là số lượng các thuộc tính có thể rất lớn do
những lý do sau:
Dữ liệu được thu thập không đơn giản chỉ phục vụ cho một tác nghiệp cụ thể
chẳng hạn như khai phá dữ liệu. Do đó, đối với một ứng dụng cụ thể bộ dữ liệu
có thể có rất nhiều các thuộc tính thừa hoặc không phù hợp.
Đôi khi thậm chí nếu chúng ta biết các thuộc tính được thiết kế cho một tác
nghiệp cụ thể thì thuộc tính nào là thuộc tính có liên quan thường không được
biết. Điều này là do bản chất của nghiên cứu. Chúng ta tiến hành thực nghiệm và
thu thập số liệu vì chúng ta muốn biết nhiều hơn lĩnh vực mà chúng ta muốn tìm
hiểu và chúng ta thông thường không có một ý niệm chính xác về các thuộc tính
cần thiết. Do đó, chúng ta phải tìm các thuộc tính cần thiết nhiều nhất mà chúng
ta có thể nghĩ đến thậm chí chúng có thể là các thuộc tính dư thừa hoặc không
liên quan. Chúng ta chỉ có thể biết được thuộc tính nào là liên quan sau khi chúng
ta nghiên cứu bộ số liệu đã được thu thập.
Một tác nghiệp có thể yêu cầu dữ liệu từ nhiều nguồn khác nhau. Nếu dữ liệu từ
mỗi nguồn là lớn thì sau khi nối các nguồn dữ liệu trên chúng ta sẽ có một bộ dữ
10

liệu khổng lồ. Nếu chúng ta biết được các thuộc tính liên quan thì chúng ta có thể
giải quyết được vấn đề trên nhưng trên thực tế chúng ta thường không biết trước
các thuộc tính nào là thuộc tính liên quan.
Các thuộc tính không liên quan hoặc thừa có thể có những ảnh hưởng tiêu cực đối
với các giải thuật phân lớp: Có nhiều thuộc tính thông thường có nghĩa là cần nhiều
thực thể, vì vậy chúng ta cần đảm bảo các ràng buộc thống kê giữa các thực thể trong
các lớp khác nhau, Các thuộc tính/dữ liệu thừa hoặc không liên quan có thể là nguyên
nhân dẫn đến việc học của giải thuật không được chính xác hoặc dẫn đến hiện tượng
overfitting trong mô hình, Thêm vào đó với sự có mặt của dữ liệu thừa hoặc dữ liệu
không liên quan có thể làm cho bộ phân lớp trở lên phức tạp hơn. Điều này là gây ra
những khó khăn không cần thiết cho chúng ta trong việc diễn giải các kết quả học
được từ tập huấn luyện.
Do chúng ta không biết được thuộc tính nào là liên quan trước khi chúng ta tiến
hành thu thập dữ liệu và các thuộc tính thừa hoặc không liên quan thường gây ra
những ảnh hưởng tiêu cực đối với các giải thuật phân lớp, do đó chúng ta cần giải
quyết vấn này đối với các bài toán phân lớp. Về cơ bản, chúng ta chỉ muốn lựa chọn
các thuộc tính liên quan đến ứng dụng của chúng ta nhằm mục đích sao cho ứng dụng
của chúng có được hiệu quả tốt nhất với các đo lường, tính toán là ít nhất, nói một
cách đơn giản chúng ta mong muốn có một đầu vào cho mô hình là đơn giản nhất có
thể nhưng lại cho kết quả ở đầu ra là tốt nhất có thể. Sử dụng trích chọn thuộc tính
trong phân lớp cho ta những lợi thế sau:
Dữ liệu ít hơn do đó giải thuật phân lớp có thể học nhanh hơn;
Độ chính xác cao hơn do đó bộ phân lớp có thể cho những kết quả phân lớp tốt;
Các kết quả đơn giản hơn do đó các kết quả này có thể hiểu được dễ dàng hơn;
Ít thuộc tính hơn do đó trong các vòng thu thập số liệu sau, nếu có thể chúng ta
có thể tiết kiệm được nhiều nguồn lực do việc loại bỏ các thuộc tính thừa và
không liên quan.

11

1.4 Phương pháp dự kiến thực hiện
Hướng nghiên cứu của luận văn là tìm hiểu về phương pháp lựa chọn thuộc
tính. Bài toán được phát biểu như sau: đối với bộ số liệu lớn thu được gồm hàng trăm
đến hàng nghìn bản ghi và mỗi bản ghi lại gồm hàng nghìn các thuộc tính. Các bản ghi
được phân thành các lớp cho trước. Yêu cầu đặt ra là tìm các thuộc tính hữu ích, tối ưu
nhất, loại ra các thuộc tính ít liên quan để vẫn đảm bảo việc phân lớp đúng các bản ghi.
Luận văn nghiên cứu phương pháp lựa chọn thuộc tính dựa vào giải thuật di truyền và
mạng nơron nhân tạo. Phương pháp này có thể tìm thấy trên một số bài báo [2] – [4].
Tuy nhiên dựa trên mô hình và lý thuyết có trong một số bài báo đó, luận văn tìm hiểu
và cố gắng đưa ra đề xuất cải tiến để mong muốn thuật toán thu được kết quả dự đoán
cao hơn và tìm được bộ thuộc tính tốt hơn.

12

Chương 2: Một số kỹ thuật lựa chọn thuộc tính
2.1 Phương pháp lựa chọn thuộc tính là gì?
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ý [5].
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à 2
n
. 2
n
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
13

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 and 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 [6].

Hình 2.1: Các thành phần chính của lựa chọn thuộc tính
2.1.1 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ả 2
N
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ẽ
14

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 (2
N
), 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ử chúng ta ban đầu 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 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
15

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.

Tác giả

Ngô Thùy Linh

Nhà xuất bản

ĐHCN

Năm xuất bản

2011

Người hướng dẫn

Nguyễn Hà Nam

Định danh

00050000731

Kiểu

text

Định dạng

text/pdf

Chủ đề

Bài toán,Giải thuật di truyền,Mạng nơron nhân tạo,Hệ thống thông tin,Khai phá dữ liệu

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Áp dụng máy học để tìm ra các đặc trưng tối ưu trong các bài toán xử lý số liệu lớn”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *