Tài liệu Bài giảng kho dữ liệu - chương 5 khai phá dữ liệu trong kinh doanh

  • Số trang: 38 |
  • Loại file: PDF |
  • Lượt xem: 258 |
  • Lượt tải: 0
bangnguyen-hoai

Đã đăng 3509 tài liệu

Mô tả:

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
- Xem thêm -