Chương 5-P2:
Khai phá dữ liệu trong kinh doanh
Data Warehouse and Business Intelligence
1
Nội dung
1.
2.
3.
4.
5.
6.
Giới thiệu chung về khai phá dữ liệu
Khai phá luật kết hợp và ứng dụng
Phân lớp dữ liệu và ứng dụng
Phân cụm dữ liệu và ứng dụng
Khai phá dữ liệu chuỗi thời gian
Một số ứng dụng khác
Data Warehouse and Business Intelligence
2
1. Giới thiệu chung về khai phá dữ liệu
1.1 Khái niệm về khai phá dữ liệu
1.2 Quá trình khám phá tri thức
1.3 Khai phá dữ liệu trong kinh doanh thông minh
1.4 Quá trình khám phá tri thức
1.5 Các lĩnh vực có ảnh hưởng đến khai phá dữ liệu
Data Warehouse and Business Intelligence
3
1
1.1. Khái niệm về khai phá dữ liệu
Khai phá dữ liệu
một quá trình trích xuất tri thức từ lượng lớn dữ liệu
• “extracting or mining knowledge from large amounts of data”
• “knowledge mining from data”
một quá trình không dễ trích xuất thông tin ẩn, hữu ích, chưa được biết
trước từ dữ liệu
• “the nontrivial extraction of implicit, previously unknown, and
potentially useful information from data”
Các thuật ngữ thường được dùng tương đương: knowledge
discovery/mining in data/databases (KDD), knowledge
extraction, data/pattern analysis, data archeology, data
dredging, information harvesting, business intelligence
Học có giám sát và không có giám sát
Data Warehouse and Business Intelligence
4
1.2. Quá trình khám phá tri thức
Pattern Evaluation/
Presentation
Data Mining
Patterns
Task-relevant Data
Selection/Transformation
Data Warehouse
Data
Cleaning
Data Integration
Data Sources
Data Warehouse and Business Intelligence
5
1.3 Khai phá dữ liệu trong kinh doanh thông minh
Increasing potential
to support
business decisions
End User
Decision
Making
Data Presentation
Visualization Techniques
Business
Analyst
Data Mining
Information Discovery
Data
Analyst
Data Exploration
Statistical Summary, Querying, and Reporting
Data Preprocessing/Integration, Data Warehouses
Data Sources
Paper, Files, Web documents, Scientific experiments, Database Systems
Data Warehouse and Business Intelligence
DBA
6
2
1.4 Quá trình khám phá tri thức
Input Data
Data PreProcessing
Data integration
Normalization
Feature selection
Dimension reduction
Data
Mining
Pattern discovery
Association & correlation
Classification
Clustering
Outlier analysis
…………
PostProcessing
Pattern
Pattern
Pattern
Pattern
evaluation
selection
interpretation
visualization
• This is a view from typical machine learning and statistics
communities
Data Warehouse and Business Intelligence
7
1.5 Các lĩnh vực có ảnh hưởng đến khai phá dữ liệu
Machine
Learning
Applications
Algorithm
Pattern
Recognition
Data Mining
Database
Technology
Statistics
Visualization
High-Performance
Computing
Data Warehouse and Business Intelligence
8
2. Khai phá luật kết hợp và ứng dụng
Các khái niệm cơ sở
Mẫu phổ biến và khai phá luật
Data Warehouse and Business Intelligence
9
3
2.1 Khái niệm cơ sở: Tập phổ biến và luật kết hợp
Cơ sở dữ liệu giao dịch (transaction database)
• Giao dịch: danh sách các mặt hàng (mục: item) trong một phiếu mua hàng của khách
hàng. Giao dịch T là một tập mục.
• Tập toàn bộ các mục I = {i1, i2, …, ik} “tất cả các mặt hàng”. Một giao dịch T là một
tập con của I: T ⊆ I. Mỗi giao dịch T có một định danh là TID.
• A là một tập mục A ⊆ I và T là một giao dịch: Gọi T chứa A nếu A ⊆ T.
Luật kết hợp
• Gọi A → B là một “luật kết hợp” nếu A ⊆ I, B ⊆ I và A∩B=∅.
• Luật kết hợp A → B có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong D có
s% các giao dịch T chứa AB: chính là xác suất P(AB). Tập mục A có P(A) ≥ s>0 (với
s cho trước) được gọi là tập phổ biến (frequent set). Luật kết hợp (association rule)
A → B có độ tin cậy (confidence) c trong CSDL D nếu như trong D có c% các giao
dịch T chứa A thì cũng chứa B: chính là xác suất P(B|A).
Support (A → B)
= P(A∪B)
: 1 ≥ s (A → B) ≥ 0
Confidence (A → B) = P(B|A)
: 1 ≥ c (A → B) ≥ 0
• Luật A → B được gọi là đảm bảo độ hỗ trợ s trong D nếu s(A → B) ≥ s. Luật A→B
được gọi là đảm bảo độ tin cậy c trong D nếu c(A → B) ≥ c (luật mạnh)
Data Warehouse and Business Intelligence
11
2.1 Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp
Tid
Items bought
10
Beer, Nuts, Diaper
20
Beer, Coffee, Diaper
30
Beer, Diaper, Eggs
40
Nuts, Eggs, Milk
50
Nuts, Coffee, Diaper, Eggs, Milk
Customer
buys both
Customer
buys diaper
Customer
buys beer
Data Warehouse and Business Intelligence
Tập mục I={i1, …, ik}.
CSDL giao dịch D = {d ⊆ I}
A, B ⊆ I, A∩B=∅: A B là luật kết hợp
Bài toán tìm luật kết hợp:
Cho trước độ hỗ trợ tối thiểu s>0, độ tin
cậy tối thiếu c>0. Hãy tìm mọi luật kết hợp
mạnh X Y.
Giả sử min_support = 50%, min_conf = 50%:
Freq. Pat.: Beer:3, Nuts:3, Diaper:4,
Eggs:3, {Beer, Diaper}:3
Luật kết hợp:
Beer
Diaper (60%, 100%)
Diaper
Beer (60%, 75%)
Chỉ ra các luật kết hợp còn lại
13
4
Một ví dụ tìm luật kết hợp
Transaction-id
Items bought
10
A, B, C
20
A, C
30
A, D
40
B, E, F
Với luật A
Min. support 50%
Min. confidence 50%
C:
Frequent pattern
Support
{A}
75%
{B}
50%
{C}
50%
{A, C}
50%
support = support({A}∪{C}) = 50%
confidence = support({A}∪{C})/support({A}) = 66.6%
Data Warehouse and Business Intelligence
14
Mẫu đóng (Closed Patterns) và mẫu cực đại
(Max-Patterns)
A long pattern contains a combinatorial number of subpatterns, e.g., {a1, …, a100} contains (1001) + (1002) + … +
(110000) = 2100 – 1 = 1.27*1030 sub-patterns!
Solution: Mine closed patterns and max-patterns instead
An itemset X is closed if X is frequent and there exists no
super-pattern Y ﬤX, with the same support as X (proposed by
Pasquier, et al. @ ICDT’99)
An itemset X is a max-pattern if X is frequent and there exists
no frequent super-pattern Y כX (proposed by Bayardo @
SIGMOD’98)
Closed pattern is a lossless compression of freq. patterns
Reducing the # of patterns and rules
Data Warehouse and Business Intelligence
15
Closed Patterns and Max-Patterns
Exercise. DB = {
, < a1, …, a50>}
Min_sup = 1.
What is the set of closed itemset?
: 1
< a1, …, a50>: 2
What is the set of max-pattern?
: 1
What is the set of all patterns?
!!
Data Warehouse and Business Intelligence
16
5
2.1. Khái niệm khai phá kết hợp
Data Warehouse and Business Intelligence
17
2.1. Khái niệm khai phá luật kết hợp
Khai phá luật kết hợp:
• Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu trú
nhân-quả trong tập các mục hoặc đối tượng trong CSDL quan
hệ hoặc các kho chứa thông tin khác.
• Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy mục…)
mà xuất hiện phổ biến trong 1 CSDL [AIS93]
• Động lực: tìm mẫu qui tắc(regularities pattern) trong DL
• Các mặt hàng nào được mua cùng nhau? - Bia và bỉm
(diapers)?!
• Mặt hàng nào sẽ được mua sau khi mua một PC ?
• Kiểu DNA nào nhạy cảm với thuộc mới này?
• Có khả năng tự động phân lớp Web hay không ?
•
Data Warehouse and Business Intelligence
18
2.1. Mẫu phổ biến và khai phá luật
Nền tảng của nhiều bài toán KPDL:
Kết hợp, tương quan, nhân quả
Mẫu tuần tự, kết hợp thời gian hoặc vòng, chu kỳ bộ phận,
kết hợp không gian và đa phương tiện
Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích tụ
(nén dữ liệu ngữ nghĩa)
Ứng dụng:
Phân tích dữ liệu bóng rổ, tiếp thị chéo (cross-marketing),
thiết kế catalog, phân tích chiến dịch bán hàng
Phân tích Web log (click stream), Phân tích chuỗi DNA
v.v.
Data Warehouse and Business Intelligence
19
6
2.2. Khám phá mẫu phổ biến
Giải thuật Apriori: khám phá các mẫu phổ biến với tập dự
tuyển (ứng viên)
Giải thuật FP-Growth: khám phá các mẫu phổ biến với FP-tree
Data Warehouse and Business Intelligence
20
2.1 Giải thuật Apriori
Khái quát: Khai phá luật kết hợp gồm hai bước:
Tìm mọi tập phổ biến: theo min-sup
Sinh luật mạnh từ tập phổ biến
Mọi tập con của tập phổ biến cũng là tập phổ biến
Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi giao dịch
chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}.
Nguyên lý tỉa Apriori: Với mọi tập mục không phổ biến thì mọi tập bao
không cần phải sinh ra/kiểm tra!
Phương pháp:
Sinh các tập mục ứng viên dài (k+1) từ các tập phổ biến có độ dài k (Độ dài tập
mục là số phần tử của nó),
Kiểm tra các tập ứng viên theo CSDL
Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng của
thuật toán (Agrawal & Srikant 1994, Mannila, và cộng sự 1994)
Data Warehouse and Business Intelligence
21
2.2 Giải thuật Apriori
Trên cơ sở tính chất (nguyên lý tỉa) Apriori, thuật toán
hoạt động theo quy tắc quy hoạch động
Từ các tập Fi = {ci| ci tập phổ biến, |ci| = i} gồm mọi tập
phổ biến có độ dài i với 1 ≤ i ≤ k,
Tìm tập Fk+1 gồm mọi tập phổ biến có độ dài k+1.
Trong thuật toán, các tên mục i1, i2, … in (n = |I|) được sắp
xếp theo một thứ tự cố định (thường được đánh chỉ số 1,
2, ..., n).
Data Warehouse and Business Intelligence
22
7
2.1 Giải thuật Apriori
Data Warehouse and Business Intelligence
23
Thuật toán Apriori: Thủ tục con Apriori-gen
Trong mỗi bước k, thuật toán Apriori đều phải duyệt CSDL D.
Khởi động, duyệt D để có được F1.
Các bước k sau đó, duyệt D để tính số lượng giao dịch t thoả từng ứng viên c của
Ck+1: mỗi giao dịch t chỉ xem xét một lần cho mọi ứng viên c thuộc Ck+1.
Thủ tục con Apriori-gen sinh tập phổ biến:
Data Warehouse and Business Intelligence
24
2.2 Giải thuật Apriori:Thủ tục con Apriori-gen
Data Warehouse and Business Intelligence
25
8
Một ví dụ thuật toán Apriori (s=0.5)
Itemset
sup
{A}
{B}
2
3
{C}
3
{D}
1
{E}
3
Database TDB
Tid
Items
10
A, C, D
20
B, C, E
30
A, B, C, E
40
B, E
C1
1st scan
C2
L2
Itemset
{A, C}
{B, C}
{B, E}
{C, E}
C3
sup
2
2
3
2
Itemset
{B, C, E}
Itemset
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
3rd scan
sup
1
2
1
2
3
2
L3
Itemset
L1
2
{B}
3
{C}
3
{E}
3
C2
2nd scan
Itemset
{B, C, E}
sup
{A}
Itemset
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
sup
2
Data Warehouse and Business Intelligence
26
Chi tiết quan trọng của Apriori
Cách thức sinh các ứng viên:
Bước 1: Tự kết nối Lk
Bước 2: Cắt tỉa
Cách thức đếm hỗ trợ cho mỗi ứng viên.
Ví dụ thủ tục con sinh ứng viên
L3={abc, abd, acd, ace, bcd}
Tự kết nối: L3*L3
• abcd từ abc và abd
• acde từ acd và ace
Tỉa:
• acde là bỏ đi vì ade không thuộc L3
C4={abcd}
Data Warehouse and Business Intelligence
27
Ví dụ: D, min_sup*|D| = 2 (C4 = ∅)
Data Warehouse and Business Intelligence
28
9
Sinh luật kết hợp
Việc sinh luật kết hợp gồm hai bước
• Với mỗi tập phổ biến W tìm được hãy sinh ra mọi tập con
thực sự X khác rỗng của nó.
• Với mỗi tập phố biến W và tập con X khác rỗng thực sự của
nó: sinh luật X → (W – X) nếu P(W-X|X) ≥ c.
Như ví dụ đã nêu có L3 = {{I1, I2, I3}, {I1, I2, I5}}
Với độ tin cậy tối thiểu 70%, xét tập phổ biến {I1, I2, I5} có 3
luật như dưới đây:
Data Warehouse and Business Intelligence
29
Cách thức tính độ hỗ trợ của ứng viên
Tính độ hỗ trợ ứng viên là vấn đề cần quan tâm
Số lượng ứng viên là rất lớn
Một giao dịch chứa nhiều ứng viên
Phương pháp:
Tập mục ứng viên được chứa trong một cây-băm (hashtree)
Lá của cây băm chứa một danh sách các tập mục và bộ đếm
Nút trong chứa bảng băm
Hàm tập con: tìm tất cả các ứng viên
Data Warehouse and Business Intelligence
30
Cách thức tính độ hỗ trợ của ứng viên
Tập các ứng viên Ck được lưu trữ trong một cây-băm.
Gốc của cây băm ở độ sâu 1. Lá chứa một danh sách tập mục
Nút trong chứa một bảng băm: mỗi thùng của bảng trỏ tới một nút khác (Nút ở độ sâu d
trỏ tới các nút ở độ sâu d+1).
Khi khởi tạo, tất cả các nút là lá.
Khi thêm một tập mục c:
bắt đầu từ gốc đi xuống theo cây cho đến khi gặp một lá.
Tại một nút trong độ sâu d:
• quyết định theo nhánh nào bằng cách áp dụng hàm băm tới mục thứ d của tập mục
này.
• Khi số lượng tập mục tại một lá vượt quá ngưỡng quy định, nút lá được chuyển
thành một nút trong.
Bắt đầu từ gốc, tìm tất cả các ứng viên thuộc giao dịch t:
Nếu ở nút gốc: băm vào mỗi mục trong t.
Nếu ở một lá: tìm các tập mục ở lá này thuộc t và bổ sung chỉ dẫn tới các tập mục này tới
tập trả lời.
Nếu ở nút trong và đã đạt được nó bằng cách băm mục i, trên từng mục đứng sau i trong t
và áp dụng đệ quy thủ tục này sang nút trong thùng tương ứng.
Data Warehouse and Business Intelligence
31
10
Ví dụ: Tính độ hỗ trợ các ứng viên
Hàm tập con
3,6,9
Transaction: 1 2 3 5 6
1,4,7
2,5,8
1+2356
234
567
13+56
145
136
345
12+356
124
457
125
458
356
357
689
367
368
159
Data Warehouse and Business Intelligence
32
Thách thức khai phá mẫu phổ biến
Thách thức
Duyệt nhiều lần CSDL giao dịch
Số lượng rất lớn các ứng viên
Phức tạp trong việc tính toán độ hỗ trợ
Cải tiến Apriori: (ý tưởng chung)
Giảm số lần duyệt CSDL giao dịch
Rút gọn số lượng các ứng viên
Đơn giản trong việc tính độ hỗ trợ của các ứng viên
Data Warehouse and Business Intelligence
33
Một số phương pháp cải tiến
DIC (Đếm tập mục động): Rút gọn số lượng duyệt CSDL
Giải pháp Phân hoạch (Partition): Duyệt CSDL chỉ hai lần
DHP: Rút gọn số lượng các ứng viên
Eclat/MaxEclat và VIPER: Thăm dò dạng dữ liệu theo chiều
ngang
Khai phá mẫu phổ biến không cần sinh ứng viên
Data Warehouse and Business Intelligence
34
11
Khai phá mẫu phổ biến không cần sinh ứng viên
Dùng các mục phổ biến để tăng độ dài mẫu từ các mẫu
ngắn hơn
“abc” là một mẫu phổ biến
Nhận mọi giao dịch có “abc”: DB|abc
“d” là một mục phổ biến trong DB|abc
phổ biến
abcd là một mẫu
Data Warehouse and Business Intelligence
35
Xây dựng FP-tree từ một CSDL giao dịch
TID
100
200
300
400
500
Items bought
(ordered) frequent items
{f, a, c, d, g, i, m, p}
{f, c, a, m, p}
{a, b, c, f, l, m, o}
{f, c, a, b, m}
{b, f, h, j, o, w}
{f, b}
{b, c, k, s, p}
{c, b, p}
{a, f, c, e, l, p, m, n}
{f, c, a, m, p}
min_support = 3
{}
1. Duyệt CSDL một lần, tìm Header Table
các 1-tập phổ biến (mẫu
Item frequency head
mục đơn)
f
c
2. Sắp xếp các mục phổ
biến theo thứ tự giảm dần a
b
về bậc, F-list
m
4
4
3
3
3
3
3. Duyệt CSDL lần nữa, xây p
dựng FP-tree
F-list=f-c-a-b-m-p
Từ FP-tree tìm luật kết hợp
f:4
c:1
c:3
b:1 b:1
a:3
p:1
m:2
b:1
p:2
m:1
Data Warehouse and Business Intelligence
36
Lợi ích của cấu trúc FP-tree
Tính đầy đủ
Duy trì tính đầy đủ thông tin để khai phá mẫu phổ biến
Không phá vỡ mẫu dài với bất kỳ giao dich
Tính cô đọng
Giảm các thông tin không liên quan: mục không phổ biến
bỏ đi
Sắp mục theo tần số giảm: xuất hiện càng nhiều thì càng
hiệu quả
Không lớn hơn so với CSDL thông thường
Data Warehouse and Business Intelligence
42
12
Độ đo hấp dẫn: Tương quan (nâng cao)
play basketball ⇒ eat cereal [40%, 66.7%] là lạc
Phần trăm chung của sinh viên ăn ngũ cốc là 75% cao hơn
so với 66.7%.
play basketball ⇒ not eat cereal [20%, 33.3%] là chính
xác hơn, do độ hỗ trợ và tin cậy thấp hơn
Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao)
Basketball
Not basketball
Cereal
2000
1750
3750
Not cereal
1000
250
1250
Sum(col.)
3000
2000
5000
Data Warehouse and Business Intelligence
Sum (row)
43
Thuật toán Apriori— Ví dụ
Database D
L1
C1
Scan D
C2
C2
Scan D
L2
C3
Scan D
L3
Data Warehouse and Business Intelligence
44
3. Phân lớp dữ liệu (classification)
3.1 Tổng quan về phân lớp dữ liệu
3.2 Qui trình 2 pha
3.3 Các loại phân lớp
3.4 Đánh giá bộ phân lớp
3.5 Một số phương pháp phân lớp
Data Warehouse and Business Intelligence
46
13
3.1 Tổng quan về phân lớp dữ liệu
Phân lớp dữ liệu:
Dự đoán nhãn (label) của lớp phân loại
Phân lớp dữ liệu (xây dựng mô hình) dựa trên tập huấn
luyện và các giá trị (các nhãn của lớp) trong thuộc tính
phân lớp và dùng nó để phân lớp dữ liệu mới
Một số ứng dụng điển hình:
Phê duyệt tín dụng/khoản vay
Chuẩn đoán y tế
Dò tìm lỗi
Phân loại trang web
Data Warehouse and Business Intelligence
47
3.2 Qui trình 2 pha
Pha 1: Xây dựng mô hình (Model Construction)
Mô tả một tập hợp các lớp đã xác định trước
Pha 2: Sử dụng mô hình (Model usage)
Dùng để phân lớp sau này hoặc những mục tiêu chưa biết
Data Warehouse and Business Intelligence
48
Pha 1: Xây dựng mô hình
Training
Data
Classification
Algorithms
Classifier
(Model)
IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
Data Warehouse and Business Intelligence
49
14
Pha 2: Sử dụng mô hình
Classifier
Testing
Data
Unseen Data
(Jeff, Professor, 4)
Tenured?
Data Warehouse and Business Intelligence
50
3.3 Các loại phân lớp
Phân lớp nhị phân/đa lớp:
|C|=2: phân lớp nhị phân.
|C|>2: phân lớp đa lớp.
Phân lớp đơn nhãn/đa nhãn:
Đơn nhãn: mỗi đối tượng được gán vào chính xác một lớp.
Đa nhãn: một đối tượng có thể được gán nhiều hơn một
lớp.
Phân cấp: lớp này là cha/con của lớp kia
Data Warehouse and Business Intelligence
54
3.4 Đánh giá mô hình phân lớp
Các phương pháp đánh giá độ chính xác của mô hình phân
lớp:
Holdout method, random subsampling
Cross-validation
Bootstrap
Ma trận lỗi (Confusion Matrix)
Lớp dự đoán (Predicted class)
Lớp thật
(Actual
class)
C1
¬ C1
C1
True Positives (TP)
False Negatives (FN)
¬ C1
False Positives (FP)
True Negatives (TN)
Data Warehouse and Business Intelligence
55
15
True Positives (TP): Thực dương
True Negatives (TN): Thực âm
False Positives (FP): Dương sai
False Negatives (FN): Âm sai
Data Warehouse and Business Intelligence
57
3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp
nhị phân
Dùng độ chính xác (Accuracy), tỉ lệ lỗi (Error rate), Độ
nhạy (Sensitivity) và độ đặc trưng (Specificity)
A\P
C
Sensitivity: True Positive
recognition rate
!
=
¬C
C
TP FN
¬C
FP TN
N
P’
All
N’
P
Độ chính xác của bộ phân lớp
(Classifier Accuracy):
Acc
=
Specificity: True Negative
recognition rate
!
" #
=
Tỉ lệ lỗi (Error rate):
+
=
= 1−
Data Warehouse and Business Intelligence
58
58
3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp
nhị phân
Dùng độ chính xác (Precision), độ hồi tưởng (Recall) và các
độ đo F (F-measures)
Data Warehouse and Business Intelligence
59
16
3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp
đa lớp
Bài toán ban đầu: C gồm có k lớp
Đối với mỗi lớp Ci , cho thực hiện thuật toán với các dữ
liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi
(như bảng dưới đây)
Giá trị qua bộ phân lớp đa lớp
Lớp Ci
Thuộc lớp Ci
Không thuộc
lớp Ci
TPi
FNi
FPi
TNi
Thuộc lớp Ci
Giá trị thực
Không thuộc
lớp Ci
Data Warehouse and Business Intelligence
63
3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp
đa lớp
Tương tự bộ phân lớp nhị phân
Độ chính xác Pri của lớp Ci là tỷ lệ số phần tử dương được
thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ được
thuật toán phân lớp vào lớp Ci :
Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được
thuật toán phân lớp cho giá trị đúng trên tổng số ví dụ
dương thực sự thuộc lớp Ci:
Data Warehouse and Business Intelligence
64
3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp
đa lớp
ρi : Độ chính xác của lớp Ci
πi : Độ hồi tưởng của lớp Ci.
Đánh giá mô hình phân lớp theo các độ đo:
Vi trung bình (microaveraging) (được ưa chuộng) ρµ và πµ
Trung bình lớn (macroaveraging) ρM và πM
Data Warehouse and Business Intelligence
65
17
3.5 Một số phương pháp phân lớp dữ liệu
3.5.1 Phương pháp dựa trên cây quyết định (Decision Tree
based Methods)
3.5.2 Phương pháp Naïve Bayes
3.5.3 Một số phương pháp khác:
Phương pháp dựa trên luật (Rule-based Methods)
Các phương pháp máy vector hỗ trợ (Support Vector
Machines)
Lập luận dưa trên ghi nhớ (Memory based reasoning)
Các phương pháp mạng nơron (Neural Networks)
Data Warehouse and Business Intelligence
66
3.5.1 Phân lớp với cây quyết định
Cơ sở dữ liệu
khách hàng dùng
cho bước học
Data Warehouse and Business Intelligence
67
3.5.1 Phân lớp với cây quyết định
Cây quyết định (decision tree) - mô hình phân lớp
Node nội: phép kiểm thử (test) trên một thuộc tính
Node lá: nhãn/mô tả của một lớp (class label)
Nhánh từ một node nội: kết quả của một phép thử trên
thuộc tính tương ứng
Cây quyết định học được
từ tập huấn luyện
Data Warehouse and Business Intelligence
68
18
3.5.1 Phân lớp với cây quyết định
Giải thuật xây dựng cây quyết định
ID3, C4.5, CART (Classification and Regression Trees –
binary decision trees)
Algorithm: Generate decision tree. Generate a decision tree from the training
tuples of data partition, D.
Input:
Data partition, D, which is a set of training tuples and their associated class
labels;
attribute list, the set of candidate attributes;
Attribute selection method, a procedure to determine the splitting criterion that
“best” partitions the data tuples into individual classes. This criterion consists of
a splitting attribute and, possibly, either a split-point or splitting subset.
Output: A decision tree.
Data Warehouse and Business Intelligence
69
3.5.1 Phân lớp với cây quyết định
Method:
(1) create a node N;
(2) if tuples in D are all of the same class, C, then
(3) return N as a leaf node labeled with the class C;
(4) if attribute list is empty then
(5) return N as a leaf node labeled with the majority class in D; // majority voting
(6) apply Attribute selection method(D, attribute list ) to find the “best” plitting criterion;
(7) label node N with splitting criterion;
(8) if splitting attribute is discrete-valued and multiway splits allowed then // not restricted to
binary trees
(9) Attribute list attribute list splitting attribute; // remove splitting attribute
(10) for each outcome j of splitting criterion
// partition the tuples and grow subtrees for each partition
(11) let Dj be the set of data tuples in D satisfying outcome j; // a partition
(12) if Dj is empty then
(13)
attach a leaf labeled with the majority class in D to node N;
(14) else attach the node returned by Generate decision tree(D, attribute list ) to node N;
endfor
(15) return N;
Data Warehouse and Business Intelligence
70
3.5.1 Phân lớp với cây quyết định
Đặc điểm của giải thuật:
Giải thuật tham lam (không có quay lui), chia để trị, đệ qui,
từ trên xuống
Độ phức tạp với tập huấn luyện D gồm |D| phần tử (đối
tượng), mỗi phần tử gồm n thuộc tính
• O(n*|D|*log|D|)
• Mỗi thuộc tính ứng với mỗi mức (level) của cây.
• Cho mỗi mức của cây, |D| phân tử huấn luyện được duyệt qua.
Data Warehouse and Business Intelligence
71
19
3.5.1 Phân lớp với cây quyết định
Phương pháp chọn thuộc tính
Phương thức dùng heuristic để chọn tiêu chí rẽ nhánh tại
một node, i.e. phân hoạch tập huấn luyện D thành các phân
hoạch con với các nhãn phù hợp
• Xếp hạng mỗi thuộc tính
• Thuộc tính được chọn để rẽ nhánh là thuộc có trị số điểm
(score) lớn nhất
o Độ đo chọn thuộc tính phân tách (splitting attribute):
o information gain (dùng trong ID3, C4.5/J48)
o gain ratio (dùng trong C4.5/J48)
o gini index (dùng trong CART)
Data Warehouse and Business Intelligence
72
3.5.1 Phân lớp với cây quyết định
A là thuộc tính phân tách (splitting attribute).
Data Warehouse and Business Intelligence
73
3.5.1 Phân lớp với cây quyết định
Độ đo Information Gain (Độ lợi thông tin)
Dựa trên lý thuyết thông tin (information theory) của
Claude Shannon về giá trị (nội dung thông tin) của tin
Thuộc tính tương ứng với information gain lớn nhất sẽ
được chọn làm thuộc tính phân hoạch (splitting attribute)
cho node N.
• Node N là node hiện tại cần phân hoạch các phần tử trong D.
• Splitting attribute đảm bảo sự trùng lắp (impurity)/ngẫu
nhiên (randomness) ít nhất giữa các phân hoạch tạo được.
• Cách tiếp cận này giúp tối thiểu số phép thử (test) để phân
loại một phần tử.
Data Warehouse and Business Intelligence
74
20