Tiểu luận môn cơ sở toán

ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
TIỂU LUẬN MÔN HỌC
TIỂU LUẬN MÔN HỌC
CƠ SỞ TOÁN
CƠ SỞ TOÁN
Đề tài
Đề tài
:
:
TÌM HIỂU LUẬT KẾT HỢP
TRONG KHAI PHÁ DỮ LIỆU
HỌC VIÊN THỰC HIỆN: 1. Võ Thanh Minh
2. Nguyễn Quang
3. Hồ Văn Lâm
4. Phạm Vinh
5. Trần Thị Quế Vy
LỚP: CAO HỌC KHOA HỌC MÁY TÍNH
KHOÁ HỌC: 2009 – 2011
Huế, tháng 01 – 2010
Nhóm 2 1
Tiểu luận môn cơ sở toán
Nhóm 2 2
Tiểu luận môn cơ sở toán
MỤC LỤC
Nội dung Trang
.........................................................................................................................................................3
PHẦN MỞ ĐẦU.............................................................................................................................4
NỘI DUNG......................................................................................................................................5

2. Phân tích chương trình......................................................................................................27
KẾT LUẬN....................................................................................................................................29
TÀI LIỆU THAM KHẢO:............................................................................................................30

Nhóm 2 3
Tiểu luận môn cơ sở toán
PHẦN 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ữ

như: thống kê, học máy, CSDL, thuật toán, trực quan hoá dữ liệu, tính toán song
song và hiệu năng cao,…
Mục đích của quá trình khám phá tri thức là rút ra tri thức từ dữ liệu trong
CSDL lớn. Quá trình KDD là quá trình gồm nhiều giai đoạn và lặp lại, mà trong
đó sự lặp lại có thể xuất hiện ở bất cứ bước nào.
Quá trình đó có thể được mô tả theo hình sau:
Nhóm 2 5
Tiểu luận môn cơ sở toán
Bước thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu
lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải
hoàn thành. Bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và
cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng
dụng và bản chất của dữ liệu.
Bước thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn
được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc
thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết,
bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri
thức. Do dữ liệu được lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể
gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn
và rời rạc hoá.
Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là khai phá dữ liệu, hay
nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu. Giai
đoạn này rất quan trọng, bao gồm các công đoạn như: chức năng, nhiệm vụ và
mục đích của khai phá dữ liệu, dùng phương pháp khai phá nào? Thông thường,
các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đưa ra
tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện
các suy diễn dựa trên dữ liệu hiện có. Tùy theo bài toán xác định được mà ta lựa
chọn các phương pháp khai phá dữ liệu cho phù hợp.
Bước thứ tư: Sử dụng các tri thức phát hiện được. Là hiểu tri thức đã tìm
được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi

chính.
Phân tích chuỗi theo thời gian: 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.
Phân cụm: xếp các đối tượng theo từng cụm dữ liệu tự nhiên.
Mô tả khái niệm: 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.
3.2. Dạng dữ liệu có thể khai phá
Do Data Mining được ứng dụng rộng rãi nên nó có thể làm việc với rất
nhiều kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: CSDL
quan hệ, CSDL đa chiều (multidimentional structures, data warehouses), 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...
3.3. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực được quan tâm và ứng dụng rộng rãi. Một
số ứng dụng điển hình trong khai phá dữ liệu có thể liệt kê: 1) phân tích dữ liệu
và hỗ trợ ra quyết định; 2) điều trị y học; 3) phát hiện văn bản; 4) tin sinh học; 5)
tài chính và thị trường chứng khoán; 6) bảo hiểm...
3.4. 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. Ý nghĩa của các luật kết hợp khá dễ nhận thấy: Cho trước
một cơ sở dữ liệu có D là tập các giao tác - trong đó mỗi giao tác T∈D là tập các
item - khi đó X ⇒ Y diễn đạt ý nghĩa rằng bất cứ khi nào giao tác T có chứa X
thì chắc chắn T có chứa Y. Độ tin cậy của luật (rule confidence) có thể được
hiểu như xác suất điều kiện p(Y⊆T  X⊆T). Ý tưởng của việc khai thác các luật
kết hợp có nguồn gốc từ việc phân tích dữ liệu mua hàng của khách và nhận ra
rằng “Một khách hàng mua mặt hàng X
1
và X
2

Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong
đó sự xuất hiện của tập các mục S nào đó trong các bản ghi của D sẽ kéo theo sự
xuất hiện của một tập những mục U cũng trong những bản ghi đó. Mỗi luật kết
hợp được đặc trưng bởi một cặp tỉ lệ. Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ
% những bản ghi trong D chứa cả S và U.
Vấn đề khám phá luật kết hợp được phát biểu như sau: 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.
Giả thiết D là CSDL giao dịch và với θ = 40%, β = 90%. Vấn đề phát hiện
luật kết hợp được thực hiện như sau:
Liệt kê, đếm tất cả những qui luật chỉ ra sự xuất hiện một số các mục sẽ
kéo theo một số mục khác.
Nhóm 2 8
Tiểu luận môn cơ sở toán
Chỉ xét những qui luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn
90%.
Hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách
hàng được yêu cầu điền vào các mẫu bán hàng để công ty có được một CSDL về
các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ "tuổi,
giới tính, nghề nghiệp và sản phẩm". Khi đó có thể có rất nhiều câu hỏi tương
ứng với luật trên. Ví dụ trong lứa tuổi nào thì những khách hàng nữ là công nhân
đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất, thoả mãn một
ngưỡng nào đó ?
2. Lý thuyết về luật kết hợp
2.1. Khái niệm
Cho một tập I = {I
1
, I
2
, ..., I

không có độ hỗ trợ tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa
mãn support(X) ≥ minsup.
→Một khoản mục X được gọi là k-itemset nếu lực lượng của X bằng k, tức
là |X|=k.
Một luật kết hợp có dạng R: X => Y, trong đó X, Y là tập các mục, X, Y ⊆
I và X ∩Y = ∅. X được gọi là tiên đề và Y được gọi là hệ quả của luật.
Nhóm 2 9
Tiểu luận môn cơ sở toán
Luật X => Y tồn tại một độ tin cậy c . Độ tin cậy c được định nghĩa là khả
năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Ta có công thức tính độ tin cậy c
như sau:
)sup(
)sup(
)(
)(
|()(
X
YX
TXp
TXTYp
IXIYpYXconf
∪
=
⊆
⊆∧⊆
=⊆⊆=⇒
(2.2)
Tuy nhiên, không phải bất cứ luật kết hợp nào có mặt trong tập các luật có
thể được sinh ra cũng đều có ý nghĩa trên thực tế. Mà các luật đều phải thoả mãn
một ngưỡng hỗ trợ và tin cậy cụ thể. Thực vậy, cho một tập các giao dịch D, bài

Nếu mục B là mục phổ biến trên D, nghĩa là support(B) ≥ minsup thì mọi
tập con A của B là tập phổ biến trên D vì support(A) ≥ support(B) > minsup.
2.2.2. Luật kết hợp:
Nhóm 2 10
Tiểu luận môn cơ sở toán
Tính chất 1:( Không hợp các luật kết hợp)
Nếu có X→Z và Y→Z trong D thì không nhất thiết X∪Y→Z là đúng
Xét trường hợp X ∩Z =∅ và các tác vụ trong D hỗ trợ Z nếu và chỉ nếu
chúng hỗ trợ mỗi X hoặc Y, khi đó luật X∪Y→Z có độ hỗ trợ 0%.
Tương tự : X→Y ∧ X→Z ⇒ X→Y∪Z
Tính chất 2:(Không tách luật)
Nếu X∪Y→Z thì X→Z và Y→Z chưa chắc xảy ra
Ví dụ trường hợp Z có mặt trong một giao tác chỉ khi cả hai X và Y cũng
có mặt, tức là sup(X∪Y)= sup(Z), nếu độ hỗ trợ của X và Y đủ lớn hơn
sup(X∪Y), tức là sup(X) > sup(X∪Y) và sup(Y) > sup(X∪Y) thì hai luật riêng
biệt sẽ không đủ độ tin cậy
Tuy nhiên đảo lại: X→Y∪Z ⇒ X→Y ∧ X→Z
Tính chất 3: (Các luật kết hợp không có tính bắc cầu)
Nếu X→Y và Y→Z, chúng ta không thể suy ra X→Z.
Ví dụ: giả sử T(X) ⊂ T(Y) ⊂ T(Z), ở đó T(X), T(Y), T(Z) tương ứng là các
giao dịch chứa X,Y,Z, và độ tin cậy cực tiểu minconf
conf(X→Y) =conf(Y→Z)=minconf thế thì: conf(X→Y) =minconf2 <
minconf vì minconf < 1, do đó luật X→Z không đủ độ tin cậy
Tính chất 4:
Nếu A→(L - A) không thoả mãn độ tin cậy cực tiểu thì luật
B →(L -B) cũng không thoả mãn, với các tập mục L,A,B và B ⊆ A ⊂ L
Vì supp(B) ≥ sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta
nhận được:
conf
B

2.3. Một số hướng tiếp cận trong khai phá luật kết hợp
Lĩnh vực khai thác luật kết hợp cho đến nay đã được nghiên cứu và phát
triển theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến tốc độ thuật
Nhóm 2 11
Tiểu luận môn cơ sở toán
toán, có những đề xuất nhằm tìm kiếm luật có ý nghĩa hơn… và có một số
hướng chính như sau:
Luật kết hợp nhị phân là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu
hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp
nhị phân. Trong dạng luật kết hợp này, các mục, thuộc tính, chỉ được quan tâm
là có hay không xuất hiện trong giao tác của CSDL chứ không quan tâm về
“mức độ” xuất hiện. Ví dụ: Trong hệ thống tính cước điện thoại thì việc gọi 10
cuộc điện thoại và một cuộc được xem là giống nhau. Thuật toán tiêu biểu nhất
khai phá dạng luật này là thuật toán Apriori và các biến thể của nó. Đây là dạng
luật đơn giản và các luật khác cũng có thể chuyển về dạng luật này nhờ một số
phương pháp như rời rạc hoá, mờ hoá, … Một ví dụ về dạng luật này: “gọi liên
tỉnh= ‘yes’ AND gọi di động= ‘yes’ => gọi quốc tế= ‘yes’ AND gọi dịch vụ 108
= ‘yes’, với độ hỗ trợ 20% và độ tin cậy 80%”
Luật kết hợp có thuộc tính số và thuộc tính hạng mục: Các thuộc tính của
các CSDL thực tế có kiểu rất đa dạng, như số nhị phân, giá trị định tính, định
lượng... Để phát hiện luật kết hợp với các thuộc tính này, các nhà nghiên cứu đã
đề xuất một số phương pháp rời rạc hoá nhằm chuyển dạng luật này về dạng nhị
phân để có thể áp dụng các thuật toán đã có. Một ví dụ về dạng luật này
“phương thức gọi = ‘Tự động’ AND giờ gọi IN [‘23:00:39.. 23:00:59’] AND
Thời gian đàm thoại IN [‘200.. 300’] => gọi liên tỉnh = ‘có’ , với độ hỗ trợ là 23.
53% , và độ tin cậy là 80%”.
Luật kết hợp tiếp cận theo hướng tập thô: Tìm kiếm luật kết hợp dựa trên lý
thuyết tập thô.
Luật kết hợp nhiều mức: Cách tiếp cận theo luật này sẽ tìm kiếm thêm
những luật có dạng “mua máy tính PC => mua hệ điều hành AND mua phần