Bài giảng Khai phá dữ liệu: Chương 2 - TS. Võ Thị Ngọc Châu

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (274.14 KB, 20 trang )

<b>Ch</b>

<b>ươ</b>

<b>ng</b>

<b>2: </b>

<b>Các</b>

<b>v</b>

<b>vấn</b>

<b>ấ</b>

<b>n</b>

<b>đ</b>

<b>ề</b>

<b>ti</b>

<b>tiền</b>

<b>ề</b>

<b>n</b>

<b>x</b>

<b>xử</b>

<b>ử</b>

<b>lý</b>

<b>d</b>

<b>dữ</b>

<b>ữ</b>

<b>li</b>

<b>liệu</b>

<b>ệ</b>

<b>u</b>

Học kỳ 1 – 2011-2012

Cao

H

ọ

c

Ngành

Khoa

H

ọ

c

Máy

Tính

Giáo

trình

đ

i

ệ

n

t

ử

Biên

so

ạ

n

b

ở

i

: TS.

Võ

Th

ị

Ng

ọ

c

Châu

(

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

[1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and
Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006.

[2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of Data

Mining”, MIT Press, 2001.

[3] David L. Olson, Dursun Delen, “Advanced Data Mining

Techniques”, Springer-Verlag, 2008.

[4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory,

Methodology, Techniques, and Applications”, Springer-Verlag, 2006.

[5] Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and

Vipin Kumar, “Next Generation of Data Mining”, Taylor & Francis
Group, LLC, 2009.

[6] Daniel T. Larose, “Data mining methods and models”, John Wiley

& Sons, Inc, 2006.

[7] Ian H.Witten, Eibe Frank, “Data mining : practical machine

learning tools and techniques”, Second Edition, Elsevier Inc, 2005.

[8] Florent Messeglia, Pascal Poncelet & Maguelonne Teisseire,

“Successes and new directions in data mining”, IGI Global, 2008.

[9] Oded Maimon, Lior Rokach, “Data Mining and Knowledge

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

Ch

ươ

ng 1: T

ổ

ng quan v

ề

khai phá d

ữ

li

ệ

u

<b>Ch</b>

<b>ươ</b>

<b>ng 2: Các v</b>

<b>ấ</b>

<b>n</b>

<b>đề</b>

<b>ti</b>

<b>ề</b>

<b>n x</b>

<b>ử</b>

<b>lý d</b>

<b>ữ</b>

<b>li</b>

<b>ệ</b>

<b>u</b>

Ch

ươ

ng 3: H

ồ

i qui d

ữ

li

ệ

u

Ch

ươ

ng 4: Phân lo

ạ

i d

ữ

li

ệ

u

Ch

ươ

ng 5: Gom c

ụ

m d

ữ

li

ệ

u

Ch

ươ

ng 6: Lu

ậ

t k

ế

t h

ợ

p

Ch

ươ

ng 7: Khai phá d

ữ

li

ệ

u v

à công ngh

ệ

c

ơ

s

ở

d

ữ

li

ệ

u

Ch

ươ

ng 8:

Ứ

ng d

ụ

ng

khai phá d

ữ

li

ệ

u

Ch

ươ

ng 9: Các

đề

tài nghiên c

ứ

u trong khai phá

d

ữ

li

ệ

u

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

2.1. T

ổ

ng quan v

ề

giai

đ

o

ạ

n ti

ề

n x

ử

lý d

ữ

li

ệ

u

2.2. Tóm t

ắ

t mô t

ả

v

ề

d

ữ

li

ệ

u

2.3. Làm s

ạ

ch d

ữ

li

ệ

u

2.4. Tích h

ợ

p d

ữ

li

ệ

u

2.5. Bi

ế

n

đổ

i d

ữ

li

ệ

u

2.6. Thu gi

ả

m d

ữ

li

ệ

u

2.7. R

ờ

i r

ạ

c hóa d

ữ

li

ệ

u

2.8. T

ạ

o cây phân c

ấ

p ý ni

ệ

m

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

Giai

đ

o

ạ

n ti

ề

n x

ử

lý d

ữ

li

ệ

u

Quá trình x

ử

lý d

ữ

li

ệ

u thơ/g

ố

c (raw/original

data) nh

ằ

m c

ả

i thi

ệ

n ch

ấ

t l

ượ

ng d

ữ

li

ệ

u

(quality of the data) và do

đ

ó, c

ả

i thi

ệ

n ch

ấ

t

l

ượ

ng c

ủ

a k

ế

t qu

ả

khai phá.

D

ữ

li

ệ

u thơ/g

ố

c

Có c

ấ

u trúc, bán c

ấ

u trúc, phi c

ấ

u trúc

Đượ

c

đư

a vào t

ừ

các ngu

ồ

n d

ữ

li

ệ

u trong các h

ệ

th

ố

ng

x

ử

lý t

ậ

p tin (file processing systems) và/hay các h

ệ

th

ố

ng c

ơ

s

ở

d

ữ

li

ệ

u (database systems)

Ch

ấ

t l

ượ

ng d

ữ

li

ệ

u (data quality): t

ính chính xác,

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

Ch

ấ

t l

ượ

ng d

ữ

li

ệ

u (data quality)

tính chính xác (accuracy): giá tr

ị đượ

c ghi nh

ậ

n

đ

úng v

ớ

i giá tr

ị

th

ự

c.

tính hi

ệ

n hành (currency/timeliness): giá tr

ị

đượ

c ghi nh

ậ

n không b

ị

l

ỗ

i th

ờ

i.

tính tồn v

ẹ

n (completeness): t

ấ

t c

ả

các giá tr

ị

dành cho m

ộ

t bi

ế

n/thu

ộ

c tính

đề

u

đượ

c ghi

nh

ậ

n.

tính nh

ấ

t quán (consistency): t

ấ

t c

ả

giá tr

ị

d

ữ

li

ệ

u

đề

u

đượ

c bi

ể

u di

ễ

n nh

ư

nhau trong t

ấ

t c

ả

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

<b>Data </b>

<b>Cleaning</b>

<b>Data Integration</b>

<b>Data Sources</b>

<b>Data Warehouse</b>

<b>Task-relevant Data</b>

<b>Selection/Transformation</b>

<b>Data Mining</b>

<b>Pattern Evaluation/</b>

<b>Presentation</b>

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8></div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>

Các k

ỹ

thu

ậ

t ti

ề

n x

ử

lý d

ữ

li

ệ

u

Làm s

ạ

ch d

ữ

li

ệ

u (data cleaning/cleansing): lo

ạ

i b

ỏ

nhi

ễ

u

(remove noise), hi

ệ

u ch

ỉ

nh nh

ữ

ng ph

ầ

n d

ữ

li

ệ

u không

nh

ấ

t quán (correct data inconsistencies)

Tích h

ợ

p d

ữ

li

ệ

u (data integration): tr

ộ

n d

ữ

li

ệ

u (merge

data) t

ừ

nhi

ề

u ngu

ồ

n khác nhau vào m

ộ

t kho d

ữ

li

ệ

u

Bi

ế

n

đổ

i d

ữ

li

ệ

u (data transformation): chu

ẩ

n hoá d

ữ

li

ệ

u

(data normalization)

Thu gi

ả

m d

ữ

li

ệ

u (data reduction): thu gi

ả

m kích th

ướ

c d

ữ

</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

Các k

ỹ

thu

ậ

t ti

ề

n x

ử

lý d

ữ

li

ệ

u

Làm s

ạ

ch d

ữ

li

ệ

u (data cleaning/cleansing)

Tóm tắt hố dữ liệu: nhận diện đặc điểm chung của dữ liệu

và sự hiện diện của nhiễu hoặc các phần tử kì dị (outliers)

Xử lý dữ liệu bị thiếu (missing data)
Xử lý dữ liệu bị nhiễu (noisy data)

Tích h

ợ

p d

ữ

li

ệ

u (data integration)

Tích hợp lược đồ (schema integration) và so trùng đối tượng

(object matching)

Vấn đề dư thừa (redundancy)

Phát hiện và xử lý mâu thuẫn giá trị dữ liệu (detection and

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

Các k

ỹ

thu

ậ

t ti

ề

n x

ử

lý d

ữ

li

ệ

u

Biến đổi dữ liệu (data transformation)

Làm trơn dữ liệu (smoothing)

Kết hợp dữ liệu (aggregation)

Tổng quát hóa dữ liệu (generalization)

Chuẩn hóa dữ liệu (normalization)

Xây dựng thuộc tích (attribute/feature construction)

Thu giảm dữ liệu (data reduction)

Kết hợp khối dữ liệu (data cube aggregation)

Chọn tập con các thuộc tính (attribute subset selection)

Thu giảm chiều (dimensionality reduction)

Thu giảm lượng (numerosity reduction)

Tạo phân cấp ý niệm (concept hierarchy generation) và rời rạc hóa

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

Xác

đị

nh các thu

ộ

c tính (properties) tiêu

bi

ể

u c

ủ

a d

ữ

li

ệ

u v

ề

xu h

ướ

ng chính (central

tendency) và s

ự

phân tán (dispersion) c

ủ

a

d

ữ

li

ệ

u

Các

độ đ

o v

ề

xu h

ướ

ng chính: mean, median,

mode, midrange

Các

độ đ

o v

ề

s

ự

phân tán: quartiles, interquartile

range (IQR), variance

Làm n

ổ

i b

ậ

t các giá tr

ị

d

ữ

li

ệ

u nên

đượ

c

xem nh

ư

nhi

ễ

u (noise) ho

ặ

c ph

ầ

n t

ử

biên

(outliers), cung c

ấ

p cái nhìn t

ổ

ng quan v

ề

</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13>

D

ữ

li

ệ

u m

ẫ

u v

ề đơ

n giá c

ủ

a các m

ặ

t hàng

đ

ã

đượ

c

</div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>

Các

độ đ

o v

ề

xu h

ướ

ng chính c

ủ

a d

ữ

li

ệ

u

Mean

Weighted arithmetic mean

Median

Mode: giá tr

ị

xu

ấ

t hi

ệ

n th

ườ

ng xuyên nh

ấ

t trong

t

ậ

p d

ữ

li

ệ

u

Midrange: giá tr

ị

trung bình c

ủ

a các giá tr

ị

l

ớ

n

 



+
=

+ <i>if</i> <i>N</i> <i>even</i>

<i>x</i>
<i>x</i>
<i>odd</i>
<i>N</i>
<i>if</i>
<i>x</i>
<i>Median</i>
<i>N</i>
<i>N</i>
<i>N</i>
2
/
)
( <sub>/</sub><sub>2</sub> <sub>/</sub><sub>2</sub> <sub>1</sub>

</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>

Các

độ đ

o v

ề

xu h

ướ

ng chính c

ủ

a d

ữ

li

ệ

u

Mean =

Σ

(count[i]*price[i])/

Σ

(count[i])

Weighted arithmetic mean

Median

Mode = price[i] n

ế

u count[i] l

ớ

n nh

ấ

t

Midrange = (

Σ

(count[i]*price[i]) +

Σ

(count[j]*price[j]))/(

Σ

(count[i]) +

Σ

(count[j]))

</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>

Các

độ đ

o v

ề

s

ự

phân tán c

ủ

a d

ữ

li

ệ

u

Quartiles

The first quartile (Q1): the 25

percentile

The second quartile (Q2): the 50

percentile (median)

The third quartile (Q3): the 75

percentile

Interquartile Range (IQR) = Q3 – Q1

Outliers (the most extreme observations): giá tr

ị

n

ằ

m

cách trên Q3 hay d

ướ

i Q1 m

ộ

t kho

ả

ng 1.5xIQR

</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>

Q1 Q2 Q3

Tóm tắt mơ tả về sự phân bố dữ liệu gồm năm trị số quan trọng:
median, Q1, Q3, trị lớn nhất, và trị nhỏ nhất (theo thứ tự:

</div>
<span class='text_page_counter'>(18)</span><div class='page_container' data-page=18>

X

ử

lý d

ữ

li

ệ

u b

ị

thi

ế

u (missing data)

Nh

ậ

n di

ệ

n ph

ầ

n t

ử

biên (outliers) và gi

ả

m

thi

ể

u nhi

ễ

u (noisy data)

X

ử

lý d

ữ

li

ệ

u không nh

ấ

t quán (inconsistent

</div>
<span class='text_page_counter'>(19)</span><div class='page_container' data-page=19>

X

ử

lý d

ữ

li

ệ

u b

ị

thi

ế

u (missing data)

Đị

nh ngh

ĩ

a c

ủ

a d

ữ

li

ệ

u b

ị

thi

ế

u

Dữ liệu khơng có sẵn khi cần được sử dụng

Nguyên nhân gây ra d

ữ

li

ệ

u b

ị

thi

ế

u

Khách quan (không tồn tại lúc được nhập liệu, sự cố, …)
Chủ quan (tác nhân con người)

Gi

ả

i pháp cho d

ữ

li

ệ

u b

ị

thi

ế

u

Bỏ qua

Xử lý tay (không tự động, bán tự động)

Dùng giá trị thay thế (tự động): hằng số toàn cục, tr

ị

ph

ổ

bi

ế

n

nh

ấ

t,

trung bình tồn cục, trung bình cục bộ, trị dự đoán, …

Ngăn chặn dữ liệu bị thiếu: thiết kế tốt CSDL và các thủ tục

</div>
<span class='text_page_counter'>(20)</span><div class='page_container' data-page=20>