Khai phá dữ liệu

Khai phá d li u ữ ệ (Data Mining)

Nguy n Đình Thuân ễ

UIT – VNU HCM

1

18/01/13

N i dung môn h c ọ

ộ

1 1

Ch Ch Ch Ch

ươ ươ ươ ươ

ng 1: T ng quan v khai phá d li u ng 1: T ng quan v khai phá d li u ề ề ng 1: T ng quan v khai phá d li u ng 1: T ng quan v khai phá d li u ề ề

ữ ệ ữ ệ ữ ệ ữ ệ

ổ ổ ổ ổ

Ch Ch

ng 2: Lu t k t h p ng 2: Lu t k t h p

ươ ươ

ậ ế ợ ậ ế ợ

Ch Ch

ng 3: Dãy ph bi n ng 3: Dãy ph bi n

ươ ươ

ổ ế ổ ế

Ch Ch

ng 4: Phân l p d li u ng 4: Phân l p d li u

ươ ươ

ữ ệ ữ ệ

ớ ớ

Ch Ch

ng 5: Gom c m d li u ng 5: Gom c m d li u

ươ ươ

ữ ệ ữ ệ

ụ ụ

Gi Gi

i thi u 10 thu t toán hàng đ u c a DataMining i thi u 10 thu t toán hàng đ u c a DataMining

ớ ớ

ủ ủ

ệ ệ

ậ ậ

ầ ầ

2

01/18/13

www.lhu.edu.vn

Thông tin v môn h c ề

ọ

Đánh giá Đánh giá

Ph ng pháp đánh giá Tr ng s [%] ươ ố ọ

Chuyên c n, bài t p trên l p 10% ầ ậ ớ

Th c hành, thí nghi m 15% ự ệ

Ki m tra gi a kỳ 15% ữ ể

Ti u lu n, báo cáo trên l p 20% ể ậ ớ

40% Thi cu i h c kỳ ố ọ

3

01/18/13

www.lhu.edu.vn

Tài li u tham kh o

ệ

ả

, Giáo trình + Slide Bài gi ng Khai thác d li u,

1. Đ Phúc ỗ

ữ ệ ĐHQG

ả

TPHCM, 2005.

2. H Tú B o

ả , Introduction to knowledge discovery and data mining,

ồ

IOIT, 2001.

3. Jiawei Han and Micheline Kamber, Data Mining Concepts and

Techniques, University of Illinois, Morgan Kaufmann Publishers, 2006.

4. X. Wu, V. Kumar, J. Ross Quinlan, ... Top 10 Algorithms in Data

Mining, Chapman & Hall/CRC, Taylor & Francis Group, LLC, 2009.

5. ZhaoHui Tang & Jamie MacLennan, Data Mining with SQL Server

2005, Wiley Publishing, 2005.

4

01/18/13

www.lhu.edu.vn

ươ

ng 1 T ng quan ổ

Các khái ni m c b n ệ Các khái ni m c b n ệ ơ ả ơ ả

ỗ

ậ

ữ ệ Data): có th xem là chu i các D li u ( ể bit, là s , ký t …mà chúng ta thu th p ự ố hàng ngày trong công vi c.ệ

ợ

ữ ệ ử

ủ ả ả ặ

ữ , gi ng nào đó. Thông tin (Information): là t p h p ậ c x lý, dùng c a nh ng d li u đã đ ượ ủ i thích đ c tính c a m t đ i mô t ố ộ t ượ

Knowledge): th c ( ứ ợ

ậ ẽ ậ

ứ ệ ể

ượ ề ủ ư

là Tri t p h p ậ nh ng thông tin có liên h v i nhau, ệ ớ ữ đ c l p lu n ch t ch ho c đ c ượ ặ ặ th c nghi m ki m ch ng quan nhi u ự th h . Tri th c th hi n t duy c a ể ứ ế ệ con ng ườ ề ộ ấ ệ i v m t v n đ . ề

5

01/18/13

www.lhu.edu.vn

Khám phá tri th c t

c s d li u:

ứ ừ ơ ở ữ ệ (Knowledge Discovery in Databases – KDD) – “KDD is the automatic extraction of non-obvious, hidden knowledge from large volumes of data.” Fayyad, Platetsky-Shapiro, Smyth (1996)

Các khái ni m c b n ệ Các khái ni m c b n ệ ơ ả ơ ả

ồ ề ậ ấ

ữ ệ ợ ế

– “Khám phá tri th c t ạ ề ọ ọ ả c s d li u là quy trình bao ứ ừ ơ ở ữ ệ g m nhi u công đo n nh : xác đ nh v n đ , t p h p ư và ch n l c d li u, khai thác d li u, đánh giá k t i thích d li u, áp d ng tri th c vào th c t qu , gi ụ ả ị ữ ệ ứ ự ế ữ ệ

– http://www.kdnuggets.com/

6

01/18/13

www.lhu.edu.vn

c thu th p hàng ậ

ượ

T i sao ph i khai phá d li u ? T i sao ph i khai phá d li u ? ữ ệ ữ ệ ả ả ạ ạ

ồ

John Naisbitt (www.naisbitt.com/) in 1982: “We are drowning in data, but starving for knowlegde”. D li u đ ữ ệ ngày là r t l n ấ ớ – Các CSDL kh ng l ổ – D li u t Internet

ủ

ỉ

ữ ệ

Theo các báo cáo c a IBM, c ượ i n ạ ẩ

ch có 80% d li u đ khai thác, 20% còn l trong các Database là nh ngữ tri th c quý giá

ứ

ữ ệ ừ

7

01/18/13

www.lhu.edu.vn

ữ ệ

ế

i thích d li u trên các t p d li u l n .

Khai phá d li u (Datamining) là m t b ộ ướ trong quy trình khám phá tri th c, nh m: ằ ứ – Rút trích thông tin h u ích, ch a bi t, ti m n ề ẩ ữ trong kh i d li u l n ố ữ ệ ớ – Phân tích d li u bán t ữ ệ – Gi ữ ệ

đ ng ự ộ ậ

ữ ệ ớ

ả

Khai phá d li u là gì? Khai phá d li u là gì? ữ ệ ữ ệ

8

01/18/13

www.lhu.edu.vn

L i ích c a khai phá d li u L i ích c a khai phá d li u ữ ệ ữ ệ ủ ủ ợ ợ

EDP

MIS

DSS

Giá trị

Số lượng

9

01/18/13

EDP: Electronic Data Processing MIS: Management Information Systems DSS: Decision Support Systems

www.lhu.edu.vn

Khai phá d li u là gì ? Khai phá d li u là gì ?

ữ ệ ữ ệ

t ngậ ThuThu t ngậ

ữ:: ữ

– Khai phá d li u - Data mining ữ ệ ộ ế

• KPDL là m t bu c c a ti n trình KDD ớ ủ – Knowledge discovery in databases (KDD)

• Thu t ng t ng quát g m các bu c nh ti n ư ề ớ ậ

ồ ữ ổ x lý, KPDL, h u x lý . ử ử ậ

10 i gì ? i gì ?

Khai phá d li u có ích l ữ ệ Khai phá d li u có ích l ữ ệ

ợ ợ

ị ị

Ti p thế ị

•Cung c Cung c p tri th c h p tri th c h ứ ỗ ấ ứ ỗ ấ tr ra quyêt đ nh ợ tr ra quyêt đ nh ợ •D báoựD báoự •KhKhái quát d li u ái quát d li u ữ ệ ữ ệ

CSDL Ti p thế ị

Nhà kho d li u

ữ ệ

KDD & Data Mining

11 Ti nế trình khai phá d li u

ữ ệ (1)(1)

ên c u lĩnh v c NghiNghiên c u lĩnh v c ự ứ ự ứ NghiNghiên c u lĩnh v c ên c u lĩnh v c ự ứ ự ứ

TT o t p d li u đ u vào o t p d li u đ u vào ạ ậ ữ ệ ầ ạ ậ ữ ệ ầ TT o t p d li u đ u vào o t p d li u đ u vào ạ ậ ữ ệ ầ ạ ậ ữ ệ ầ

TiTi n x lý/ làm s ch, mã hóa n x lý/ làm s ch, mã hóa ạ ề ử ạ ề ử TiTi n x lý/ làm s ch, mã hóa n x lý/ làm s ch, mã hóa ạ ề ử ạ ề ử

RRút g n / chi u út g n / chi u ề ọ ề ọ RRút g n / chi u út g n / chi u ề ọ ề ọ

ụ ụ ụ ụ

ChCh n tác v Khai thác d li u n tác v Khai thác d li u ữ ệ ọ ữ ệ ọ ChCh n tác v Khai thác d li u n tác v Khai thác d li u ữ ệ ọ ọ ữ ệ

12 Ti nế trình khai phá d li u

ữ ệ (2)(2)

i KTDL n các thu t gi ChCh n các thu t gi ả ọ i KTDL ả ọ ChCh n các thu t gi i KTDL n các thu t gi ả ọ i KTDL ọ ả

ậ ậ ậ ậ

ế ế ế ế

KTDL: Tìmìm ki m tri th c KTDL: T ki m tri th c ứ ứ KTDL: Tìmìm ki m tri th c KTDL: T ki m tri th c ứ ứ

Đánh giá m u tìm đ Đánh giá m u tìm đ Đánh giá m u tìm đ Đánh giá m u tìm đ ẫ ẫ ẫ ẫ c ượ c ượ c ượ c ượ

u di n tri th c BiBi u di n tri th c ứ ễ ể ứ ễ ể BiBi u di n tri th c u di n tri th c ứ ễ ể ể ứ ễ

SS d ng các tri th c v a khám phá d ng các tri th c v a khám phá ứ ừ ử ụ ứ ừ ử ụ SS d ng các tri th c v a khám phá d ng các tri th c v a khám phá ứ ừ ử ụ ứ ừ ử ụ

13 Ti n trình KDD tiêu bi u Ti n trình KDD tiêu bi u

ể ể

ế ế

Raw data

Time based selection

Operational Operational Operational Operational Database Database Database Database

n n

t i o t i o

c c

S e l e S e l e

Eval. of interes- tingness

Preprocessing Preprocessing

Postprocessing Postprocessing

Input data Input data Input data Input data

Results Results Results Results

Data mining Data mining Data mining Data mining

n n

t i o t i o

c c

S e l e S e l e

Cleaned Verified Focused

Utilization Utilization Utilization Utilization

Selected usable patterns

14 Khai phá d li u

ữ ệ

End User

Increasing potential to support business decisions

Making Decisions

Business Analyst

Data Presentation Visualization Techniques

Data Analyst

Data Mining Information Discovery

Data Exploration Statistical Analysis, Querying and Reporting

DBA

Data Warehouses / Data Marts OLAP, MDA Data Sources Paper, Files, Information Providers, Database Systems, OLTP

15 ừ ữ ệ ừ ữ ệ

ế ị ế ị

TT d li u đ n quy t đ nh d li u đ n quy t đ nh ế ế

QuyQuy t đ nh t đ nh ế ị ế ị • Promote product A in region Z. • Mail ads to families of profile P • Cross-sell service B to clients C

Tri thTri th cứcứ • A quantity Y of product A is used in

region Z • Customers of class Y use x% of C during period D

ông tin ThThông tin • X lives in Z • S is Y years old • X and S moved • W has money in Z

DD li u ữ ệ li u ữ ệ • Customer data • Store data • Demographical Data • Geographical data

16 ềv KPDL Các quan ni m ệm ệ v KPDL ề Các quan ni

Các ti p c n t ng quan: ậ ổ Các ti p c n t ng quan: ậ ổ

ế ế – KPDL mô t

:ả

t đi u gì là h u ích có th tìm th y đ

ế

ữ

ề

ể

ấ

ượ

c trong d ữ

• Cho bi li uệ

• Gi

i thích d li u đó

ả

ữ ệ

– KPDL d báo:

ự

• D a trên d li u quá kh , d báo t

ng lai

ứ ự

ữ ệ

ự

ươ

• Xu th phát tri n!

ế

ể

17 ề ề

CCác quan ni m v KTDL ác quan ni m v KTDL ệ ệ Quan ni m d a trên … ệ Quan ni m d a trên … ệ

ự ự

– CSDL đ khai thác ể

– Tri th c đ c khám phá ứ ượ

– Các k thu t đ ỹ ậ ượ c s d ng ử ụ

– Các ng d ng ứ ụ

18 Các quan ni m v KPDL ề ệ Các quan ni m v KPDL ề ệ CSDL c n khai thác CSDL c ần khai thác ầ CSDL c n khai thác CSDL c ần khai thác ầ

Databases Databases

ệ

Quan h ệ Giao tác Hu ng đ i ố ớ ngượ t Hu ng đ i ố ớ t ng, quan h ượ Active Không gian Th i gian

ờ

Text, XML Multi-media Heterogeneous Legacy Inductive WWW etc.

19 Các quan ni m v KPDL ệ Các quan ni m v KPDL ệ

ụ

ề ề ụTTác v khai thác ụác v khai thác TTác v khai thác ụác v khai thác

ặ

Phân tích đ ộ

l ch ệ

Knowledge Knowledge == tasktask

Phân tích hi m ế

etc.

Đ c tr ng ư tệ Phân bi K t h p ế ợ Phân l pớ Gom c mụ Xu thế

20 Các quan ni m KPDL ệ Các quan ni m KPDL ệ CCác k thu t đã s d ng ác k thu t đã s d ng ỹ ậ ử ụ ỹ ậ ử ụ CCác k thu t đã s d ng ác k thu t đã s d ng ỹ ậ ử ụ ỹ ậ ử ụ

Techniques Techniques

i GA

ậ

ả

CSDL Nhà kho d li u (OLAP) ữ ệ Máy h c ọ Th ng kê ố Tr c quan hóa ự M ng n ron và thu t gi ơ ạ . . . .

21

ụ ụ ụ ụ

CCác quan ni m v KPDL ác quan ni m v KPDL ề ệ ề ệ CCác ng d ng ác ng d ng ứ ứ CCác ng d ng ác ng d ng ứ ứ

, siêu th ị

Phân tích c ổ

Applic. Applic.

Bán l ẻ Ngân hàng Khai thác gen

phi uế KTDL Web Phân tích d ữ

li uệ

22

Các ng d ng Các ng d ng ụ ụ ứ ứ

ữ ệ ị

ứ

- Phân tích d li u bán hàng và ti p thế - Phân tích đ u tầ ư - Ch ng khoán - Xác đ nh gian l n ị

ậ

ề ả

- Đi u khi n và l p l ch ể - Qu n tr m ng l ị ạ - Phân tích k t qu th nghi m ế

ậ ị i ướ ả ử

ệ

S n xu t ấ ả Kinh doanh

Khoa h cọ

- Không gian - Sinh h cọ - Đ a lý ị - etc.

- B nh lý ệ - Sinh h cọ

Y h cọ

23

01/18/13

www.lhu.edu.vn

ủ ớ

ụ

Tìm các đ c tr ng c a l p ng và s d ng các đ i t ử ụ đ phân l p d li u m i. ớ

ặ ố ượ ớ

ữ ệ

ể

Xác đ nh các c m ị ti m n trong các ề ẩ ng ch a t p đ i t ố ượ ư ậ c x p l p. đ ế ớ ượ

Các k thu t s d ng Các k thu t s d ng ậ ử ụ ậ ử ụ ỹ ỹ

Gom c mụ

bi n t

ữ

Tìm các m u ph ổ ẫ d li u và m i ế ừ ữ ệ ố quan h c a các đ i ố ệ ủ t ng d li u. ượ

ữ ệ

D đoán d li u t ng ữ ệ ươ lai d a trên d li u quá ữ ệ ự kh .ứ

Phân l p ớ

ợ

Khám phá các m u tín hi u ph ẫ ổ ệ bi n nh t t d ấ ừ ữ ế li u các s ki n ự ệ ệ

d Xác đ nh tr t t ậ ự ữ ị li u, c u trúc l u tr ữ ư ấ ệ phù h p v i tác v ụ ớ khai phá

D đoán Lu t k t h p ự ậ ế ợ

M u tu n t ầ ự ẫ

Nhà kho- OLAP

24

01/18/13

www.lhu.edu.vn

K t lu n K t lu n ế ế ậ ậ

KPDL: ti n trình khám phá bán t KPDL: ti n trình khám phá bán t

ế ế

đ ng các ự ộ đ ng các ự ộ CSDL l n ớ CSDL l n ớ

ừ ừ

Các b Các b

ử ậ

thông tin, m u có ích t ẫ thông tin, m u có ích t ẫ c c a KDD ướ ủ c c a KDD ướ ủ – Ti n x lý ử ề – KTDL( data mining tasks) – H u x lý ệ ệ

– CSDL (quan h , h

ạ ạ ng đ i t

ng, không gian, WWW,

Các quan ni m, khía c nh … Các quan ni m, khía c nh … ố ượ

Tri th c (đ c tr ng, gom c m, k t h p, …)

ụ

ệ ướ

ế ợ – K thu t (máy h c, th ng kê, tr c quan hóa, …) ự ố – , đi n tho i, khai thác Web …) ệ

ặ ậ ụ

…) ứ ọ ỹ ng d ng (bán l ẻ Ứ ạ

25

01/18/13