数据挖掘概述3

1、讲授：吴雄华,第一章 数据挖掘概述,电话Email：,一、引例,网站这种推荐并非漫无边际，而是有一定技术依据的，这种技术就是数据挖掘技术（DM）。,网站怎么知道读者可能会对这些物品干兴趣？,这是因为网站采用了新的技术来了解顾客的潜在需求，比如：网站从顾客的购买清单中发现你买的书与张三买过的书有几本是相同的，但是还有些书张三已经买了，而你却还没买，网站会据此认为你们的阅读偏好相近，从而你会对那些书也干兴趣。,例1。如果你在当当的购书网站并购买过书籍或音像制品，以后再浏览该网站时经常看到类似的提示：“欢迎你，下面是我们给您推荐的新书和VCD。” 然后就可以在网页的某个位置

2、看到几本新书或VCD的名字及其相关链接。,从这个销售数据中可以得出什么结论？,某超市Post机上记录如下的销售数据：,例2。啤酒与尿布的故事,从数据挖掘的角度就是得到了如下的很强的关联规则：,简单分析发现，有6个顾客买了啤酒，而其中5个人买了尿布，或说，5个买了尿布的顾客都买了啤酒。,规则1：“买啤酒”,“买尿布”。,置信度为5/6,规则2：“买尿布”,“买啤酒”。,置信度为5/5,结论：“买尿布的顾客很可能会买啤酒”。,原因？,对决策者的启示:商品的摆放设计和销售策略。,二、数据挖掘的定义,三、数据挖掘技术产生的动力,数据挖掘的定义有多种不同的定义方式，现在为大家广泛采用的是如下定义：,数据

3、挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。,简单的说，数据挖掘就是从大量的数据中发现有用的信息。,1.数据爆炸问题。 例3、美国未来学家阿尔温托夫勒在1980年的著作在第三次浪潮中认为，未来的信息量将以指数级的速度增长。现在已成事实。,例5.John Roth在联合国世界电信论坛上又提出了一个关于网络科技的一个观点：互联网宽带每9个月会增加一倍的容量，但成本降低一半，比芯片的变革速度还快。-“光纤定律”。,例4.1965年，Intel公司联合创始人Gordon Morore在准备一个演讲时发现了一个具有历史意义的现象:芯片的容量每1824个月增加

4、一倍。他据此推断，按此趋势发展下去，在较短时间内计算能力将呈指数增长。-“摩尔定律”。 。,还有很多案例都可以印证，现在的社会是一个信息爆炸的社会。是在信息的潮流中随波逐流还是“到中流击水，浪遏飞舟”？,数据挖掘技术的另一个产生动力 2.数据过量而知识贫乏,现代人了解古代的主要方式主要是通过前人留下的记录，但是这些记录往往是零碎的、不完全的。例如？,想象一下，如果后人希望了解现在人们的生活状况，他们面临的已不再是信息缺失，而是需要从浩如烟海的资料中有选择性的收集他们认为有用的信息，若没有一定技术支持，其难度恐怕可以用“浪里淘金”或“大海捞针”来形容。,四、数据挖掘的支撑技术,数据挖掘融合了统计

5、、人工智能及数据库等多种学科的理论、方法和技术,如统计学：除了实验设计与数据挖掘的关系不大，其他几乎所有方法都可以用于数据挖掘，如估计、假设检验、回归分析、主成分分析、时间序列分析、马尔科夫链等。,五、数据挖掘的主要任务,1、预测：分类和回归,2、关联分析：如研究顾客的行为模式,3、聚类分析：例如 对于新闻可以根据他们的主题分组。,4、异常检测：识别其特征显著不同于其他数据的观测值（异常点）。主要应用包括检测欺诈、网络攻击、疾病的不寻常模式等。,例 6。信用卡欺诈检测 信用卡公司记录每个持卡人所做的交易，同时也记录信用限度、年龄、年薪和地址等个人信息。由于与合法交易相比，欺诈行为的数目相对较少

6、，因此异常检测技术可以用来构造合法交易的轮廓。当一个新的交易到达时就与之比较。如果该交易的特性与所构造的轮廓很不相同，就把交易标记为可能是欺诈。,第二章 数据,一、理解数据,例 1。有人给你如下数据，每行包含一个病人的信息，用前4个字段预测后一个字段。,你做了相关的工作后再与数据提供者交流，字段1只是一个标号不代表任何实际意义，而字段4中0表示缺失值，在录入数据时偏偏所有的10都变成了0.？!,二、数据属性及其类型,属性（Attitude）是对象的性质或特性。,三、数据集的类型,1、记录数据。如,三、数据集的类型,2、事务数据（购物篮数据），如,三、数据集的类型,3、矩阵数据。如距离矩阵，协方

7、差矩阵，相关系数矩阵等。,4、文档词数据。如,5、时间序列数据,6、其他,四、数据对象之间的相异度和相似度,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、简单属性的相似度和相

8、异度,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/27。,2.数据对象之间的相似度相似性度量的例子,2.1。二元数据的相似性度量,两个仅包含二元属性的对象之间的相似性度量也称为相似系数。设x和y

9、是两个对象，都由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如下，计算

10、其SMC和J。,x=（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和J。,2.1.3 余弦相似度,通常类似于文档词这样的数据，度量其相似性不能依赖共享0的个数，如果统计0-0匹配，则大多数文档都非常相似，因此同样要忽略0-0匹配。这类数据最常用的相似度之一就是余弦相似度，定义如下,Cos（x，y）=xy/(|x|y|),2.1.4 广义Jaccard系数,广义Jaccard系数也可以用于文档

11、数据，并在二元属性情况下归约为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）来描述。其定义如下：,其中,第三章 数据挖掘中的统计方法,一、数据探索,1.1 汇总统计,1.1.1频率与众数,给定一个在v1,v2,.,vk取值的分

12、类属性x和m个对象的集合，值vi的频率定义为,f（vi）=具有属性值vi的对象数/m,众数：具有最高频率的分类属性,例1.某所大学中各年级的学生人数如下表：,则年级属性的众数为“一年级”。,对于连续属性，按照目前的定义，众数通常没有用（为什么？），但在某些情况下，众数可能提供关于值的性质或关于出现遗漏值的重要信息。,例如，以毫米为单位，20个人的身高通常不会重复，但如果以分米为单位，则某些人很可能具有相同的身高。此外，如果使用一个唯一的值表示遗漏值，该值通常用众数。,1.1.2 百分位数,百分位数的定义：设有容量为n的样本观察值想x1，x2，x3，.，xn，样本的p分位数（0p1）是指满足如下

13、性质的xp :,A：至少有np个观察值小于或等于xp。,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，此时

14、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,江苏,

15、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,

16、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=

17、 (7)= (6)=21/9;,又E（X）=3-2，,令3-2 =19.8/9;,解得=0.4,估计的一个指导思想是奥卡姆剃刀原则（Ockhams Razor):越简单的模型能产生越好的结果。,三、主成分分析,3.1 主成分分析概述,在处理多元样本数据时，经常遇到观察数据多，维数很高的问题。如果有每个观察对象有p个属性，选取n个对象进行观察，则达到np个数据。如何从这些数据中提取主要规律，从而分析样本或总体的主要性质？,例如，要分析若干个地区的经济发展状况，对每个地区都要统计很多指标，但如果只根据这些统计数据对不同地区进行评价、比较或排序，则因指标太多、主次不明显很难做到公正客观。另外，这些指

18、标有点是主要的，有点是,有的是次要的，甚至某些指标间还有一定的相关性。能否用较少的几项指标来代替原来较多的指标，使得这较少的几项指标仍能反映原来较多的指标反映的信息？,主成分分析就是把一种原来多个指标变量转化为少数几个相互独立指标变量的统计方法，它不是去分析比较各指标的重要性，将那些不重要的指标简单去掉，而是通过全面分析各项指标所携带的信息，从中提取一下潜在的综合性指标（称为主成分）。,三、主成分分析,3.2 主成分分析的数学模型及其求解步骤,设每个数据对象的有p个属性（指标）观察了n次，得到观察数据矩阵为,用数据矩阵X的p个指标作线性组合（即综合变量）为：,系数aij的确定方法：,对数据集X

19、进行标准化，标准化后的数据仍记为X，然后求出X的样本协方差阵S和相关系数阵R，进而求出R的特征值与及其对应的特征向量。特征值按从大到小顺序排列,对应的标准化特征向量为,则第i个综合变量的组合系数（a1i, a2i,api)即为第i个特征值对应的标准化特征向量。即,第一个综合变量为：,第i个综合变量为：,可以Zi与Zj是正交的，因此主成分分析去除了指标之间的线性相关性。,主成分分析的目的之一就是为了简化数据结构，因而在实际应用中一般绝不用p个主成分，而选用m个主成分（mp）。m取多大，这是一个和实际的问题，为此引入贡献率的概念。,定义3.1：称,为主成分Zi的贡献率。,m的确定：通常累积贡献率达

20、到70%以上时即可。,为m个主成分Z1 ,Z2, ,Zm的累积贡献率。,主成分分析的几何意义。,三、主成分分析,3.3 主成分分析实例,附表1是2008年中国内地各地区按登记注册类型分城镇单位就业人员平均劳动报酬（数据来源：中国统计年鉴2008），对其进行主成分分析。,主成分分析步骤：,1.对数据进行标准化：,设标准后的数据仍记为X。,2.求观察数据的相关系数矩阵。数据标准化后，样本的相关系数矩阵即为：,3.计算样本相关阵的特征值和特征向量，并按特征值从小到大排列。,4.计算累积贡献率，确定综合变量个数。,标准化后的数据为如下，设为X。,按公式求出相关系数矩阵R如下：,求R的特征值和特征向量，

21、特征值从小到大排列，并计算相应的贡献率，如下表：,从上表可以看出，主成分的个数取23个较好。这里取3个。他们对于的单位特征向量为：,第一主成分为：Z1=0.3728*x1+0.2175*x2+0.236*x3+0.3938*x4+0.3581*x8,同样方法可以得到另外两个主成分。根据实际情况，可以对相应的主成分命名。,如上，原数据要考虑8个因素，通过提取主成分后只需要考虑3个因素，设原数据集（未标准化前）为X，三个最大特征值对应的特征向量构成的矩阵为：,主成分分析的应用：1）降维,做矩阵乘法X*V，即可把原8维数据降为3维数据。如本例，变换后的数据为,当第一主成分的系数（最大特征值对应的特征

22、向量）全部同号是，可按第一主成分对数据进行排序。如本例，所给省市的劳动报酬由高到低依次为,主成分分析的应用：1）排序,敬请各位同学提出宝贵意见,非常感谢,作业,第四章 分类,分类（Classification)就是通过学习得到一个目标函数（称为模型函数）f，然后把新的对象x通过f映射到一个预先定义的类别号y。,1.分类的定义：,一、相关概念,2.数据挖掘中分类任务的一般模型,数据集,模型是否合理,2.分类性能的度量,考虑二分类问题即类标号只有2个，可设为1和0.,定义：f11：实际为第一类，按模型也判别为第一类；,f00：实际为第二类，按模型也判别为第二类；,f10：实际为第一类，按模型也判别

23、为第二类；,f01：实际为第二类，按模型也判别为第一类；,则分类性能可以用准确率或错误率来度量,准确率=（f11+f00)/(f11+f00+f10+f01),准确率=1-准确率,3.常见的分类方法,常见的分类有：决策树、神经网络、支持向量机、遗传算法、粗糙集、贝叶斯等。,三、基于决策树的分类方法,例1.下表是用于构造分类模型的数据集，包括14个样本和5个属性:Outlook、Temperature、Humidity、Windy和Play，其中前4个属性是天气，最后一个属性是根据前4个属性的情况说明这样的天气状况是否适合比赛。各属性取值如下：,Outlook：sunny(s),overcast

24、(o),rain(r); Temperature:hot(h),mild(m),cool(c); Humidity:high(h),normal(n); Windy:false,true Play:Yes(y),no(n),训练样本集如下,决策树是类似如下的一棵树,Outlook,Play=no,Play=yes,windy,Play=yes,Play=no,给定一个新的天气象:“rain,hot,high,true”，则判别其类别,决策树的构造：分裂属性的选择,四、基于信息增益的特征选择策略,1.相关概念,设信息源X的取值为A=(a1,a2,an)，ai出现的概率为pi，称,I(ai)=lo

25、g(1/pi)=-logpi,为ai的信息量；称,为X的信息熵。,决策树分类方法利用信息量增加（信息增益）作为特征选择的一种指标。信息增益衡量每个属性对分裂后的数据子集的信息量的贡献。,假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，称,为集合T的信息熵。,如果m=1，即T的样本都属于一个类，则I（T）=0，达到最小值，何时（）达到最大？,假设属性把集合划分为个子集T1,T2,.,Tv,其中Ti所包含的样本数为ni，那么划分后的熵就是：,分裂后的信息增益定义为,基于信息理论的特征选择方法就是逐一计算每种分裂的信息增益，选择信息增益最大的属性作为分裂属性。,

26、下面以前面给出的数据集为例，利用信息增益方法构造决策树。,第一步：计算训练样本集的信息量。分类属性Play有两个类，其样本数统计如下：,因此T的信息量为：,第二步：计算每个属性的信息增益，对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,Outlook的信息熵为：,Outlook的信息增益为：,同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,Temperature的信息熵为：,Temperature的信息增益为：,对于Humidity属性和Windy属性，统计如下：,计算其信息增益值分别为0.165

27、3和0.0481.,第三步：比较四个属性的信息增益，按大小顺序排列为,Gain(Outlook)Gain(Humidity)Gain(Windy) Gain(Temperature),因此应该选Outlook作为首分裂结点，即决策树的形状为：,Outlook,第二层结点的选择与首结点类似，具体选择过程如下：,对于“Sunny”的分支，从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T。,计算T的信息量为：,对于Temperature属性，简单统计如下：,显然,对于Humidity属性，简单统计如下：,显然,因此Sunny分支下的分裂属性可选Temperature或Hum

28、idity，若取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,该分支下所有记录均为同一类，因此该分支算法结束，其结构

29、如下右。,综合以上结果，最后得到决策树如下：,Outlook,Temp,Play=No,Play=No,Play=Yes,Windy,Play=Yes,Play=No,Play=Yes,决策树构造好后，给出新的对象便可判别其类别，例如，新的天气对象为： 1)“Overcast,cool ,high,False” 2)“Rain,Mild,Normal,True”，其类别分别为：,五、基于数据分布的特征选择策略,除了基于信息增益的特征选择策略外，还可以根据结点的数据类别的分布来选择最优分裂结点，称之为Gini Index方法。,定义：假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类

30、在T中出现的比例为pi，则T的Gini Index定义为：,假设属性把集合划分为个子集T1,T2,.,Tv,其中Ti所包含的样本数为ni，那么这个划分的Gini Index为：,Gini Index的特征选择方法就是逐一计算按每个属性分裂后的Gini Index值，选择gini Index值最小的属性作为分裂属性。,下面以前面给出的数据集为例，利用Gini Index选择策略构造决策树的过程。对总样本进行统计如下：,样本集T的gini Index值为,对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,每个子集的Gini Index值如下：,因此属性Out

31、look的Gini Index值为：,同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,因此属性Temperature的Gini Index值为：,对于Humidity属性和Windy属性，统计如下：,计算其Gini Index值分别为0.3674和0.4357.,第三步：比较四个属性的Gini Index值如下：,因此应该选Outlook作为首分裂结点，即决策树的形状为：,Outlook,第二层结点的选择与首结点类似，具体选择过程如下：,对于“Sunny”的分支，从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T。

32、,对于Temperature属性，简单统计如下：,对于Humidity属性，简单统计如下：,显然,因此Sunny分支下的分裂属性可选Temperature或Humidity，若取Humidity，则其属性H和N下的记录都为相同的类，该分支算法结束。,其分支结构如下：,Humidity,Play=No,Play=Yes,剩下的计算类似，最后得到决策树如下：,Outlook,Temp,Play=No,Play=No,Play=Yes,Windy,Play=Yes,Play=No,Play=Yes,六、信息增益和Gini Index值的另一个应用,考虑如下问题：预测贷款申请者是否会按时归还贷款，历史

33、数据如下：,对于“年收入”属性，它是连续型变量，按前面决策树的构造方法，应该每个属性都是离散型属性。为此，应该把连续型属性划分成若干个区间，这样把该属性化为离散型属性。简单的，若划分为两个区间，如何划分？,可以用信息增益或Gini Index值方法。步骤如下：,把连续型属性值由小到大排列，取每两个值的中间值作为候选划分点：,然后计算按各个候选划分点划分的信息增益或GiniIndex值，例如，用Gini Index值方法如下：,对于候选点65，划分后类别统计如下,对于候选点72，划分后类别统计如下,对于候选点80，,对于候选点87，,对于候选点92，,对于候选点97，,对于候选点110，,对于候

34、选点122，,对于候选点172，,根据上面的分析，可把“年收入”属性划分成两个区间（0,97）和97,10000)分别设为属性A1和A2，则原数据集变为：,再按前面的方法构造决策树，便可对类似的顾客：“否，单身，100K”进行分类判别。,七、朴素贝叶斯分类法,1.朴素贝叶斯分类方法描述,设样本集T有n个属性：A1，A2，An，可能的类别有m个： C1，C2，Cm，待分类的样本为x=X1,X2，Xn，分别计算条件概率：,则条件概率P(Ci|X）最大所对应的类Ci即为X所在的类。,在公式（1）中，计算等式左边的每个条件概率时，右边的分母相同，因此只需要计算分子，然后比较大小即可。,各概率的计算如下

35、：,另外，用朴素贝叶斯分类时还需假设各属性之间相互独立，此时有：,2.条件概率 P(xj|Ci）的估计,条件概率 P(xj|Ci）的估计值分两种情况,情形1. 第j个属性Aj为离散型 的情况,此时，条件概率 P(xj|Ci）可按如下公式计算：,例1：给定训练样本集如下，请用贝叶斯方法判别对象：“rain，hot，high，true”的类别。,解：分类属性Play有两个类， Play=yes（C1）和其Play=no（C2），样本数统计如下：,于是P（C1）=9/14， P（C2）=5/14,对于Outlook属性，数据汇总如下表：,于是各条件概率为：,，,，,，,同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：,于是各条件概率为：,，,，,，,对于Hu