Download miễn phí Luận văn Lựa chọn thuộc tính trong khai phá dữ liệu



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


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_lua_chon_thuoc_tinh_trong_khai_pha_du_lieu.ZixGhqRw3V.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42416/
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung:

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 hay đã 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 hay 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 hay 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 đ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ì...

---