模糊k均值分类器

毕业论文•论文题目模糊k均值分类器•指导老师•论文完成人论文结构设计•前言•1模糊集合理论•2模糊聚类分析方法•3模糊k均值分类器的算法实现•4模糊k均值分类器运用实例•5结论、致谢词、参考文献•对于一个普通的集合，空间中任一元素，要么要么，二者必居其一。如果利用特征函数法来描述元素属于集合的程度，则对于集合，其特征函数可以标记为:•从上式可以看出，对于任意给定的都有唯一确定的特征函数与之对应，因此可以将集合表示为：•其中是从到的一个映射，它唯一确定了集合。AxAxAxAxuA1,()0,AxAxxAxX1,0xuAA1,0:XxuAxuAX{0,1}A1.1经典集合与特征函数由此可见，经典集合A与其特征函数uA是一一对应的．由于uA只取0和1两个值，故经典集合A只能用来描述界限分明的研究对象，对界限不分明的对象却无能为力。比如，对“年轻”这个模糊概念，用经典集合就无法给出合理的描述。而在自然界和现实生活中，模糊现象是普遍存在的。因此，必须把经典集合扩充，使之能够刻划模糊现象和解决模糊性问题。1.2模糊集合的定义Ｌ.Ａ.Ｚadeh教授于1965年提出了模糊集合概念，具体定义如下:定义1.2.1模糊集合：论域上X的模糊集合由隶属度来表征，其中在实轴的闭区间[0,1]上取值，的值反应了中的元素对于的隶属程度。：X[0，1]，所确定的集合为X上的模糊集合，而称为模糊集合的隶属函数，μA(u)称为元素u对于的隶属度。1图1.1隶属度函数xuAAxuAxuAxuAXxAAxuAAAAu•由此可见，模糊集合是一个抽象的概念，其元素是不确定的，我们只能通过隶属函数来认识和掌握．(u)的数值的大小反映了论域X中的元素u对于模糊集合的隶属程度，(u)的值越接近于1，表示u隶属于的程度越高；而μ(u)的值越接近于０，表示u隶属于的程度越低．特别地，•若(u)=１，则认为u完全属于；•若(u)=０，则认为u完全不属于．因此,经典集合可看作是特殊的模糊集合．换言之，模糊集合是经典集合的推广。AAAAAAAAAAAAA•1.3模糊集合的表示方法•1扎德表示法例1.3.1：设U={u1,u2,u3,u4,u5}，则表示论域U上u1对于A的隶属度为0.87，u2对于A的隶属度为0.75，u3对于A的隶属度为0.96，u4对于A的隶属度为0.78，u5对于A的隶属度为0.56的模糊集合。5432156.078.096.075.087.0uuuuuA2.向量表示法当论域U={u1,u2,…,un}时，AF(U)也可用如下向量来表示：A=(A(u1)，A(u2)，…，A(un))（1）例如，例1.2.1中的模糊集合A也可表示为A=(0.87，0.75，0.96，0.78，0.56)由于A(ui)[0,1](i=1，2，…，n)，故称式（1）所示的向量为模糊向量。1.4模糊关系与模糊矩阵1.4.1普通关系与Boole矩阵例如设U表示某校全体学生的集合,R={(u,v)|v是u的同学}.则R表示U上的“同学”关系定1.4.2设U={u1,u2,…,um},V={v1,v2,…,vn},R∈P(U×V),令rij=R(ui,vj)(i=1,2,…,m;j=1,2,…,n),则R=(rij)m×n为一个m×n矩阵,由于故R=(rij)m×n是一个布尔矩阵.这说明:有限论域间的普通关系可由Boole矩阵来表示.RvuRvuvuRjijiji),(,0;),(,1,1.4.2模糊关系与模糊矩阵定义1.3.3设U,V为两个论域,若R∈F(U×V)则称R为U到V的一个模糊关系.对(u,v)∈U×V,称R(u,v)为u对v具有模糊关系R的相关程度.特别地(1)称R∈F(U×U)为U上的模糊关系;(2)若(u,v)∈U×U,有则称R为U上的恒等关系,这时记R=I;(3)若(u,v)∈U×V,有R(u,v)=0,则称R为U到V的零关系,这时记R=0;(4)若(u,v)∈U×V,有R(u,v)=1,则称R为全称关系,这时记R=E.由定义可见,R(u,v)反映了u对于v的相关程度,若R(u,v)越接近于1,则u与v对R的关系越密切;若R(u,v)越接近于0,则u与v对R的关系越稀疏.特别地,当R(u,v)∈{0,1}时,与u与v对R具有明确关系.因此,模糊关系是普通关系的推广,它能从更深刻的意义上表现出事物的更广泛的联系.定义3.1.4设U={u1,u2,…,um},V={v1,v2,…,vn},R∈F(U×V),则可以用一个m×n阶矩阵来表示,即R=(rij)m×n,其中rij=R(ui,vj)(i=1,2,…,m;j=1,2,…,n),由于R(ui,vj)∈[0,1],故称R=(rij)m×n为模糊矩阵.由于{0,1}[0,1],故模糊矩阵是Boole矩阵的推广.例1.4.1设U={u1,u2,u3,u4}为生产资料商品集,V={v1,v2}为两种消费品的集合,W={w1,w2,w3}为三个市场的细分,以R表示U到V的原料供应关系,以Q表示V到W的市场占有关系。模糊关系矩阵表示如下：82.053.047.024.045.038.0,60.025.063.012.080.030.040.060.0QR主要内容3.1算法简介3.2算法原理3.3算法实例3.4分类器算法步骤3.5流程图3模糊k均值分类器的实现2模糊聚类分析方法•1分类数不定（根据不同要求对事物进行动态聚类）•2分类数确定（主要是基于目标函数的聚类如模糊k均值聚类分析）•3在摄动有意义的情况下的聚类3.1算法简介•k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。•3.2算法原理•聚类：将物理或抽象对象的集合分组成为由类似的对象组成的多各类的过程被称为聚类。所形成的类是一组数据对象的集合，这些对象与同一个类中的对象彼此相似，与其他类中的对象相异。•对于数据聚类的效果，可以使用类内距离来描述。在空间中，定义两个对象的距离，使用欧式空间的距离公式。设x1，x2是两个样本数据,分别有n个属性。•则其空间距离定义为：•类内总距离定义为：其中K表示的是分类数，表示类别点，表示第i类的中心，表示属于第i类的第几个点。2121()niiidxxiixjx211()KLjiijDxx•Step1：为中心向量,,…,初始化k个种子•Step2:分类：将样本分配给距离其最近的中心向量表示各聚类中心点（类距离平均值）•Step3：确定中心:用各个聚类的中心向量作为新的中心•Step4：计算准则函数E：若的值和前一次分类的不相等，重复分类和确定中心的步骤，直至算法收敛nijikjPx12},...,2,1{minjPICxiixCx1kiCxiixxE12EEkc1c2c•3.3算法实例Oxy10220031.50450552数据对象集合S见表1，作为一个聚类分析的二维样本，要求的类的数量k=2。(1)选择，为初始的簇中心即，。(2)对剩余的每个对象，根据其与各个类中心的距离，将它赋给最近的类。对：2,01O0,02O2,011OM0,022OM3O5.2025.10,2231OMd5.1005.10,2232OMd显然，故将分配给3132,,OMdOMd3O2C4O2214,052029dMO2224,05005dMO2414,,dMOdMO4O2c5O2215,05225dMO2225,050229dMO1525,,dMOdMO5O1C511,OOC252250220022221E25.272E2234,,COOOOxy10220031.504505522,011OM0,022OM•对于：•因为所以将分配给•对于:•因为所以将分配给•更新得到新的分类和•计算平方误差准则，单个方差为，。总体平均方差是：（3）计算新的类的中心。25.5225.272521EEE2,5.2222,2501M0,17.23000,355.102M重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配给C2，O4分配给C2，O5分配给C1。更新，得到新类和。中心为，。单个方差分别为511,OOC4322,,OOOC2,5.21M0,17.22M5.122255.2225.2022221E15.132E总体平均误差是：65.2515.135.1221EEE由上可以看出，第一次迭代后，总体平均误差值52.25~25.65，显著减小。由于在两次迭代中，类中心不变，所以停止迭代过程，算法停止。Oxy10220031.50450552k-means算法的性能分析主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果类是密集的，而类与类之间区别明显时,它的效果较好。主要缺点在类的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。该算法对于连续型数据的分聚类有较好效果，不适用于离散型数据必须事先给出k（要生成的类的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。•3.4分类器算法步骤输入：类的数目和包含M×N个数据其中M为样本数目，N为样本属性（维数）。输出：k个类，使平方误差准则最小。算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有k个初始聚类中心。2.将样本集中的样本按照最小距离原则分配到最邻近聚类3.更新簇的平均值，即类中心，重新计算每个类中对象的平均值；4.如果新的平均值发生改变，转至（2）步；5.新的平均值不在发生改变，算法聚类结束，得到k个聚类。•3.5流程图•k均值算法流程图开始输入聚类样本的属性（维数），样本数目，类别（簇）数K对新生成的类重新计算平均值新的平均值改变结束聚类NY4实例演示例：为了检验分类器的效果，我们抽取出宁夏磁窑堡井田的煤层地址条件进行模糊分类，从而说明模糊K均值分类器在工业实际上的重要应用。选择磁窑堡井田某煤层的12个煤层段作为分类对象的集合：•并且采用如下煤层分类特性指标：煤层厚度用；•煤层倾角；•煤厚标准率：式中M为大于可采厚度的钻孔数，n为煤层内钻孔个数；},,...,,,{12321uuuuUmH%%100nM•煤厚离差系数：离差系数r是一种离散性参数，它反映煤层内煤厚偏离平均厚度的大小，即式中为煤厚的标准差，即这里为煤层的平均值，为煤层内各钻孔的煤厚，为煤层内钻孔个数。于是对于分类煤层集合中任一对象均对应一个分类特性指标四维向量：分类煤层集合中各煤层段的特性指标见表4.1：(%)r%100ur21121niiuunuiumnuiu12321,...,,,,,,iiiiiuuuurHu},,...,,,{12321uuuu•表4.1各煤层的特性指标煤层块段序号平均煤厚煤层倾角煤厚合标准率离差系数14.421810.0623.791310.2735.911110.3641.12170.670.5252.961710.5762.421110.5470.99130.630.2381130.60.4991.26130.690.55