trondoiyeuanh19
New Member
Download miễn phí Đồ án Khai phá và làm sạch dữ liệu
Thuật toán Apriori
Gồm 2 bước:
Tạo tập item phổ biến: tạo tất cả các tập item
dự kiến, tính toán độ hỗ trợ, loại bỏ các tập dự
kiến không đạt minsupp.
Kiểm tra tập 1 item có là phổ biến không.
Lần duyệt thứ k: Sử dụng các tập Lk-1 của tập k-1
item phổ biến để tạo tập dự kiến Ck (dùng hàm
apriori_gen). Duyệt CSDL và tính support cho Ck.
Lk: là tập hợp của các tập k_item phổ biến, mỗi
phần tử là một tập có 2 trường itemset, support.
Ck: tập hợp của tập k_item dự kiến
Để tải bản Đầy Đủ của tài liệu, 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 tài liệu:
1BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
-------o0o-------
Khai phá và làm sạch dữ liệu
ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
NGÀNH CÔNG NGHỆ THÔNG TIN
Giáo viên hướng dẫn: PGS. TS. Đỗ Trung Tuấn
Sinh viên: Nguyễn Hoài Nam
Lớp: CT701
Hải Phòng, 2007
2Nội dung báo cáo
Chương 1. Mở đầu.
Chương 2. CSDL và nhu cầu về dữ liệu meta.
Chương 3. Khai phá dữ liệu.
Chương 4. Luật kết hợp và các tiếp cận.
Chương 5. Thử nghiệm việc khai phá dữ liệu.
Chương 6. Kết luận
3Chương 2. CSDL và nhu cầu về dữ liệu meta
Mô hình dữ liệu quan hệ
Nhu cầu về dữ liệu meta
Trong vài thập niên với những tác động mạnh
mẽ của các tiến bộ trong công nghệ công nghệ
thông tin và truyền thông nhu cầu về dữ liệu
ngày càng nhiều
Yêu cầu về các thông tin trong các lĩnh vực hoạt
động đó đòi hỏi cao hơn, người quyết định
không những cần dữ liệu mà còn cần có thêm
nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc
ra quyết định của mình.
4Chương 3. Khai phá dữ liệu
Giới thiệu chung
Về khai phá dữ liệu
Quá trình phát hiện tri thức trong CSDL
Nhiệm vụ chính trong khai phá dữ liệu
Các kĩ thuật khai phá dữ liệu
Ứng dụng của khai phá dữ liệu
Khai phá luật kết hợp và ứng dụng
5Giới thiệu chung
Những năm 60 của thế kỷ trước, người ta bắt đầu sử
dụng các công cụ tin học để tổ chức và khai thác các
CSDL
Người ta nói “Chúng ta đang chìm ngập trong dữ liệu
mà vẫn đói tri thức”
Khai phá dữ liệu là một lĩnh vực mới, nhằm tự động
khai thác những thông tin, những tri thức có tính tiềm
ẩn, hữu ích từ những CSDL lớn
6Về khai phá dữ liệu
Khai phá dữ liệu là một khái niệm ra đời vào
những năm cuối của thập kỉ 80
Khai phá dữ liệu 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
Định nghĩa: Data Mining là một quá trình tìm
kiếm, phát hiện tri thức mới, tiềm ẩn, hữu
dụng trong CSDL lớn
7Quá trình phát hiện tri thức trong CSDL
8Nhiệm vụ chính trong khai phá dữ liệu
Phân lớp, phân loại
Hồi quy
Phân nhóm
Tóm tắt
Mô hình hoá phụ thuộc
9Các kĩ thuật khai phá dữ liệu
Các kĩ thuật tiếp cận
Dạng dữ liệu có thể khai phá
10
Các kĩ thuật tiếp cận
Trên quan điểm của học máy, các kĩ thuật trong Data
Mining gồm:
Học có giám sát
Học không có giám sát
Học nửa giám sat
Căn cứ vào lớp các bài toán cần giải quyết, khai phá
dữ liệu có các kỹ thuật áp dụng sau:
Phân lớp và dự đoán
Luật kết hợp
Phân tích chuỗi theo thời gian
Phân cụm
Mô tả khái niệm
11
Dạng dữ liệu có thể khai phá
CSDL quan hệ
CSDL đa chiều
CSDL dạng giao dịch
CSDL quan hệ-hướng đối tượng
Dữ liệu không gian và thời gian
Dữ liệu chuỗi thời gian
CSDL đa phương tiện
Dữ liệu Text và Web…
12
Ứng dụng của khai phá dữ liệu
Kinh doanh
Ngân hàng
Bảo hiểm sức khoẻ
Y tế…
13
Khai phá luật kết hợp và ứng dụng
Luật kết hợp là một biểu thức có dạng: X-
>Y, trong đó X và Y là tập các trường gọi là
item
Ứng dụng trực tiếp của các luật này trong các
bài toán kinh doanh
14
Thuật toán về khai phá dữ liệu
thuật toán Apriori
Ý tưởng thuật toán
Thuật toán Apriori
Ví dụ minh hoạ
15
Ý tưởng thuật toán
Đề xuất lần đầu vào năm 1993
Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin cậy
thoả mãn lớn hơn một giá trị ngưỡng nào đó
Thuật toán được tỉa bớt những tập ứng cử viên có tập
con không phổ biến trước khi tính độ hỗ trợ
Thuật toán Apriori tính tất cả các tập ứng cử của tập
k trong một lần duyệt CSDL
16
Thuật toán Apriori
Gồm 2 bước:
Tạo tập item phổ biến: tạo tất cả các tập item
dự kiến, tính toán độ hỗ trợ, loại bỏ các tập dự
kiến không đạt minsupp.
Kiểm tra tập 1 item có là phổ biến không.
Lần duyệt thứ k: Sử dụng các tập Lk-1 của tập k-1
item phổ biến để tạo tập dự kiến Ck (dùng hàm
apriori_gen). Duyệt CSDL và tính support cho Ck.
Lk: là tập hợp của các tập k_item phổ biến, mỗi
phần tử là một tập có 2 trường itemset, support.
Ck: tập hợp của tập k_item dự kiến
17
Thuật toán Apriori
18
Thuật toán Apriori
Tạo luật kết hợp: Từ các tập con của tập phổ biến xây dựng luật
kết hợp và tính độ tin cậy của luật.
Từ tập item phổ biến L, tìm tất cả các tập con không rỗng f L rồi
tạo ra luật f L – f thoả mãn minconf.
VD: Nếu {A,B,C,D} là tập item phổ biến thì có các luật dự kiến:
ABC D, ABD C, ACD B, BCD A,
A BCD, B ACD, C ABD, D ABC
AB CD, AC BD, AD BC, BC AD,
BD AC, CD AB,
Nếu L có k item thì có thể tạo ra 2k-2 luật kết hợp dự kiến(bỏ qua luật
L và L)
Dựa vào tính chất của độ tin cậy để tạo ra luật có conf >= minconf.
Độ tin cậy không có tính chất c(ABC D) có thể lớn hơn hay nhỏ hơn
c(AB D)
Nhưng nếu luật được sinh ra từ cùng một tập item phổ biến thì có
thuộc tính đó:
VD: L = {A,B,C,D}
c(ABC D) c(AB CD) c(A BCD)
19
Thuật toán Apriori
20
Ví dụ minh hoạ
21
Ví dụ minh hoạ
22
Chương 4. Luật kết hợp và các tiếp cận
Khai phá luật kết hợp
Cho trước tỉ lệ hỗ trợ và độ tin cậy .. Đánh
số tất cả các luật trong D có các giá trị tỉ lệ hỗ
trợ và tin cậy lớn hơn và tương ứng.
Lý thuyết về luật kết hợp
23
Chương 5. Thử nghiệm
24
Chương 5. Thử nghiệm
25
Chương 5. Thử nghiệm
26
Chương 5. Thử nghiệm
27
Chương 5. Thử nghiệm
28
Chương 6. Kết luận
Trong quá trình nghiên cứu viết luận văn em
đã: tìm hiểu tổng quan về lí thuyết khai phá
dữ liệu, thuật toán Apriori và luật kết hợp.
Do thời gian và kinh nghiệm thực tế chưa
nhiều nên luận văn còn nhiều thiếu sót mong
các thầy cô bỏ qua và góp ý.
Em xin chân thành cảm ơn!
...