数据挖掘整理.ppt

四、数据对象之间的相异度和相似度,1、简单属性的相似度和相异度,假设数据对象只有一个属性，则通常其相似度和相异度可按如下定义1.1 标称属性的相异度和相似度,相异度,相似度：s=1-d,例如，如果只考虑顾客的性别属性，如果都是“男”，则他们的相似度为1，相异度为0.,1、简单属性的相似度和相异度,1.2 序数属性的相异度和相似度,d=|x-y|/(n-1)，,相异度,相似度：s=1-d,例如，考虑学生的成绩，共分为A、B、C、D四个等级，则n=4,相异度为2/3.,其中n为属性取值的总个数1、简单属性的相似度和相异度,1.3 区间或比率属性的相异度和相似度,d=|x-y|,相异度,较常用的相似度有：s=1/(1+d),,例如，考虑如下的身高数据,S=1-(d-min_d)/(max_d-min_d),可以计算学生身高的相异度矩阵如下：,,二元属性：属性的值只接受两个值：如真/假，男/女、是/否等，通常用0/1表示则S2与S6之间的相异度为10，而相似度为1/11,有min_d=2,max_d=29,因此，也可以定义相似度为1-(10-2)/(29-2)=19/272.数据对象之间的相似度—相似性度量的例子,2.1。

二元数据的相似性度量,两个仅包含二元属性的对象之间的相似性度量也称为相似系数设x和y是两个对象，都由n个二元属性组成定义如下四个量,,f00=x取0且y取0的属性个数,f01=x取0且y取1的属性个数,f10=x取1且y取0的属性个数,f11=x取1且y取1的属性个数,2.1.1一种常用的相似系数是简单匹配系数,（Simple Matching Coeffient,SMC)，定义如下,SMC=,f00+f11,对于类似顾客是否购买某商品这样的非对称二元数据，这个相似系数则难以体现顾客相同的购买行为Why?,,2.1.2 Jaccard 相似系数Jaccard （ Jaccard Coeffient,JC)相似系数定义如下,J=,f11,例1.设二元数据对象x和y如下，计算其SMC和Jx=（1 0 0 0 1 0 1 0 0 1）,y=（1 0 1 0 1 1 0 0 1 1）,解：f00=,3,f01=,3,f10=,1,f11=,3,因此，SMC=6/10，J=3/7,例2.设两个顾客x和y购买的商品如下，计算 它们的相似系数SMC和J2.1.3 余弦相似度,通常类似于文档—词这样的数据，度量其相似性不能依赖共享0的个数，如果统计0-0匹配，则大多数文档都非常相似，因此同样要忽略0-0匹配。

这类数据最常用的相似度之一就是余弦相似度，定义如下,Cos（x，y）=xy/(||x||||y||),2.1.4 广义Jaccard系数,广义Jaccard系数也可以用于文档数据，并在二元属性情况下归约为Jaccard系数，其定义如下：,例3.两个文档向量x和y如下，分别计算其余弦相似度cos(x，y）和EJ,x= （3 2 0 5 0 0 0 2 0 0）,,EJ=xy/(||x||2+||y||2-xy),y=（1 0 0 3 1 0 6 0 0 1）,,2.1.4 相关性,两个具有二元变量或连续的数据之间对象之间的相关性是对象之间线性联系的度量，一般可以用Pearson相关系数（Pearson，s correlation）来描述其定义如下：,其中,例如，以毫米为单位，20个人的身高通常不会重复，但如果以分米为单位，则某些人很可能具有相同的身高此外，如果使用一个唯一的值表示遗漏值，该值通常用众数1.1.2 百分位数,百分位数的定义：设有容量为n的样本观察值想x1，x2，x3，.，xn，样本的p分位数（0

B：至多有n（1-p）个观察值大于或等于xp样本的p分位数xp 可以按如下方法求得：,将观察值按自小到大的顺序排列成：x(1)≤ x(2) ≤. ≤ x(n);,即：xp=,1若np不是整数，则只有一个数据满足定义的两点要求，这一数据位于大于np的最小整数处，即[np]+1处；,2若np是整数，则位于np和np+1位置的数据均符合要求，此时取这两个数的平均值作为xp；,当np不是整数,（x（np）+x（np+1）)/2,当np是整数,与分位数有关常用术语,一、极差：x(n)- x(1);,median(x)=,二、中位数：p=0.5，此时xp称为中位数，记为median(x)其计算如下:,当n为奇数,（x（n/2）+x（n/2+1）)/2,当n整为偶数,三、第一四分位数Q1：p=0.25；第三四分位数Q3：p=0.75；四分位数极差IQR=Q3-Q1；,例1.下表是中国各省（市）国有单位的人均报酬，单位：元/年分别计算p=0.25,0.5,0.75时的分位数及样本均值解：n=34，n*0.75=8.5,Q3= 32738(江苏）,同理，median=22956（湖北或湖南），Q1=21608（贵州），Q3-Q1=11130，样本均值为27501.59,箱线图如下：,,18392,黑龙江,21608,贵州,32738,江苏,50311,上海,,,,,,箱线图的说明：若中位数位于箱子中间，则数据分布较为对称；若Min离M的距离较Max离M的距离大，在表示数据分布向左倾斜；反之向右。

二、估计,2.1 点估计,2.1.1 矩估计与极大似然估计,另外一种常用的估计方法为折叠刀估计，它通过从一组观测值中忽略一个值来实现对参数的估计假设一个具有n个值的集合x={x1，x2，.，xn}，对均值的单次估计为：,2.1.2 折叠刀估计,θ(i)=(x1+.+xi-1+xi+1+.xn)/(n-1),对这些单次估计求平均值θ= (θ(1)+. θ(n))/n作为总统的均值估计例：设总体的分布率如下：,现有样本的10个观察值：3,3,2,2,1,2,1,2,3,3，分别用矩估计发、极大似然估计法和折叠刀估计法估计θ解：矩估计法,E（X）=3-2θ，,又样本均值为2.2，,因此θ得矩估计值为0.4,极大似然估计：L（ θ）= θ的极大似然估计值也是0.4,数据：3,3,2,2,1,2,1,2,3,3,折叠刀估计法,计算θ(1)=(3+2+2+1+2+1+2+3+3)/9=θ(2)= θ(9)=θ(10)=19/9;,因此对总体均值的估计为: （(19/9+20/9)*4+21/9*2）/10=19.8/9;,θ(3)=(3+3+2+1+2+1+2+3+3)/9= θ(4)= θ(6)=θ(8)=20/9;,θ(5)=(3+3+2+2+2+1+2+3+3)/9= θ(7)= θ(6)=21/9;,又E（X）=3-2θ，,令3-2θ =19.8/9;,解得θ=0.4,估计的一个指导思想是奥卡姆剃刀原则（Ockham’s Razor):越简单的模型能产生越好的结果。

主成分分析步骤：,1.对数据进行标准化：,设标准后的数据仍记为X2.求观察数据的相关系数矩阵数据标准化后，样本的相关系数矩阵即为：,3.计算样本相关阵的特征值和特征向量，并按特征值从小到大排列4.计算累积贡献率，确定综合变量个数训练样本集如下,,决策树是类似如下的一棵树,Outlook,Play=no,Play=yes,windy,Play=yes,Play=no,给定一个新的天气象:“rain,hot,high,true”，则判别其类别,,决策树的构造：分裂属性的选择,四、基于信息增益的特征选择策略,1.相关概念,设信息源X的取值为A=(a1,a2,…,an)，ai出现的概率为pi，称,I(ai)=log(1/pi)=-logpi,为ai的信息量；称,为X的信息熵决策树分类方法利用信息量增加（信息增益）作为特征选择的一种指标信息增益衡量每个属性对分裂后的数据子集的信息量的贡献假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，称,为集合T的信息熵如果m=1，即T的样本都属于一个类，则I（T）=0，达到最小值，何时Ｉ（Ｔ）达到最大？,,假设属性Ａ把集合Ｔ划分为ｖ个子集{T1,T2,,Tv},其中Ti所包含的样本数为ni，那么划分后的熵就是：,分裂后的信息增益定义为,基于信息理论的特征选择方法就是逐一计算每种分裂的信息增益，选择信息增益最大的属性作为分裂属性。

下面以前面给出的数据集为例，利用信息增益方法构造决策树第一步：计算训练样本集Ｔ的信息量分类属性Play有两个类，其样本数统计如下：,因此T的信息量为：,第二步：计算每个属性的信息增益，对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,,Outlook的信息熵为：,,Outlook的信息增益为：,同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,,Temperature的信息熵为：,Temperature的信息增益为：,,对于Humidity属性和Windy属性，统计如下：,计算其信息增益值分别为0.1653和0.0481.,,第三步：比较四个属性的信息增益，按大小顺序排列为,Gain(Outlook)>Gain(Humidity)>Gain(Windy) >Gain(Temperature),因此应该选Outlook作为首分裂结点，即决策树的形状为：,Outlook,,第二层结点的选择与首结点类似，具体选择过程如下：,对于“Sunny”的分支，从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T。

计算T的信息量为：,对于Temperature属性，简单统计如下：,显然,,对于Humidity属性，简单统计如下：,显然,,因此Sunny分支下的分裂属性可选Temperature或Humidity，若取Humidity，则其属性H和N下的记录都为相同的类，该分支算法结束其分支结构如下：,Humidity,Play=No,Play=Yes,,若取Temperature，则重新确定记录集如下：,Temp,Play=No,Play=No,可以看出其三个分支H，C和M下的所有记录也属于相同的类，此分支算法结束其分支结构如右：,Play=Yes,,同理，对于Rain分支，统计数据如下：,Windy,Play=Yes,Play=No,因此选Windy其分支结构如右：,,同理，对于Overcast分支，统计数据如下：,Play=Yes,该分支下所有记录均为同一类，因此该分支算法结束，其结构如下右综合以上结果，最后得到决策树如下：,Outlook,Temp,Play=No,Play=No,Play=Yes,Windy,Play=Yes,Play=No,Play=Yes,,Gini Index的特征选择方法就是逐一计算按每个属性分裂后的Gini Index值，选择gini Index值最小的属性作为分裂属性。

下面以前面给出的数据集为例，利用Gini Index选择策略构造决策树的过程对总样本进行统计如下：,样本集T的gini Index值为,,对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,每个子集的Gini Index值如下：,因此属性Outlook的Gini Index值为：,,同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,因此属性Temperature的Gini Index值为：,,对于Humidity属性和Windy属性，统计如下：,计算其Gini Index值分别为0.3674和0.4357.,,第三步：比较四个属性的Gini Index值如下：,。