Bài giảng Kho dữ liệu và kinh doanh thông minh - Chương 5: Khai phá dữ liệu trong kinh doanh

ction, data/pattern analysis, data archeology, data dredging, information harvesting, business intelligence Data Warehouse and Business Intelligence 5 1.2. Quá trình khám phá tri thức Data Cleaning Data Integration Data Sources Data Warehouse Task-relevant Data Selection/Transformation Data Mining Pattern Evaluation/ Presentation Patterns Data Warehouse and Business Intelligence 6 1.3 Khai phá dữ liệu trong kinh doanh thông minh Increasing potential to support business decisions End User Business Analyst Data Analyst DBA Decision Making Data Presentation Visualization Techniques Data Mining Information Discovery 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 7 1.4 Quá trình khám phá tri thức Input Data Data Mining Data Pre- Processing Post- Processing • This is a view from typical machine learning and statistics communities Data integration Normalization Feature selection Dimension reduction Pattern discovery Association & correlation Classification Clustering Outlier analysis Pattern evaluation Pattern selection Pattern interpretation Pattern visualization Data Warehouse and Business Intelligence 8 1.5 Các lĩnh vực có ảnh hưởng đến khai phá dữ liệu Data Mining Machine Learning Statistics Applications Algorithm Pattern Recognition High-Performance Computing Visualization Database Technology Data Warehouse and Business Intelligence 9 1.5 Các lĩnh vực có ảnh hưởng đến khai phá dữ liệu  Học máy (Machine Learning)  Học có giám sát (Supervised learning)  Học không có giám sát (Unsupervised learning)  Học bán giám sát (Semi-supervised learning)  Học tích cực (Active learning) Data Warehouse and Business Intelligence 10 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 11 2.1 Khái niệm cơ sở: Tập phổ biến và luật kết hợp  Một số ví dụ về “luật kết hợp” (associate rule) • “98% khách hàng mà mua tạp chí thể thao thì đều mua các tạp chí về ôtô”  sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô” • “60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em”  sự kết hợp giữa “bia” với “bỉm trẻ em” • “Có tới 70% người truy nhập Web vào địa chỉ Url 1 thì cũng vào địa chỉ Url 2 trong một phiên truy nhập web”  sự kết hợp giữa “Url 1” với “Url 2”. Khai phá dữ liệu sử dụng Web (Dữ liệu từ file log của các site, chẳng hạn được MS cung cấp). • Các Url có gắn với nhãn “lớp” là các đặc trưng thì có luật kết hợp liên quan giữa các lớp Url này. Data Warehouse and Business Intelligence 12 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 14 Độ đ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 Sum (row) Cereal 2000 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 2000 5000 )()( )( , BPAP BAP corr BA   Data Warehouse and Business Intelligence 15 2.1 Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp 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 Customer buys diaper Customer buys both Customer buys beer  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. 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 Data Warehouse and Business Intelligence 16 Một ví dụ tìm luật kết hợp Với luật A  C: support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) = 66.6% Min. support 50% Min. confidence 50% Transaction-id Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F Frequent pattern Support {A} 75% {B} 50% {C} 50% {A, C} 50% Data Warehouse and Business Intelligence 17 Mẫu đóng (Closed Patterns) và mẫu cực đại (Max-Patterns)  A long pattern contains a combinatorial number of sub- patterns, e.g., {a1, , a100} contains (100 1) + (100 2) + + (1 1 0 0 0 0) = 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 18 Closed Patterns and Max-Patterns Exercise. DB = {, }  Min_sup = 1. What is the set of closed itemset?  : 1  : 2 What is the set of max-pattern?  : 1 What is the set of all patterns?  !! Data Warehouse and Business Intelligence 19 2.1. Khái niệm khai phá kết hợp Data Warehouse and Business Intelligence 20 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 21 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 22 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 23 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 24 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 25 2.1 Giải thuật Apriori Data Warehouse and Business Intelligence 26 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 27 2.2 Giải thuật Apriori:Thủ tục con Apriori-gen Data Warehouse and Business Intelligence 28 Một ví dụ thuật toán Apriori (s=0.5) Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 Data Warehouse and Business Intelligence 29 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 30 Ví dụ: D, min_sup*|D| = 2 (C4 = ) Data Warehouse and Business Intelligence 31 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 32 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 (hash- tree)  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 33 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 34 Ví dụ: Tính độ hỗ trợ các ứng viên 1,4,7 2,5,8 3,6,9 Hàm tập con 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 4 5 7 1 2 5 4 5 8 1 5 9 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 Transaction: 1 2 3 5 6 1 + 2 3 5 6 1 2 + 3 5 6 1 3 + 5 6 Data Warehouse and Business Intelligence 35 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 36 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 37 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  abcd là một mẫu phổ biến Data Warehouse and Business Intelligence 38 Xây dựng FP-tree từ một CSDL giao dịch {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 1. Duyệt CSDL một lần, tìm các 1-tập phổ biến (mẫu mục đơn) 2. Sắp xếp các mục phổ biến theo thứ tự giảm dần về bậc, F-list 3. Duyệt CSDL lần nữa, xây dựng FP-tree F-list=f-c-a-b-m-p Từ FP-tree tìm luật kết hợp Data Warehouse and Business Intelligence 41 Data Warehouse and Business Intelligence 43 Partition Patterns and Databases Frequent patterns can be partitioned into subsets according to f-list  F-list = f-c-a-b-m-p  Patterns containing p  Patterns having m but no p   Patterns having c but no a nor b, m, p  Pattern f Completeness and non-redundency Data Warehouse and Business Intelligence 44 Find Patterns Having P From P-conditional Database  Starting at the frequent item header table in the FP-tree  Traverse the FP-tree by following the link of each frequent item p  Accumulate all of transformed prefix paths of item p to form p’s conditional pattern base Conditional pattern bases item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 Data Warehouse and Business Intelligence 45 From Conditional Pattern-bases to Conditional FP-trees For each pattern-base  Accumulate the count for each item in the base  Construct the FP-tree for the frequent items of the pattern base m-conditional pattern base: fca:2, fcab:1 {} f:3 c:3 a:3 m-conditional FP-tree All frequent patterns relate to m m, fm, cm, am, fcm, fam, cam, fcam   {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 Data Warehouse and Business Intelligence 46 Recursion: Mining Each Conditional FP-tree {} f:3 c:3 a:3 m-conditional FP-tree Cond. pattern base of “am”: (fc:3) {} f:3 c:3 am-conditional FP-tree Cond. pattern base of “cm”: (f:3) {} f:3 cm-conditional FP-tree Cond. pattern base of “cam”: (f:3) {} f:3 cam-conditional FP-tree Data Warehouse and Business Intelligence 47 A Special Case: Single Prefix Path in FP-tree Suppose a (conditional) FP-tree T has a shared single prefix-path P Mining can be decomposed into two parts  Reduction of the single prefix path into one node  Concatenation of the mining results of the two parts  a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 + a2:n2 a3:n3 a1:n1 {} r1 = Data Warehouse and Business Intelligence 48 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 49 Thuật toán Apriori— Ví dụ TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. {1} 2 {2} 3 {3} 3 {4} 1 {5} 3 itemset sup. {1} 2 {2} 3 {3} 3 {5} 3 Scan D C1 L1 itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2 itemset sup {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 L2 C2 C2 Scan D C3 L3 itemset {2 3 5} Scan D itemset sup {2 3 5} 2 min_support=30% Mã số giao dịch Danh sách các mặt hàng 1 I1, I4 2 I1, I2, I5 3 I2, I3, I4, I6 4 I2, I3, I4, I5 5 I1, I3, I5, I6 6 I2, I3, I4, I5, I6 7 I2,I4, I5 8 I2, I3, I5 9 I2, I3, I4, I6 10 I1, I2, I3, I5 Data Warehouse and Business Intelligence 53 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 54 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 55 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 56 Pha 1: Xây dựng mô hình Training Data NAME RANK YEARS TENURED Mike Assistant Prof 3 no Mary Assistant Prof 7 yes Bill Professor 2 yes Jim Associate Prof 7 yes Dave Assistant Prof 6 no Anne Associate Prof 3 no Classification Algorithms IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’ Classifier (Model) Data Warehouse and Business Intelligence 57 Pha 2: Sử dụng mô hình Classifier Testing Data NAME RANK YEARS TENURED Tom Assistant Prof 2 no Merlisa Associate Prof 7 no George Professor 5 yes Joseph Assistant Prof 7 yes Unseen Data (Jeff, Professor, 4) Tenured? Data Warehouse and Business Intelligence 61 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 62 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) C1 ¬ C1 Lớp thật (Actual class) C1 True Positives (TP) False Negatives (FN) ¬ C1 False Positives (FP) True Negatives (TN) Data Warehouse and Business Intelligence 63 Estimating accuracy with the holdout method Data Warehouse and Business Intelligence 65 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 66 3.4 Đánh giá mô hình phân lớp: Đánh giá phân lớp nhị phân  Độ chính xác của bộ phân lớp (Classifier Accuracy): Acc𝑢𝑟𝑎𝑐𝑦 = 𝑇𝑃+𝑇𝑁 𝐴𝑙𝑙  Tỉ lệ lỗi (Error rate): 𝐸𝑟𝑟𝑜𝑟 𝑟𝑎𝑡𝑒 = 𝐹𝑃 + 𝐹𝑁 𝐴𝑙𝑙 = 1 − 𝑎𝑐𝑐𝑢𝑟𝑎𝑐𝑦  Sensitivity: True Positive recognition rate 𝑆𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 = 𝑇𝑃 𝑃  Specificity: True Negative recognition rate 𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 = 𝑇𝑁 𝑁 66 A\P C ¬C C TP FN P ¬C FP TN N P’ N’ All  Dùng độ chính xác (Accuracy), tỉ lệ lỗi (Error rate), Độ nhạy (Sensitivity) và độ đặc trưng (Specificity) Data Warehouse and Business Intelligence 67 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 71 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) Lớp Ci Giá trị qua bộ phân lớp đa lớp Thuộc lớp Ci Không thuộc lớp Ci Giá trị thực Thuộc lớp Ci TPi FNi Không thuộc lớp Ci FPi TNi Data Warehouse and Business Intelligence 72 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: ii i i FPTP TP  Pr ii i i FNTP TP  Re Data Warehouse and Business Intelligence 73 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 )( 1 1       K c cc K c c FPTP TP  )( 1 1       K c cc K c c FNTP TP     K c c M K 1 1     K c c M K 1 1  Data Warehouse and Business Intelligence 74 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 75 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 76 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 77 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 78 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 79 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 80 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 81 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 82 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 83 3.5.1 Phân lớp với cây quyết định Độ đo Information Gain  Lượng thông tin cần để phân loại một phần tử trong D (= Entropy của D): Info(D) • pi: xác suất để một phần tử bất kỳ trong D thuộc về lớp Ci với i = 1..m • Ci,D: tập các phần tử của lớp Ci trong D || || )(log)( , 2 1 D C p ppDInfo Di i i m i i     Data Warehouse and Business Intelligence 84 3.5.1 Phân lớp với cây quyết định  Độ đo Information Gain  Lượng thông tin cần để phân loại một phần tử trong D dựa trên thuộc tính A: InfoA(D) • Thuộc tính A dùng phân tách D thành v phân hoạch {D1, D2, , Dj, , Dv}. • Mỗi phân hoạch Dj gồm |Dj| phần tử trong D. • Lượng thông tin này sẽ cho biết mức độ trùng lắp giữa các phân hoạch, nghĩa là một phân hoạch chứa các phần tử từ một lớp hay nhiều lớp khác nhau. • Mong đợi: InfoA(D) càng nhỏ càng tốt. )(* || || )( 1 j v j j A DInfo D D DInfo    Data Warehouse and Business Intelligence 86 3.5.1 Phân lớp với cây quyết định Độ đo Information Gain  Information gain chính là độ sai biệt giữa trị thông tin Info(D) ban đầu (trước phân hoạch) và trị thông tin mới InfoA(D) (sau phân hoạch với A). )()()( DInfoDInfoAGain A Data Warehouse and Business Intelligence 87 3.5.1 Phân lớp với cây quyết định Gain(age)=0.246 bits Gain(income)? Gain(student)? Gain(credit_rating)?  Splitting attribute? Gain(income)= 0.029 bits, Gain(student)= 0.151 bits Gain(credit_rating)= 0.048 bits Data Warehouse and Business Intelligence 88 3.5.1 Phân lớp với cây quyết định  Độ đo Gain Ratio: GainRatio(A)  Dùng với C4.5  Giải quyết vấn đề một thuộc tính được dùng tạo ra rất nhiều phân hoạch (thậm chí mỗi phân hoạch chỉ gồm 1 phần tử).  Chuẩn hoá information gain với trị thông tin phân tách (split information): SplitInfoA(D)  Thuộc tính phân tách (Splitting attribute): A tương ứng với trị GainRatio(A) là trị lớn nhất. )( )( )( || || log || || )( 2 1 DSplitInfo AGain AGainRatio D D D D DSplitInfo A j v j j A           Data Warehouse and Business Intelligence 89 Data Warehouse and Business Intelligence 90 3.5.1 Phân lớp với cây quyết định  Độ đo Gini Index  Dùng với CART  Sự phân tách nhị phân (binary split) cho mỗi thuộc tính A • A  SA? • SA là một tập con gồm một hay v-1 trị thuộc tính A.  Gini index của một thuộc tính là trị nhỏ nhất tương ứng với một tập con SA từ 2 v – 2 tập con.  Splitting attribute tương ứng với gini index nhỏ nhất để tối đa hóa sự suy giảm về độ trùng lắp giữa các phân hoạch. )()()( )( || || )( || || )( 1 21)( 2 2 1 1 DginiDginiAgini Dgini D D Dgini D D Dgini n j p jDgini A A      Data Warehouse and Business Intelligence 91 3.5.1 Phân lớp với cây quyết định Giniincome{low,high} = ? Giniincome{medium} = ? Giniincome{medium,high} = ? Giniincome{low} = ?  Giniincome {medium,high}/{low}= ? Giniage {youth,senior}/{middle_aged} = ? Ginistudent= ? Ginicredit_rating= ?  Splitting attribute? Data Warehouse and Business Intelligence 92 3.5.1 Phân lớp với cây quyết định Xây dựng cây quyết định từ cơ sở dữ liệu huấn luyện  Dùng độ đo Information Gain  Dùng độ đo Gain Ratio  Dùng độ đo Gini Index Các cây quyết định học được giống nhau ??? Tiến hành đánh giá và phân loại với các cây quyết định học được Data Warehouse and Business Intelligence 93 3.5.2 Phân lớp Bayes Định lý Bayes  P(H|X): • Xác suất có điều kiện của H đối với X. • Ví dụ: P(buys_computer=yes|age=young, income=high) là xác suất mua máy tính của khách hàng có tuổi “young” và thu nhập “high”.  P(X|H): • Xác suất có điều kiện của X đối với H. • Ví dụ: P(age=young, income=high|buys_computer=yes) là xác suất khách hàng mua máy tính có tuổi “young” và thu nhập “high”. • P(age=young, income=high|buys_computer=yes) = 0 • P(age=young, income=high|buys_computer=no) = 2/5 = 0.4 Data Warehouse and Business Intelligence 94 3.5.2 Phân lớp Bayes age income student credit_rating buys_computer 1 <=30 high no fair no 2 <=30 high no excellent no 3 3140 high no fair yes 4 >40 medium no fair yes 5 >40 low yes fair yes 6 >40 low yes excellent no 7 3140 low yes excellent yes 8 <=30 medium no fair no 9 <=30 low yes fair yes 10 >40 medium yes fair yes 11 <=30 medium yes excellent yes 12 3140 medium no excellent yes 13 3140 high yes fair yes 14 >40 medium no excellent no Data Warehouse and Business Intelligence 95 3.5.2 Phân lớp Bayes Định lý Bayes  P(H): prior probability • Xác suất của H • Ví dụ: P(buys_computer=yes) là xác suất mua máy tính của khách hàng nói chung. • P(buys_computer=yes) = 9/14 = 0.643 • P(buys_computer=no) = 5/14 = 0.357  P(X): prior probability • Xác suất của X • Ví dụ: P(age=young, income=high) là xác suất khách hàng có tuổi “young” và thu nhập “high”. • P(age=young, income=high) = 2/14 = 0.143 Data Warehouse and Business Intelligence 96 3.5.2 Phân lớp Bayes Định lý Bayes  P(H), P(X|H), P(X) có thể được tính từ tập dữ liệu cho trước.  P(H|X) được tính từ định lý Bayes. )( )()|( )|( XP HPHXP XHP  P(buys_computer=yes|age=young, income=high) = ? P(buys_computer=no|age=young, income=high) = ? Data Warehouse and Business Intelligence 97 3.5.2 Phân lớp Bayes Cho trước tập dữ liệu huấn luyện D với mô tả (nhãn) của các lớp Ci, i=1..m, quá trình phân loại một tuple/đối tượng X = (x1, x2, , xn) với mạng Bayesian như sau:  X được phân loại vào Ci nếu và chỉ nếu P(Ci|X) > P(Cj|X) với 1i  Tối đa hóa P(Ci|X) (i.e. chọn Ci nếu P(Ci|X) là trị lớn nhất)  Tối đa hóa P(X|Ci)P(Ci) • P(C1) = P(C2) = .. = P(Cm) hoặc P(Ci) = |Ci,D|/|D| )( )()|( )|( XP CPCXP XCP iii  Data Warehouse and Business Intelligence 98 3.5.2 Phân lớp Bayes P(X|Ci) được tính với giả định class độc lập điều kiện. xk, k = 1..n: trị thuộc tính Ak của X P(Xk|Ci) được tính như sau:  Ak là thuộc tính rời rạc. • P(xk|Ci) = |{X’|x’k = xk  X’  Ci}|/|Ci,D|  Ak là thuộc tính liên tục. • P(xk|Ci) tuân theo một phân bố xác suất nào đó (ví dụ: phân bố Gauss). )|(*..*)|(*)|()|()|( 21 1 inii n k iki CxPCxPCxPCxPCXP   Data Warehouse and Business Intelligence 100 3.5.2 Phân lớp Bayes C1 = {X’|X’.buys_computer = yes} C2 = {X’’|X’’.buys_computer = no}  X  C1 Data Warehouse and Business Intelligence 101 Xác định phân lớp cho X X={age=senior, income=high, student=no, credit_rating=fair} P(age=senior|buy=yes)=3/9 P(income=high|buy=yes)=2/9 P(student=no|buy=yes)=3/9 P(credit_rating=fair|buy=yes)=6/9 P(age=senior|buy=no)=2/5 P(income=high|buy=no)=2/5 P(student=no|buy=no)=4/5 P(credit_rating=fair|buy=no)=2/5 P(buy=yes)=9/14 P(buy=no)=5/14 -->P(X|buy=yes)P(buy=yes) ? P(X|buy=no)P(buy=no) ? Data Warehouse and Business Intelligence 102 3.5.3 Một số phương pháp phân lớp dữ liệu khác Phân lớp dữ liệu với mạng Neural Phân lớp dữ liệu k-láng giềng gần nhất (k-nearest neighbor hay K-NN) 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) Data Warehouse and Business Intelligence 103 3.5.3 Phân lớp dữ liệu với mạng Neural Mạng Neural sinh học Data Warehouse and Business Intelligence 104 3.5.3 Một số phương pháp phân lớp dữ liệu khác: Mạng Neural Quá trình xử lý thông tin tại một neuron của mạng Neural nhân tạo Data Warehouse and Business Intelligence 105 3.5.3 Một số phương pháp phân lớp dữ liệu khác: Phân loại k-nn Unknown record  Phân loại k-nn (k-nearest neighbor)  Cho trước tập dữ liệu huấn luyện D với các lớp, phân loại record/object X vào các lớp dựa vào k phần tử tương tự với X nhất (dùng luật số đông: majority vote)  Phụ thuộc • Độ đo khoảng cách để xác định sự tương tự. • Trị k, số phần tử láng giềng  k <= |D|1/2 Data Warehouse and Business Intelligence 106 3.5.3 Một số phương pháp phân lớp dữ liệu khác: Phân loại k-nn Chọn độ đo  Độ đo Euclidean Chọn trị k  Nếu k quá nhỏ thì kết quả dễ bị ảnh hưởng bởi nhiễu.  Nếu k quá lớn thì nhiều phần tử láng giềng chọn được có thể đến từ các lớp khác.   i ii qpqpd 2)(),( Xk quá lớn! Data Warehouse and Business Intelligence 107 3.5.3 Một số phương pháp phân lớp dữ liệu khác: Phân loại k-nn X X X (a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor X  MINUS X  MINUS hay X  PLUS ? X  PLUS Data Warehouse and Business Intelligence 108 4. Phân cụm dữ liệu 4.1 Tổng quan 4.2 Các yêu cầu tiêu biểu 4.2 Các cách tiếp cận tiêu biểu 4.3 Các phương pháp đánh giá việc phân cụm dữ liệu 4.4 Thuật toán k-mean Data Warehouse and Business Intelligence 109 age income student credit_rating buys_computer 1 <=30 high no fair ? 2 <=30 high no excellent ? 3 3140 high no fair ? 4 >40 medium no fair ? 5 >40 low yes fair ? 6 >40 low yes excellent ? 7 3140 low yes excellent ? 8 <=30 medium no fair ? 9 <=30 low yes fair ? 10 >40 medium yes fair ? 11 <=30 medium yes excellent ? 12 3140 medium no excellent ? 13 3140 high yes fair ? 14 >40 medium no excellent ? Data Warehouse and Business Intelligence 110 4.1 Tổng quan Cụm (Cluster): Một tập hợp các đối tượng dữ liệu  Tương tự (hoặc có liên hệ) đối với những đối tượng khác trong cùng nhóm  Không tương tự (hoặc không có liên hệ) đối với những đối tượng thuộc các nhóm khác Phân tích cụm - cluster analysis (hoặc gom cụm- clustering, data segmentation, ) tìm những dữ liệu tương tự phụ thuộc vào những đặc tính được tìm thấy trong dữ liệu và nhóm những đối tượng tương tự vào các cụm. Data Warehouse and Business Intelligence 111 4.1. Các yêu cầu tiêu biểu  Khả năng co giãn về tập dữ liệu (scalability)  Khả năng xử lý nhiều kiểu thuộc tính khác nhau (different types of attributes)  Khả năng khám phá các cụm với hình dạng tùy ý (clusters with arbitrary shape)  Tối thiểu hóa yêu cầu về tri thức miền trong việc xác định các thông số nhập (domain knowledge for input parameters)  Khả năng xử lý dữ liệu có nhiễu (noisy data)  Khả năng gom cụm tăng dần và độc lập với thứ tự của dữ liệu nhập (incremental clustering and insensitivity to the order of input records)  Khả năng xử lý dữ liệu đa chiều (high dimensionality)  Khả năng gom cụm dựa trên ràng buộc (constraint-based clustering)  Khả diễn và khả dụng (interpretability and usability) Data Warehouse and Business Intelligence 112 4.2. Các cách tiếp cận tiêu biểu Dựa trên lưới (grid-based):  Dựa trên a multiple-level granularity structure.  Tiêu biểu STING, WaveCluster, CLIQUE Dựa trên mô hình (model-based):  Một mô hình giả thuyết được đưa ra cho mỗi cụm; sau đó hiệu chỉnh các thông số để mô hình phù hợp với cụm dữ liệu/đối tượng nhất.  Tiêu biểu: EM, SOM, COBWEB Dựa trên mẫu phổ biến (Frequent pattern-based):  Dựa trên phân tích mẫu phổ biến  Tiêu biểu: p-Cluster . Data Warehouse and Business Intelligence 113 4.2. Các cách tiếp cận tiêu biểu (tt) Phân hoạch (partitioning):  Các phân hoạch được tạo ra và đánh giá theo một tiêu chí nào đó.  Tiêu biểu k-means, k-medoids, CLARANS Phân cấp (hierarchical):  Phân rã tập dữ liệu/đối tượng có thứ tự phân cấp theo một tiêu chí nào đó.  Tiêu biểu Diana, Agnes, BIRCH, CAMELEON Dựa trên mật độ (density-based):  Dựa trên connectivity and density functions.  Tiêu biểu DBSACN, OPTICS, DenClue Data Warehouse and Business Intelligence 114 Hierarchical Clustering Use distance matrix as clustering criteria. This method does not require the number of clusters k as an input, but needs a termination condition 114 Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 agglomerative (AGNES) divisive (DIANA) Data Warehouse and Business Intelligence 115 4.3. Các phương pháp đánh giá việc phân cụm dữ liệu  Đánh giá ngoại (external validation)  Đánh giá kết quả gom cụm dựa vào cấu trúc được chỉ định trước cho tập dữ liệu  Độ đo: Rand statistic, Jaccard coefficient, Folkes and Mallows index,  Đánh giá nội (internal validation)  Đánh giá kết quả gom cụm theo số lượng các vector của chính tập dữ liệu (ma trận gần – proximity matrix)  Độ đo: Hubert’s  statistic, Silhouette index, Dunn’s index, Data Warehouse and Business Intelligence 116 4.3. Các phương pháp đánh giá việc phân cụm dữ liệu (tt)  Đánh giá tương đối (relative validation)  Đánh giá kết quả gom cụm bằng việc so sánh các kết quả gom cụm khác ứng với các bộ trị thông số khác nhau  Tiêu chí cho việc đánh giá và chọn kết quả gom cụm tối ưu - Độ nén (compactness): các đối tượng trong cụm nên gần nhau. - Độ phân tách (separation): các cụm nên xa nhau. Data Warehouse and Business Intelligence 117 Các kiểu dữ liệu trong phân tích gom cụm Biến trị khoảng (Interval-scaled variables) Biến nhị phân (Binary variables) Nominal, ordinal, and ratio variables Variables of mixed types Data Warehouse and Business Intelligence 118 Biến trị khoảng Tính toán trung bình (mean) |)|...|||(|1 21 fnffffff mxmxmxns  .)... 21 1 nffff xx(xn m  Data Warehouse and Business Intelligence 119 Interval-valued variables Standardize data  Calculate the mean absolute deviation: where  Calculate the standardized measurement (z-score) Using mean absolute deviation is more robust than using standard deviation .)... 21 1 nffff xx(xn m  |)|...|||(|1 21 fnffffff mxmxmxns  f fif if s mx z   Data Warehouse and Business Intelligence 120 Similarity and Dissimilarity Between Objects Distances are normally used to measure the similarity or dissimilarity between two data objects Some popular ones include: Minkowski distance:  where i = (xi1, xi2, , xip) and j = (xj1, xj2, , xjp) are two p-dimensional data objects, and q is a positive integer  If q = 1, d is Manhattan distance q q pp qq j x i x j x i x j x i xjid )||...|||(|),( 2211  ||...||||),( 2211 pp j x i x j x i x j x i xjid  Data Warehouse and Business Intelligence 121 Similarity and Dissimilarity Between Objects (Cont.)  If q = 2, d is Euclidean distance:  Properties • d(i,j)  0 • d(i,i) = 0 • d(i,j) = d(j,i) • d(i,j)  d(i,k) + d(k,j) Also, one can use weighted distance, parametric Pearson product moment correlation, or other disimilarity measures )||...|||(|),( 22 22 2 11 pp j x i x j x i x j x i xjid  Binary Variables • A contingency table for binary data • Distance measure for symmetric binary variables: • Distance measure for asymmetric binary variables: • Jaccard coefficient (similarity measure for asymmetric binary variables): cba a jisim Jaccard  ),( dcba cb jid  ),( cba cb jid  ),( pdbcasum dcdc baba sum    0 1 01 Object i Object j Data Warehouse and Business Intelligence 123 Dissimilarity between Binary Variables Example  gender is a symmetric attribute  the remaining attributes are asymmetric binary  let the values Y and P be set to 1, and the value N be set to 0 Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N 75.0 211 21 ),( 67.0 111 11 ),( 33.0 102 10 ),(             maryjimd jimjackd maryjackd Data Warehouse and Business Intelligence 124 Nominal Variables A generalization of the binary variable in that it can take more than 2 states, e.g., red, yellow, blue, green Method 1: Simple matching  m: # of matches, p: total # of variables Method 2: use a large number of binary variables  creating a new binary variable for each of the M nominal states p mp jid ),( Data Warehouse and Business Intelligence 125 Biến thứ tự (Ordinal Variables) An ordinal variable can be discrete or continuous Order is important, e.g., rank Can be treated like interval-scaled  replace xif by their rank  map the range of each variable onto [0, 1] by replacing i-th object in the f-th variable by  compute the dissimilarity using methods for interval-scaled variables 1 1    f if if M r z },...,1{ fif Mr  Data Warehouse and Business Intelligence 126 Biến tỉ lệ (Ratio-Scaled Variables) Ratio-scaled variable: a positive measurement on a nonlinear scale, approximately at exponential scale, such as AeBt or Ae-Bt Methods:  treat them like interval-scaled variables—not a good choice! (why?—the scale can be distorted)  apply logarithmic transformation yif = log(xif)  treat them as continuous ordinal data treat their rank as interval-scaled Data Warehouse and Business Intelligence 127 Variables of Mixed Types A database may contain all the six types of variables  symmetric binary, asymmetric binary, nominal, ordinal, interval and ratio One may use a weighted formula to combine their effects  f is binary or nominal: • dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise  f is interval-based: use the normalized distance  f is ordinal or ratio-scaled • compute ranks rif and • and treat zif as interval-scaled )( 1 )()( 1),( f ij p f f ij f ij p f d jid        1 1    f if M r z if Data Warehouse and Business Intelligence 130 4.2. Thuât toán K-mean  Input  Số nguyên k > 0: số cụm biết trước  Tập tài liệu D (cho trước) Output  Phân D thành k cụm “tốt nhất”, mỗi đối tượng thuộc một cụm Định hướng  Tinh chỉnh dần  Mỗi cụm gồm một đối tượng đại diện và các đối tượng gần đại diện cụm nhất. S = {dS* và mọi dD mà sim (d,dS*) > sim (d,dS), dS đại diện cụm khác Data Warehouse and Business Intelligence 131 4.4 Thuật toán K-mean Data Warehouse and Business Intelligence 132 Ví dụ Cho tập hợp điểm: • X1={1,3} • X2={1.5,3.2} • X3={1.3,2.8} • X4={3,1} Data Warehouse and Business Intelligence 133 4.4 Thuật toán K-mean Data Warehouse and Business Intelligence 135 4.4 Thuật toán K-mean  Ưu điểm  Đơn giản, dễ sử dụng  Hiệu quả về thời gian: tuyến tính O(tkn), t số lần lặp, k số cụm, n là số phần tử  Một thuật toán phân cụm phổ biến nhất  Thường cho tối ưu cục bộ. Tối ưu toàn cục rất khó tìm  Nhược điểm  Phải “tính trung bình được”: dữ liệu phân lớp thì dựa theo tần số  Cần cho trước k : số cụm  Nhạy cảm với ngoại lệ (cách xa so với đại đa số dữ liệu còn lại): ngoại lệ thực tế, ngoại lệ do quan sát sai (làm sạch dữ liệu)  Nhạy cảm với mẫu ban đầu: cần phương pháp chọn mẫu thô tốt  Không thích hợp với các tập dữ liệu không siêu-ellip hoặc siêu cầu (các thành phần con không ellip/cầu hóa) Data Warehouse and Business Intelligence 136 4.4 Thuật toán K-mean Data Warehouse and Business Intelligence 137 Đánh giá kết quả gom cụm: Đánh giá ngoài  Giả sử G1 , G2 , , Gn là tập các cụm được gom cụm bằng một quá trình học có giám sát. A1 , A2 , , An là tập các cụm được gom cụm bằng giải thuật đề nghị.  Cho D là tập dữ liệu chứa các chuỗi dữ liệu hoặc là các đặc trưng, với mọi cặp (Di , Dj) ta đếm các số liệu sau:  a là số cặp thuộc về một cụm trong G và được gom cụm tương ứng trong A.  b là số cặp thuộc về một cụm trong G nhưng không được gom cụm tương ứng trong A.  c là số cặp thuộc về một cụm trong A nhưng không được gom cụm tương ứng trong G.  d là số cặp không thuộc về một cụm trong A và cũng không được gom cụm tương ứng trong G. Data Warehouse and Business Intelligence 138 Đánh giá kết quả gom cụm: Đánh giá ngoài Sử dụng các phép đo như sau: Hệ số tương đồng (%) của Jaccard (1901):  𝐽𝑎𝑐𝑐𝑎𝑟𝑑 = 𝑎 𝑎+𝑏+𝑐 Hệ số Rand:  𝑅𝑎𝑛𝑑 = 𝑎+𝑑 𝑎+𝑏+𝑐+𝑑 Hệ số Folkes và Mallow (FM):  𝐹𝑀 = 𝑎 𝑎+𝑏 × 𝑎 𝑎+𝑐 Data Warehouse and Business Intelligence 139 5. Khai phá dữ liệu chuỗi thời gian 5.1 Giới thiệu về chuỗi thời gian 5.2 Khai phá dữ liệu chuỗi thời gian 5.3 Ứng dụng Data Warehouse and Business Intelligence 140 5.1 Giới thiệu về chuỗi thời gian Chuỗi thời gian (Time series): Chuỗi tuần tự theo thời gian là một chuỗi các gía trị của một đại lượng nào đó được ghi nhận tuần tự theo thời gian. Các thành phần của chuỗi thời gian:  Thành phần xu huớng (Trend component)  Thành phần mùa (Seasonal component)  Thành phần chu kỳ (Cyclical component)  Thành phần bất thuờng (Irregular component) Phân tích chuỗi thời gian  Mô hình cộng: TS = T + C + S + I  Mô hình nhân: TS = T  C  S  I Data Warehouse and Business Intelligence 141 5.2 Khai phá dữ liệu chuỗi thời gian Tìm kiếm tương tự (Similarity Search) Phân lớp (Classification) Phân cụm (Clustering) Phát hiện mô-típ (Motif Discovery) Novelty/Anomaly Detection Time series visualization Time series prediction Data Warehouse and Business Intelligence 142 5.3 Ứng dụng Financial: stock price, inflation  Industry: power consumption Scientific: experiment results Meteorological: precipitation Data Warehouse and Business Intelligence 144 6. Một số ứng dụng khác Text Mining Web Mining Data Warehouse and Business Intelligence 145 Tham khảo  Jiawei Han, Micheline Kamber, “Data Mining: Concepts and Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006. Vercellis- Carlo, “Business Intelligence: Data Mining and Optimization for Decision Making”, John Wiley & Sons, 2009.