BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC KINH TẾ - KĨ THUẬT CÔNG NGHIỆP KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO NHÓM 2 MÔN KHAI PHÁ DỮ LIỆUGiảng viên hướng dẫn : Trần Thanh ĐạiSinh viên thực hiện :
Trang 1BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KINH TẾ - KĨ THUẬT CÔNG NGHIỆP
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO NHÓM 2 MÔN KHAI PHÁ DỮ LIỆU
Giảng viên hướng dẫn : Trần Thanh Đại Sinh viên thực hiện : Nguyễn Hồng Phước
Nguyễn Thị Hải Phương Nguyễn Tiến Đại Phạm Thị Hà Thu Trần Trung Sơn Đàm Ngọc Huyền Khúc Trần Ánh Ngân Lớp : DHTI14A4HN
Hà Nội, tháng 4 năm 2024
Trang 2BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KINH TẾ - KĨ THUẬT CÔNG NGHIỆP
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO NHÓM 2 MÔN KHAI PHÁ DỮ LIỆU
Giảng viên hướng dẫn : Trần Thanh Đại Sinh viên thực hiện : Nguyễn Hồng Phước
Nguyễn Thị Hải Phương Nguyễn Tiến Đại Phạm Thị Hà Thu Trần Trung Sơn Đàm Ngọc Huyền Khúc Trần Ánh Ngân Lớp : DHTI14A4HN
Hà Nội, tháng 4 năm 2024
Trang 3Lời mở đầu Trong những năm gần đây, việc nắm bắt được thông tin được coi là cơ sở của mọi hoạt động sản xuất, kinh doanh Cá nhân hoặc tổ chức nào thu thập và hiểu được thông tin và hành động dựa trên các thông tin được kết xuất từ các thông tin đã có sẽ đạt được thành công trong mọi hoạt động Chính vì lý do đó, việc tạo ra thông tin, tổ chức lưu trữ và khai thác ngày càng trở nên quan trọng và gia tăng không ngừng
Sự tăng trưởng vượt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống như: thương mại, quản lý và khoa học đã làm nảy sinh và thúc đẩy sự phát triển của kỹ thuật thu thập, lưu trữ, phân tích và khai phá dữ liệu không chỉ bằng các phép toán đơn giản thông thường như: phép đếm, thống kê mà đòi hỏi cách xử lý thông minh hơn, hiệu quả hơn Từ đó các nhà quản lý có được thông tin có ích để tác động lại quá trình sản xuất, kinh doanh của mình đó là tri thức Các kỹ thuật cho phép ta khai thác được tri thức hữu dụng từ CSDL (lớn) được gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining) Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu
Kỹ thuật khám phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng
Khai phá dữ liệu (Data Mining) được coi là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL, kho dữ liệu Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác
có ý nghĩa tương tự như: Khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database-KDD), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredging)
Tiểu luận này trình bày một số vấn đề về khám phá tri thức, khai phá dữ liệu, và trình bày rõ vấn đề khai phá luật kết hợp và ứng dụng một số thuật toán khai phá luật kết hợp trong CSDL
Trang 4Bài 1: Xây dựng cây Tree và tìm các tập mục phổ biến bằng thuật toán FP-Grow với min_sup=3 cho CSDL giao dịch sau:
- Ta có L1:
Danh mục Độ phổ biến
Vì min_Sup = 3 => Bỏ danh mục D có độ phổ biến bằng 2
=>
STT Mã danh mục Độ phổ biến
Trang 5- Sắp xếp lại thứ tự các danh mụctrong từng giao dịch:
- Xây dựng cây FP – tree:
Trang 6- Tìm tập phổ biến của C:
- Vì min_Sup = 3 => Bỏ W : 2
=> Tập phổ biến của C là: { A , C : 3 }; { T , C : 3 }; { A , T , C : 1 }
Trang 7- Tìm tập phổ biến cảu T:
=> Tập phổ biến của T là: { A , T : 4 }; { W , T : 3 }; { A , W , T : 3 }
- Tìm tập phổ biến của W:
=> Tập phổ biến của W là: { A , W : 4 }
Trang 8Bài 2: Sử dụng phương pháp phân loại dữ liệu của Bayesian để xác định một sinh viên trẻ với mức thu nhập trung bình, được đánh giá tín dụng bình thường thì có mua hay không mua máy tính
- Biểu diễn bài toán phân loại :
+ z = (Age = Young , Income = Medium , Student = Yes , Credit_rating = Fair) + Có hai lớp phân thê :
C1= Yes ( Mua máy tính )
C2 = No (Không mua máy tính )
- Tính giá trị xác suất trước cho mỗi phân lớp :
+ P(c1) = 4/14
+ P(c2) = 10/14
- Tính giá trị xác suất của mỗi giá trị thuộc tính đối với mỗi phân lớp :
+ P(Age = Young|c1) = 1/4
+ P(Income = Medium |c1) = 2/4
Trang 9+ P(Student = Yes |c1) = 3/4
+ P(Credit_rating = Fair|c1) = 1/4
+ P(Age = Young|c2) = 5/10
+ P(Income = Medium |c2) = 2/10
+ P(Student = Yes |c2) = 2/10
+ P(Credit_rating = Fair|c2) = 3/10
- Tính xác suất có thể xảy ra của bài toán đối với mỗi phân lớp :
+ Đối với phân lớp c1 :
P(z|c1) = P(Age = Young|c1)* P(Income = Medium |c1) *P(Student = Yes |c1) * P(Credit_rating = Fair|c1) = (1/4 * 2/4 * 3/4 *1/4) = 3/128 ≈ 0.023
+ Đối với phân lớp c2 :
P(z|c2) = P(Age = Young|c2)* P(Income = Medium |c2) *P(Student = Yes |c2) * P(Credit_rating = Fair|c2) = (5/10*2/10*2/10*3/10 ) = 3/500 ≈ 0.006
- Xác định phân lớp có thể nhất :
+ Đối với phân lớp c1 :
P(c1) * P(z|c1) = 4/14 * 0.023 = 0.006
+ Đối với phân lớp c2 :
P(c2) * P(z|c2) = 10/14 * 0.006 = 0.0064
Nhận xét : Vì P(z|c1) > P(z|c2) => Sinh viên sẽ mua máy tính
Bài 3: Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại được biểu diễn bởi 2 đặc trưng X,Y như sau
Sử dụng thuật toán K-Mean để phân loại 4 đối tượng trên vào 2 nhóm G1 và G2 với tâm cụm ban đầu là G1(2,2); G2(3,2)
Trang 10- Tính khoảng cách từ các đối tượng đến tâm của các nhóm: D0; G1(2, 2); G2(3, 2)
- Nhóm các đối tượng vào nhóm gần nhất: J0
Group 1 có 1 đổi tượng là A
Group 2 có 3 đối tượng là B, C, D
Vì group 1 chỉ có 1 đối tượng là A => G1 không đổi
- Tính G2 mới:
G2 = (3+4 +5
2+3+4
= ( 4 , 3 )
- Tính khoảng cách từ các đối tượng đến tâm mới của các nhóm: D1; G1(2, 2); G2(4, 3)
Trang 11- Nhóm các đối tượng vào nhóm gần nhất: J1
Group 1 có 2 đối tượng là A và B
Group 2 có 2 đối tượng là C và D
=> Tính tâm cụm mới
- Tâm cụm mới:
G1 = (2+3
2+2
2 ) = (5
2, 2) G2 = (4 +5
3+4
2 ) = (9
2,
7
2)
- Tính khoảng cách từ các đối tượng đến tâm mới của các nhóm: D2; G1(52, 2); G2(92, 72)
2
√ 41 2
√ 34
2
3 √ 2 2
√ 2 2
√ 2 2
- Nhóm các đối tượng vào nhóm gần nhất: J2
=> J1 = J2 Không có sự thay đổi cụm nào của đối tượng => Dừng
=>
Trang 12Đối tượng X Y Cụm