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

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

Mining:

Concepts

andTechniques1星期二分類分類:–

分類的類標(biāo)號

(class

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

認(rèn)證(credit

approval)–醫(yī)療

(medical

diagnosis)Data

Mining:

Concepts

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

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

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

Mining:

Concepts

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

Mining:

Concepts

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

Mining:

Concepts

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

samples

都在同一個類C

thenreturnN

作為葉結(jié)點(diǎn)，以類C標(biāo)記；if

attribut_list

為空thenreturn

N

作為葉結(jié)點(diǎn)，標(biāo)記為samples中最普Data

Mining:

Concepts

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

N

為test_attribute；for

each

test_attribute

中的未知值a

i//partition

the

samples由結(jié)點(diǎn)N

長出一個條件為test_attribute

=a

i的分枝；

設(shè)si

是samples

中test_attribute=a

i的樣本的集合；//a

partitionif

si

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

else

加上一個由Generate_decision_tree(si,attribute_list–test_attribute)返回的結(jié)點(diǎn)；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é)點(diǎn)，并以該屬性標(biāo)記，對屬性的每個值創(chuàng)建分枝，并據(jù)此劃分樣本Data

Mining:

Concepts

andTechniques16星期二星期二Data

Mining:

Concepts

andTechniques17例:

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

判定樹歸納類標(biāo)號屬性

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é)點(diǎn),用age標(biāo)記,并對于每個屬性值,引出一個分枝,據(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ù)值屬性的信息增益屬性值按遞增排序，每對相鄰值的中點(diǎn)看成可能的

點(diǎn)對每個可能的

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

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

Mining:

Concepts

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

Mining:

Concepts

andTechniques24星期二8.2.3

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

Mining:

Concepts

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

Mining:

Concepts

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

Mining:

Concepts

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

Mining:

Concepts

andTechniques28星期二第8章分類–分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準(zhǔn)確性小結(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é)點(diǎn)的路徑創(chuàng)建一個規(guī)則。沿著給定路徑上的每個 準(zhǔn)則的邏輯AND形成規(guī)則的前件存放類

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

Mining:

Concepts

andTechniques31星期二第8章分類分類?用判定樹歸納分類分類基于規(guī)則的分類分類的準(zhǔn)確性小結(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)比較分類方法評估

的準(zhǔn)確率:

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

Mining:

Concepts

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

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

Mining:

Concepts

andTechniques37星期二8.6

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

Mining:

Concepts

andTechniques38星期二Data

Mining:

Concepts

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

決策樹歸納、樸素

分類分類評價的度量

：準(zhǔn)確率、錯誤率率如何獲得可靠的分類器準(zhǔn)確率評估：保持交叉驗證提高分類準(zhǔn)確率的技術(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