數(shù)據(jù)挖掘復(fù)習(xí)-chapter

第8章分類–分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準確性小結(jié)Data

Mining:

Concepts

andTechniques1星期二分類分類:–

分類的類標號

(class

labels)(離散的或標稱的)–基于訓(xùn)練數(shù)據(jù)和和類標號屬性上的值(類標號)構(gòu)造模型,并使用它對新的數(shù)據(jù)進行分類典型應(yīng)用–

認證(credit

approval)–醫(yī)療

(medical

diagnosis)Data

Mining:

Concepts

andTechniques2星期二分類:包括兩步過程模型構(gòu)造:描述預(yù)先確定的數(shù)據(jù)類或概念集假定每個元組屬于一個預(yù)定義的類，由一個類標號屬性確定基本概念訓(xùn)練數(shù)據(jù)集：由為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練樣本：訓(xùn)練數(shù)據(jù)集中的單個樣本（元組）模型用分類規(guī)則、判定樹或數(shù)學(xué)公式的形式提供模型使用:對未來的或未知的對象分類評估模型的精度檢驗(測試)樣本的已知標號與模型分類結(jié)果進行比較準確率：是正確被模型分類的檢驗樣本的百分比檢驗樣本獨立于訓(xùn)練集,否則將出現(xiàn)過分擬合Data

Mining:

Concepts

andTechniques3星期二分類過程

(1):模型構(gòu)造訓(xùn)練數(shù)據(jù)NAMERANKYEARSTENUREDMikeAssistant

Prof3nossistant

Prof7yesBillProfessor2yesJimAssociate

Prof7yesDaveAssistant

Prof6noAnneAssociate

Prof3no分類算法IF

rank

=

‘professor’OR

years

>

6THEN

tenured

=‘yes’分類法(模型)Data

Mining:

Concepts

andTechniques4星期二分類過程

(2):使用模型分類分類法檢驗數(shù)據(jù)NAMERANKYEARSTENUREDTomAssistant

Prof2noMerlisaAssociate

Prof7noGeorgeProfessor5yesJosephAssistant

Prof7yes未知數(shù)據(jù)(Jeff,

Professor,

4)Tenured?Data

Mining:

Concepts

andTechniques5星期二有監(jiān)督學(xué)習(xí)VS.無監(jiān)督學(xué)習(xí)有監(jiān)督的學(xué)習(xí)

(分類)模型的學(xué)

知每個訓(xùn)練樣本屬于哪個類的“指導(dǎo)”下進行

-訓(xùn)練數(shù)據(jù)(觀測)具有類標號新數(shù)據(jù)的分類基于訓(xùn)練集無監(jiān)督學(xué)習(xí)

(聚類)訓(xùn)練數(shù)據(jù)的類標號未知給定度量,觀測等,目標是找出數(shù)據(jù)中的類或簇/聚類(clusters)Data

Mining:

Concepts

andTechniques6星期二第8章分類–分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準確性小結(jié)Data

Mining:

Concepts

andTechniques7星期二用判定樹歸納分類?判定樹類似于流程圖的樹結(jié)構(gòu)每個 節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個樹葉節(jié)點代表類或類分布判定樹的生成由兩個階段構(gòu)成判定樹構(gòu)建開始時，所有的訓(xùn)練樣本都在根節(jié)點遞歸的通過選定的屬性，來劃分樣本樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪音和孤立點，樹剪枝試圖檢測和剪去這種分枝判定樹的使用：對未知樣本進行分類通過將樣本的屬性值與判定樹相比較Data

Mining:

Concepts

andTechniques8星期二期二Techniques訓(xùn)練數(shù)據(jù)集<=30>40<

3031…4031…40>40輸出:一棵判定樹“

puter”age?student?credit

rating?noyes30..40<30>40noyesyesnoyesexcellentfairData

Mining:

Concepts

andTechniques10星期二判定樹歸納算法基本思想判定樹以自頂向下,遞歸分治的方式構(gòu)造屬性的選擇基于啟發(fā)式或統(tǒng)計度量(例如,信息增益)節(jié)點上的樣本遞歸地基于選定的屬性劃分停止劃分的條件Data

Mining:

Concepts

andTechniques11星期二判定樹歸納算法算法：Generate_decision_tree。由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵判定樹。輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵判定樹。創(chuàng)建結(jié)點N；if

samples

都在同一個類C

thenreturnN

作為葉結(jié)點，以類C標記；if

attribut_list

為空thenreturn

N

作為葉結(jié)點，標記為samples中最普Data

Mining:

Concepts

and12星//majorityvotingT多echn的ique類s；期二判定樹歸納算法(續(xù))選擇attribute_list中具有最高信息增益的屬性test_attribute；標記結(jié)點

N

為test_attribute；for

each

test_attribute

中的未知值a

i//partition

the

samples由結(jié)點N

長出一個條件為test_attribute

=a

i的分枝；

設(shè)si

是samples

中test_attribute=a

i的樣本的集合；//a

partitionif

si

為空then(12)加上一個樹葉，標記為samples中最普通的類；(13)

else

加上一個由Generate_decision_tree(si,attribute_list–test_attribute)返回的結(jié)點；Data

Mining:

Concepts

andTechniques13星期二屬性選擇度量–信息增益ID3/C4.5使用的方法D包含|D|個樣本,其中類Ci的樣本數(shù)為|Di

|,

i={1,…,m}對一個給定的樣本分類所需的期望信息log2

(

pi

)mInfo(D)

pii1Data

Mining:

Concepts

andTechniques14星期二屬性選擇度量–信息增益(續(xù))設(shè)屬性A具有v個不同值{a1,...,av}.可以用屬性A將D劃分為v個子集{D1,...,Dv}；其中,Dj包含S中這樣一些樣本,它們在A上具有值aj.根據(jù)A劃分子集的熵(entropy)或期望信息vj

1s

jAInfo

(D)

jInfo(D

)sData

Mining:

Concepts

andTechniques15星期二屬性選擇度量

–信息增益(續(xù))在A上分枝的信息增益是Gain

Info(D)

InfoA

(D)算法計算每個屬性的信息增益.具有最高信息增益的屬性選作給定集合S的測試屬性,創(chuàng)建一個結(jié)點，并以該屬性標記，對屬性的每個值創(chuàng)建分枝，并據(jù)此劃分樣本Data

Mining:

Concepts

andTechniques16星期二星期二Data

Mining:

Concepts

andTechniques17例:

判定樹歸納(訓(xùn)練數(shù)據(jù)集)9<=30lo10>40m11<=30m1231…40m1331…40h14>40m例:

判定樹歸納類標號屬性

puter有兩個不同值（即,

{yes,

no}）,因此有兩個不同的類(m

=2).設(shè)類C1對應(yīng)于yes,而類C2對應(yīng)于no.類yes有9個樣本,類no有5個樣本–計算對給定樣本分類所需的期望信息14Info(D)

9

logData

Mining:

Concepts

andTechniques18星期二例:

判定樹歸納(續(xù))計算每個屬性的熵,以屬性age

為例如果樣本按age劃分，對一個給定的樣本分類所需的期望信息為54agIn

(

)2)2

514

5

52

5

5

(

3

log

3

2

log

0.694Data

Mining:

Concepts

andTechniques19星期二例:

判定樹歸納(續(xù))這種劃分的信息增益是Gain(age)

Info類似地,通過計算得到–

Gain( e)

=

0.029Gain(student)

=

0.151Gain(credit_rating)

=

0.048由于age在屬性中具有最高信息增益,它被選作測試屬性.創(chuàng)建一個結(jié)點,用age標記,并對于每個屬性值,引出一個分枝,據(jù)此劃分樣本Data

Mining:

Concepts

andTechniques20星期二例:

判定樹歸納(續(xù))用age劃分樣本,構(gòu)造判定樹的根和Data

Mining:

Concepts

andTechniques21星期二例:

判定樹歸納(續(xù))age?student?credit

rating?noyes30..40<30>40noyesyesnoyesexcellentfair最終的判定樹Data

Mining:

Concepts

andTechniques22星期二如何計算連續(xù)值屬性的信息增益屬性值按遞增排序，每對相鄰值的中點看成可能的

點對每個可能的

點，計算InfoA(D),選最大的點作為

點其它的屬性選擇度量方法增益率：傾向于產(chǎn)生不平衡的劃分基尼指數(shù)……注意：所有的度量都有某種偏倚傾向于產(chǎn)生較淺的樹的度量可能更可取偏向于多值屬性Product_id,合理嗎？Data

Mining:

Concepts

andTechniques23星期二ID3算法ID3算法采用信息增益作為屬性選擇度量缺點：信息增益傾向于特征取值的數(shù)目較多的特征ID3在建樹時。每個節(jié)點僅含一個特征，特征間的相關(guān)性強調(diào)不夠?qū)υ肼曒^為敏感要求離散屬性Data

Mining:

Concepts

andTechniques24星期二8.2.3

樹剪枝過分擬合: 判定樹可能過分擬合訓(xùn)練數(shù)據(jù)分枝太多,由于數(shù)據(jù)中的噪音和孤立點,許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常對新數(shù)據(jù)的 精度差兩種避免過分擬合的方法先剪枝(prepruning)很難選擇合適的閾值是建樹過程中判斷當前節(jié)點是否需要繼續(xù)劃分的剪枝方法。通常是通過重要性檢測判斷是否停止 節(jié)點后剪枝(postpruning)是讓樹充分生長之后，再判斷是否將某些分支變成節(jié)點。常用方法是根據(jù)錯誤 率（或者決策樹編碼長度）進行決策樹的事后修剪Data

Mining:

Concepts

andTechniques25星期二剪枝前后的決策樹Data

Mining:

Concepts

andTechniques26星期二決策樹的重復(fù)和問題組合屬性劃分其它知識表示方法Data

Mining:

Concepts

andTechniques27星期二第8章分類–分類?–用判定樹歸納分類–分類基于規(guī)則的分類分類的準確性小結(jié)Data

Mining:

Concepts

andTechniques28星期二第8章分類–分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準確性小結(jié)Data

Mining:

Concepts

andTechniques29星期二8.4.2由判定樹提取分類規(guī)則例:由上例的判定樹提取的規(guī)則IF

age

=

“<=30”

AND

student

=

“no”

THENIF

age

=

“<=30”

AND

student

=

“yes”

THENIF

age

=

“31…40”

THENIF

age

=

“>40”

AND

credit_rating

=

“excellent”

THENIF

age

=

“<=30”

AND

credit_rating

=

“fair”

THENputer

=

“no”puter

=

“yes”puter

=

“yes”puter

=

“yes”puter

=

“no”規(guī)則前件規(guī)則后件一條規(guī)則Data

Mining:

Concepts

andTechniques30星期二8.4.2由判定樹提取分類規(guī)則方法：對每條從根到樹葉結(jié)點的路徑創(chuàng)建一個規(guī)則。沿著給定路徑上的每個 準則的邏輯AND形成規(guī)則的前件存放類

的樹葉節(jié)點形成規(guī)則的后件注意：規(guī)則間是互斥的：即不存在規(guī)則是窮舉的：每種可能的屬性-值組合都存在一個規(guī)則規(guī)則是無序的Data

Mining:

Concepts

andTechniques31星期二第8章分類分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準確性小結(jié)Data

Mining:

Concepts

andTechniques32星期二8.5.1評估分類器性能的度量圖8.14矩陣Data

Mining:

Concepts

andTechniques33星期二8.5.1評估分類器性能的度量圖8.13

評估度量類不平衡性問題Data

Mining:

Concepts

andTechniques34星期二Data

Mining:

Concepts

andTechniques35星期二模型評估與選擇(2)比較分類方法評估

的準確率:

模型正確地 新的或先前未見過的數(shù)據(jù)的類標號的能力速度：產(chǎn)生和使用模型的計算花費魯棒性：給定噪音數(shù)據(jù)或有空缺值的數(shù)據(jù),模型正確 的能力可伸縮性：給定大量數(shù)據(jù),有效地構(gòu)造模型的能力用規(guī)模漸增的一系列數(shù)據(jù)集評估可解釋性：學(xué)習(xí)模型提供的理解和洞察的層次帶有 性，難易評估Data

Mining:

Concepts

andTechniques36星期二如何獲得可靠的分類器準確率評估8.5.2

保持方法和隨機二次抽樣保持方法評估分類法的準確性訓(xùn)練集導(dǎo)出分類法評估精度數(shù)據(jù)測試集交叉驗證，……Data

Mining:

Concepts

andTechniques37星期二8.6

提高分類準確率的技術(shù)組合分類器提高分類法的準確性Data

Mining:

Concepts

andTechniques38星期二Data

Mining:

Concepts

andTechniques39星期二總結(jié)分類:

決策樹歸納、樸素

分類分類評價的度量

：準確率、錯誤率率如何獲得可靠的分類器準確率評估：保持交叉驗證提高分類準確率的技術(shù)：組合分類器Data

Mining:

Concepts

andTechniques40星期二References

(1)C.

Apte

and

S.

Weiss.

Data

mining

with

decision

trees

and

decision

rules.FutureGeneration

Computer

Systems,

13,

1997.L.

Breiman,

J.

Friedman,

R.

Olshen,

and

C.

Stone.

Classification

and

Regression

Trees.Wadsworth

International

Group,

1984.P.

K.

Chan

and

S.

J.

Stolfo.Learning

arbiter

and

combiner

trees

from

partitioned

datafor

scaling

machine

learning.

In

Proc.

1st

Int.Conf.

Knowledge

Discovery

and

DataMining

(KDD'95),

pages39-44,

Montreal,Canada,

August1995.U.

M.Fayyad.

Branching

on

attribute

values

in

decision

tree

generation.In

Proc.

1994AAAI

Conf.,pages601-606,

AAAI

Press,1994.J.

Gehrke,R.

Ramakrishnan,

and

V.Ganti.Rainforest:

A

frameworkforfastdecisiontree

construction

of

large

datasets.

In

Proc.

1998

Int.

Conf.

Very

Large

Data

Bases,pages

416-427,

New

York,NY,

August

1998.J.

Gehrke,

V.

Gant,

R.

Ramakrishnan,

and

W.-Y.

Loh,

BOAT

--

Optimistic

Decision

Tree

Construction

.

In

SIGMOD'99

,

Philadelphia,

Pennsylvania,

1999Data

Mining:

Concepts

andTechniques41星期二References

(2)M.

Kamber,

L.

Winstone,

W.

Gong,

S.

Cheng,

and

J.

Han.

Generalization

and

decision

treeinduction:

Efficient

classification

in

data

mining.

In

Proc.

1997

Int.

Workshop

Research

Issues

onData

Engineering

(RIDE'97),

Birmingham,

England,

April

1997.B.

Liu,

W.

Hsu,

and

Y.Ma.

Integrating

Classification

and

Association

Rule

Mining.

Proc.

1998

Int.Conf.

Knowledge

Discovery

and

Data

Mining

(KDD'98)

New

York,

NY,

Aug.

1998.W.

Li,

J.

Han,

and

J.

Pei,

CMAR:

Accurate

and

Efficient

Classification

Based

on

Multiple

Class-

Association

Rules,

,

Proc.

2001

Int.

Conf.

on

Data

Mining

(ICDM'01),

San

Jose,

CA,

Nov.

2001.J.

Magidson.

The

Chaid

approach

to

segmentation

modeling:

Chi-squared

automatic

interactiondetection.

In

R.

P.Bagozzi,

editor,

Advanced

Methods

of

Marketing

Research,

pages

118-159.Blackwell

Business,

Cambridge

Massechusetts,

1994.M.

Mehta,

R.

Agrawal,

and

J.

Rissanen.

SLIQ

:

A

fast

scalable

classifier

for

data

mining.(EDBT'96),

Avignon,

France,

March

1996.Data

Mining:

Concepts

andTechniques42星期二References

(3)T.

M.Mitc .

Machine

Learning.

McGraw

Hill,

1997.S.

K.

Murthy,

Automatic

Construction

of

Decision

Trees

from

Data:

A

Multi-Diciplinary

Survey,

DataMining

and

Knowledge

Discovery