第八讲-matlab数据挖掘

第八讲Matlab数据挖掘韩璐Matlab数据挖掘分类方法2聚类方法31一、聚类分析聚类分析含义将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类，由聚类所组成的簇是一组对象的集合，这些对象与同一簇中的对象彼此相似，与其它簇中的对象相异。与分类不同，它要划分的类是未知的。二、数据类型及转换1、数据矩阵：用p个变量（也称为度量或属性）来表现n个对象，例如用年龄、身高、性别等属性来表现对象“人”。构成一个n*p的矩阵。2、相异度矩阵：存储n个对象两两之间的近似程度性，表现形式是一个n*n的矩阵。这里d(i,j)是对象i和对象j之间相异性的量化表示npnfnipifipfxxxxxxxxx......................................1111110....)2,()1,(..........0)2,3()1,3(0)1,2(0ndndddd3、区间标度度量一个粗略线性标度的连续度量。（如重量，温度等）为什么这么做?选用的度量单位会直接影响聚类结果。例如千克改位克。一般，所用的单位越小，变量的值域就越大，对聚类的影响也越大。为了避免数据对度量单位的依赖，数据应当标准化。实现度量值的标准化：将原来的度量值转换为无单位的值。数据类型及转换变换方法1）计算平均的绝对偏差Sf2）计算标准化度量值，或z-score:121fnfff121(||||...||)//x,...,xfnmf1m(..)nfffffnffffnfsxmxmxmnxxx是的维度量值，是的平均值，即ffififsmxz对象的相似度计算方法（1）欧几里德距离2222211||..||||),(jpipjijixxxxxxjid（2）曼哈坦距离（3）明斯基距离||..|||x|),(2211jpipjijixxxxxjidqqjpipqjiqjixxxxxjid||..|||x|),(2211（1）二元变量变量的取值只有两个状态，如性别，表示是否吸烟，医疗检查正常还是不正常等。i和j是两个变量：q是两个变量中都为1的个数t是两个变量中都为0的个数s是i变量中为0，j中为1的个数r是i变量中为1，j中为0的个数p=q+r+s+t•二元变量权重相同(对称的，如性别）tsrqsrjid),(即：分子为两者相异的总数，分母为二元变量总数其它类型变量的相异度计算•二元变量权重不同(非对称的）例如，一个疾病化验结果正常和不正常，对一个群体，正常者总是大多数，我们用1表现几率小的情况，0表示另一种情况。评价系数，Jaccard系数srqsrjid),(即：两个相异的数量作为分子，相异的数量加两个为1的数量作为分母。（同对称二元变量相比，两个同为0的数量不出现在分母中）其它类型变量的相异度计算（2）枚举变量可以有若干个不同取值，比如反映产品颜色的color可以是{红、黄、绿、兰、粉红}假设一个枚举变量的状态数目是M。这些状态可以映射到字母、符号或一组整数(1,2,…,M)。pmpjid),(p是全部变量的数目m是匹配的数目。其它类型变量的相异度计算（3）序数型变量•是枚举但有序，比如{金牌、银牌、铜牌}•区间标度度量值划成了区间，比如年龄分成了年龄段{10岁以下，11..20,21..30,..}等。一个序数型变量的值可以映射为秩。例如一个变量f可以有Mf个状态，可以映射到一个有序排列{1，2，…,Mf}。其它类型变量的相异度计算如何处理序数型变量？11fififMrz假设f是用于描述n个对象的一组序数型变量之一，关于f的相异度计算包括如下步骤：1）第i个对象的f值为xif，变量f有Mf个有序的状态，对应于序列1，…，Mf。用对应的秩rif代替xif，rif{1，..，Mf}2）既然每个序数型变量可以有不同数目的状态，经常必须将每个变量的值映射到[0.0，1.0]上，以便每个变量都有相同的权重。可以通过用zif代替rif来实现3)相异度的计算可以采用前面的任意一种距离度量方法（4）比例标度型非线性的取正的数据，如指数型数据。BtBteeAA•对数变换，对象i的f变量的值xif被变换成yif，yif=log(xif)•将xif看成序数型数据其它类型变量的相异度计算三、划分方法划分方法:将一个包含n个数据对象的数据库组织成k个划分（k=n），其中每个划分代表一个簇。给定一个k，要构造出k个簇，并满足采用的划分准则：k-平均:由簇的中心来代表簇；k-中心点:每个簇由簇中的某个数据对象来代表。K-平均算法把n个对象分为k个簇，是簇内具有较高的相似度，而簇间的相似度较底。相似度的计算根据一个簇中对象的平均值（重心）来进行。流程：首先，随机的抽取k个对象，每个对象初始地代表一个簇的平均值。对剩余的每个对象，根据与各个簇中心的距离，将它赋给最近的簇。然后重新计算各个簇的平均值。过程不断反复，直到准则函数收敛。一般采用平方误差准则：kiCpiimpE12||这里，p是空间的点，表示给定的对象，mi是簇Ci的平均值。例子012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910初始点初始点K-中心点首先为每个簇随意选择一个代表；剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象代替代表对象，以改进聚类质量。质量用一个代价函数估算。该函数计算对象与参照对象之间的平均相异度。（比如：代替后的点的平方误差函数-原来的平方误差函数)描述：1）随机选择k个对象作为初始的中心点；2）repeat3）指派每个剩余的对象给离它最近的中心点所代表的簇；4）随机地选择一个非中心点对象Orandom;5)计算用Orandom代替Oj的总代价S;6)ifS0thenOrandom代替Oj,形成新的k个中心点的集合；7)until不发生变化；K-中心点判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：1）p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Oi更近，p重新分配给OiOiOjpOrandom变化过程判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：2)p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Orandom更近，p重新分配给Orandom。OiOjpOrandom变化过程判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：3)p当前隶属于中心点对象Oi。如果Oj被Orandom代替作为中心点后，而p仍然离Oi更近，那么对象的隶属关系不变。OiOjpOrandom变化过程判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：4)p当前隶属于中心点对象Oi。如果Oj被Orandom代替作为中心点后，而p离Orandom更近，那么p重新分配给Orandom。OiOjpOrandom变化过程举例%*************************读取数据，并进行标准化变换*************************[X,textdata]=xlsread('examp09_04.xls');%从Excel文件中读取数据row=~any(isnan(X),2);%返回一个逻辑向量，非缺失观测对应元素1，缺失观测对应元素0X=X(row,:);%剔除缺失数据，提取非缺失数据countryname=textdata(3:end,1);%提取国家或地区名称，countryname为字符串元胞数组countryname=countryname(row);%剔除缺失数据所对应的国家或地区名称X=zscore(X);%数据标准化，即减去均值，然后除以标准差%*************************选取初始凝聚点，进行聚类***************************startdata=X([8,27,42],:);%选取第8、第27和第42个观测为初始凝聚点idx=kmeans(X,3,'Start',startdata);%设置初始凝聚点，进行K均值聚类%******************************绘制轮廓图*********************************[S,H]=silhouette(X,idx);%绘制轮廓图，并返回轮廓值向量S和图形句柄Hcountryname(idx==1)%查看第1类所包含的国家或地区countryname(idx==2)%查看第2类所包含的国家或地区countryname(idx==3)%查看第3类所包含的国家或地区examp08_01文件列出了46个国家和地区3年的婴儿死亡率和出生时预期寿命的数据，使用Kmeans聚类法，实现对国家和地区的聚类分析。Matlab数据挖掘分类方法2聚类方法31概述支持向量机SVM是Vapnik等人提出的基于统计学习理论发展起来的一种新的机器学习的方法。统计学习理论是研究利用经验数据进行机器学习的一种理论，属于计算机科学、模式识别和应用统计学相交叉与结合的范畴，其主要创立者是VladimirN.Vapnik。1974年，Vapnik和Chervonenkis提出了结构风险最小化归纳原则.90年代中期，有限样本情况下的机器学习理论研究逐渐成熟起来,形成了较完善的理论体系—统计学习理论(StatisticalLearningTheory,简称SLT)概述1963年Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子集的划分等价于对整个数据集的划分，这组特征子集就被称为支持向量(SV)。1971年Kimeldorf提出使用线性不等约束重新构造SV的核空间,解决了一部分线性不可分问题。1995年Vapnik的《TheNatureofStatisticalLearningTheory》出版，详细叙述了SVM理论，同时也标志着统计学习理论体系已经走向成熟。近年来，SVM的研究主要集中在本身性质的研究完善以及加大SVM应用研究的深度和广度两方面。概述传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。SVM实质是将最优化的方法应用到机器学习当中，寻找求解分类问题和回归问题等的若干途径。SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值。Vapnik’sinequality:h比较小时，实际风险与经验风险差别不大；随着h增大，置信范围变大，使得用经验风险值代替实际风险值误差很大。empln21ln(4)hnhRRn训练点：最优分类线：w为最优分类线的法向量,b为偏移量。训练点如图所示：可得到两个边界分类线和一个最优分类线。其中：是输入指标向量，是输出指标线性可分支持向量分类机nixxR{1,1}iyyN221y,y,y,NXXXT1最优化问题和判别面这样可以得到一个最大间隔思想：判别面：由得到决策函数如右图所示：**(,)wb2,1min2..1,1,2,,bnnstybnN))sgn(()(bxwxf近似线性可分（广义最优分类面）优化问题：Lagrange方程：广义最优分类面