MỤC LỤC
Trang phụ bìa .1
Mục lục .2
Lời mở đầu .4
Chương 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU .6
1.1.Tại sao phải khai phá dữ liệu .6
1.2. Quá trình khai phá dữ liệu .7
1.3. Các phương pháp khai phá dữ liệu .9
1.4. Các loại dữ liệu có thể khai phá .10
1.5. Các ứng dụng của khai phá dữ liệu.10
1.6. Một số thách thức đặt ra cho việc khai phá dữ liệu .14
1.7. Tổng kết chương 1 .15
Chương 2. KHÁI QUÁT VỀ LỰA CHỌN THUỘC TÍNH TRONG KHAI
PHÁ DỮ LIỆU .16
2.1. Rút gọn thuộc tính .16
2.2. Khái quát về lựa chọn thuộc tính .18
2.2.1. Bài toán lựa chọ thuộc tính .18
2.2.2. Đặc điểm chung của các thuật toán lựa chọn thuộc tính .20
2.2.3. Ứng dụng của các kỹ thuật lựa chọn thuộc tính .23
2.3. Kết luận chương 2 .26
Chương 3. MỘT SỐ THUẬT TOÁN LỰA CHỌN THUỘC TÍNH ĐIỂN HÌNH .28
3.1. Các thuật toán theo cách tiếp cận filter .28
3.1.1 Thuật toán RELIEF .28
3.1.2. Thuật toán FOCUS .31
3.1.3. Thuật toán LVF .33
3.1.4. Thuật toán EBR .35
3.1.5. Thuật toán SCRAP .38
3.1.6. Lựa chọn nhóm .40
3.2. Các thuật toán theo cách tiếp cận wrapper .42
3.3.1 Thuật toán LVW .42
3.3.2 Thuật toán NEURALNET .43
3.3. Một số thuật toán khác .44
3.3.1. Thuật toán Genetic .44
3.3.2. Lựa chọn thuộc tính thông qua rời rạc hóa dữ liệu .46
3.4. Kết luận chương 3 .53
KẾT LUẬN .54
Tài liệu tham khảo .5
58 trang |
Chia sẻ: maiphuongdc | Lượt xem: 5840 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận văn Lựa chọn thuộc tính trong khai phá dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
n trọng khác trong lựa chọn thuộc tính là xác định cách thức
đánh mức độ phù hợp của mỗi tập con.
Hiện nay có hai cách tiếp cận chính đối với bài toán lựa chọn thuộc tính:
filter (lọc) và wrapper (đóng gói). Mỗi cách tiếp cận có những chú trọng riêng
dành cho việc rút kích thước dữ liệu hay để nâng cao độ chính xác.
Cách tiếp cận kiểu filter thực hiện việc lựa chọn thuộc tính độc lập với
thuật khai phá sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan
trọng của chúng trong việc mô tả dữ liệu.
Ngược lại với cách tiếp cận filter, lựa chọn thuộc tính kiểu wrapper tiến
hành việc lựa chọn bằng cách áp dụng ngay thuật khai phá, độ chính xác của kết
quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Cách tiếp cận filter có ưu điểm là thời gian tính toán nhanh, nhược điểm là
không sử dụng sử dụng thông tin nhãn lớp của các bộ dữ liệu nên độ chính xác
không cao
Hình 2.3. Các cách tiếp cận filter và wrapper
Gần đây một số cách tiếp cận mới cũng đã được các tác giả đã đề xuất,
chẳng hạn cách tiếp cận lai ghép (hybrid approach) nhằm kết hợp các ưu điểm
của cả hai cách tiếp cận filter và wrapper, cách tiếp cận tập thô. Cũng có thể
phân chia các cách tiếp cận bài toán lựa chọn thuộc tính thành hai loại: có giám
sát (supervised) và không có giám sát (unsupervised), tùy theo việc lựa chọn có
sử dụng hay không sử dụng thông tin nhãn lớp của các đối tượng.
2.2.2. Đặc điểm chung của các thuật toán lựa chọn thuộc tính
Hai khâu chủ yếu trong quá trình lựa chọn thuộc tính là tạo lập các tập con
và đánh giá các tập con.
2.2.2.1 Tạo lập các tập con
Thông thường có hai phương pháp tạo lập các tập con cho việc chọn lựa:
phương pháp tiến (Forward Generation) và phương pháp lùi (Backward
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
Generation). Tạo lập theo phương pháp tiến bắt đầu bằng tập rỗng. Sau đó, tại
mỗi bước lặp một thuộc tính tốt nhất (theo tiêu chuẩn đánh giá) trong số các
thuộc tính còn lại sẽ được thêm vào. Quá trình tạo lập dừng lại khi đã vét cạn tất
cả các thuộc tính của tập dữ liệu ban đầu hoặc đã tìm được tập con tối ưu.
Ngược lại với phương pháp tiến, phương pháp lùi bắt đầu bằng tập tất cả các
thuộc tính. Tại mỗi bước lặp, một thuộc tính tồi nhất (theo tiêu chuẩn đánh giá)
sẽ bị loại. Tập thuộc tính ban đầu sẽ nhỏ dần cho đến khi chỉ còn lại một thuộc
tính hoặc khi điều kiện dừng thỏa mãn. Một phương pháp khác để tạo lập các
tập con là bắt đầu bằng một tập con thuộc tính chọn ngẫu nhiên, sau đó tại mỗi
bước lặp lần lượt thêm vào hoặc loại bớt một thuộc tính cũng được chọn một
cách ngẫu nhiên.
2.2.2.2. Tiêu chuẩn đánh giá
Một tập con thuộc tính là tối ưu luôn được hiểu theo một tiêu chuẩn đánh
giá nào đó. (Một tập tối ưu theo tiêu chuẩn này chưa chắc sẽ là tối ưu theo tiêu
chuẩn khác). Có thể phân các tiêu chuẩn đánh giá thành hai loại: độc lập và phụ
thuộc. Tiêu chuẩn độc lập là những tiêu chuẩn được dùng trong cách tiếp cận
filter; chúng đánh giá mức độ phù hợp của một hay một tập con thuộc tính một
cách độc lập, không thông qua áp dụng một thuật học. Ngược lại với tiêu chuẩn
độc lập, tiêu chuẩn phụ thuộc đánh giá một tập con thuộc tính thông qua độ hiệu
quả của một thuật học áp dụng trên chính tập thuộc tính cần đánh giá. Nói một
cách khác, tiêu chuẩn phụ thuộc chính là số đo mức độ hiệu quả của thuật học.
Các tiêu chuẩn phụ thuộc thường được sử dụng trong cách tiếp cận wrapper.
Dưới đây, ta giới thiệu tóm tắt một số tiêu chuẩn thuộc hai loại nêu trên.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
a) Tiêu chuẩn độc lập
Các tiêu chuẩn độc lập thường được sử dụng để đánh giá các tập con thuộc
tính cho lựa chọn là: số đo khoảng cách, số đo lượng thông tin thu thêm
(Information gain), số đo độ phụ thuộc, số đo độ nhất quán và số đo độ tương tự.
Số đo khoảng cách. Số đo này còn được gọi là số đo độ khả tách
(separability), độ phân kỳ (divergence), độ phân biệt (discrimination).
Giả sử cần lựa chọn thuộc tính để giải quyết một bài toán phân lớp
trong trường hợp có hai lớp. Gọi D là thuộc tính nhãn lớp (thuộc tính
quyết định), X là một tập con thuộc tính nào đó. Người ta có thể sử
dụng khoảng cách giữa hai phân phối xác suất có điều kiện
( / )P D C
( / )P D X
để lựa chọn. Thuộc tính X sẽ được coi là tốt hơn thuộc tính
Y nếu khoảng cách giữa
( / )P D C
và
( / )P D X
lớn hơn khoảng cách
( / )P D C
và
( / )P D Y
.
Số đo lượng thông tin thu thêm (information gain). Lượng thông tin
thu thêm từ thuộc tính X được định nghĩa bằng hiệu số giữa độ bất
định (entropy) tiên nghiệm và giá trị kỳ vọng của độ bất định hậu
nghiệm của thuộc tính quyết định D khi đã biết X. Thuộc tính X được
coi là tốt hơn thuộc tính Y nếu lượng thông tin thu thêm được từ X lớn
hơn lượng thông tin thu thêm được từ Y.
Số đo độ phụ thuộc (dependency - hay còn gọi là số đo độ tương quan).
Số đo này đánh giá khả năng dự đoán của một thuộc tính đối với giá trị
của một thuộc tính khác. Trong hai thuộc tính điều kiện X và Y, thuộc
tính nào tương quan mạnh hơn với thuộc tính quyết định D thì nó sẽ
được ưu tiên lựa chọn. Số đo độ tương quan giữa hai thuộc tính cũng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
được mở rộng để đánh giá sự phụ thuộc giữa một thuộc tính vào một
số thuộc tính khác.
Số đo độ nhất quán (consistency). Đây là một tiêu chuẩn mới, gần đây
thường được sử dụng vào việc đánh giá lựa chọn thuộc tính. Khác với
các số đo khác, tiêu chuẩn này gắn kết chặt chẽ với tập dữ liệu huấn
luyện. Số đo độ nhất quán là tỷ lệ các bộ dữ liệu (đối tượng) nhất quán
trong tập dữ liệu. Tập thuộc tính được chọn là tập nhỏ nhất bảo đảm
được tỷ lệ dữ liệu nhất quán theo ngưỡng quy định bởi người sử dụng.
b) Tiêu chuẩn phụ thuộc
Trong học luật phân lớp (học có giám sát), mục đích đầu tiên của là cực
tiểu hóa sai số dự báo. Do đó, sai số dự báo (hay độ chính xác của dự báo)
thường được chọn làm tiêu chuẩn (phụ thuộc) để đánh giá các tập con thuộc
tính. Như đã nói ở trên, tiêu chuẩn phụ thuộc luôn được sử dụng trong cách tiếp
cận wrapper. Việc lựa chọn các thuộc tính được tiến hành thông qua việc áp
dụng một thuật phân lớp, nên tập con thuộc tính chọn được sẽ có khả năng dự
báo rất cao. Tuy vậy, việc sử dụng tiêu chuẩn phụ thuộc để lựa chọn thuộc tính
sẽ tiêu tốn nhiều thời gian tính toán.
2.2.3. Ứng dụng của các kỹ thuật lựa chọn thuộc tính
Nhiều hệ thống thông tin trong nhiều lĩnh vực đã nhận thấy rõ lợi ích của
việc lựa chọn thuộc tính nhằm giảm bớt số chiều của dữ liệu trong các cơ sở dữ
liệu có kích thước lớn. Hình 1.3 dưới đây trình bày một số lĩnh vực áp dụng
quan trọng của các kỹ thuật lựa chọn thuộc tính.
Những giải thuật lựa chọn đặc trưng thường được ứng dụng để tối ưu hóa
hiệu quả phân lớp của các hệ thống nhận dạng tự động, nhất là khi số cá thể mẫu
trong tập huấn luyện có hạn. Thông thường, độ chính xác của một thuật phân lớp
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
học được sẽ bị giảm khi sử dụng quá nhiều thuộc tính. Ví dụ như trong chuẩn
đoán khối u ác tính, do có quá nhiều thuộc tính, độ chính xác của việc nhận biết
khối u ác tính của các bác sĩ chuyên khoa qua chỉ vào khoảng 65% đến 85%.
Với việc ứng dụng các giải thuật lựa chọn thuộc tính, hiện nay các những hệ
thống nhận dạng tự động khối u có thể đạt kết quả phân loại khối u chính xác
đến 95%.
Lựa chọn
thuộc tính
Nhận dạng ảnh
Phân loại văn bản
Kiểm tra hệ thống Phân cụm
Tin-sinh-học
Qui nạp luật
If ... ... then X
If ... ... then Y
If ... ... then Z
Hình 2.4: Các lĩnh vực ứng dụng của lựa chọn thuộc tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
Trong những năm gần đây, dữ liệu có tính cấu trúc thu được từ các phân
tích về gen người gia tăng nhiều lần. Điều này tạo ra nhiều cơ hội đồng thời
cũng là những thách thức đối với những nhà khoa học trí tuệ nhân tạo. Do công
nghệ phân tích gen ngày càng phát triển, trong một thí nghiệm, người ta có thể
phân tích tới hàng ngàn, thậm chí cả chục ngàn cấu trúc. Vấn đề đặt ra là làm
sao có thể phân biệt giữa người bị ung thư và người khỏe mạnh dựa trên hiện
trạng cấu trúc gen có kích rất lớn. Để giải quyết vấn đề này, người ta đã áp dụng
các kỹ thuật lựa chọn thuộc tính, rút gọn đáng kể kích thước các cấu trúc gen
trong tập dữ liệu huấn luyện.
Cũng có thể nêu một áp dụng khác nữa của lựa chọn thuộc tính trong tin-
sinh-học, đó là để hình thành các giả thuyết về mối quan hệ giữa các đặc trưng
hóa học của các phân tử và sự hoạt động của nó, từ đó đưa ra dự đoán về vị trí,
phát hiện các chỗ nối giữa hai miền mã hóa và không mã hóa của AND.
Cách tiếp cận chung đối với vấn đề biểu diễn tri thức sao cho mang tính mô
tả và dễ hiểu đối với con người là sử dụng các luật dạng if-then. Thế nhưng,
trong nhiều lĩnh vực thực tiễn, con người thường rất thiếu những luật có tính hệ
thống và về cùng một loại được cung cấp bởi chuyên gia. Cần phải học luật từ
các ví dụ. Để có thể làm tăng quá trình quy nạp luật, rút gọn tính phức tạp của
các luật thu được, đòi hỏi phải rút gọn thuộc tính. Rút gọn thuộc tính cho phép
giảm số chiều của một tập dữ liệu kích thước lớn mà chỉ làm mất đi một lượng
thông tin tối thiểu cần thiết cho viêc học luật. Nhờ đó, rút gọn thuộc tính giúp ta
loại bỏ những dữ liệu dư thừa, đơn giản hóa công việc thiết kế và cài đặt các
thuật học. Ngoài ra, nhờ số thuộc tính được rút gọn, việc học luật sẽ tiêu tốn ít
thời gian hơn, kết quả thu được trong nhiều trường hợp cũng tốt hơn.
Hiện nay, nhiều hệ thống đo đạc suy luận đã được xây dựng sử dụng
phương pháp luận căn cứ vào dữ liệu. Các mô hình suy đoán giá trị của các
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
thuộc tính đích cài đặt bên trong hệ thống được xây dựng sử dụng dữ liệu thu
thập được theo thời gian thực. Điều đó làm cho các hệ thống suy luận chịu ảnh
hưởng nhiều bởi chất lượng dữ liệu. Khi giải quyết các vấn đề phức tạp, chẳng
hạn như kiểm tra độ tin cậy hay chẩn đoán lỗi của các dây chuyền sản xuất công
nghiệp, ta thường phải đối mặt với rất nhiều thuộc tính, trong đó có những thuộc
tính dư thừa. Việc phải đo đạc cả những thuộc tính như vậy sẽ rất tốn kém.
Trong trường hợp này, rõ ràng phải áp dụng các kỹ thuật rút gọn hiệu quả, loại
bỏ các thuộc tính dư thừa, lựa chọn các thuộc tính liên quan nhiều nhất cho việc
xây dựng một mô hình xử lý có độ tin cậy, chính xác cao.
Phân cụm văn bản là việc phân chia các tài liệu tương tự thành các cụm.
Mỗi văn bản là một tập hợp lớn các từ. Điều này dẫn đến không gian các thuộc
tính mô tả có số chiều rất cao, cũng như sự phân tán của dữ liệu, ảnh hưởng lớn
đến độ hiệu quả của các thuật phân cụm. Để có được các thuật phân cụm khả thi
trong phân loại văn bản, các kỹ thuật trích lọc, cũng như lựa chọn thuộc tính đã
được nhiều hãng phần mềm áp dụng.
Giống như phân cụm, phân loại văn bản coi các tài liệu như là những tập
hợp các từ ngữ. Để phân loại văn bản, người ta tiến hành kiểm tra, trích lọc các
từ khóa và đánh giá chúng theo một tiêu chí nào đó, chẳng hạn tần số xuất hiện.
Vì số từ khóa trích lọc được thường có tới hàng chục ngàn, các kỹ thuật rút gọn
số chiều cần phải được áp dụng. Gần đây, các thuật rút gọn thuộc tính đã được
ứng dụng thành công trong phân loại trang web và phân loại dấu sách
(bookmark).
2.3. Kết luận chƣơng 2
Mục đích của rút gọn thuộc tính là làm giảm số chiều của không gian thuộc
tính, loại bỏ dữ liệu dư thừa, không liên quan. Rút gọn thuộc tính đóng vai trò
quan trọng trong bước tiền xử lý dữ liệu cũng như trong quá trình khai phá. Kết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27
quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ
khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu
được.
Trong chương 2 này, chúng tôi đã trình bày khái quát về nội dung, các
phương pháp và quy trình giải quyết vấn đề lựa chọn thuộc tính. Một số ứng
dụng quan trọng của lựa chọn thuộc tính cũng đã được bàn tới ở cuối chương.
Chương 3 tiếp theo dành cho việc nghiên cứu một số thuật toán rút gọn
thuộc tính điển hình.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
CHƢƠNG 3
MỘT SỐ THUẬT TOÁN
LỰA CHỌN THUỘC TÍNH ĐIỂN HÌNH
Như đã biết mục đích chính của lựa chọn thuộc tính là làm sao giảm kích
thước dữ liệu, chính vì điều này nên khi nghiên cứu các kỹ thuật lựa chọn thuộc
tính có nghĩa là đi nghiên cứu một số phương pháp để làm thế nào có thể rút gọn
dữ liệu một cách tối ưu nhất mà không làm thay đổi ngữ nghĩa của dữ liệu.
Chương 3 này dành cho việc nghiên cứu một số thuật toán lựa chọn thuộc tính
điển hình. Các thuật toán được trình bày theo ba nhóm chính: các thuật toán kiểu
filter, các thuật toán kiểu wrapper và một số thuật toán khác. Các thuật toán này
thường được sử dụng để lựa chọn thuộc tính giải quyết các vấn đề phân cụm và
phân lớp trong khai phá dữ liệu.
3.1. Các thuật toán theo cách tiếp cận filter
Để minh họa hoạt động của các thuật toán kiểu filter nêu trong phần này,
một tập dữ liệu ví dụ cho trong bảng 3.1 dưới đây sẽ được sử dụng. Tập dữ liệu
được chọn làm ví dụ này chỉ chứa các giá trị nhị phân, đó là nhằm đáp ứng
những yêu cầu khác nhau của các thuật toán sẽ được trình bày. Trong luận văn
này, từ đây về sau C ký hiệu tập các thuộc tính điều kiện, D ký hiệu tập các
thuộc tính quyết định (thuộc tính nhãn lớp).
3.1.1 Thuật toán RELIEF
Đây là thuật toán lựa chọn thuộc tính đầu tiên được xây dựng theo cách
tiếp cận lọc (filter). Trong quá trình thực hiện, RELEF sẽ tính toán cho mỗi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
Bảng 3.1: Tập dữ liệu ví dụ
thuộc tính một trọng số phù hợp (relevance weight) phản ánh khả năng phân biệt
các nhãn lớp của nó. Thuộc tính được chọn sẽ là thuộc tính có trọng số phù hợp
vượt mức quy định. Thuật toán này là như sau:
RELIEF(O, c, it s, ).
O: tập tất cả các đối tượng
c : số các thuộc tính điều kiện
its: số bước lặp
: giá trị ngưỡng đối với trọng số
(1) R ← { }
(2) Wa, Wa ←0
(3) for i = 1...it s
(4) chọn ngẫu nhiên một đối tượng x từ tập tất cả các đối tượng O
(5) tính nearHit và nearMiss của x
(6) for j = 1...c
(7) Wj ←Wj − diff(x j , nearH it j )/ it s + diff(x j , nearMiss j )/ it s
(8) for j = 1...c
(9) if Wj ≥ ; R ←R { j}
(10) return R
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
Tham số đầu tiên mà người sử dụng phải cung cấp cho RELIEF là its.
Tham số này chỉ ra số bước lặp, tức là số đối tượng mẫu được chọn liên tiếp để
tính toán các trọng số. Tại mỗi lần lấy mẫu, một đối tượng x được chọn ngẫu
nhiên rồi tính các giá trị nearHit và nearMiss của nó. nearHit là đối tượng có
cùng nhãn lớp với x và gần x nhất, còn nearMiss là đối tượng gần x nhất nhưng
không có cùng nhãn lớp với x. Độ gần nhau được đánh giá dựa trên khoảng cách
giữa các đối tượng xác định như sau: Khoảng cách giữa hai đối tượng o và x là
số tất cả các thuộc tính có giá trị khác nhau trên o và x,
1
( , ) ( , )
C
i i
i
dist o x diff o x
với
1
( , )
0
i i
i i
i i
o x
diff o x
o x
Để sử dụng RELIEF, người sử dụng còn phải cung cấp một tham số thứ
hai, đó là mức thích hợp tối thiểu mà mỗi thuộc tính được chọn phải đáp ứng.
Có thể thấy, RELIEF sẽ là thuật toán lựa chọn thuộc tính không hiệu quả
nếu tập dữ liệu có các thuộc tính điều kiện tương quan chặt chẽ với nhau và
chúng đều cho trọng phù hợp cao như nhau. Hiện nay, RELIEF đã được một số
tác giả phát triển cho phép lựa chọn thuộc tính từ cả các tập dữ liệu không nhất
quán, có nhiễu và có nhiều nhãn lớp. Một tập dữ liệu được gọi là không nhất
quán nếu chứa các cặp đối tượng mâu thuẫn nhau, nghĩa là các cặp đối tượng có
cùng các giá thuộc tính điều kiện nhưng lại có nhãn lớp khác nhau.
Áp dụng RELIEF vào tập dữ liệu ví dụ như sau: Chọn ngẫu nhiên một đối
tượng, chẳng hạn đối tượng 0. Trong trường hợp này ta có nearHit là đối tượng
5 và nearMiss là đối tượng 12. Với mỗi thuộc tính j, trọng số phù hợp của nó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
được cập nhật dần bằng một giá trị phụ thuộc vào sự khác nhau giữa xj và
nearHit, cũng như sự khác nhau giữa xj và nearMiss. Cụ thể là tại lần chọn ngẫu
nhiên một đối tượng thứ i, trọng số phù hợp của thuộc tính j sẽ là:
Wj := Wj − diff(x j , nearH it j )/ it s + diff(x j , nearMiss j )/ it s .
Quá trình cứ tiếp tục cho đến khi số bước lặp đạt tới giới hạn quy định its.
Thuộc tính sẽ được thêm vào tập các thuộc tính lựa chọn nếu trọng số phù hợp
của nó không thấp hơn mức yêu cầu Chạy RELIEF trên tập dữ liệu ví dụ với
its = 100 và = 0 thu được tập cuối cùng các thuộc tính lựa chọn là {a,d,e,f }.
Như vậy, ta đã loại bỏ được hai thuộc tính dư thừa là b và c. Với tập con gồm
bốn thuộc tính được lựa chọn {a,d,e,f }, tính nhất quán của tập dữ liệu ban đầu
vẫn được bảo tồn. Tuy nhiên, có thể thấy tập thuộc tính được chọn này vẫn còn
có thể được thu gọn hơn bằng cách loại bỏ thêm thuộc tính e.
3.1.2. Thuật toán FOCUS
Focus là một thuật toán rút gọn thuộc tính cũng được xây dựng theo cách
tiếp cận filter. Thuật toán này áp dụng phương pháp tìm kiếm từng bước ưu tiên
độ rộng từ thấp đến cao trong số tất cả các tập con của các thuộc tính để tìm ra
tập con nhỏ nhất mà vẫn bảo tồn được tính nhất quán của tập dữ liệu huấn luyện.
Tựa code của FOCUS là như sau:
FOCUS(O, c).
O: tập tất cả các đối tượng;
c: số các thuộc tính điều kiện;
(1) R ← { }
(2) for num = 1...c
(3) for mỗi tập con L có cỡ num
(4) cons = Độnhấtquán(L, O)
(5) if cons == true
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
(6) R ←L
(7) return R
(8) else continue
Với mỗi giá trị num = 1, … , c , FOCUS kiến tạo tất cả các tập con thuộc
tính cỡ num (tập con gồm num thuộc tính). Sau đó kiểm tra tính nhất quán của
dữ liệu đối với mỗi tập con này. Nếu tính nhất quán bị vi phạm, tập con thuộc
tính tương ứng sẽ bị loại. Thủ tục tìm kiếm tiếp tục cho đến khi tìm được tập con
bảo tồn sự nhất quán của dữ liệu hoặc khi tất cả các tập con thuộc tính đã được
xem xét hết.
Dễ thấy, vì FOCUS sử dụng tính nhất quán của dữ liệu làm tiêu chuẩn lựa
chọn tập con thuộc tính nên nó sẽ rất nhạy cảm với nhiễu dữ liệu. Hơn nữa, do
số tập con (lực lượng của tập lũy thừa) của tập các thuộc tính tăng theo hàm mũ
của số thuộc tính, thuật toán FOCUS sẽ không thể áp dụng được khi kích thước
của tập dữ liệu huấn luyện là tương đối lớn. Để khắc phục trở ngại này, thông
thường người ta cho phép tiến hành việc tìm tập thuộc tính rút gọn với một
ngưỡng tỷ lệ các đối tượng mâu thuẫn nhau cho phép nào đó. Khi đó, dòng
(5) của tựa code trên đây sẽ được thay bằng lệnh kiểm tra điều kiện if cons .
Chú ý rằng, số đếm các đối tượng mâu thuẫn nhau được định nghĩa là hiệu
số giữa số tất cả các đối tượng mâu thuẫn nhau và số các đối tượng mâu thuẫn
nhau có nhãn lớp xuất hiện nhiều nhất. Chẳng hạn, có n đối tượng mâu thuẫn
nhau trong tập dữ liệu với 2 nhãn lớp là 1 và 2; nếu trong số n đối tượng mâu
thuẫn nhau có c1 đối tượng nhận nhãn lớp 1, c2 đối tượng nhận nhãn lớp 2, c1 +
c2 = n. Khi đó, nếu
1 2c c
thì (thay cho n) số các đối tượng đối lập sẽ được tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
bằng n - c1 và tỷ lệ các đối tượng đối lập trong tập dữ liệu sẽ là
1n c N
, trong
đó N là số tất cả các đối tượng có trong tập dữ liệu.
Áp dụng FOCUS cho tập dữ liệu ví dụ 2.2: Trước tiên FOCUS đánh giá
tính nhất quán của dữ liệu theo từng thuộc tính riêng biệt
, , , , ,a b c d e f
, (các tập con thuộc tính có cỡ bằng 1). Không có
thuộc tính nào trong số các thuộc tính này bảo tồn tính nhất quán của dữ liệu.
Chẳng hạn, với thuộc tính f , có hai đối tượng mâu thuẫn nhau là 0 và 12. Tiếp
tục vòng lặp thứ hai, FOCUS đánh giá độ nhất quán của dữ liệu theo mỗi tập
con gồm hai thuộc tính
, ,a b ,a c
,
,a d
,
,a e
,
,a f
,
,b c
,b d
,
,b e
,
,b f
,
,c d
,
,c e
,
,c f
,
,d e
,
,d f
,
,e f
. Trong số các tập con này
cũng không có tập con nào cho phép bảo tồn tính nhất quán của dữ liệu và do đó
tất cả đều bị loại. Tiếp tục vòng lặp thứ ba, tìm được tập con cỡ 3 bảo tồn tính
nhất quán của dữ liệu là tập
, ,a d f
. Với kết quả này, tập thuộc tính ban đầu có
thể được rút gọn lại thành tập
, ,a d f
mà vẫn duy trì được tính nhất quán của
tập dữ liệu.
3.1.3. Thuật toán LVF
Khác với RELIEF và FOCUS, thuật toán LVF thực hiện việc sinh các tập
con thuộc tính để lựa chọn bằng phương pháp chọn ngẫu nhiên nhờ thuật toán
tạo số ngẫu nhiên Las Vegas. Thuật toán LVF là như sau:
LVF(O, C, att , ).
O: tập tất cả các các đối tượng;
C: tập tất cả các thuộc tính điều kiện;
att : số bước lặp của thuật toán;
: ngưỡng tỷ lệ các đối tượng mâu thuẫn nhau;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
R: Tập con thuộc tính tốt nhất hiện thời.
(1) R ← C
(2) for num = 1...att
(3) S ← Tập con thuộc tính chọn ngẫu nhiên( )
(4) if |S|≤ |R|
(5) if Độnhấtquán(S, O) ≤
(6) if |S| < |R|
(7) R ← S; output R
(8) else R ←
R S
(9) return R
Đầu tiên, LVF coi toàn bộ tập thuộc tính điều kiện là tập thuộc tính tốt
nhất. Tiếp đó, chọn ngẫu nhiên một tập con từ tập tất cả các thuộc tính điều kiện.
Nếu tập con thuộc tính này có lực lượng nhỏ hơn tập con tốt nhất hiện thời và
cho tỷ lệ các đối tượng mâu thuẫn nhau trong tập dữ liệu không vượt quá
ngưỡng cho trước, nó sẽ được xem là tập con mới tốt nhất. Một khi có tập con
tốt hơn được phát hiện, tập con này sẽ được LVF đưa ra dưới dạng kết quả tính
toán tức thời.
Nhược điểm của LVF là tiêu tốn thời gian nhiều hơn so với các thuật toán
heuristic trong việc tìm kiếm tập con thuộc tính tối ưu. Ngoài ra, khi tập dữ liệu
có kích thước khổng lồ, việc kiểm tra tính nhất quán của dữ liệu cũng tiêu tốn
khá nhiều thời gian.
Xét tập dữ liệu ví dụ 2.2: LVF chọn ngẫu nhiên một tập con thuộc tính từ
6 thuộc tính đã cho, chẳng hạn tập {a,b,c}. Đối với tập thuộc tính này, sẽ có 6
đối tượng không nhất quán, trong đó có 3 đối tượng mang nhãn lớp 1, 3 đối
tượng mang nhãn lớp 2, vậy tỷ lệ các đối tượng không nhất quán được tính bằng
(6-3)/12=1/4. Nếu tỷ lệ đối tượng không nhất quán cho phép = 0 thì tập
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
{a,b,c} bị loại. Tiếp tục quá trình tìm kiếm ngẫu nhiên, LVF sẽ cho kết quả tập
con thuộc tính tối ưu cục bộ là
, ,a d f
.
3.1.4. Thuật toán EBR
EBR cũng là thuật toán lựa chọn thuộc tính theo tiếp cận filter. Thuật toán
này áp dụng chiến lược tìm kiếm heuristic dựa vào entropy giống như một số
thuật toán học máy, chẳng hạn thuật giá trị toán xây dựng cây quyết định C4.5
của Quinlan. Có thể mô tả EBR như sau:
EBR(C)
C: tập tất cả các thuộc tính điều kiện;
(1)
A C
(2) calculate
( / )H D x
;
(3) choose A giving lowest value of
( / )H D A
;
(4) R ← A ;
(5) do
(6) T ← R ;
(7)
( )A C R
(8) if
/ ( / )H D R A H D T
(9)
T R A
;
(10)
;R T
(11) until
( / ) ( / )H D R H D C
;
(12) return R ;
Tại bước đầu tiên, EBR kiểm tra toàn bộ tập dữ liệu, chọn thuộc tính cho
lượng thông tin thu thêm (information gain) lớn nhất, điều này tương đương với
việc tìm thuộc tính A cho entropy có điều kiện
( / )H D A
nhỏ nhất. Entropy
( / )H D A
xác định bởi công thức:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
2
1 1
( / ) ( ) ( / )log ( / )
m n
j i j i j
j i
H D A P a P d a P d a
trong đó,
1 2, , ... , ma a a
là các giá trị của A ,
1 2, , ... , nd d d
là các giá trị của thuộc
tính quyết định D trong tập dữ liệu. Các xác suất được ước lượng được ước
lượng dựa vào tập dữ liệu. Chẳng han:
1
1( )
S
P a
N
trong đó
1S
là số các đối tượng có giá trị thuộc tính A bằng a1 , N là số tất cả
các đối tượng có trong tập dữ liệu.
Tại các bước tiếp theo, EBR tìm tập con cho entropy có điều kiện
( / )H D R A
nhỏ nhất trong số các tập con thu được bằng cách thêm vào tập R
đã tìm được ở bước trước một thuộc tính còn lại.
Tương tự như trên, ta có:
1 2( / , , ... , )kH C A A A
1 2 1 2 2 1 2
1 1
( , , ... , ) ( / , , ... , )log ( / , , ... , )
m n
j j kj i j j kj i j j kj
j i
P a a a P c a a a P c a a a
trong đó, (
1 2, , ... ,j j kja a a
), (
12 22 2, , ... , ka a a
), … , (
1 2, , ... ,m m kma a a
) là các tổ hợp
giá trị khác nhau của các thuộc tính
1 2, , ... , kA A A
.
Xét tập dữ liệu ví dụ 2.2. Trước tiên, EBR tính entropy của mỗi thuộc tính
điều kiện, thu được:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
Tập con Entropy
a
0.8885861
b
0.9543363
c
0.9543363
d
0.8885860
e
0.8650087
f
0.6186034
Vì {f} có entropy nhỏ nhất, nó trở thành thuộc tính được chọn
Các file đính kèm theo tài liệu này:
- doc413.pdf