Banner-baigiang-1090_logo1
Banner-baigiang-1090_logo2

Tìm kiếm theo tiêu đề

Tìm kiếm Google

Quảng cáo

Hướng dẫn sử dụng thư viện

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 036 286 0000
  • contact@bachkim.vn

LUANVAN

Wait
  • Begin_button
  • Prev_button
  • Play_button
  • Stop_button
  • Next_button
  • End_button
  • 0 / 0
  • Loading_status
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Đại Khoa
Ngày gửi: 00h:17' 27-10-2008
Dung lượng: 370.0 KB
Số lượt tải: 413
Số lượt thích: 0 người
Các thuật toán khai phá dữ liệu và ứng dụng
Giáo viên hướng dẫn :
PGS.TSKH Nguyễn Xuân Huy
Sinh viên thực hiện:
Lê Thị Mai
Phạm Thị Hoàng Linh
Nội dung
Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quá trình khai phá luật kết hợp
Thuật toán Apriori


Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quy trình khai phá luật kết hợp
Thuật toán Apriori

Quá trình phát hiện tri thức
Hình thành
định và định nghĩa bài toán
Thu thập và
tiền xử lý dữ liệu
Khai phá dữ liệu,
rút ra kết luận
Phân tích và
kiểm định kết quả
Sử dụng các tri thức
phát hiện được.
Quá trình phát hiện tri thức
1. Hình thành, xác định và định nghĩa bài toán.
2. Thu thập và tiền xử lý dữ liệu.
3. Khai phá dữ liệu, rút ra các tri thức.
4. Sử dụng các tri thức phát hiện được.
Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quy trình khai phá luật kết hợp
Thuật toán Apriori

Khái niệm khai phá dữ liệu

Phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu).

Phương pháp khai phá dữ liệu
Phương pháp suy diễn
Phương pháp quy nạp
Phương pháp phát hiện các luật kết hợp
Các phương pháp dựa trên mẫu
Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quy trình khai phá luật kết hợp
Thuật toán Apriori


Khái niệm về luật kết hợp
Cho I = { I1,I2,…Im}.
Một giao dịch T (T I).
Gọi D là cơ sở dữ liệu bao gồm n giao dịch
T D hỗ trợ (support) cho một tập X  I nếu nó chứa tất cả các khoản mục của X, nghĩa là X  T
Ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ cho X.
Ví dụ về luật kết hợp
Cho CSDL:
1- có mua sản phẩm; 0- không mua sản phẩm


Ví dụ về luật kết hợp
Tập các khoản mục:
I = {Bánh mì, Bơ, Phomat, Táo, Nho}
D là CSDL bao gồm 4 giao dịch
D = {T1, T2, T3, T4}
Cho tập X = {Bánh mì, Phomat}
Các giao dịch không hỗ trợ cho X: T1, T3.
Các giao dịch hỗ trợ cho X: T2,T4.
Ví dụ về luật kết hợp
Độ hỗ trợ của X được ký hiệu là Support (X). Và Support (X) được tính như sau:



= 2 / 4 = 1 / 2
Ví dụ về luật kết hợp
Định nghĩa luật kết hợp
Luật kết hợp có dạng X  Y, X, Y I là các tập mục gọi là itemsets, X được gọi là tiền đề, Y là mệnh đề kết quả.
Độ hỗ trợ của luật XY có công thức :


Định nghĩa luật kết hợp
Độ tin cậy (Confidence) của luật XY có công thức:



Các ngưỡng Minsup và mincof của độ hỗ trợ và độ tin cậy do người dùng xác định.


Ví dụ về luật kết hợp:
Cho bảng cơ sở dữ liệu D như sau :
Ví dụ về luật kết hợp
Luật kết hợp: A  C
Support = support ({A}  {C}) = 50%
Cofidence = support({A}{C}) / support ({A})
= 66,6%.
Cho min_support = 50%, min_conf = 50% :
A  C (support = 50%, confidence = 66.6%)
C  A (support = 50%, confidence = 100%).
Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quy trình khai phá luật kết hợp
Thuật toán Apriori


Quy trình khai phá luật kết hợp
Khai phá luật kết hợp trải qua 2 giai đoạn sau:
Khai phá tập các khoản mục thường xuyên.
Khai phá luật kết hợp.

Quá trình phát hiện tri thức
Khái niệm,phương pháp khai phá dữ liệu
Khái niệm về luật kết hợp
Quy trình khai phá luật kết hợp
Thuật toán Apriori



Thuật toán Apriori
Ý tưởng của thuật toán Apriori
Triển khai thuật toán Apriori
Cài đặt thuật toán Apriori
Giới hạn của Apriori
Ví dụ minh hoạ thuật toán Apriori



Ý tưởng của thuật toán Apriori
Tạo ra các tập phổ biến (thường xuyên) có 1 item, rồi tiếp đến là 2 items, 3 items ... cho đến khi chúng ta tạo ra tập phổ biến của mọi kích thước.
Mỗi tập item được tạo ra phải được tính toán độ hỗ trợ và độ tin cậy.
Tập k item được tạo ra từ tập k-1 items. Tạo danh sách các item dự kiến của tập k items bằng cách hợp từng đôi một tập k-1 items có trong danh sách.
Triển khai thuật toán Apriori
Qua 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 minsup.
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.
Cài đặt thuật toán Apriori
Đầu tiên tính toán và 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 được tìm thấy ở lần duyệt thứ k-1 để tạo tập dự kiến Ck. Tiếp theo duyệt CSDL và tính support cho Ck.
Tập hợp các tập k item Lk: là tập hợp của các tập k_item phổ biến.

Giới hạn của Apriori
Chi phí khá đắt, sử dụng bộ nhớ lớn và thời gian chậm
Không tốt đối với những mẫu lớn.
Tốn bộ nhớ để duyệt, quét CSDL nhiều lần.
Ví dụ minh hoạ thuật toán Apriori
Cho CSDL, tìm tập thường xuyên có độ hỗ trợ tối thiểu : 60%


Quét D
Xoá SupVí dụ minh hoạ thuật toán Apriori
Kết nối
Quét D
Kết nối
Quét D
Xin chân thành cảm ơn
No_avatar

Chị ơi chị có thế cho em xin bài giảng này của chị được không? Em đang cần mà không tải về máy được. Nếu được chị làm ơn gửi cho em qua mail này nhé. quyntdl@gmail.com. Xin chân thành cám ơn chị trước ạ!

No_avatar
Slide này hay quá, cám ơn nhé! Mình đang làm về đề tài này, không biết anh Khoa có liên lạc của Mai và Hoàng Linh k vậy?
No_avatar
Email của mình là hdt8x@yahoo.com, cám ơn trước nhé !
No_avatarf
Thanks
No_avatar

ai có code của thuật toán apriori ko? cho mình xin với. hic. Mình viết code kém lắm ak. Đây là mail của minh: thanhtrung1190cntt@gmail.com

 
Gửi ý kiến