- 1- Phát hiện tri thức trong tập dữ liệu lớn
MỤC LỤC
MỤC LỤC 1
LỜI CẢM ƠN 5
CÁC KÝ HIỆU VÀ CÁC TỪ VIẾT TẮT 7
DANH MỤC CÁC HÌNH MINH HỌA 8
DANH MỤC CÁC BẢNG 9
PHẦN I. PHẦN MỞ ĐẦU 10
1. TÊN ĐỀ TÀI 10
2. LÝ DO CHỌN ĐỀ TÀI 10
3. MỤC TIÊU VÀ NHIỆM VỤ NGHIÊN CỨU 11
4. CƠ SỞ LÝ THUYẾT 11
5. GIẢ THIẾT KHOA HỌC 12
6. PHẠM VI ỨNG DỤNG 12
7. PHƯƠNG PHÁP TIẾP CẬN 12
1.4.1. Định nghĩa khai phá dữ liệu 22
1.4.2. Nhiệm vụ KPDL là gì? 23
1.4.3. Triển khai việc KPDL như thế nào? 25
1.4.4. Một số ứng dụng KPDL 27
1.4.5. Các kỹ thuật khai phá dữ liệu 29
1.4.6. Kiến trúc của hệ thống khai phá dữ liệu 32
1.4.7. Quá trình khai phá dữ liệu 34
1.4.8. Những khó khăn trong khai phá dữ liệu 36
CHƯƠNG II. LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU - MỘT SỐ
THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 39
2.1. Bài toán kinh ñiển dẫn ñến việc KPLKH 39
2.2. Định nghĩa luật kết hợp 40
Định nghĩa: 40
Định nghĩa: Độ hỗ trợ 40
Định nghĩa: Độ tin cậy 41
Kết luận về Thuật toán Apriori 86
CHƯƠNG III. KHAI THÁC LUẬT KẾT HỢP TRONG BÀI TOÁN QUẢN
LÝ THIẾT BỊ TRƯỜNG ĐHCN – HÀ NỘI 86
3.1. Phát biểu bài toán 86
3.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
91
3.4. Cơ sở dữ liệu dạng nhị phân 92
3.5 Các bước thực hiện chương trình 95
PHẦN III. KẾT LUẬN 96
1. KẾT LUẬN VÀ ĐÁNH GIÁ KẾT QUẢ 96
2. HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN 98
- 4- Phát hiện tri thức trong tập dữ liệu lớn
TÀI LIỆU THAM KHẢO 99
- 5-
Nguyễn Đức Lưu
- 7- Phát hiện tri thức trong tập dữ liệu lớn
CÁC KÝ HIỆU VÀ CÁC TỪ VIẾT TẮT
CSDL Cơ sở dữ liệu
DM Data Mining
KDD Knowledge Discovery in Databases
KPDL Khai phá dữ liệu
KPLKH Khai phá luật kết hợp
SQL Structured Query Language
TID Transaction Identification
- 8- Phát hiện tri thức trong tập dữ liệu lớn
DANH MỤC CÁC HÌNH MINH HỌA
Danh
mục
Nội dung Trang
Hình 1.1 Quá trình khám phá tri thức từ cơ sở dữ liệu 13
Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu 26
Hình 1.3 Quá trình khai phá dữ liệu 28
Hình 2.1 Dùng thuật toán Apriori tính ra các tập xuất hiện
σ-thường xuyên.
mục
Nội dung Trang
Bảng 2.1 Giao dịch mua hàng 36
Bảng 2.2 Tính ñộ hỗ trợ cho các mặt hàng 37
Bảng 2.3 Các luật kết hợp và ñộ tin cậy của chúng 38
Bảng 2.4 Các giao tác cơ sở dữ liệu 59
Bảng 3.1 Bảng danh mục các phòng cần quản lý thiết bị 71
Bảng 3.2 Bảng thống kê chi tiết các thiết bị trong phòng 72
Bảng 3.3 Bảng ñăng ký tên các thuộc tính rời rạc 73
Bảng 3.4 Bảng dữ liệu nhị phân 74
- 10- Phát hiện tri thức trong tập dữ liệu lớn
PHẦN I. PHẦN MỞ ĐẦU
1. TÊN ĐỀ TÀI
Phát hiện tri thức trong tập dữ liệu lớn
2. LÝ DO CHỌN ĐỀ TÀI
Trong những năm gần ñây, vai trò của máy tính trong việc lưu trữ và xử
lý thông tin ngày càng trở nên quan trọng. Bên cạnh ñó, các thiết bị thu
thập dữ liệu tự ñộng tương ñối phát triển ñã tạo ra những kho dữ liệu lớn,
như các dữ liệu ngân hàng, dữ liệu bán hàng
,
y tế, marketing, viễn thông,
internet … Theo như ñánh giá cho thấy cứ sau 20 tháng, lượng thông tin
trên thế giới lại tăng gấp ñôi. Cùng với sự phát triển mạnh mẽ của công
nghệ, các thiết bị lưu trữ và các thiết bị thu thập thông tin tự ñộng ñã làm
Vận dụng kỹ thuật khai thác dữ liệu nhằm tìm ra những thông
tin, hoạt ñộng xảy ra
ñồng thời và áp dụng chúng vào bài toán
quản lý thiết bị.
Phân tích những ưu nhược ñiểm một số thuật toán trong khai
thác dữ liệu, ñánh giá, so sánh giữa các thuật toán.
Xây dựng chương trình thể hiện và ñánh giá các kết quả lý
thuyết.
4. CƠ SỞ LÝ THUYẾT
Các khái niệm và kỹ thuật cơ bản về Data mining
,
khái niệm tri
thức, dữ liệu, quá trình phát hiện tri thức, nhiệm vụ và các kỹ thuật
phát hiện tri thức.
Cơ sở toán học của các thuật toán khai phá tri thức.
- 12- Phát hiện tri thức trong tập dữ liệu lớn
Các kiểu cấu trúc dữ liệu dùng trong khai thác dữ liệu, trong bài
toán quản lý.
5. GIẢ THIẾT KHOA HỌC
Sử dụng kỹ thuật phát hiện tri thức trong khai thác dữ liệu một
cách hiệu quả thì nguồn dữ liệu lớn sẽ có giá trị và hữu ích hơn cho
người dùng.
6. PHẠM VI ỨNG DỤNG
-
Bài toán quản lý thiết bị.
ứng viên dựa vào cấu trúc cây FP Tree, các thuật toán phổ thông tìm luật kết
hợp.
Chương III: Cài ñặt chương trình tìm luật kết hợp, ứng dụng trong
quản lý trang thiết bị của trường Đại học Công nghiệp Hà Nội.
- 14- Phát hiện tri thức trong tập dữ liệu lớn
PHẦN II. NỘI DUNG
CHƯƠNG I.
TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU
1.1. Khám phá tri thức và khai phá dữ liệu
Trong thời ñại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ
liệu ngày càng phát triển tạo ñiều kiện cho các ñơn vị thu thập dữ liệu tốt
hơn. Đặc biệt trong lĩnh vực kinh doanh, các doanh nghiệp ñã nhận thức
ñược tầm quan trọng của việc nắm bắt và xử lí thông tin, nhằm giúp các chủ
doanh nghiệp trong việc vạch ra các chiến lược kinh doanh kịp thời mang lại
những lợi nhuận to lớn cho doanh nghiệp của mình. Tất cả lí do ñó khiến
cho các cơ quan, ñơn vị và các doanh nghiệp ñã tạo ra một lượng dữ liệu
lớn cỡ Gigabyte thậm chí là Terabyte cho riêng mình. Các kho dữ liệu ngày
càng lớn và tiềm ẩn nhiều thông tin có ích. Sự bùng nổ ñó dẫn tới một yêu
cầu cấp thiết ñó là phải có những kỹ thuật và công cụ mới ñể biến kho dữ
liệu lớn kia thành những thông tin cô ñọng và có ích. Kỹ thuật Khai phá dữ
liệu (Data mining ) ra ñời như một kết quả tất yếu ñáp ứng các nhu cầu ñó .
Thông thường chúng ta coi dữ liệu như một dãy các bits, hoặc các số
và các ký hiệu, hoặc “các ñối tượng” với một ý nghĩa nào ñó. Chúng ta sử
dụng các bits ñể ño lường các thông tin và xem nó như là các dữ liệu ñã
ñược lọc bỏ các dư thừa, ñược rút gọn tới mức tối thiểu ñể ñặc trưng một
- Khai phá dữ liệu (Data mining ): Các kỹ thuật ñược áp dụng ñể
trích xuất thông tin có ích hoặc các mẫu ñiền hình trong dữ liệu.
- Đánh giá mẫu (Pattern evaluation ): Đánh giá mẫu hoặc tri thức
ñã thu ñược.
- 16- Phát hiện tri thức trong tập dữ liệu lớn
- Trình diễn dữ liệu (Knowledge Presentation ): Biểu diễn những
tri thức khai phá ñược cho người sử dụng.
Như trên ñã trình bày quá trình phát hiện tri thức về nguyên lý, trải qua
các giai ñoạn khác nhau mà khai phá dữ liệu chỉ là giai ñoạn phát hiện tri
thức của quá trình KDD.
Hình 1.1: Mô tả 5 giai ñoạn trong quá trình khám phá tri thức từ cơ sở
dữ liệu. Mặc dù có 5 giai ñoạn như trên xong quá trình khám phá tri thức từ
cơ sở dữ liệu là một quá trình tương tác và lặp ñi lặp lại theo chu trình liên
tục kiểu xoáy trôn ốc, trong ñó lần lặp sau hoàn chỉnh hơn lần lặp trước.
Ngoài ra, giai ñoạn sau lại dựa trên kết quả thu ñược của giai ñoạn trước
theo kiểu thác nước. Đây là một quá trình biện chứng mang tính chất học
của lĩnh vực phát hiện tri thức và là phương pháp luận trong việc xây dựng
các hệ thống phát hiện tri thức.
à xác ñ
ịnh
vấn ñề
- 17- Phát hiện tri thức trong tập dữ liệu lớn
1.2.1. Xác ñịnh vấn ñề
Đây là một quá trình mang tính ñịnh tính với mục ñích xác ñịnh ñược
lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực
tế, các cơ sở dữ liệu ñược chuyên môn hoá và phân chia theo các lĩnh vực
khác nhau như sản phẩm, kinh doanh, tài chính, … Với mỗi tri thức phát hiện
ñược có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý
nghĩa ñối với một lĩnh vực khác. Vì vậy việc xác ñịnh lĩnh vực và ñịnh nghĩa
bài toán giúp ñịnh hướng cho giai ñoạn tiếp theo thu nhập và tiền xử lý dữ
liệu.
1.2.2. Thu thập và tiền xử lý dữ liệu
Các cơ sở dữ liệu thu ñược thường chứa rất nhiều thuộc tính nhưng lại
không ñầy ñủ, không thuần nhất, có nhiều lỗi và các giá trị ñặc biệt. Vì vậy,
giai ñoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá
trình phát hiện tri thức từ cơ sở dữ liệu. Có thể nói giai ñoạn này chiếm từ
70% ñến 80% giá thành trong toàn bộ bài toán.
Người ta chia giai ñoạn thu thập và tiền xử lý dữ liệu thành các công
ñoạn như: lựa chọn dữ liệu, làm sạch, làm giàu, mã hoá dữ liệu. Các công
ñoạn ñược thực hiện theo trình tự ñưa ra ñược một cơ sở dữ liệu thích hợp
cho các giai ñoạn sau. Tuy nhiên, tuỳ từng dữ liệu cụ thể mà quá trình trên
ñược ñiều chỉnh cho phù hợp vì người ta ñưa ra một phương pháp cho mọi
loại dữ liệu.
Phát hiện tri thức trong tập dữ liệu lớn
- Xử lý nhiễu và các ngoại lệ: Thông thường, nhiễu dữ liệu có thể là
nhiễu ngẫu nhiên hoặc các giá trị bất thường. Để làm sạch nhiễu, người ta
có thể sử dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát
hiện ra các ngoại lệ ñể xử lý.
c. Làm giàu dữ liệu:
Việc thu thập dữ liệu ñôi khi không ñảm bảo tính ñầy ñủ của dữ liệu.
Một số thông tin quan trọng có thể thiếu hoặc không ñầy ñủ. Chẳng hạn,
dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có hoặc không
ñầy ñủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng
trong quá trình khai thác dữ liệu ñể phân tích hành vi khách hàng thì rõ ràng
là ta không thể chấp nhận ñưa các dữ liệu thiếu khuyết vào ñược.
Quá trình làm giàu cũng bao gồm việc tích hợp và chuyển ñổi dữ liệu.
Các dữ liệu từ nhiều nguồn khác nhau ñược tích hợp thành một kho thống
nhất. Các khuôn dạng khác nhau của dữ liệu cũng ñược quy ñổi, tính toán
lại ñể ñưa về một kiểu thống nhất, tiện cho quá trình phân tích. Đôi khi, một
số thuộc tính mới có thể ñược xây dựng dựa trên các thuộc tính cũ.
d. Mã hoá:
Các phương pháp dùng ñể chọn lọc, làm sạch, làm giàu dữ liệu sẽ ñược
mã hoá dưới dạng các thủ tục, chương trình hay tiện ích nhằm tự ñộng hoá
việc kết xuất, biến ñổi và di chuyển dữ liệu. Các hệ thống con ñó có thể
ñược thực thi ñịnh kỳ làm tươi dữ liệu phục vụ cho việc phân tích.
- 20- Phát hiện tri thức trong tập dữ liệu lớn
Ngoài ra trong quá trình khai thác người ta có thể thực hiện các cải tiến,
nâng cấp cho phù hợp.
1.3. Sự hạn chế của các công cụ SQL
Các CSDL của các tổ chức có thể xem như những kho dữ liệu bao gồm
nhiều Gigabytes dữ liệu với các thông tin tiềm ẩn bên trong, không thể dễ
dàng tìm ñược bằng công cụ SQL hoặc các công cụ truy vấn thông thường.
Cụ thể nói, công cụ SQL và các công vụ truy vấn thông thường không ñủ ñể
thực hiện quá trình khai thác dữ liệu. Chúng chỉ là các công cụ truy vấn giúp
tìm ra các dữ liệu dưới các ràng buộc ñã biết. Trong khi ñó, các công cụ khai
thác dữ liệu có thể chia dữ liệu thành các nhóm, phát hiện các luật,… Các
giải thuật và công cụ khai thác dữ liệu có thể chỉ quan tâm tới một bộ phận
hoặc toàn bộ cơ sở dữ liệu và có thể sử dụng lặp ñi lặp lại các câu truy vấn
SQL và lưu kết qủa trung gian trong quá trình phát hiện tri thức.
Tuy nhiên, công cụ SQL cũng có những vai trò nhất ñịnh trong việc khai
thác dữ liệu và cùng với các công cụ khai thác dữ liệu chúng có những bổ
trợ lẫn nhau. Công cụ khai thác dữ liệu không thể thay thế công cụ truy vấn
nhưng làm tăng khả năng khai thác dữ liệu của người dùng. Trong những
trường hợp cụ thể, có thể xuất hiện những yêu cầu về dữ liệu mà các công
cụ SQL không thể trả lời hoặc có nhưng quá ñắt. Trong khi ñó, một thuật
toán học máy thích hợp có thể cho câu trả lời trong một thời gian ngắn hơn
- 22- Phát hiện tri thức trong tập dữ liệu lớn
nhiều. Khi kết quả trả về của các công cụ khai thác dữ liệu là các phân loại
dữ liệu, công cụ truy vấn lúc ñó sẽ ñược sử dụng ñể hỏi và phân tích dữ liệu.
Có thể nói một cách tổng quát: khi muốn biết những gì một cách
chính xác thì hãy sử dụng SQL, khi muốn biết những gì một cách
mờ và ẩn thì hãy tìm ñến các công cụ khai thác dữ liệu. Người ta
1.4.2. Nhiệm vụ KPDL là gì?
Các bài toán liên quan ñến KPDL về bản chất là các bài toán thống kê.
Điểm khác biệt giữa các kỹ thuật KPDL và các công cụ phục vụ tính toán
thống kê mà chúng ta ñã biết là ở khối lượng cần tính toán. Một khi dữ liệu
trở nên lớn thì những khâu như: thu thập dữ liệu, tiền xử lý và xử lý dữ liệu
ñều ñòi hỏi phải ñược tự ñộng hóa. Tuy nhiên, ở công ñoạn cuối cùng, việc
phân tích kết quả sau khi ñã KPDL vẫn luôn là công việc của con người.
Do là một lĩnh vực ña ngành, KPDL thu hút các lĩnh vực khoa học khác
như: trí tuệ nhân tạo, học máy, cơ sở dữ liệu, hiển thị dữ liệu, marketing,
toán học, vận trù học, tin sinh học, nhận dạng mẫu, tính toán thống kê.v.v
Điều mà KPDL có thể làm rất tốt là phát hiện ra những giả thuyết mạnh
trước khi sử dụng các công cụ tính toán thống kê. Mô hình dự báo sử dụng
kỹ thuật phân cụm (clustering) ñể chia nhóm các sự vật, sự kiện, sau ñó rút
ra các luật nhằm tìm ra ñặc trưng cho mỗi nhóm và cuối cùng ñề nghị một
mô hình. Ví dụ, những bạn ñọc ñăng ký dài hạn của một tạp chí có thể ñược
phân nhóm dựa theo nhiều tiêu chí khác nhau (lứa tuổi, giới tính, thu
- 24- Phát hiện tri thức trong tập dữ liệu lớn
nhập ), sau ñó tạp chí căn cứ vào ñặc trưng riêng của từng nhóm ñể ñề ra
mức phí phi thu trong năm sao cho phù hợp nhất.
Chúng ta thấy, những nhiệm vụ cơ bản nhất của KPDL là:
• Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời câu
hỏi: một dữ liệu mới thu thập ñược sẽ thuộc về nhóm nào? Quá trình
này thường ñược thực hiện một cách tự ñộng.
• Khai phá luật kết hợp. Nhiệm vụ là phát hiện những mối quan hệ
giống nhau về cấu trúc của các bản ghi giao dịch. Luật kết hợp X=>Y
có dạng tổng quát là: nếu một giao dịch ñã sở hữu các tính chất X, thì
bao gồm cả ñặc trưng hoá, phân biệt, tìm luật kết hợp, phân lớp hay
phân cụm dữ liệu liên quan ñến thời gian, phân tích dữ liệu theo
chuỗi thời gian, sánh mẫu theo chu kì và phân tích dữ liệu dựa trên
tính tương tự.
1.4.3. Triển khai việc KPDL như thế nào?
Nhóm các tác giả Cabena et al. ñề nghị triển khai quá trình KPDL theo 5
bước:
Bước 1: Xác ñịnh rõ ràng mục tiêu thương mại cần khai phá.
Bước 2: Chuẩn bị dữ liệu (thu thập, tiền xử lý, chuyển ñổi khuôn dạng
dữ liệu, nếu thấy cần thiết).
Bước 3: Khai phá dữ liệu (chọn thuật toán thích hợp).
Bước 4: Phân tích kết quả thu ñược (xem có gì mới và thú vị không?).
Bước 5: Vận dụng các tri thức thu lượm ñược trong việc hoạch ñịnh
sản xuất kinh doanh.
Copyright: Tài liệu đại học ©