Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Mục Lục
Mục Lục 1
Lời Cảm Ơn 2
Lời Mở Đầu 3
I. Tổng Quan Về Khai Phá Dữ Liệu 4
1. Khái niệm Khai Phá Dữ Liệu 4
2. Chức năng của Khai Phá Dữ Liệu 4
3. Ứng Dụng Khai Phá Dữ Liệu 5
4. Các bước trong Khai Phá Dữ Liệu 6
II. Cơ sở toán học trong Khai Phá Dữ Liệu 8
1. Các tập hợp khai thác dữ liệu 8
2. Các kết nối Galois 8
3. Tập hợp mặt hàng phổ biến 8
4. Luật kết hợp 8
III. Tiếp cận các luật kết hợp và thuật toán để Khai Phá Dữ Liệu 9
1. Định nghĩa luật kết hợp 9
2. Ý nghĩa luật kết hợp 10
3. Thuật toán Apriori 10
IV. Hệ quản trị cơ sở dữ liệu hỗ trợ data mining 13
1. Tổng quan hệ quản trị cơ sở dữ liệu Microsoft SQL Server 2008 R2 13
2. Kiến trúc Analysis Services trong hệ quản trị cơ sở dữ liệu Microsoft SQL
Server 2008 R2 14
3. Ứng dụng Analysis Services trong hệ quản trị cơ sở dữ liệu Microsoft SQL
Server 2008 R2 19
V. Tổng Quan Chương Trình Tìm tập phổ biến và luật kết hợp demo 38
1. Cấu trúc lập trình chương trình 38
2. Demo chương trình 43
VI. Một số ứng dụng Demo khác được phát triển để minh họa các kỹ thuật Data
Mining 50
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Lời Mở Đầu
Ngay khi nói đến máy tính và hệ thống thông tin, chúng ta không thể không biết
và không quan tâm đến trung tâm của hệ thống là cơ sở dữ liệu. Mọi vấn đề lưu
trữ, truy xuất, hổ trợ ra quyết định đều thao tác trên hàng tỉ giao dịch trên thế giới
mỗi giây. Tuy nhiên, việc tận dụng những tập dữ liệu khổng lồ đó để lấy thông tin
là vấn đề bức thiết và đem lại nhiều lợi ích.
Khai thác dữ liệu (Data Mining) là phương pháp khám phá tri thức tiềm ẩn trong
các cơ sở dữ liệu. Đó là tiến trình trích lọc, sản sinh ra những loại tri thức hoặc các
mẫu tiềm ẩn, chưa biết nhưng đem lại hữu ích từ khối dữ liệu tưởng chừng không
có quy luật đó.
Để khai thác hiệu quả nguồn thông tin từ các cơ sở dữ liệu, nhiều hệ cơ sở dữ liệu
cũng đã hỗ trợ tiến trình ra quyết định một cách truyền thống, một số kỹ thuật và
phương pháp chuyên biệt tổng hợp thông tin cũng ra đời.
Cụ thể hơn về khai phá dữ liệu, giả sử một công ty bán lẻ có hàng triệu giao dịch
mỗi tháng, chúng ta có thể tìm ra một số quy luật kết hợp giữa các sản phẩm và xu
hướng thị trường, từ đó chúng ta có thể đưa ra những chương trình, chiến lược
nhập hàng và bố trí mặt hàng phù hợp theo nhu cầu và đem lại doanh nghiệp lợi
nhuận cao nhất.
Ngoài việc tìm hiểu lý thuyết, e có viết chương trình demo tìm tập phổ biến, tập
phổ biến tối đại và tìm tập luật sinh theo thuật giải Apriori.
Ngoài ra, để tìm hiểu sâu thêm về các lĩnh vực khác của Data Mining, em có viết
chương trình và demo về phân lớp bằng Bayes (Bayes Classifcation), Gom cụm
bằng KMean (KMean Cluster), và sinh ma trận phân biệt cho Tập Thô (Rough
Set)
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 3/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
I. Tổng Quan Về Khai Phá Dữ Liệu
dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ
liệu đó.
2. Chức năng của Khai Phá Dữ Liệu
Data Mining được chia nhỏ thành một số hướng chính như sau:
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 4/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
• Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm
tắt khái niệm.
Ví dụ: tóm tắt văn bản.
• Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá
đơn giản.
Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ
sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực
kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v.
• Phân lớp và dự đoán (classification & prediction): xếp một đối tượng
vào một trong những lớp đã biết trước.
Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này
thường sử dụng một số kỹ thuật của machine learning như cây quyết định
(decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Người ta còn
gọi phân lớp là học có giám sát (học có thầy).
• Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng cũng
như tên của cụm chưa được biết trước. Người ta còn gọi phân cụm là học
không giám sát (học không thầy).
• Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá
luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận
này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng
khoán vì nó có tính dự báo cao.
3. Ứng Dụng Khai Phá Dữ Liệu
Data Mining tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều
dụng web hoặc từ data center của các web service.
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 6/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
2. Trích lọc dữ liệu (Selection)
Dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn. Ví dụ
chọn nhân viên có tuổi từ 23-30 và tốt nghiệp đại học.
3. Làm sạch, tiền xử lý và chuẩn bị dữ liệu (Cleansing, Pre-processing and
Preparation)
Đây là bước rất quan trọng trong quá trình khai phá dữ liệu. Ở đây có
một số lỗi thường mắc phải là tính phi logic dữ liệu như chứa các giá trị
vô nghĩa và gây nên lỗi dữ liệu. Đây là giai đoạn tiến hành xử lý những
dữ liệu không chặt chẽ, phi logic và loại bỏ những dữ liệu dư thừa
không có giá trị.
Ví dụ: trong việc xác định từ có nghĩa và hữu ích trong nhận dạng văn
bản tiếng Anh, nên loại bỏ a, the, for, which, vì bản chất nó dư thừa
không mang lại thông tin có giá trị.
4. Chuyển đổi dữ liệu (Transformation)
Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý
bằng việc sử dụng và điều khiển bởi việc tổ chức lại giúp chuyển đổi
phù hợp mục đích khai thác.
5. Phát hiện và trích mẫu dữ liệu (Data mining)
Là một trong các bước quan trọng nhất, trong đó sử dụng những phương
pháp thông minh để chắt lọc ra những mẫu dữ liệu.
6. Phát hiện và trích mẫu dữ liệu (Post-Processing hoặc Pattern Extraction
and Discovery)
Đây là bước mang tính tư duy trong khai phá dữ liệu. Giai đoạn sử dụng
nhiều thuật toán khác nhau để trích ra các mẫu dữ liệu thường xử dụng
là theo nguyên tắc phân loai, nguyên tắc kết hợp và các mô hình dữ liệu
tuần tự.
tập phổ biến.
Ký hiệu FS(O,I,R,minsupp) = { S ∈ P(I) | SP(S) ≥ minsupp }
4. Luật kết hợp
a. Định nghĩa:
Cho NCKTDL (O,I,R) và ngưỡng minsupp ∈(0,1]. Với một S∈ S(O,I,R,minsupp),
gọi X và Y là các tập con khác rỗng của S sao cho S = X∪Y và X ∩Y=∅. Luật
kết hợp X với Y có dạng X→Y phản ánh khả năng khách hàng mua tập mặt hàng
Y khi mua tập mặt hàng X. Độ phổ biến của luật kết hợp X→Y với S= X∪Y là
SP(S). Độ tin cậy của luật kết hợp X→Y được ký hiệu là CF(X→Y) và được tính
bằng công thức CF(X→Y)=SP(X∪Y)/SP(X)
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 8/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Nguyên lý Apriori:
• Cho S ∈ FS(O,I,R,minsupp), nếu T ⊆ S thì T ∈ FS(O,I,R,minsupp)
• Cho T ∉ FS(O,I,R,minsupp), nếu T ⊆ S thì S ∉ FS(O,I,R,minsupp)
b. Tìm tập phổ biến
Cho NCKTDL (O,I,R) và minsupp∈(0,1], tìm FS(O,I,R,minsupp). Thuật toán
được xây dựng dựa trên nguyên lý Apriori. Đầu tiên thuật toán sẽ tìm các tập phổ
biến có một phần tử. Sau đó các ứng viên của các tập phổ biến có hai phần tử sẽ
được tạo lập bằng cách hợp các tập phổ biến có một phần tử. Một cách tổng quát,
các tập ứng viên của tập phổ biến có k phần tử sẽ được tạo từ các tập phổ biến có
k-1 phần tử. Gọi Fk ={S∈ P(I) | SP(S) ≥ minsupp và |S|= k }. Thuật toán sẽ duyệt
từng ứng viên để tạo Fk bao gồm các ứng viên có độ phổ biến lớn hơn hoặc bằng
ngưỡng minsupp.
c. Tìm tập phổ biến tối đại
Trong tất cả các tậ p phổ biến một số tập thuộc tính thoả mãn tính chất không có
tập cha nào của chúng phổ biến, thì đó là các tập phổ biến tối đại – maximal
frequent itemset.
Do vậy bài toán tìm các tập phổ biến có thể chuyển sang bài toán tìm tập phổ biến
hai mặt hàng bánh mì và sữa, trong số các bản ghi chứa “bánh mì” có 45% bản ghi
chứa “sữa”.
Tuy nhiên không phải luật kết hợp giữa mặt hàng nào cũng có ý nghĩa, chúng ta
chỉ quan tâm tới những luật có một cơ sở nào đó hay còn gọi là ngưỡng. Một trong
các ngưỡng thường dùng đó là giới hạn cơ sở, min_sup. Ví dụ: chúng ta chỉ quan
tâm tới những luật kết hợp có độ hỗ trợ lớn hơn min_sup, như vậy luật kết hợp tìm
được sẽ có giá trị cao hơn.
2. Ý nghĩa luật kết hợp
Một ứng dụng quan trọng của luật kết hợp là từ mớ dữ liệu hỗn độn tưởng chừng
không theo một nguyên tắc gì cả và thực chất có thể phân tích. Đó là việc phân
tích thói quen mua hàng của khách để tìm sự kết hợp giữa các mặt hàng khác nhau
trong một lần mua hàng của họ.
Ví dụ: Quay lại ví dụ trên, trong 1 lần mua hàng tại siêu thị nếu khách hàng mua
bánh mì, thường thì họ sẽ mua sữa. Thông tin như thế có thể chỉ dẫn người bán lựa
chọn mặt hàng và vị trí của chúng trên giá hàng. Do đó người bán có thể đặt sữa
và bánh mì trong phạm vi gần kề để gây tác động tích cực tới việc mua của khách
cho cả hai mặt hàng này. Việc nhận ra các mặt hàng thường được mua cùng nhau
giúp người bán hàng có thể bán được nhiều hàng hơn do đó tăng doanh thu.
Khai thác luật kết hợp nhằm tìm ra những mối liên kết đáng quan tâm hoặc những
quan hệ tương quan trong một tập lớn các đối tượng. Trong giao dịch thương mại
khám phá mối quan hệ trong số lượng lớn các bản ghi giao dịch có thể giúp nhiều
nhà kinh doanh xử lí giải quyết các vấn đề.
3. Thuật toán Apriori
Vấn đề đặt ra là làm thế nào để tìm ra được các luật liên kết giữa khối lượng
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 10/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
khổng lồ của DL? DL thể hiện mối liên hệ đó ở đâu? luật kết hợp nào đáng quan
tâm nhất? Tìm ra luật kết hợp đáng quan tâm như thế nào?
1. Chức năng
biến, nhưng tất cả tập phổ biến k phần tử đều được chứa trong Ck. Qúa trình duyệt
và đếm các phần tử của Ck sẽ loại bỏ các phần tử không thoả mãn giới hạn cơ sở
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 11/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
và cho kết quả là tập Lk. Việc giảm kích thước của Ck được tiến hành như sau:
- Tất cả các tập (k-1) phần tử không phổ biến không là tập con của tập phổ biến k
phần tử.
- Nếu tập (k-1) phần tử nào của tập ứng viên k phần tử không thuộc Lk-1 thì ứng
viên đó không là tập phổ biến và loại bỏ khỏi Ck.
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 12/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
IV. Hệ quản trị cơ sở dữ liệu hỗ trợ data mining
1. Tổng quan hệ quản trị cơ sở dữ liệu Microsoft SQL Server 2008 R2
SQL Server 2008 R2 của hãng Microsoft là hệ quản trị cơ sở dữ liệu mạnh và nổi
tiếng, nhờ gắn kết với hệ thống lớn mạnh mẽ như Domain, Sharepoint, và những
sản phẩm gì Microsoft triển khai. Một trong số chức năng chính của SQL Server
2008 R2 như sau:
1.1. SQL Manager Studio
Quản lý CSDL là cách cho phép quản lý dự án một cách tốt nhất từ việc tạo đến
bảo trì database.
Một số công cụ là SQL Analysis, SQL Integrate, SQL Report.
1.2 SQL Integrate
Công cụ cho phép người quản trị tích hợp data từ nhiều nguồn khác nhau như Text
(có cấu trúc), xml, Excel, Access, SQL, Oracle
Cơ chế này cho phép chuyển đổi hầu hết các dữ liệu có cấu trúc vào CSDL SQL
2008. Với khả năng linh hoạt cho phép ta chọn những dữ liệu cần thiết, ngoài ra
còn cơ chế báo lỗi dữ liệu không hợp lệ người dùng.
Ngoài ra còn hổ trợ khả năng tích hợp một cách linh hoạt, có thề sữ dụng các câu
1.4. SQL Reporting
Giúp ích cho việc đưa ra các báo cáo dưới dạng văn bản hoặc trình duyệt giúp cho
quản lý lãnh đạo có thể xem xét đưa ra quyết định.
Báo cáo có thể đưa ra nhiều dạng khác nhau: HTML, Web, Doc, Excel, pdf,
Image
Report trong SQL đưa ra các báo cáo từ dữ liệu có trực tiếp trong CSDL, ngoài ra
bao gồm các dữ liệu khác như dữ liệu từ việc phân tích các khối, từ phân tích data
mining.
Ngoài ra report còn hổ trợ nhiều định dạng theo ý muốn như dữ liệu dạng số, ngày
và đặc biệt rất nhiều dạng biểu đồ trực quan
2. Kiến trúc Analysis Services trong hệ quản trị cơ sở dữ liệu Microsoft
SQL Server 2008 R2
Sau đây, chúng ta tìm hiểu công cụ SQL 2008: SQL Server Analysis Services
(SSAS) mà hổ trợ Data Mining
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 14/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Kiến trúc của DDAS
Kiến trúc luận lý (Logical Architecture)
• Mining Structures
Mining Structure là một cấu trúc dữ liệu hợp lý xác định lĩnh vực dữ liệu mà từ
đó xây dựng mô hình khai thác. Một Mining Structure đơn có thể hỗ trợ nhiều
mô hình khai thác mà chia sẻ cùng một tên miền. Data mining structure cũng
có thể được phân chia thành một tập huấn luyện và thử nghiệm, bằng cách xác
định một tỷ lệ phần trăm hoặc số lượng dữ liệu như một người hết.
• Mining Models
Mining model thể hiện sự tổ hợp các dữ liệu, giải thuật data mining, và tập hợp
các thông số các cấu hình filter mà quyết định data nào sử dụng và xử lý data
đó như thế nào. Trong SQL server, sử dụng ngôn ngữ Data Mining Extensions
(DMX)
Working with Other SQL Server Features
Solution Design Considerations
Sau đây chúng ta tìm cụ thể vào SSAS
Cài đặt Analysis Services cho SQL Server 2008 R2
- Chọn Analysis Services để install dịch vụ Analysis Services.
- Chọn Business Intelligence Development Studio
- Ngoài ra có thể chọn thêm Client Tools Connectivity và Management Tools
Basic và Completed để hỗ trợ các tool và library
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 16/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
- Khi cài SQL Server Analysis Services cần chú ý gán vào một instant
database nào đó với username và password.
- Sau khi cài thành công, vào Sql Server Configuration Manager và start dịch
vụ SQL Service Analysis Services:
Kết nối Analysis Services cho SQL Server 2008 R2
- Sau khi cài đặt thành công Analysis Services, vào Microsoft SQL Server
Management Studio và kế nối đến Server Type là Analysis Services và
Server Name là máy và Instance đã cài đặt
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 17/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
- Giao diện sau khi kết nối thành công:
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 18/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
3. Ứng dụng Analysis Services trong hệ quản trị cơ sở dữ liệu Microsoft
SQL Server 2008 R2
Sau đây, chúng ta tìm hiểu ứng dụng cho SQL Server Analysis Services (SSAS)
mà hổ trợ Data Mining qua ví dụ cụ thể trên một database mẫu.
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Nhấn chuột phải vào thư mục Data Source Views và chọn New Data
Source View Tiếp tục Wizard để add vào:
Chọn 1 số table mẫu có các mối quan hệ với nhau
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 23/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 24/66
Bài Thu Hoạch Chuyên Đề - Khai Phá Dữ Liệu, Luật Kết Hợp Và Ứng Dụng Về Khai
Phá Dữ Liệu Trong Hệ Quản Trị Cơ Sở Dữ Liệu
Sau khi import thành công, ta có thể xem lại diagram của các bảng quan hệ
như sau:
SV: Nguyễn Võ Ngọc Huy (CH1101091) Trang 25/66
Copyright: Tài liệu đại học ©