Khai Phá Dữ Liệu
Nguyễn Nhật Quang
quangnn-fit@mail.hut.edu.vn
Viện Công nghệ Thông tin và Truyền thông
Trường Đại học Bách Khoa Hà Nội
Năm học 2010-2011
Nội dung môn học:
Giới thiệu về Khai phá dữ liệu
ề
Giới thiệu v
ề
công cụ WEK
A
Tiền xử lý dữ liệu
Phát hiện các luật kết hợp
Các kỹthuật phân lớpvàdự đoán
Các
kỹ
thuật
phân
lớp
và
dự
đoán
Các kỹ thuật phân nhóm
2
Khai Phá Dữ Liệu
Phát hiện các luật kết hợp – Giới thiệu
Bài toán phát hiện luật kết hợp (Association rule mining)
Với m
ộ
t t
ập
các
g
iao d
ị
ch
(
transactions
)
cho trước
,
cần tìm các
ộ ậpgị(),
luật dự đoán khả năng xuất hiện trong một giao dịch của các mục
(items) này dựa trên việc xuất hiện của các mục khác
TID Items
1 Bread, Milk
Các ví dụ của luật kết hợp:
{Diaper}
→
{Beer}
2 Bread, Diaper, Beer, Eggs
3 Milk, Diaper, Beer, Coke
4
Diaper
,
Beer
{Diaper}
→
{Beer}
{Milk, Bread} →{Eggs, Coke}
{Beer, Bread} →{Milk}
4
Diaper
,
Beer
5 Bread, Milk, Diaper, Coke
3
Khai Phá Dữ Liệu
Các định nghĩa cơbản (1)
Tập mục (Itemset)
Một tập hợp gồm một hoặc nhiều mục
Ví dụ: {Milk, Bread, Diaper}
Tập mục mức k(k-itemset)
Một tập mục gồm kmục
ổ ố ỗ (S )
TID Items
1 Bread, Milk
2
Bread Diaper Beer Eggs
T
ổ
ng s
ố
h
ỗ
trợ
(S
upport count
)
σ
Số lần xuất hiện của một tập mục
Ví dụ: σ({Milk, Bread, Diaper}) = 2
2
Bread
,
Diaper
,
Beer
,
Eggs
3
Milk, Diaper, Beer, Coke
4
Bread, Milk, Diaper, Beer
5
Bread Milk Diaper Coke
Đ
ộ hỗ trợ (Support) s
Tỷ lệ các giao dịch chứa một tập mục
Ví dụ: s({Milk, Bread, Diaper}) = 2/5
5
Bread
,
Milk
,
Diaper
,
Coke
Tập mục thường xuyên
(Frequent/large itemset)
Một tập mục mà độ hỗ trợ lớn hơn
hoặc bằng một giá trị ngưỡng minsup
4
Khai Phá Dữ Liệu
Các định nghĩa cơbản (2)
Luật kết hợp (Association
rule)
ể
TID Items
1 Bread, Milk
Một bi
ể
u thức kéo theo có
dạng: X →Y, trong đó X và Y
là các tập mục
Ví dụ: {Milk Diaper}
→
{Beer}
2
Bread, Diaper, Beer, Eggs
3
Milk, Diaper, Beer, Coke
4
Bread, Milk, Diaper, Beer
Ví
dụ:
{Milk
,
Diaper}
→
{Beer}
Các độ đo đánh giá luật
Độ
hỗ tr
ợ
(
Su
pp
ort
)
s
Beer
}
Diaper
Milk
{
→
5
Bread, Milk, Diaper, Coke
ộ ợ (pp)
Tỷ lệ các giao dịch chứa cả
X và Y đối với tất cả các
giao dịch
Beer
}
Diaper
,
Milk
{
→
4.0
5
2
|
T
|
)Bee
r
Diaper,,Milk( ===
σ
s
Đ
ộ tin cậy (Confidence) c
Tỷ lệ các giao dịch chứa cả
X và Y đối với các giao dịch
chứaX
5
|
T
|
67.0
3
2
)Diaper,Milk(
)BeerDiaper,Milk,( ===
σ
σ
c
chứa
X
5
Khai Phá Dữ Liệu