ả
ọ Bài gi ng môn h c
KHO DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU
CHƯƠNG 2. TIỀN XỬ LÝ DỮ LIỆU
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
1
ệ
ả
Tài li u tham kh o
J.
M.
and
Han
Kamber
(2006). Morgan
[HK06] Data Mining-Concepts and Techniques (Second Edition), Kaufmann. Chapter 2. Data Preprocessing [NEM09] Robert Nisbet, John Elder, and Gary Miner (2009). Handbook of Statistical Analysis and Data Mining, Elsevier, 6/2009. Chapter 4. Data Understanding and Preparation; Chapter 5. Feature Selection. [Chap05] Chapman, A. D. (2005). Principles of Data Cleaning, Report for the Global Biodiversity Information Facility, Copenhagen [Chap05a] Chapman, A. D. (2005a). Principles and Methods of Data Cleaning – Primary Species and Species- Occurrence Data (version 1.0), Report for the Global Biodiversity Information Facility, Copenhagen [Hai02] Đoàn An Hải (2002). Learning to Map between Structured Representations of Data, PhD Thesis, The University of Washington, ACM 2003 Award Winners and Fellows (Doctoral Dissertation Award). [RD00] Erhard Rahm, Hong Hai Do (2000). Data Cleaning: Problems and Current Approaches, IEEE Data Eng. Bull., 23(4): 3-13 (2000) và một số tài liệu khác
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
2
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ủ ử ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
3
ờ ạ ế ệ
ữ
ể ể
ấ
ữ ề ơ ả Nh ng v n đ c b n đ hi u d li uệ
ậ
ượ
ữ ệ
ầ
ế ể
Cách thu th p đ
c d li u c n thi
t đ mô hình hóa:
Data Acquisition
ế ợ
ữ ệ
ồ
Cách k t h p d li u tìm đ
ượ ừ c t
ữ ệ các ngu n d li u khác nhau
Data Integeation.
ả ữ ệ
Mô t
d li u
Data Description
ấ ượ
ộ ạ
ữ ệ
ủ
Đánh giá ch t l
ng (đ s ch) c a d li u
Data Assessment
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
4
ữ ệ
ậ
Thu th p d li u
Cách thu thập dữ liệu cần thiết để mô hình hóa
ọ
ỏ ừ
ớ ậ
CSDL t
i t p tin
ph ngẳ
ữ ỏ ậ
ự
ế
ậ
Ngôn ng h i b c cao truy nh p tr c ti p CSDL
ự
ứ
ể
ế
ấ
K t n i m c th p đ truy nh p tr c ti p CSDL
ậ ế ố Loại bỏ ràng buộc không gian/thời gian khi di chuyển khối
lượng lớn dữ liệu
Hỗ trợ việc quản lý và bảo quản dữ liệu tập trung hóa
Rút gọn sự tăng không cần thiết của dữ liệu
Tạo điều kiện quản trị dữ liệu tốt hơn để đáp ứng mối quan
tâm đúng đắn
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
5
Data Acquisition: ữ ệ Trích ch n d li u theo câu h i t
ữ ệ
ợ
Tích h p d li u
ữ ệ
ồ
Cách k t h p d li u tìm đ
ượ ừ c t
ữ ệ các ngu n d li u khác nhau
ế ợ Data Integeation.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
6
ả ữ ệ
Mô t
d li u
Giá trị kỳ vọng (mean)
ỳ ọ
ố ữ ệ
ỏ
ể
ạ
ố ầ
ị ủ
ấ
L
ồ
ậ ồ ọ
ễ ầ
ị ủ
ế
ấ
ộ
ố
Xu hướng trung tâm của tập dữ liệu Độ lệch chuẩn (Standard deviation) Phân b d li u xung quanh k v ng ự C c ti u (Minimum) ấ ị Giá tr nh nh t ự C c đ i (Maximum) ấ ị ớ Giá tr l n nh t ầ ả B ng t n su t (Frequency tables) ế ấ Phân b t n su t giá tr c a các bi n ượ ể Cung c p k thu t đ h a bi u di n t n s giá tr c a m t bi n
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
7
c đ (Histograms) ỹ
Mô tả dữ liệu, so sánh với phân bố chuẩn (chủ yếu trong miền [0,10])
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
8
ồ ơ ữ ệ
ậ Đánh giá và l p h s d li u
Đánh giá dữ liệu
Định vị một vấn đề trong dữ liệu cần giải quyết: Tìm ra và quyết định
cách nắm bắt vấn đề
Mô tả dữ liệu sẽ làm hiện rõ một số vấn đề Kiểm toán dữ liệu: lập hồ sơ dữ liệu và phân tích ảnh hưởng của dữ
liệu chất lượng kém. ồ ơ ữ ệ
L p h s d li u (c s căn c : phân b d li u)
ơ ở ố ữ ệ ứ
test, hoặc chỉ đơn giản dữ liệu rác
Những phát hiện nên được trình bày dưới dạng các báo cáo và liẹt kế
như các mốc quan trọng của kế hoạch
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
9
ậ Tâm của dữ liệu Các ngoại lai tiềm năng bất kỳ Số lượng và phân bố các khoảng trong trong mọi trường hợp Bất cứ dữ liệu đáng ngờ, như mã thiếu (miscodes), dữ liệu học, dữ liệu
ề ơ ả
ị ữ ệ
ữ
ể
ấ
ẩ
Nh ng v n đ c b n đ chu n b d li u
Cách thức làm sạch dữ liệu:
Data Cleaning
Cách thức diễn giải dữ liệu: Data Transformation
Cách thức nắm bắt giá trị thiếu:
Data Imputation
Trọng số của các trường hợp: Data Weighting and Balancing
Xử lý dữ liệu ngoại lai và không mong muốn khác:
Data Filtering
Cách thức nắm bắt dữ liệu thời gian/chuỗi thời gian:
Data Abstraction
Cách thức rút gọn dữ liệu để dùng: Data Reduction
Bản ghi : Data Sampling Biến: Dimensionality Reduction Giá trị: Data Discretization
ữ ệ
ữ ệ
Cách thức tạo biến mới: Data Derivation ươ Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
10
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ử ủ ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
11
ờ ạ ế ệ
ử
ủ
ề
ọ
Tính quan tr ng c a ti n x lý
Không có d li u t
ữ ệ ố ể ả ố ế t, không th có k t qu khai phá t t!
Quy t đ nh ch t l
ạ
ố
ộ
ế ị ấ ượ ả ự ữ ệ ấ ng ph i d a trên d li u ch t
ể
ầ
ữ ệ ậ
chính xác, th m chí gây hi u nh m.
ngượ l ế ẳ Ch ng h n, d li u b i hay thi u là nguyên nhân th ng không
Kho d li u c n tích h p nh t quán c a d li u ch t
ữ ệ ữ ệ ủ ấ ầ ấ ợ
ngượ l ớ ữ ệ ệ
ộ ổ ữ ệ ạ ọ ự Phân l n công vi c xây d ng m t kho d li u là trích ể ch n, làm s ch và chuy n đ i d li u —Bill Inmon .
D li u có ch t l
ợ ụ i ớ m c đích
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
12
ng cao n u nh phù h p v ậ ấ ượ ề ư ế ị ế ạ ữ ệ ế ử ụ s d ng trong đi u hành, ra quy t đ nh, và l p k ho ch
ộ
ữ ệ
ề
ng d li u
ấ ượ Đ đo đa chi u ch t l MultiDimensional Measure of Data Quality
ấ t:
ộ
ầ
ấ
ị
ậ ộ
ị
Phân lo i b r ng (Broad categories):
ễ ậ ể ế c (Interpretability) c (Accessibility)
ậ ố ề Khung đa chi u c p nh n t Đ chính xác (Accuracy) ủ Tính đ y đ (Completeness) Tính nh t quán (Consistency) ờ Tính k p th i (Timeliness) Đ tin c y (Believability) Giá tr gia tăng (Value added) ượ Bi u di n đ ượ Ti p c n đ ạ ề ộ ấ ả
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
13
ữ ả B n ch t (intrinsic), ng c nh (contextual),trình di n ế ượ ậ ễ c (accessibility). (representational), và ti p c n đ
Major Tasks in Data Preprocessing
ề
ặ
ơ
ị
ạ Làm s ch d li u
ữ ệ Đi n giá tr thi u, làm tr n d li u nhi u, đ nh danh ho c xóa ấ
ễ ngo i lai, và kh tính không nh t quán
ữ ệ ế ị ử
ạ ợ Tích h p d li u
ố ữ ệ
ặ ậ
ợ
ứ Tích h p CSDL, kh i d li u ho c t p tin ph c
ữ ệ
ề
ọ
ướ
ữ
ấ
ả
c nh ng s n xu t cùng
ượ ặ ươ
ả
ữ ệ ổ ạ Chuy n d ng d li u ợ
Chu n hóa và t ng h p ữ ệ c trình bày thu g n v kích th k t qu phân tích ng t
ự ế ữ ệ
ữ ệ
ề
ọ
ị
t c a rút g n d li u (rút g n mi n giá tr )
ể ẩ ọ Rút g n d li u Thu đ ho c t
ặ ộ
ặ
ọ ệ ớ ữ ệ
ố
ệ ủ ọ nh ng có đ quan tr ng riêng, đ c bi
t v i d li u s
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
14
ờ ạ R i r c hóa d li u ậ ộ B ph n đ c bi ư
ữ ệ
ủ
ử
ề
ầ
ả
Các thành ph n c a ti n x lý d li u (B ng 2.1)
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
15
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ủ ử ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
16
ờ ạ ệ ế
ữ ệ
ạ
Làm s ch d li u
Là quá trình
xác định tính không chính xác, không đầy đủ/tính bất hợp lý của dữ liệu
chỉnh sửa các sai sót và thiếu sót được phát hiện
nâng cao chất lượng dữ liệu.
Quá trình bao gồm
kiểm tra định dạng, tính đầy đủ, tính hợp lý, miền giới hạn,
xem xét dữ liệu để xác định ngoại lai (địa lý, thống kê, thời gian hay môi
trường) hoặc các lỗi khác,
đánh giá dữ liệu của các chuyên gia miền chủ đề.
Quá trình thường dẫn đến
loại bỏ, lập tài liệu và kiểm tra liên tiếp và hiệu chỉnh đúng bản ghi nghi
ngờ.
Kiểm tra xác nhận có thể được tiến hành nhằm đạt tính phù hợp với
các chuẩn áp dụng, các quy luật, và quy tắc.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
17
ơ ồ
ữ ệ
ứ
ồ
ơ
ụ Ngu n d li u đ n: m c s đ (Ví d )
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
18
ể ệ
ữ ệ
ứ
ồ
ơ
ụ Ngu n d li u đ n: m c th hi n (Ví d )
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
19
ồ
ữ ệ
ứ
ể ệ
ơ ồ ứ Ngu n d li u ph c: m c s đ ụ và th hi n (Ví d )
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
20
ữ ệ
ạ
Làm s ch d li u
Nguyên lý chất lượng dữ liệu cần được áp dụng ở mọi giai đoạn quá trình quản lý dữ liệu (nắm giữ, số hóa, lưu trữ, phân tích, trình bày và sử dụng). hai vấn đề cốt lõi để cải thiện chất lượng - phòng ngừa và chỉnh sửa Phòng ngừa liên quan chặt chẽ với thu thập và nhập dữ liệu vào CSDL. Tăng cường phòng ngừa lỗi, vẫn/tồn tại sai sót trong bộ dữ liệu lớn (Maletic và Marcus 2000) và không thể bỏ qua việc xác nhận và sửa chữa dữ liệu Vai trò quan tr ngọ ộ
ấ ủ
ữ ệ
ớ
ữ ệ
ả
“là m t trong ba bài toán l n nh t c a kho d li u”—Ralph Kimball “là bài toán “number one” trong kho d li u”—DCI kh o sát
Xử lý giá trị thiếu Dữ liệu nhiễu: định danh ngoại lai và làm trơn. Chỉnh sửa dữ liệu không nhất quán Giải quyết tính dư thừa tạo ra sau tích hợp dữ liệu.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
21
ữ ệ ạ ộ Các bài toán thu c làm s ch d li u
ử
ị ế X lý thi u giá tr
Bỏ qua bản ghi có giá trị thiếu:
ườ
ớ
ớ
s bài toán phân l p)
ỷ ệ ố
ế ớ
ả
ị
ế Th ể không hi u qu khi t
ng làm khi thi u nhãn phân l p (gi l
ả ử s giá tr thi u l n (bán giám sát)
Điền giá trị thiếu bằng tay:
tẻ nhạt tính khả thi
Điền giá trị thiếu tự động:
Hằng toàn cục: chẳng hạn như“chưa biết”, có phải một lớp mới Trung bình giá trị thuộc tính các bản ghi hiện có Trung bình giá trị thuộc tính các bản ghi cùng lớp: tinh hơn Giá trị khả năng nhất: dựa trên suy luận như công thức Bayes hoặc cây
quyết định
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
22
ữ ệ
ễ
D li u nhi u
Nhi u: ễ
Lỗi ngẫu nhiên Biến dạng của một biến đo được
Giá tr không chính xác do
Lỗi do thiết bị thu thập dữ liệu Vấn đề nhập dữ liệu: người dùng hoặc máy có thể sai Vấn đề truyền dữ liệu: sai từ thiết bị gửi/nhận/truyền Hạn chế của công nghệ: ví dụ, phần mềm có thể xử lý không đúng Thiết nhất quán khi đặt tên: cũng một tên song cách viết khác nhau
ị
Các v n đ d li u khác yêu c u làm s ch d li u
ữ ệ ầ ạ ề ữ ệ
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
23
ấ Bộ bản ghi Dữ liệu không đầy đủ Dữ liệu không nhất quán
ắ
ễ ắ ữ ệ N m b t d li u nhi u (Handle Noisy Data)
Ph
ươ ng pháp đóng thùng (Binning): ắ ề
S p d li u tăng và chia “đ u” vào các thùng Làm tr n: theo trung bình
ữ ệ ơ ế , theo trung tuy n, theo
biên… ụ
ạ
K t h p ki m tra máy tính và con ng
Phân c m (Clustering) ạ ỏ ệ Phát hi n và lo i b ngo i lai (outliers) ể ế ợ ệ
Phát hi n giá tr nghi ng đ con ng
ườ
ờ ể ạ ị ố ẳ ạ ớ i ườ ể i ki m tra ể (ch ng h n, đ i phó v i ngo i lai có th )
ồ H i quy
Làm tr n: ghép d li u theo các hàm h i quy
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
24
ữ ệ ồ ơ
ươ
ờ ạ
ả
ơ
Ph ng pháp r i r c hóa đ n gi n (Simple Discretization Methods: Binning)
Phân ho ch cân b ng b r ng Equalwidth
ề ộ ạ ẳ (distance)
ư ạ ị N đo n dài nh nhau:
ị ừ partitioning: ề Chia mi n giá tr : Mi n giá tr t ỏ A (nh nh t) t ớ ấ ớ B (l n nh t) > i uniform grid ấ W = (B –
ề A)/N. ơ ả ướ ạ
ị ị ữ ệ ử
ng theo ngo i lai. ằ t khi d li u không cân b ng (đ u). ằ ấ Đ n gi n nh t song b đ nh h ố Không x lý t ạ ề ề Phân ho ch cân b ng theo chi u sâu Equaldepth
ạ (frequency) partitioning: ề ố ề Chia mi n xác đ nh thành N đo n “đ u nhau v s
ề ụ ẫ ỉ ố ượ l
ố t.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
25
ể ộ ớ ị ạ ấ ng”, các đo n có x p x s ví d m u. ả ỡ ữ ệ Kh c d li u: t ả ệ Vi c qu n lý các thu c tính l p: có th “khôn khéo”.
ươ
ữ ệ
ế
ơ
ng pháp x p thùng làm tr n d li u
Ph (Binning Methods for Data Smoothing)
ế
ượ
c x p theo giá: 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
ề
ơ
ữ ệ * D li u đ * Chia thùng theo chi u sâu: Bin 1: 4, 8, 9, 15 Bin 2: 21, 21, 24, 25 Bin 3: 26, 28, 29, 34 ơ * Làm tr n thùng theo trung bình: Bin 1: 9, 9, 9, 9 Bin 2: 23, 23, 23, 23 Bin 3: 29, 29, 29, 29 * Làm tr n thùng theo biên: Bin 1: 4, 4, 4, 15 Bin 2: 21, 21, 25, 25 Bin 3: 26, 26, 26, 34
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
26
Phân tích c m ụ (Cluster Analysis)
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
27
BÀI TOÁN PHÂN C MỤ
Bài toán
T p đ i t Phân tách D thành các c mụ
ố ượ
ộ ụ
ự
ầ
ng trong m t c m: “t
ươ
ươ ng t ” nhau (g n nhau) ự
ng t ” nhau (xa nhau)
Các đ i t ố ượ Đ i t ươ
ậ ố ượ ng D = {d}
Đo “t
ộ ố ượ
ự
Tiên đ phân c m:
ng
ụ ng hai c m: “không t ầ ng t ” (g n) nhau ? ườ ế ụ N u ng ề ố ượ ọ ự ọ d thì h cũng l a ch n các đ i t ự
ộ ố ộ
ươ
ư
ớ d ố ượ
ụ ễ
ng
ủ
ườ
Đ a ra m t s đ đo “t ọ ự Khai thác “cách ch n l a” c a ng
ọ i dùng l a ch n m t đ i t ng cùng c m v i ể ng t ” theo bi u di n đ i t i dùng
ố ượ
ố ượ
ụ
ướ
ộ ạ D y b phân cum ồ ươ ộ ự ng đ ng Xây d ng đ đo t ổ Khai thác thông tin b sung ướ ụ S l
ng c m cho tr
c, s l
ng c m không cho tr
c
ự
Ụ
Ầ
YÊU C U PHÂN C M
Tính phù h pợ
ả
ụ
ệ t ợ
ệ ụ
ầ
ớ
ườ
ớ
ầ ạ ấ Cung c p s phân bi
t c m phù h p v i yêu c u ng
i dùng v i các
ả T o c m c n đ m b o tính phân bi ự ụ ợ c m không phù h p khác. ả ễ ọ T ng h p ph i d đ c ọ ắ ả
ủ
ụ
ng n g n và chính xác c a các c m
ủ ề
ỉ
ề ộ ụ
ộ
ng ch thu c v m t c m.
S d ng các m u thông tin
ỉ
ượ
c
ả
ố ượ
ợ ổ ấ Cung c p mô t Tính đa hình ề ố ượ ng nhi u ch đ Đ i t ế ộ ố ượ ạ Tránh h n ch m t đ i t ẩ ử ụ ả ạ ụ ươ Ph ng pháp ph i t o c m “t ờ ợ ệ ố Tránh ph i ch đ i h th ng t
ố ẩ t”: ch dùng m u thông tin có đ ộ ả i toàn b các đ i t
ng.
Phân ho chạ ạ
ậ
ậ
ố ư
Phân ho ch t p thành các t p con Đánh giá theo các tiêu chí T i u chung, kmean
Phân c pấ
ả
ấ
ừ
ậ S d ng ma tr n kho ng cách Xây d ng ki n trúc phân c p: t
ừ ướ d
i lên (
trên
Ộ Ố ƯƠ Ụ Ể M T S PH NG PHÁP PHÂN C M ĐI N HÌNH
AGNES) t
ử ụ ế ự ố DIANA) xu ng ( D a theo m t đ
ậ ộ
ự
ố ượ ố ể
ậ
ậ
ố
ể ở ộ
ậ
i thi u
m t lân c n
ậ ộ ự D a trên hàm m t đ các đ i t ng Lân c n, bán kính lân c n, s đi m t
D a theo l
ướ
ữ ệ
ề
ề
ượ
Ộ Ố ƯƠ Ụ Ể M T S PH NG PHÁP PHÂN C M ĐI N HÌNH
i đa chi u: mi n d li u đ
c chia thành
ấ
ộ
ự Xây d ng c u trúc l
ễ
ể
ộ
đ nh m t lo i mô hình bi u di n các c m
D a trên mô hình ạ ố
ụ ặ ố
ả ị ị
ấ ậ
ầ
Self Organization Matrix (SOM) ự Gi Xác đ nh tham s mô hình cho phép đ t t
t nh t t p c n phân
ụ
c m vào
ướ i ấ ự h p các c p
Ộ
Ụ
Đ ĐO TRONG PHÂN C M WEB
ứ
ộ ươ Đ đo t ồ ạ T n t ể Bi u di n đ i t
ồ ng đ ng ộ ố ộ i m t s đ đo, căn c vào ố ượ ễ ng: d=(d
1, d2, …, dn) vector
ể
M t s đ đo đi n hình
ộ ố ộ ả kho ng cách Minkowski (q=2: Kho ng cách Ơ ơ c lit)
wv (cid:0)
ả
ự ầ ơ ng t (g n nhau): cosin hai vect ặ ho c
ả ộ đ đo t ạ ượ đ i l ươ ng CoordLevel (q,d) vector b n
(cid:0)
CoordLevel
K
dq ,(
)
(
)
cos
q K
d
wv . wv .
(cid:0) (cid:0) (cid:0)
ƯƠ
Ụ
PH
Ậ NG PHÁP LU N PHÂN C M
ế
ạ
ậ
Ti p c n theo phân ho ch
ậ
ậ
ạ
Phân ho ch t p D thành k t p con {D
i}
ố ượ
ụ
ướ
ướ
S l
ng c m k cho tr
c / không cho tr
c
M c tiêu phân ho ch ả
ộ ộ ậ
ể ổ
ự
ặ
ạ ụ Ho c c c ti u t ng kho ng cách n i b t p con
ạ ổ
ặ
ươ
ự ộ ộ ậ
ự Ho c c c đ i t ng t
ng t
n i b t p con
ố ượ
Kh i l
ng tính toán
ộ ộ ộ ậ
ố ượ
ả
ộ
“N i b m t t p con”: toàn b kho ng cách ? Kh i l
ng
l nớ
ố ượ
ạ
ệ
ố ượ
ệ
ạ ng đ i di n
Thông qua đ i t ạ
ố ượ
ượ
Đ i t
ng đ i di n đ
ng đ i di n: Tính theo đ i t ổ ệ c thay đ i
ƯƠ
Ụ
PH
Ậ NG PHÁP LU N PHÂN C M
ế
ậ
Ti p c n theo hình h c
ọ ề
ề
ề
ế
ề
Quy chi u không gian nhi u chi u v hai chi u
ươ
Ph
ng pháp
selforganizing map ố ượ
ố
ố Phân b các đ i t
ng không gian g c vào không gian hai
chi uề ế
ườ
ươ
ấ
ự
ả
ậ ộ Đ đo t
ố i dùng cung c p
ượ ng c
Ti p c n theo mô hình sinh và th ng kê (kho ng cách) đ ẫ
ng t ộ
ố ượ
ộ
ố Sinh ra m t phân b ng u nhiên các đ i t
ng theo đ đo đã
cho
Ạ
PHÂN HO CH BOTTOMUP HAC
Phân c m tích lũy (Agglomerative)
ơ
ễ
ể
ụ
bottomup agglomerative hierarchical agglomerative clustering (HAC) ử ụ ậ
ở ộ
ố ượ d thành m t c m {
ệ ng hi n có) d}
ầ
ộ
2
ụ ọ Tên g i khác
kh i Gỏ
s
)(
)
dds ( , 1
2
)1
(
dd 1 ,
2
ổ
ộ s(d,q): đ đo cosin
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
: s((cid:0) ) t ng s h ng ạ
ặ
ầ ử ư
S d ng bi u di n vect ệ ậ Thu t toán (G: ký hi u cho t p các c m đ i t ộ ụ ỗ ố ượ ng Kh i đ ng: Gán m i đ i t ệ ặ ự Trong khi |G| > 1 th c hi n l p và (cid:0) ụ (cid:0) ộ ớ thu c G là “g n nhau” theo đ đo V i hai c m (cid:0) • Đ t ặ (cid:0) (cid:0) = (cid:0) và (cid:0) ạ ỏ (cid:0) • Lo i b ổ • B sung vào G ầ “hai c m g n nhau” ộ ộ ủ và (cid:0)
ố ạ ầ : c c đ i min và max g n nhau các c p ph n t
. L u ý
ụ ộ ầ ờ
ủ
ậ
ụ (cid:0) Đ đo n i b c a c m ự G n nhau th i gian tính toán: tính tăng c a thu t toán
(cid:0)
ự Ạ PHÂN HO CH TOPDOWN VÀ BOTTOMUP (xây d ng dendrogram)
Ậ
THU T TOÁN KMEAN
ớ
Gi
ỗ ụ
ủ ỗ ụ
đ i di n cho m i c m
ứ
ở ộ
ơ ọ
ụ c tr ng tâm cho các c m
ố ơ
ẫ t h n” v n còn
ớ
ầ d nh tấ
ớ
ạ ọ
ố ượ
i tr ng tâm theo theo các đ i t
ộ ng thu c nó
/*
ề
ệ Đi u ki n “làm t
ệ i thi u ứ ạ ọ D ng c ng: theo tr ng tâm c a m i c m ầ ử ạ ệ Theo ph n t ố ượ Đ i t 1, d2, …, dn) ng: d=(d ộ N i dung kmean c ng ọ Kh i đ ng: Ch n tùy ý các vect ệ ề */ Trong khi đi u ki n “làm t ọ ố ượ d ng V i m i đ i t • Tìm c m ụ c có tr ng tâm g n ọ • Gán d vào c m ụ c ọ ụ c V i m i c m • Tính toán l ố ơ t h n” ể
ố ượ
ừ ụ
ụ
ng t
c m này sang c m khác
ặ
ổ
• Không/chuy n ít đ i t ự • Ho c s thay đ i ít
ờ
ự
ệ
ậ
ọ
ơ ạ
ụ
Th i gian th c hi n ề Thu t toán kmean m m liên quan ch n vect
ệ đ i di n c m
ồ
H i quy (Regression)
Y1
Y1’
y
X1
y = x + 1
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
38
x
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ủ ử ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
39
ờ ạ ệ ế
ữ ệ
ợ
Tích h p d li u
Tích h p d li u (Data integration): ữ ệ ừ
ữ ệ
K t h p d li u t
ồ ư ề ộ ồ nhi u ngu n thành m t ngu n l u
ợ ế ợ ữ tr chung ợ Tích h p s đ
ữ ệ ừ
ấ ợ ề ị ồ các ngu n khác nhau ị ự ế t
(cid:0)
ồ ệ ế ấ
t nh t quá d li u ị ộ ồ ộ ề ự Cùng m t th c th th c s : giá tr thu c tính các ngu n
ơ ồ Tích h p sieu d li u t ể ự ế ừ ự V n đ đ nh danh th c th : xác đ nh th c th th c t ữ ệ ạ ẳ ứ B.cust# ngu n d li u ph c, ch ng h n, A.custid ữ ệ ế ấ ả Phát hi n và gi i quy t v n đ thi ể ự ự khác nhau là khác nhau
Nguyên nhân: trình bày khác nhau, c khác nhau, ố ế
ỡ
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
40
ẳ ạ ơ ớ ố ị ch ng h n, đ n v qu c t khác v i Anh qu c
ắ
ắ ư ừ
ữ ệ
ợ
N m b t d th a trong tích h p d li u (Handling Redundancy in Data Integration)
D th a d li u: th
ữ ệ ườ ợ ừ ề ồ ng có khi tích h p t nhi u ngu n
ư ừ khác nhau
M t thu c tính có nhi u tên khác nhau
ề ộ ộ ở các CSDL
khác nhau
M t thu c tính: thu c tính “ngu n g c” trong CSDL
ộ ồ ố
ộ ẳ ạ ộ khác, ch ng h n, doanh thu hàng năm
D li u d th a có th đwocj phát hi n khi phân tích
ư ừ ể ệ
ữ ệ ươ t ng quan
Tích h p c n tr ng d li u ngu n ph c giúp gi m/tránh ấ
ọ ữ ệ ứ ả ồ
ẩ ế ả ố ệ ấ ộ
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
41
ợ ư ừ d th a, thi u nh t quán và tăng hi u qu t c đ và ch t ngượ l
ữ ệ
ể
ạ Chuy n d ng d li u
Làm tr n (Smoothing): lo i b nhi u t
ạ ỏ ễ ừ ữ ệ ơ d li u
T ng h p (Aggregation): tóm t
ổ ợ ắ ố ữ ệ ự t, xây d ng kh i d li u
T ng quát hóa (Generalization): leo ki n trúc khái ni m
ế ệ ổ
Chu n hóa (Normalization): thu nh vào mi n nh , riêng
ề ẩ ỏ ỏ
Chu n hóa minmax
ẩ
Chu n hóa zscore
ẩ
ỷ ệ ậ ẩ Chu n hóa t th p phân l
ự ư ặ ộ Xây d ng thu c tính/đ c tr ng
Thu c tính m i đ
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
42
ớ ượ ộ ự ừ ộ c xây d ng t các thu c tính đã có
ổ ữ ệ
ể
ẩ
Chuy n đ i d li u: Chu n hóa
Chu n hóa minmax
ẩ
A
min
(cid:0)
A
A
A
v
new
max
new
min
new
min
'
(
_
_
)
_
(cid:0) (cid:0) (cid:0)
A
A
v max
min
(cid:0)
Chu n hóa zscore
ẩ
A
(cid:0)
v
'
A
dev
mean _
(cid:0)
v stand th p phân
ấ
ố
ỏ
j : s nguyên nh nh t mà Max(| |)<1
v
' (cid:0)
'v
j
v 10
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
43
ỷ ệ ậ ẩ Chu n hóa t l
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ử ủ ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
44
ờ ạ ệ ế
ế ượ
ữ ệ
ọ
c rút g n d li u Chi n l (Data Reduction Strategies)
ứ ớ ữ ệ Kho d li u ch a t
ấ
ạ
ấ
ờ
Phân tích/khai phá d li u ph c m t th i gian r t dài khi ch y trên
ộ ữ ệ
ậ t p toàn b d li u
ượ
ề
ề
ố
ọ
i hàng TB ứ ữ ệ
ỏ ơ ế
ầ
ả ng mà sinh ra cùng (ho c h u nh cùng) k t qu .
ủ ậ ặ ữ ệ c rút g n d li u
ữ ệ ữ ệ c trình bày g n c a t p d li u mà nh h n nhi u v kh i ư
ạ ỏ
ộ
ọ
ữ ệ
ố
d li u thành mô hình ệ
ả ờ ạ
T p h p kh i d li u Gi m đa chi u – lo i b thu c tính không quan tr ng ữ ệ Nén d li u Gi m tính s hóa – R i r c hóa và sinh cây khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
45
ọ Rút g n d li u Có đ ượ l ế ượ Chi n l ậ ợ ả ọ ố ữ ệ ề
ế ợ
ố ữ ệ
K t h p kh i d li u (Data Cube Aggregation)
ố ữ ệ ứ ấ ấ ủ M c th p nh t c a kh i d li u
T ng h p d li u thành m t cá th quan tâm
ữ ệ ể ổ ợ ộ
Ch ng h n, m t khách hàng trong kho d li u cu c g i
ữ ệ ộ ộ ọ
ẳ ệ ạ ạ đi n tho i.
Các m c ph c h p c a tích h p thành kh i d li u
ố ữ ệ ứ ứ ủ ợ ợ
Gi m thêm kích th
ả ướ ữ ệ c d li u
Tham kh o m c thích h p
ứ ả ợ
ấ ủ ể ả ử ụ ỏ ễ S d ng trình di n nh nh t đ đ gi i bài toán
Nên s d ng d li u kh i l p ph
ữ ệ ố ậ ươ ng khi tr l ả ờ âu h i ỏ i c
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
46
ử ụ ợ ổ t ng h p thông tin
ề
ọ Rút g n chi u
Rút g n đ c tr ng (nh ., l a ch n t p con thu c tính):
ọ ộ
ố ỏ ư ự ấ ặ ư ọ ậ
ị
ư ổ ố ị ủ
ư
ễ ẫ ậ ẫ ơ ể Rút g n # c a các m u trong t p m u d dàng h n đ
Ph
ự ượ ọ
ế ừ
ng mũ # phép ch n): ướ c ậ phía tr ạ ỏ ạ ể ế
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
47
ế ợ ọ ể ế ị ọ ậ ư ặ ự L a ch n t p nh nh t các đ c tr ng mà phân b xác ị ủ ớ ấ ủ su t c a các l p khác nhau cho giá tr khi cho giá tr c a ầ ớ các l p này g n nh phân b v n có đã cho giá tr c a ặ các đ c tr ng ọ ủ ữ ệ ể hi u d li u ươ ng pháp Heuristic (có l c l ọ Khôn ngoan ch n chuy n ti p t K t h p chon chuy n ti p và lo i b l c h u. Rút g n câu qyuy t đ nh
ụ
ế ị
ọ
Ví d rút g n cây quy t đ nh (Example of Decision Tree Induction)
ộ ậ ở ạ
T p thu c tính kh i t o: {A1, A2, A3, A4, A5, A6}
A4 ?
A6? A1?
Class 2 Class 2 Class 1 Class 1
> T p thu c tinh rút g n: {A1, A4, A6}
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
48
ậ ộ ọ
ế ị
ớ
Phân l p cây quy t đ nh
ồ ị ạ ỉ
ả ể
ớ ế
ươ
ứ
ạ i
ỉ
Đ th d ng cây ộ Đ nh trong là m t hàm test ng ng v i k t qu ki m tra t Các nhánh t đ nh trong
ặ
ớ
Các lá là các nhãn, ho c các l p.
ế ị
ớ
Phân l p cây quy t đ nh
ế ị
ớ
Phân l p cây quy t đ nh
ế ị
ớ
Phân l p cây quy t đ nh
ế ị
ự
Xây d ng cây quy t đ nh:
Xây d ng cây quy t đ nh
ự ươ
ế ị ng pháp topdown
C t t a cây (pruning)
Ph ắ ỉ Ph
ươ ữ ị ng pháp bottomup: xác đ nh và lo i b nh ng
ạ ỏ ớ
ố ượ
ớ
ng
ượ
ữ ộ ườ nhánh r m rà tăng đ chính xác khi phân l p ố ượ nh ng đ i t
ử ụ ư ch a đ
ớ ng m i ế ị S d ng cây quy t đ nh: phân l p các đ i t c gán nhãn
ươ
ư
ọ
Ph
ặ ng pháp ch n đ c tr ng Heuristic
ậ ặ ư
ư t đ c l p đ c tr ng: ư ư ế ộ ậ thi
ừ ấ ượ t nh t đ
ướ ố ấ c t t nh t: ầ ọ c ch n đ u tiên ề ệ ơ ố t nh t ti p theo theo đi u ki n đã
ấ ế c đó, ...
ế ọ ố ch n t ạ ỏ ặ ướ c:
ạ ỏ ặ ư ặ
ặ ừ d đ c tr ng Có 2d t p con đ c tr ng t ộ ự ọ ươ ng pháp ch n dad c tr ng heuristic: M t vài ph ố ặ ả ư ặ ấ Các đ c tr ng t tnh t theo gi ử ể ọ ừ ể ch n t ki m th đi n hình. ặ ự ư ọ L a ch n đ c tr ng khôn ngoan t ng b ộ Các thu c tính đ n t ọ ố Ti p đó, ch n t ấ ướ t nh t tr ừ ư Lo i b đ c tr ng khôn ngoan t ng b ấ ồ i nh t Lo i b l p các đ c tr ng t ấ ạ ỏ ố ọ ế ợ ự K t h p l a ch n và lo i b t t nh t: ạ Nhánh và ph m vi t i u:
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
53
ử ụ ư ọ ố ư ạ ỏ ặ S d ng lo i b đ c tr ng và tùy ch n
ữ ệ
Nén d li u (Data Compression)
Nén xâu (String compression)
ủ ề ậ ỉ ố i lý thuy t đ y đ và thu t toán đi u ch nh t t
ng
ế ầ ườ ạ ượ ở ộ ế ầ ng h n ch thao tác không c n m r ng
ồ ạ T n t ấ M t mát thông th Cho phép l Nén Audio/video
ấ ể ớ
ế ế ể ộ ự ạ ạ i mà
Nén m t mát đi n hình, v i tinh ch ti n b ỏ Đôi khi các đo n nh tín hi u có th xây d ng l ạ không c n xây d ng l ả
ự ầ ộ
ệ i toàn b Dãy th i gian không ph i là audio
Ng n đi n hình và ch m theo th i gian
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
54
ể ậ ờ ờ ắ
ữ ệ
Nén d li u (Data Compression)
ữ ệ ự D li u th c (Original Data)
á t l o s s y
ượ DL đ c nén Compressed Data ỡ ấ Đ m t mát lossless
t m
ấ
M
ữ ệ ự ượ ấ D li u th c đ ỉ c x p x
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
55
Original Data Approximated
ể
ạ
Chuy n d ng sóng (Wavelet Transformation)
Daubechie4
Haar2 Discrete wavelet transform (DWT): linear signal
Compressed approximation: store only a small fraction of
processing, multiresolutional analysis
Similar to discrete Fourier transform (DFT), but better
the strongest of the wavelet coefficients
Method:
Length, L, must be an integer power of 2 (padding with 0s, when
necessary)
Each transform has 2 functions: smoothing, difference
Applies to pairs of data, resulting in two set of data of length L/2
Applies two functions recursively, until reaches the desired length
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
56
lossy compression, localized in space
DWT cho nén nhả
Image
Low Pass High Pass
Low Pass High Pass
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
57
Low Pass High Pass
ầ
Phân tích thành ph n chính (Principal Component Analysis )
Cho N vector d li u
ề c (<= k) vector tr c ự
ấ ể ữ ệ ố ữ ệ kchi u, tìm ễ t nh t đ trình di n d li u. giao t
ữ ệ ậ c rút g n thành N vector d li u c
ượ ọ ượ ữ ệ T p d li u g c đ ầ ọ ề (chi u đ c rút g n).
M i vector d li u là t ầ thành ph n chính.
ủ ế ố chi u: ề c thành ph n chính ỗ ổ ợ ữ ệ h p tuy n tính c a các vector
Ch áp d ng cho d li u s
ữ ệ ụ ỉ
Dùng khi s chi u vector l n.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
58
ề ố ố. ớ
ầ
Phân tích thành ph n chính (PCA)
X2
Y1
Y2
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
59
X1
ọ
ướ
ố
Rút g n kích th
c s
Ph
Assume the data fits some model, estimate model
ươ ố ng pháp tham s
Loglinear models: obtain value at a point in mD space as the product on appropriate marginal subspaces
Nonparametric methods
Do not assume models
Major families: histograms, clustering, sampling
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
60
parameters, store only the parameters, and discard the data (except possible outliers)
ế
ồ
H i quy và mô hình logarit tuy n tính
Linear regression: Data are modeled to fit a straight line
Often uses the leastsquare method to fit the line
Multiple regression: allows a response variable Y to be
modeled as a linear function of multidimensional feature
Loglinear model: approximates discrete
vector
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
61
multidimensional probability distributions
ế
ồ
Phân tích h i quy và mô hình logarit tuy n tính
Linear regression: Y = (cid:0) + (cid:0) X
Two parameters , (cid:0)
and (cid:0) specify the line and are to
using the least squares criterion to the known values of
be estimated by using the data at hand.
Multiple regression: Y = b0 + b1 X1 + b2 X2.
Many nonlinear functions can be transformed into the
Y1, Y2, …, X1, X2, ….
Loglinear models:
The multiway table of joint probabilities is
above.
Probability: p(a, b, c, d) = (cid:0) ab (cid:0) ac(cid:0) ad (cid:0) bcd
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
approximated by a product of lowerorder tables.
ượ
ồ
L
c đ (Histograms)
technique
20
40 A popular data reduction 35 Divide data into buckets 30 and store average (sum) 25 for each bucket Can be constructed optimally in one 15 dimension using dynamic programming 10
Related to quantization
5
problems.
0
10000
50000
70000
90000
ữ ệ
ữ ệ
Kho d li u và khai phá d li u: Ch
30000 ươ ng 2
November 4, 2015
63
Phân c mụ
Partition data set into clusters, and one can store
Can be very effective if data is clustered but not if data
cluster representation only
Can have hierarchical clustering and be stored in multi
is “smeared”
There are many choices of clustering definitions and
dimensional index tree structures
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
64
clustering algorithms
ẫ
ọ
Rút g n m u (Sampling)
Allow a mining algorithm to run in complexity that is
Simple random sampling may have very poor
potentially sublinear to the size of the data Choose a representative subset of the data
Develop adaptive sampling methods
Stratified sampling:
Approximate the percentage of each class (or
performance in the presence of skew
Used in conjunction with skewed data
Sampling may not reduce database I/Os (page at a time).
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
65
subpopulation of interest) in the overall database
ọ
ẫ Rút g n m u (Sampling)
(
a n d o m t h o u t )
s
S R S W O R r i m p l e a m p l e w i e m e n t s c e p l a
r
SRSWR
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
66
Raw Data
ẫ
ọ
Rút g n m u (Sampling)
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
67
Cluster/Stratified Sample Raw Data
ấ
ọ
Rút g n phân c p
Use multiresolution structure with different degrees of
Hierarchical clustering is often performed but tends to define partitions of data sets rather than “clusters” Parametric methods are usually not amenable to
reduction
Hierarchical aggregation
An index tree hierarchically divides a data set into
hierarchical representation
ữ ệ
ữ ệ
partitions by value range of some attributes Each partition can be considered as a bucket Thus an index tree with aggregates stored at each
ng 2
November 4, 2015
68
node is a hierarchical histogram ươ Kho d li u và khai phá d li u: Ch
ữ ệ
ử
ề Chapter 2: Ti n x lý d li u
Hi u d li u và chu n b d li u
ị ữ ệ ữ ệ ể ẩ
ữ ệ ủ ử ề Vai trò c a ti n x lý d li u
ữ ệ ạ Làm s ch d li u
Tích h p và chuy n d ng d li u
ữ ệ ể ạ ợ
ữ ệ ọ Rút g n d li u
R i r c và sinh ki n trúc khái ni m
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
69
ờ ạ ế ệ
ờ ạ
R i r c hóa
Three types of attributes:
Nominal — values from an unordered set Ordinal — values from an ordered set Continuous — real numbers
Discretization:
divide the range of a continuous attribute into
Some classification algorithms only accept
intervals
Reduce data size by discretization Prepare for further analysis
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
70
categorical attributes.
ờ ạ
ệ
ế R i r c hóa và ki n trúc khái ni m
Discretization
reduce the number of values for a given continuous attribute by dividing the range of the attribute into intervals. Interval labels can then be used to replace actual data values
Concept hierarchies
reduce the data by collecting and replacing low level concepts (such as numeric values for the attribute age) by higher level concepts (such as young, middle aged, or senior)
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
71
ệ
ế
ờ ạ ớ ữ R i r c hóa và ki n trúc khái ni m v i d ố li u sệ
Binning (see sections before)
Histogram analysis (see sections before)
Clustering analysis (see sections before)
Entropybased discretization
Segmentation by natural partitioning
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
72
ờ ạ
ự R i r c hóa d a trên Entropy
Given a set of samples S, if S is partitioned into two
|
|
|
Ent
Ent
E S T ( ,
)
(
(
)
S
S
) 1
2
S | 1 S | |
S 2 S | |
The boundary that minimizes the entropy function over all possible boundaries is selected as a binary discretization.
The process is recursively applied to partitions obtained
(cid:0)
intervals S1 and S2 using boundary T, the entropy after partitioning is (cid:0) (cid:0)
E T S (
)
,
Experiments show that it may reduce data size and
(cid:0) (cid:0) until some stopping criterion is met, e.g., Ent S ( )
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
73
improve classification accuracy
ạ
ạ
ằ
ự
Phân đo n b ng phân ho ch t
nhiên
ắ ả ượ ữ ệ ể ạ ơ Quy t c đ n gi n 345 đ c dùng đ phân đo n d li u
ạ ươ ấ ố ự ố s thành các đo n t ố ng đ i th ng nh t, “t nhiên”.
ớ ố ọ ướ H ng t ị i s giá tr khác bi ệ ở t ấ vùng quan tr ng nh t
ế ị ệ ề ặ N u 3, 6, 7 ho c 9 giá tr khác bi t thì chia mi n thành
ạ ươ ươ 3 đo n t ng đ ng.
N u ph 2, 4, ho c 8 giá tr phân bi
ủ ế ặ ị ệ t thì chia thành 4.
ữ ệ
ữ ệ
ươ
Kho d li u và khai phá d li u: Ch
ng 2
November 4, 2015
74
ủ ế ị ệ ặ N u ph 1, 5, ho c 10 giá tr phân bi t thì chia thành 5.
ụ ậ
Ví d lu t 345
count
$351
$159
profit
$1,838
$4,700
Step 1:
Min Low (i.e, 5%tile)
High(i.e, 95%0 tile) Max
Step 2:
msd=1,000
Low=$1,000
High=$2,000
($1,000 $2,000)
Step 3:
($1,000 0)
($1,000 $2,000)
(0 $ 1,000)
($4000 $5,000)
Step 4:
($2,000 $5, 000)
($1,000 $2, 000)
($400 0)
(0 $1,000)
(0 $200)
($1,000 $1,200)
($400 $300)
($2,000 $3,000)
($200 $400)
($1,200 $1,400)
($300 $200)
($3,000 $4,000)
($1,400 $1,600)
($400 $600)
($200 $100)
($4,000 $5,000)
($600 $800)
($1,600 $1,800)
ữ ệ
ữ ệ
($1,800 $2,000) ươ
($800 $1,000) Kho d li u và khai phá d li u: Ch
ng 2
($100 0) November 4, 2015
75
ữ ẹ
ế
ệ
ạ Sinh ki n trúc khái ni m cho d li u phân lo i
ị ứ m t th t b ph n giá tr thu c tính theo m c
ậ ặ ộ ứ ự ộ i dùng ho c chuyên gias
Đ c t
Đ c t
ờ ấ ữ ệ thành c u trúc phân c p nh nhóm d li u
ộ ộ ậ ắ ằ
ặ ả ộ
Đ c t
ườ
ơ ồ
s đ do ng
street Đ c t ậ b ph n ữ ệ ữ ệ ươ Kho d li u và khai phá d li u: Ch ng 2 November 4, 2015 76 ỉ theo t p các thu c tính.
ế
ị
Nh ,ư street < city Some concept hierarchies can be automatically generated based on the analysis of the number of
distinct values per attribute in the given data set
The attribute with the most distinct values is placed Note: Exception—weekday, month, quarter, year at the lowest level of the hierarchy 15 distinct values country province_or_ state 65 distinct
values
3567 distinct values city ữ ệ ữ ệ ươ Kho d li u và khai phá d li u: Ch ng 2 November 4, 2015 77 674,339 distinct values streetệ
ế
ự ộ
Sinh ki n trúc khái ni m t
đ ng
