课程二十一玩转大深入浅出数据挖掘技术apriori算法tanagra工具决策树课件0405其他分类器

北风网项目实战培训讲师：艾伦（北风网版权所有)玩转大数据–深入浅出数据挖掘技术其他分类器其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法基于规则的分类器根据“if…then…”的规则来分类数据规则: (Condition)

fi

y备注：其中Condition是根据属性判断的条件，y是推出的类举例：

(血液类型=恒温)

(是否产蛋=是)fi

鸟类基于规则的分类器范例(Can

Fly

=

yes)

fi

Birds(Live

in

Water

=

yes)

fi(Blood

Type

=

warm)

fiFishesMammalsR1:

(Give

Birth

=

no)R2:

(Give

Birth

=

no)R3:

(Give

Birth

=

yes)R4:

(Give

Birth

=

no)(Can

Fly

=

no)

fi

ReptilesR5:

(Live

in

Water

=

sometimes)

fi

AmphibiansNameBlood

TypeGiveBirthCan

FlyLive

in

WaterClasshumanwarmyesnonomammalspythoncoldnononoreptilessalmoncoldnonoyesfisheswhalewarmyesnoyesmammalsfrogcoldnonosometimesamphibianskomodocoldnononoreptilesbatwarmyesyesnomammalspigeonwarmnoyesnobirdscatwarmyesnonomammalsleopard

sharkcoldyesnoyesfishesturtlecoldnonosometimesreptilespenguinwarmnonosometimesbirdsporcupinewarmyesnonomammalseelcoldnonoyesfishessalamandercoldnonosometimesamphibiansgila

monstercoldnononoreptilesplatypuswarmnononomammalsowlwarmnoyesnobirdsdolphinwarmyesnoyesmammalseaglewarmnoyesnobirds基于规则的分类器应用(Can

Fly

=

yes)

fi

Birds(Live

in

Water

=

yes)

fi(Blood

Type

=

warm)

fiFishesMammalsR1:

(Give

Birth

=

no)R2:

(Give

Birth

=

no)R3:

(Give

Birth

=

yes)R4:

(Give

Birth

=

no)(Can

Fly

=

no)

fi

ReptilesR5:

(Live

in

Water

=

sometimes)

fi

AmphibiansHawk满足R1规则=>BirdGrizzly

bear满足R3规则=>MammalNameBlood

TypeGive

BirthCan

FlyLive

in

WaterClasshawkwarmnoyesno?grizzly

bearwarmyesnono?基于规则的分类器特征覆盖率Coverage正确率Accuracy互斥性与兼容性有序投票默认值TidRefundMaritalStatusTaxableIncomeClass1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10(Status=Single)

fi

NoCoverage

=40%, Accuracy

=

50%基于规则的分类器建立方法间接方法C4.5rules直接方法RIPPER,

CN2,

Holte’s

1R基本步骤从一个空规则集开始从数据中学习一个规则删除规则覆盖的数据重复第2步与第3步直到满足结束条件顺序覆盖算法(ii)

Step

1顺序覆盖算法(iii)

Step

2R1(iv)

Step

3R1R2需要考虑的问题规则增长实例消除规则评估停止策略规则增长从普遍到特殊从特殊到普遍实例消除为什么要移除正实例？确保下一跳规则与上一条不一样为什么要移除负实例？防止低估规则精度规则评估标准:AccuracyLaplaceM-estimate=

nc

+1n

+

kn

+

k=

nc

+

kpn:规则覆盖的数据总数n

:规则覆盖的正确数据总数ck

:类总数p

:类先验概率nnc=停止策略停止策略:计算增益如果增益不显著，放弃新规则。直接方法：RIPPER二元问题：选择一个类作为正例，另一个作为反例从正例中学习规则反例作为默认类多元问题：按照类的出现频率排序（由小至大）将最小的类作为正例开始学习规则，其他类都认为是反例将次小的类作为整理，循环学习直接方法：RIPPER一条规则学习方法初始化一个空的规则根据信息增益增加条件当规则不再覆盖反例时停止学习剪枝–标准：v=(p-n)/(p+n)p:

正例数目n:

反例数目ABCD

->

yABC

->

yAB

->

yAC

->

y直接方法：RIPPER构造规则集顺序覆盖查找覆盖正例的最佳规则消除规则覆盖的正例与反例当新规则加入时，计算描述长度当描述长度太长时停止增加新规则间接方法：C4.5RulesC4.5rules:(Give

Birth=No,

Can

Fly=Yes)

fi

Birds(Give

Birth=No,

Live

in

Water=Yes)

fi

Fishes(Give

Birth=Yes)fi

Mammals(Give

Birth=No,

Can

Fly=No,

Live

in

Water=No)fi

Reptiles(

)

fi

AmphibiansGiveBirth?Live

InWater?CanFly?MammalsFishesAmphibiansBirdsReptilesYesNoYesSometimesNoYesNo基于规则的分类器的优点与决策树类似的强描述性容易生成分类速度快与决策树性能类似其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法基于距离的分类器训练集基本思想如果走路像鸭子，叫声像鸭子，那么很可能就是鸭子。计算距离测试样例应用：手写识别K-Nearest

Neighbour

(KNN)XXX(c)

3-nearestneighbor(a)1-nearest

neighbor (b)

2-nearestneighbor如果K太小，容易受噪声影响；如果K太大，临近结点中可能有反例。距离的定义位置敏感哈希函数LSH，例如MinHashiii2

(

p

-

q

)欧式距离d

(

p,

q)

=球面距离例如经纬度，路网距离MVDM其他衡量方法向量夹角MVDMClassMarital

StatusSingleMarriedDivorcedYes201No241-in

n 1i

2

i

n1

n21

2d

(V

,V

)

=距离：d(Single,Married)= |

2/4

–

0/4

|

+

|

2/4

–

4/4

|

=1d(Single,Divorced)= |

2/4

–

1/2

|

+

|

2/4

–

1/2

|

=d(Married,Divorced)0= |

0/4

–

1/2

|

+

|

4/4

–

1/2

|

=d(Refund=Yes,Refund=No)1=

|

0/3

–

3/7

|

+

|

3/3

–

4/7

|

=

6/7TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10ClassRefundYesNoYes03No34数据之间的距离di

=12d

(

X

i

,Yi

)D(

X

,Y

)

=

wX

wYTidRefundMaritalStatusTaxableIncomeCheatXYYesNoSingleMarried125K100KNoNo10数据X与数据Y之间的距离备注:wX

@

1

如果X基本每次都预测准确wX

>1

如果X不是很可靠维度的归一化属性的归一化可以防止计算的计算被某些属性主导例如：一个人的高度变化从1.5米至1.8米一个人的重量变化从30公斤至100公斤基于距离的分类器的特点没有创建模式分类未知数据开销非常大基于距离的分类器范例Condensed

Nearest

Neighbour(CNN)基本思想减少训练集样本保留维持分类边界的结点原始数据精简集最小精简集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集Condensed

Nearest

Neighbour(CNN)基本算法初始化一个只包含一个结点的子集用现有的子集划分训练集并将任意反例放入子集重复步骤二直到子集能够完全划分训练集其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法贝叶斯分类器基于概率论的分类方法条件概率贝叶斯公式P(C)P(

A)P(

A

|

C)

=

P(

A,C)P(C

|

A)

=

P(

A,C)P(C

|

A)

=

P(

A

|

C)P(C)P(

A)贝叶斯公式范例一个医生知道脑膜炎中50%的人会患颈部僵硬一个正常人得脑膜炎的概率是1/50000（先验概率）一个正常人患颈部僵硬的概率是1/20

（先验概率）如果一个病人确诊颈部僵硬，那么他得脑膜炎的概率是多少？P(M

|

S

)

=

P(S

|

M

)P(M

)

=

0.5·1/

50000

=

0.0002P(S

)

1/

20每个属性或类都看做一个随机变量已知变量(A1,A2,…,An)，我们预测类C。相当于计算概率P(C|

A1,A2,…,An

)如何评估P(A1,A2,…,An

|

C)?假设A1,A2,…,An相互独立，P(A1,A2,…,An|C)=P(A1|

C)P(A2|

C)…P(An|

C)贝叶斯分类器P

(

A

A

A

)1

2

nP

(

A

A

A

|

C

)

P

(C

)1

2

nP

(C

|

A

A

A

)

=1

2

n如何统计概率TidRefundMaritalStatusTaxableIncomeEvade1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10类: P(C)

=Nc/N例如：P(No)=7/10,P(Yes)

=

3/10对于单个变量P(Ai

|

Ck)

=|Aik|/

Nc备注：|Aik|

表示值为Ai并且属于类Ck的数目P(Status=Married|No)

=

4/7P(Refund=Yes|Yes)=0如何统计连续值的概率连续值离散化将离散值划分到一些有序区间中二元划分(A

<

v)

or

(A

>

v)统计学估计假设变量符合统计学分布如何统计连续值的概率正态分布:对于(Income,

Class=No):若Class=No均值=110标准差=2975TidRefundMaritalStatusTaxableIncomeEvade1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10)221iji

ijiji

j2

s

22ps(

A

-m-P(

A

|

c

)

=

e12

(

2975

)=

0.00722-(120-110

)P(Income

=120

|

No)

=e2p

(54.54)规则评估标准:N:规则覆盖的数据总数Nic

:规则覆盖的正确数据总数m:类总数p

:类先验概率NNciciciciciciN

+

mN

+

mpN

+

cm

-

estimate

:

P(

A

|

C)

=N

+1Laplace

:

P(

A

|

C)

=Original

:

P(

A

|

C)

=贝叶斯分类器特点对于噪点的鲁棒性变量独立性假设有时候不一定成立其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法人工神经网络ANNX1X2X3Y10001011110111110010010001110000人工神经网络ANNX1X2X3Y100010111101111100100100011100000if

z

is

trueotherwisewhere

I

(

z

)

=

1Y

=

I

(0.3

X

1

+

0.3

X

2

+

0.3

X

3

-

0.4

>

0)人工神经网络ANN模型是一个相互关联的结点与加权链接输出结点根据链接的权重决定输出值将输出值与阙值t比较iY

=I

(wi

Xi

-t)或Y

=

sign(wi

Xi

-

t)i人工神经网络ANN人工神经网络的学习过程便是学校神经结点的权重人工神经网络算法初始化权重值(w0,w1,…,wk)根据训练集数据调整人工神经网络观测函数2i根据观察函数调整权重值i

i

i[Y

-

f

(w

,

X

)]E

=其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法支持向量机支持向量机支持向量机w

•x

+

b

=

0w

•x

+

b

=

-1w

•x

+

b

=

+1-1

if w

•

x

+

b

£

-1

1

if

•

+

b

‡

1w

xf

(

x

)

=2||

w

||2Margin=

支持向量机我们希望得到一个最大的数学上等价于得到一个最小的并且满足如下等式数学上这是一个约束优化的问题22||

w

||Margin

=22||

w

||L(w)

=if w

•

x

i

+

b

£

-11

if w

•

x

i

+

b

‡

1-

1

if

(

x

)

=约束优化假设我们希望得到个g(x)约束下的最小f(x)问题的解为：a：拉格朗日乘数支持向量机如果决策边界是非线性的呢？升维方法x=0x=0范例：一维数据升维后的数据z

=

(x

,

x2

)k

k

k其他分类器基于规则的分类器基于距离的分类器贝叶斯分类器人工神经网络支持向量机混合方法混合方法从同一个训练集中构造一批分类器通过投票的方法对无知数据进行预测混合方法误差假设共有25个基本分类器每个分类器的错误率为e=0.35假设每个分类器相互独立利用混合方法得到的预测错误率为)

=

0.0625

25i=13

25-iii

e

(1

-

e获得训练数据集的方法装袋Bagging提升Bosting装袋Bagg