luz_missngoc
New Member
Download Luận văn Phương pháp luận kết hợp và ứng dụng
MỤC LỤC
LỜI CẢM ƠN.i
DANH MỤC CÁC HÌNH.ii
MỞ ĐẦU . 3
Chương 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU. 6
1.1. Phát hiện tri thức và khai phá dữ liệu . 6
1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu . 7
1.2.1. Xác định vấn đề . 8
1.2.2.Thu thập và tiền xử lý dữ liệu . 9
1.2.3. Khai thác dữ liệu . 11
1.2.4. Minh họa và đánh giá. 11
1.2.5. Đưa kết quả vào thực tế . 11
1.3. Khai phá dữ liệu . 12
1.3.1. Các quan niệm về khai phá dữ liệu . 12
1.3.2. Nhiệm vụ của khai phá dữ liệu. 13
1.3.3. Triển khai việc khai phá dữ liệu . 15
1.3.4. Một số ứng dụng khai phá dữ liệu . 15
1.3.5. Các kỹ thuật khai phá dữ liệu . 17
1.3.6. Kiến trúc của hệ thống khai phá dữ liệu . 19
1.3.7. Quá trình khai phá dữ liệu. 21
1.3.8. Những khó khăn trong khai phá dữ liệu . 22
Chương 2 LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU . 25
2.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp . 25
2.2. Định nghĩa về luật kết hợp . 26
2.3. Một số hướng tiếp cận trong khai phá luật kết hợp . 32
Chương 3 MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP . 35
3.1. Thuật toán AIS . 35
3.2. Thuật toán SETM . 36
3.3. Thuật toán Apriori . 37
3.4. Thuật toán Apriori-TID . 44
3.5.Thuật toán Apriori-Hybrid . 46
3.6. Thuật toán FP_growth . 47
3.7. Thuật toán PARTITION [Savasere 95] . 55
Chương 4 KHAI THÁC LUẬT KẾT HỢP TRONG BÀI TOÁN QUẢN
LÝ THIẾT BỊ TRưỜNG THPT CHU VĂN AN- THÁI NGUYÊN . 58
4.1. Phát biểu bài toán . 58
4.2. Cơ sở dữ liệu của bài toán . 59
4.3. Rời rạc các thuộc tính gốc để tạo thành các thuộc tính nhị phân . 60
4.4. Cơ sở dữ liệu dạng nhị phân . 62
4.5. Kết quả khai thác luật kết hợp bằng thuật toán Apriori . 62
4.6. Kết quả khai thác cơ sở dữ liệu quản lý thiết bị Trường THPT Chu Văn
An – Thái Nguyên . 63
KẾT LUẬN . 64
TÀI LIỆU THAM KHẢO . 66
Để 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í
- Đánh giá mẫu: Thành phần này sử dụng các độ đo và tương tác với
modul khai phá dữ liệu để tập trung vào tìm các mẫu quan tâm.
Giao diện người dùng
Đánh giá mẫu
Mô tả khai phá dữ liệu
CSDL hay kho dữ liệu phục vụ
Cơ sở dữ liệu Kho dữ liệu
Cơ sở tri thức
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
- Giao diện người dùng: Đây là modul giữa người dùng và hệ thống khai
phá dữ liệu. Cho phép người dùng tương tác với hệ thống trên cơ sở
những truy vấn hay tác vụ, cung cấp thông tin cho việc tìm kiếm.
1.3.7. Quá trình khai phá dữ liệu
Các thuật toán khai phá dữ liệu thường được mô tả như những chương
trình hoạt động trực tiếp trên tệp dữ liệu. Với phương pháp máy học và thống
kê trước đây, thường thì bước đầu tiên các thuật toán nạp toàn bộ tệp dữ liệu
vào bộ nhớ. Khi chuyển sang các ứng dung công nghiệp liên quan đến việc
khai thác các kho dữ liệu lớn, mô hình này không thể đáp ứng bởi vì không
thể nạp hết dữ liệu vào bộ nhớ mà còn khó có thể chiết xuất ra những tệp đơn
giản để phân tích.
Quá trình khai phá dữ liệu (Hình 1.3) bắt đầu bằng cách xác định chính
xác vấn đề cần giải quyết. Tiếp đến là xác định dữ liệu liên quan dùng để xây
dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu liên quan và xử lý
chúng thành dạng sao cho thuật toán khai phá có thể hiểu được.
Hình 1.3. Quá trình khai phá dữ liệu
Xác định
nhiệm
vụ
Xác định
dữ liệu
liên quan
Thu thập
và tiền
xử lý dữ
liệu
Thuật
toán khai
phá dữ
liệu
Dữ liệu trực tiếp
Mẫu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Sau đó chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai
phá dữ liệu để tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng
(luật kết hợp, cây quyết định …)
Kết quả thu được mẫu phải có đặc điểm mới. Độ mới có thể được đối
sánh tương ứng với độ thay đổi trong dữ liệu hay bảng tri thức. Thường thì
độ đo mới của mẫu được đánh giá bằng một hàm logic hay hàm độ đo mới.
Ngoài ra mẫu còn có khả năng sử dụng tiềm ẩn.
Với thuật toán và nhiệm vụ khai phá dữ liệu khác nhau thì dạng mẫu
chiết xuất được cũng rất đa dạng.
1.3.8. Những khó khăn trong khai phá dữ liệu
Việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu gặp nhiều khó
khăn, nhưng không phải là không giải quyết được mà chúng cần được tìm
hiểu để có thể phát triển tốt hơn. Những khó khăn phát sinh trong khai phá dữ
liệu chính là dữ liệu trong thực tế thường động, không đầy đủ, lớn và bị nhiễu.
Trong trường hợp khác, người ta không biết cơ sở dữ liệu có chứa thông tin
cần thiết cho việc khai thác hay không và làm thế nào để giải quyết sự dư thừa
thông tin không thích hợp này.
- Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trường và bảng,
hàng triệu bản ghi với kích thước rất lớn, có thể lên đến GB. Các
phương pháp giải quyết hiện nay là đưa ra một ngưỡng cho cơ sở dữ
liệu, lấy mẫu, các phương pháp tính xấp xỉ, xử lí song song.
- Kích thước lớn: không chỉ có số lượng bản ghi mà số các trường trong
cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thước của bài toán trở nên lớn
làm tăng không gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng
một thuật toán khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp
khắc phục là làm giảm kích thước tác động của bài toán và sử dụng các
tri thức biết trước để xác định các biến không phù hợp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
- Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội
dung của chúng thay đổi liên tục. Chẳng hạn như các biến trong cơ sở
dữ liệu của ứng dụng đã cho chũng có thể bị thay đổi, bị xóa hay là
tăng lên theo thời gian. Dữ liệu có thể thay đổi theo thời gian và việc
khai phá dữ liệu bị ảnh hưởng bởi thời điểm quan sát dữ liệu, do đó có
thể làm cho mẫu khai thác được trước đó mất giá trị. Vấn đề này được
giải quyết bằng giải pháp tăng trưởng để nâng cấp các mẫu và coi
những thay đổi như là cơ hội để khai thác bằng cách sử dụng nó để tìm
kiếm các cẫu bị thay đổi.
- Các trường dữ liệu không phù hợp: Một đặc điểm quan trọng khác là
tính không thích hợp của dữ liệu – nghĩa là mục dữ liệu trở thành
không thích hợp với trọng tâm hiện tại của việc khai thác. Bên cạnh đó,
tính ứng dụng của một thuộc tính đối với một tập con của cơ sở dữ liệu
cũng là một vấn đề đôi khi cũng liên quan dến độ phù hợp.
- Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính
dữ liệu phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ
thống tương tác, sự thiếu vắng dữ liệu quan tọng có thể dẫn tới yêu cầu
cho giá trị của nó hay kiểm tra để xác định giá trị của nó. hay cũng
có thể sự vắng mặt của dữ liệu được coi như một điều kiện, thuộc tính
bị mất có thể được xem như một giá trị trung gian và gía trị không biết.
- Các trường dữ liệu bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có
thể làm cho dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ
liệu phải phát hiện được toàn bộ các thuộc tính có thể dùng để thuật
toán khai phá dữ liệu có thể áp dụng để giải quyết bài toán. Giả sử ta có
các thuộc tính để phân biệt các tình huống đáng quan tâm. Nếu chúng
không làm được điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Đây
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
cũng là vấn đề thường xảy ra trong cơ sở dữ liệu kinh doanh. Các thuộc
tính quan trọng có thể sẽ bị thiếu dữ liệu không được chuẩn bị.
- Quá phù hợp: Khi một thuật toán tim kiếm tham số tốt nhất cho một mô
thình nào đó sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng
“quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện
tượng chỉ phù hợp với dữ liệu đó mà không có khả năng đáp ứng cho
các dữ liệu lạ), làm cho mô hình hoạt động rất kém đối với các dữ liệu
thử. Các giải pháp khắc phục như đánh giá chéo, thực hiện theo nguyên
tắc nào đó hay sử dụng các biện pháp thống kê khác.
- Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng, điều quan trọng là
những điều khai thác được phải càng dễ hiểu với con người càng tốt. Vì
vậy, các giải pháp thường bao gồm việc diễn tả dưới dạng đồ họa, xây
dựng cấu trúc luật với các đồ thị có hướng, biểu diễn bằng ngôn ngữ tự
nhiên và kỹ thuật khác nhằm biểu diễn các tri thức và dữ liệu.
- Sự tương tác với người sử dụng các tri thức sẵn có: Rất nhiều công cụ
và phương pháp khai phá dữ liệu không thực sự tương tác với người
dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó.
Việc sử sụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã
có nhiều biện pháp nh...
Download miễn phí Luận văn Phương pháp luận kết hợp và ứng dụng
MỤC LỤC
LỜI CẢM ƠN.i
DANH MỤC CÁC HÌNH.ii
MỞ ĐẦU . 3
Chương 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU. 6
1.1. Phát hiện tri thức và khai phá dữ liệu . 6
1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu . 7
1.2.1. Xác định vấn đề . 8
1.2.2.Thu thập và tiền xử lý dữ liệu . 9
1.2.3. Khai thác dữ liệu . 11
1.2.4. Minh họa và đánh giá. 11
1.2.5. Đưa kết quả vào thực tế . 11
1.3. Khai phá dữ liệu . 12
1.3.1. Các quan niệm về khai phá dữ liệu . 12
1.3.2. Nhiệm vụ của khai phá dữ liệu. 13
1.3.3. Triển khai việc khai phá dữ liệu . 15
1.3.4. Một số ứng dụng khai phá dữ liệu . 15
1.3.5. Các kỹ thuật khai phá dữ liệu . 17
1.3.6. Kiến trúc của hệ thống khai phá dữ liệu . 19
1.3.7. Quá trình khai phá dữ liệu. 21
1.3.8. Những khó khăn trong khai phá dữ liệu . 22
Chương 2 LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU . 25
2.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp . 25
2.2. Định nghĩa về luật kết hợp . 26
2.3. Một số hướng tiếp cận trong khai phá luật kết hợp . 32
Chương 3 MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP . 35
3.1. Thuật toán AIS . 35
3.2. Thuật toán SETM . 36
3.3. Thuật toán Apriori . 37
3.4. Thuật toán Apriori-TID . 44
3.5.Thuật toán Apriori-Hybrid . 46
3.6. Thuật toán FP_growth . 47
3.7. Thuật toán PARTITION [Savasere 95] . 55
Chương 4 KHAI THÁC LUẬT KẾT HỢP TRONG BÀI TOÁN QUẢN
LÝ THIẾT BỊ TRưỜNG THPT CHU VĂN AN- THÁI NGUYÊN . 58
4.1. Phát biểu bài toán . 58
4.2. Cơ sở dữ liệu của bài toán . 59
4.3. Rời rạc các thuộc tính gốc để tạo thành các thuộc tính nhị phân . 60
4.4. Cơ sở dữ liệu dạng nhị phân . 62
4.5. Kết quả khai thác luật kết hợp bằng thuật toán Apriori . 62
4.6. Kết quả khai thác cơ sở dữ liệu quản lý thiết bị Trường THPT Chu Văn
An – Thái Nguyên . 63
KẾT LUẬN . 64
TÀI LIỆU THAM KHẢO . 66
Để 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:
phân cụm dữ liệu…- Đánh giá mẫu: Thành phần này sử dụng các độ đo và tương tác với
modul khai phá dữ liệu để tập trung vào tìm các mẫu quan tâm.
Giao diện người dùng
Đánh giá mẫu
Mô tả khai phá dữ liệu
CSDL hay kho dữ liệu phục vụ
Cơ sở dữ liệu Kho dữ liệu
Cơ sở tri thức
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
- Giao diện người dùng: Đây là modul giữa người dùng và hệ thống khai
phá dữ liệu. Cho phép người dùng tương tác với hệ thống trên cơ sở
những truy vấn hay tác vụ, cung cấp thông tin cho việc tìm kiếm.
1.3.7. Quá trình khai phá dữ liệu
Các thuật toán khai phá dữ liệu thường được mô tả như những chương
trình hoạt động trực tiếp trên tệp dữ liệu. Với phương pháp máy học và thống
kê trước đây, thường thì bước đầu tiên các thuật toán nạp toàn bộ tệp dữ liệu
vào bộ nhớ. Khi chuyển sang các ứng dung công nghiệp liên quan đến việc
khai thác các kho dữ liệu lớn, mô hình này không thể đáp ứng bởi vì không
thể nạp hết dữ liệu vào bộ nhớ mà còn khó có thể chiết xuất ra những tệp đơn
giản để phân tích.
Quá trình khai phá dữ liệu (Hình 1.3) bắt đầu bằng cách xác định chính
xác vấn đề cần giải quyết. Tiếp đến là xác định dữ liệu liên quan dùng để xây
dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu liên quan và xử lý
chúng thành dạng sao cho thuật toán khai phá có thể hiểu được.
Hình 1.3. Quá trình khai phá dữ liệu
Xác định
nhiệm
vụ
Xác định
dữ liệu
liên quan
Thu thập
và tiền
xử lý dữ
liệu
Thuật
toán khai
phá dữ
liệu
Dữ liệu trực tiếp
Mẫu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Sau đó chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai
phá dữ liệu để tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng
(luật kết hợp, cây quyết định …)
Kết quả thu được mẫu phải có đặc điểm mới. Độ mới có thể được đối
sánh tương ứng với độ thay đổi trong dữ liệu hay bảng tri thức. Thường thì
độ đo mới của mẫu được đánh giá bằng một hàm logic hay hàm độ đo mới.
Ngoài ra mẫu còn có khả năng sử dụng tiềm ẩn.
Với thuật toán và nhiệm vụ khai phá dữ liệu khác nhau thì dạng mẫu
chiết xuất được cũng rất đa dạng.
1.3.8. Những khó khăn trong khai phá dữ liệu
Việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu gặp nhiều khó
khăn, nhưng không phải là không giải quyết được mà chúng cần được tìm
hiểu để có thể phát triển tốt hơn. Những khó khăn phát sinh trong khai phá dữ
liệu chính là dữ liệu trong thực tế thường động, không đầy đủ, lớn và bị nhiễu.
Trong trường hợp khác, người ta không biết cơ sở dữ liệu có chứa thông tin
cần thiết cho việc khai thác hay không và làm thế nào để giải quyết sự dư thừa
thông tin không thích hợp này.
- Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trường và bảng,
hàng triệu bản ghi với kích thước rất lớn, có thể lên đến GB. Các
phương pháp giải quyết hiện nay là đưa ra một ngưỡng cho cơ sở dữ
liệu, lấy mẫu, các phương pháp tính xấp xỉ, xử lí song song.
- Kích thước lớn: không chỉ có số lượng bản ghi mà số các trường trong
cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thước của bài toán trở nên lớn
làm tăng không gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng
một thuật toán khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp
khắc phục là làm giảm kích thước tác động của bài toán và sử dụng các
tri thức biết trước để xác định các biến không phù hợp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
- Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội
dung của chúng thay đổi liên tục. Chẳng hạn như các biến trong cơ sở
dữ liệu của ứng dụng đã cho chũng có thể bị thay đổi, bị xóa hay là
tăng lên theo thời gian. Dữ liệu có thể thay đổi theo thời gian và việc
khai phá dữ liệu bị ảnh hưởng bởi thời điểm quan sát dữ liệu, do đó có
thể làm cho mẫu khai thác được trước đó mất giá trị. Vấn đề này được
giải quyết bằng giải pháp tăng trưởng để nâng cấp các mẫu và coi
những thay đổi như là cơ hội để khai thác bằng cách sử dụng nó để tìm
kiếm các cẫu bị thay đổi.
- Các trường dữ liệu không phù hợp: Một đặc điểm quan trọng khác là
tính không thích hợp của dữ liệu – nghĩa là mục dữ liệu trở thành
không thích hợp với trọng tâm hiện tại của việc khai thác. Bên cạnh đó,
tính ứng dụng của một thuộc tính đối với một tập con của cơ sở dữ liệu
cũng là một vấn đề đôi khi cũng liên quan dến độ phù hợp.
- Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính
dữ liệu phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ
thống tương tác, sự thiếu vắng dữ liệu quan tọng có thể dẫn tới yêu cầu
cho giá trị của nó hay kiểm tra để xác định giá trị của nó. hay cũng
có thể sự vắng mặt của dữ liệu được coi như một điều kiện, thuộc tính
bị mất có thể được xem như một giá trị trung gian và gía trị không biết.
- Các trường dữ liệu bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có
thể làm cho dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ
liệu phải phát hiện được toàn bộ các thuộc tính có thể dùng để thuật
toán khai phá dữ liệu có thể áp dụng để giải quyết bài toán. Giả sử ta có
các thuộc tính để phân biệt các tình huống đáng quan tâm. Nếu chúng
không làm được điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Đây
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
cũng là vấn đề thường xảy ra trong cơ sở dữ liệu kinh doanh. Các thuộc
tính quan trọng có thể sẽ bị thiếu dữ liệu không được chuẩn bị.
- Quá phù hợp: Khi một thuật toán tim kiếm tham số tốt nhất cho một mô
thình nào đó sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng
“quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện
tượng chỉ phù hợp với dữ liệu đó mà không có khả năng đáp ứng cho
các dữ liệu lạ), làm cho mô hình hoạt động rất kém đối với các dữ liệu
thử. Các giải pháp khắc phục như đánh giá chéo, thực hiện theo nguyên
tắc nào đó hay sử dụng các biện pháp thống kê khác.
- Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng, điều quan trọng là
những điều khai thác được phải càng dễ hiểu với con người càng tốt. Vì
vậy, các giải pháp thường bao gồm việc diễn tả dưới dạng đồ họa, xây
dựng cấu trúc luật với các đồ thị có hướng, biểu diễn bằng ngôn ngữ tự
nhiên và kỹ thuật khác nhằm biểu diễn các tri thức và dữ liệu.
- Sự tương tác với người sử dụng các tri thức sẵn có: Rất nhiều công cụ
và phương pháp khai phá dữ liệu không thực sự tương tác với người
dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó.
Việc sử sụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã
có nhiều biện pháp nh...