模糊聚类方法及其在数据分类中的应用研究.docx
- 文档编号:2537179
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:22
- 大小:352.57KB
模糊聚类方法及其在数据分类中的应用研究.docx
《模糊聚类方法及其在数据分类中的应用研究.docx》由会员分享,可在线阅读,更多相关《模糊聚类方法及其在数据分类中的应用研究.docx(22页珍藏版)》请在冰点文库上搜索。
模糊聚类方法及其在数据分类中的应用研究
模糊聚类方法及其在数据分类中的应用研究
摘要:
本论文主要研究模糊聚类方法在数据分类中的应用,目的是研究并提出数据分类的一种新方法——分段线性隶属度函数确定的密度聚类方法。
本论文主要分析研究了现有的数据分类中的几种方法,通过各种理论和实验仿真证明:
本文提出的密度聚类方法克服了现有方法的缺点,特别是避免了模糊
均值聚类方法结果严重依赖随机生成的初始聚类中心,能够快速得到聚类中心,是一种更简单和实用的方法。
关键字:
模糊聚类分析数据分类模式识别数据库
Fuzzyclusteringmethodanditsapplication
indataclassificationresearch
Abstract:
Thispapermainlystudiesthefuzzyclusteringmethodindataclassification,
aimstostudyandputforwarddataclassification--anewmethodofpiecewiselinearmembershipfunctiontodeterminethedensityclusteringmethod.Thispapermainlyanalysisofexistingdataclassificationmethodsthroughvarioustheoreticalandexperimentalsimulationshows:
thisdensityclusteringmethodovercomesdisadvantages,especiallyavoidfuzzymeanclusteringmethodtheresultsdependheavilyonrandomlygeneratedinitialclusteringcenter,canquicklyobtaintheclusteringcenter,isamoresimpleandpracticalmethod.
KeyWords:
Fuzzy;Clusteranalysis;Dataclassification;Patternrecognition;Database;
引言
随着电子技术、计算机技术、通信技术等先进技术的引入,工厂的信息化建设不断增强,工厂每天都会采集到海量的业务数据,包括各类的设计数据、生产监控数据等。
想要弄清楚这些数据有什么作用及其数据的分布情况,就必须对数据进行分类。
目前大多数人研究的方法有K-平均算法﹑中心点算法等,然而模糊聚类分析则是许多分类和系统建模的基础。
聚类的目的是从大量的数据中抽取固有的特征,以获得系统行为的简洁表示。
模糊聚类算法可以对样本空间进行模糊分类,目前已在图像处理、语音识别、数据挖掘等领域得到了诸多应用[1,2]。
Bezdek提出的模糊c均值聚类(FCM)方法[3]是目前比较成熟的模糊聚类方法,但算法结果严重依赖随机生成的初始聚类中心。
本文采用的密度聚类方法较为快速的确定了分段线性隶属度函数,是一种相对简单的方法。
1.模式识别中的模糊聚类的基本理论和方法
1.1模式识别的概念及发展
模式识别(PatternRecognition)是人类的一项基本智能,在日常生活中,人们经常在进行“模式识别”。
随着20世纪40年代计算机的出现以及50年代人工智能的兴起,人们当然也希望能用计算机来代替或扩展人类的部分脑力劳动。
(计算机)模式识别在20世纪60年代初迅速发展并成为一门新学科。
模式识别(PatternRecognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。
模式识别又常称作模式分类,从处理问题的性质和解决问题的方法等角度,模式识别分为有监督的分类(SupervisedClassification)和无监督的分类(UnsupervisedClassification)两种。
二者的主要差别在于,各实验样本所属的类别是否预先已知。
一般说来,有监督的分类往往需要提供大量已知类别的样本,但在实际问题中,这是存在一定困难的,因此研究无监督的分类就变得十分有必要了。
模式识别研究主要集中在两方面,一是研究生物体(包括人)是如何感知对象的,属于认识科学的范畴,二是在给定的任务下,如何用计算机实现模式识别的理论和方法。
前者是生理学家、心理学家、生物学家和神经生理学家的研究内容,后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力,已经取得了系统的研究成果。
应用计算机对一组事件或过程进行辨识和分类,所识别的事件或过程可以是文字、声音、图像等具体对象,也可以是状态、程度等抽象对象。
这些对象与数字形式的信息相区别,称为模式信息。
模式识别所分类的类别数目由特定的识别问题决定。
有时,开始时无法得知实际的类别数,需要识别系统反复观测被识别对象以后确定。
1.2模式识别方法
1.决策理论方法
又称统计方法,是发展较早也比较成熟的一种方法。
被识别对象首先数字化,变换为适于计算机处理的数字信息。
一个模式常常要用很大的信息量来表示。
许多模式识别系统在数字化环节之后还进行预处理,用于除去混入的干扰信息并减少某些变形和失真。
随后是进行特征抽取,即从数字化后或预处理后的输入模式中抽取一组特征。
所谓特征是选定的一种度量,它对于一般的变形和失真保持不变或几乎不变,并且只含尽可能少的冗余信息。
特征抽取过程将输入模式从对象空间映射到特征空间。
这时,模式可用特征空间中的一个点或一个特征矢量表示。
这种映射不仅压缩了信息量,而且易于分类。
在决策理论方法中,特征抽取占有重要的地位,但尚无通用的理论指导,只能通过分析具体识别对象决定选取何种特征。
特征抽取后可进行分类,即从特征空间再映射到决策空间。
为此而引入鉴别函数,由特征矢量计算出相应于各类别的鉴别函数值,通过鉴别函数值的比较实行分类。
2.句法方法
又称结构方法或语言学方法。
其基本思想是把一个模式描述为较简单的子模式的组合,子模式又可描述为更简单的子模式的组合,最终得到一个树形的结构描述,在底层的最简单的子模式称为模式基元。
在句法方法中选取基元的问题相当于在决策理论方法中选取特征的问题。
通常要求所选的基元能对模式提供一个紧凑的反映其结构关系的描述,又要易于用非句法方法加以抽取。
显然,基元本身不应该含有重要的结构信息。
模式以一组基元和它们的组合关系来描述,称为模式描述语句,这相当于在语言中,句子和短语用词组合,词用字符组合一样。
基元组合成模式的规则,由所谓语法来指定。
一旦基元被鉴别,识别过程可通过句法分析进行,即分析给定的模式语句是否符合指定的语法,满足某类语法的即被分入该类。
模式识别方法的选择取决于问题的性质。
如果被识别的对象极为复杂,而且包含丰富的结构信息,一般采用句法方法;被识别对象不很复杂或不含明显的结构信息,一般采用决策理论方法。
这两种方法不能截然分开,在句法方法中,基元本身就是用决策理论方法抽取的。
在应用中,将这两种方法结合起来分别施加于不同的层次,常能收到较好的效果。
1.3模式识别技术的近乎无限的发展潜力
模式识别技术是人工智能的基础技术,21世纪是智能化、信息化、计算化、网络化的世纪,在这个以数字计算为特征的世纪里,作为人工智能技术基础学科的模式识别技术,必将获得巨大的发展空间。
在国际上,各大权威研究机构,各大公司都纷纷开始将模式识别技术作为公司的战略研发重点加以重视。
2.数据分类的基本方法
2.1K-平均值法(k-means)
K-means算法,也被称为k-平均或k-均值,是一种得到最广泛使用的聚类算法。
它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点,算法的主要思想是通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优,从而使生成的每个聚类内紧凑,类间独立。
这一算法不适合处理离散型属性,但是对于连续型具有较好的聚类效果。
因此在计算数据样本之间的距离时,可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量,其中最常用的是欧式距离。
算法描述:
1.为中心向量c1,c2,…,ck初始化k个种子
2.分组:
a)将样本分配给距离其最近的中心向量
b)由这些样本构造不相交(non-overlapping)的聚类
3.确定中心:
a)用各个聚类的中心向量作为新的中心
4.重复分组和确定中心的步骤,直至算法收敛
算法流程:
输入:
簇的数目k和包含n个对象的数据库。
输出:
k个簇,使平方误差准则最小。
算法步骤:
1.为每个聚类确定一个初始聚类中心,这样就有K个初始聚类中心。
2.将样本集中的样本按照最小距离原则分配到最邻近聚类
3.使用每个聚类中的样本均值作为新的聚类中心。
4.重复步骤2.3步直到聚类中心不再变化。
5.结束,得到K个聚类
k-means算法初始中心的选取对算法的影响:
应用实例如下:
棋盘格数据集(Checkerboarddataset)仅使用其中486个正类数据,并将数据变换到[-1,1]之间,分布情况如下图所示:
图1原始数据
图2初始聚类中心均在中心附近
图3初始聚类中心在平面内随机选取
k-means算法的优缺点:
主要优点:
1.是解决聚类问题的一种经典算法,简单、快速。
2.对处理大数据集,该算法是相对可伸缩和高效率的。
因为它的复杂度是0(nkt),其中,n是所有对象的数目,k是簇的数目,t是迭代的次数。
通常k< 3.当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好。 主要缺点: 1.在簇的平均值被定义的情况下才能使用,这对于处理符号属性的数据不适用。 2.必须事先给出k(要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能会导致不同结果。 3.它对于“躁声”和孤立点数据是敏感的,少量的该类数据能够对平均值产生极大的影响。 2.2K-中心点算法(K-medoids) 前面介绍了k-means算法,并列举了该算法的缺点。 而K中心点算法(K-medoids)正好能解决k-means算法中的“噪声”敏感这个问题。 为了减轻k均值算法对孤立点的敏感性,k中心点算法不采用簇中对象的平均值作为簇中心,而选用簇中离平均值最近的对象作为簇中心。 首先,我们得介绍下k-means算法为什么会对“噪声”敏感。 还记得K-means寻找质点的过程吗? 对某类簇中所有的样本点维度求平均值,即获得该类簇质点的维度。 当聚类的样本点中有“噪声”(离群点)时,在计算类簇质点的过程中会受到噪声异常维度的干扰,造成所得质点和实际质点位置偏差过大,从而使类簇发生“畸变”。 k中心算法的基本过程是: 首先为每个簇随意选择一个代表对象,剩余的对象根据其与每个代表对象的距离分配给最近的代表对象所代表的簇;然后反复用非代表对象来代替代表对象,以优化聚类质量。 聚类质量用一个代价函数来表示。 当一个中心点被某个非中心点替代时,除了未被替换的中心点外,其余各点被重新分配。 算法如下: 输入: 包含n个对象的数据库和簇数目k; 输出: k个簇 (1)随机选择k个代表对象作为初始的中心点 (2)指派每个剩余对象给离它最近的中心点所代表的簇 (3)随机地选择一个非中心点对象y (4)计算用y代替中心点x的总代价s (5)如果s为负,则用可用y代替x,形成新的中心点 (6)重复 (2)(3)(4)(5),直到k个中心点不再发生变化 与K-means算法一样,K-medoids也是采用欧几里得距离来衡量某个样本点到底是属于哪个类簇。 终止条件是,当所有的类簇的质点都不在发生变化时,即认为聚类结束。 该算法除了改善K-means的“噪声”敏感以后,其他缺点和K-means一致,并且由于采用新的质点计算规则,也使得算法的时间复杂度上升。 下面我们再来研究一下FCM相对于以上两种算法的优越之处。 3.模糊C-均值聚类算法(FCM) 聚类分析是数据挖掘的一个重要领域,是按照一定的要求和规律将事物分类的一种数学算法。 由于现实问题的模糊性,就需要我们用模糊数学的方法对其进行聚类分析会更符合实际。 模糊聚类分析是依据客观事物间的特征,亲疏程度和相似性,通过建立模糊相似关系对客观事物进行分类的方法。 在基于目标函数的聚类算法中,FCM类型算法的理论最为完善,应用最为广泛。 FCM算法把聚类归结成一个带约束的非线性规划问题,通过优化求解获得数据集的模糊划分和聚类。 该方法设计简单,解决问题的范围广,还可以转化为优化问题而借助经典数学的非线性规划理论求解,并易于在计算机上实现。 FCM算法属于模式识别中的无监督学习,它不需要训练样本,可以直接通过机器学习达到自动分类的目的,而且它的软分类特性符合现实世界对象与类的关系,因此被广泛应用到数据挖掘和信息检索等领域。 3.1FCM算法的定义 模糊聚类算法是一种基于函数最优方法的聚类算法,使用微积分计算技术求最优代价函数,在基于概率算法的聚类方法中将使用概率密度函数,为此要假定合适的模型,模糊聚类算法的向量可以同时属于多个聚类,从而摆脱上述问题。 模糊聚类分析算法大致可分为三类 1)分类数不定,根据不同要求对事物进行动态聚类,此类方法是基于模糊等价矩阵聚类的,称为模糊等价矩阵动态聚类分析法。 2)分类数给定,寻找出对事物的最佳分析方案,此类方法是基于目标函数聚类的,称为模糊C均值聚类。 3)在摄动有意义的情况下,根据模糊相似矩阵聚类,此类方法称为基于摄动的模糊聚类分析法 在介绍FCM具体算法之前我们先介绍一些模糊集合的基本知识。 3.2模糊集基本知识 首先说明隶属度函数的概念。 隶属度函数是表示一个对象x隶属于集合A的程度的函数,通常记做μA(x),其自变量范围是所有可能属于集合A的对象(即集合A所在空间中的所有点),取值范围是[0,1],即0<=1,μA(x)<=1。 μA(x)=1表示x完全隶属于集合A,相当于传统集合概念上的x∈A。 一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A,或者叫定义在论域X={x}上的模糊子集 。 对于有限个对象x1,x2,……,xn模糊集合 可以表示为: (1) 有了模糊集合的概念,一个元素隶属于模糊集合就不是硬性的了,在聚类的问题中,可以把聚类生成的簇看成模糊集合,因此,每个样本点隶属于簇的隶属度就是[0,1]区间里面的值。 通过上面的讨论,我们不难看出FCM算法需要两个参数一个是聚类数目C,另一个是参数m。 一般来讲C要远远小于聚类样本的总个数,同时要保证C>1。 对于m,它是一个控制算法的柔性的参数,如果m过大,则聚类效果会很次,而如果m过小则算法会接近HCM聚类算法。 算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵,这个矩阵表示的是每个样本点属于每个类的隶属度。 根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。 聚类中心表示的是每个类的平均特征,可以认为是这个类的代表点。 3.3模糊C均值聚类 模糊C均值聚类(FCM),即众所周知的模糊ISODATA,是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。 1973年,Bezdek提出了该算法,作为早期硬C均值聚类(HCM)方法的一种改进。 FCM把n个向量xi(i=1,2,…,n)分为c个模糊组,并求每组的聚类中心,使得非相似性指标的价值函数达到最小。 FCM与HCM的主要区别在于FCM用模糊划分,使得每个给定数据点用值在0,1间的隶属度来确定其属于各个组的程度。 与引入模糊划分相适应,隶属矩阵U允许有取值在0,1间的元素。 不过,加上归一化规定,一个数据集的隶属度的和总等于1: (2) 那么,FCM的价值函数(或目标函数)就是式 (2)的一般化形式: (3) 这里uij介于0,1间;ci为模糊组I的聚类中心,dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离;且 是一个加权指数。 构造如下新的目标函数,可求得使(3)式达到最小值的必要条件: (4) 这里j,j=1到n,是 (2)式的n个约束式的拉格朗日乘子。 对所有输入参量求导,使式(3)达到最小的必要条件为: (5) 和 (6) 由上述两个必要条件,模糊C均值聚类算法是一个简单的迭代过程。 在批处理方式运行时,FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]: 步骤1: 用值在0,1间的随机数初始化隶属矩阵U,使其满足式 (2)中的约束条件 步骤2: 用式(5)计算c个聚类中心ci,i=1,…,c。 步骤3: 根据式(4)计算价值函数。 如果它小于某个确定的阀值,或它相对上次价值函数值的改变量小于某个阀值,则算法停止。 步骤4: 用(6)计算新的U矩阵。 返回步骤2。 上述算法也可以先初始化聚类中心,然后再执行迭代过程。 由于不能确保FCM收敛于一个最优解。 算法的性能依赖于初始聚类中心。 因此,我们要么用另外的快速算法确定初始聚类中心,要么每次用不同的初始聚类中心启动该算法,多次运行FCM。 3.4模糊C均值聚类算法如下: 重复1=123…… 步骤1: 计算cluseter原型(方法); 步骤2: 计算距离: 步骤3: 更新分区矩阵: 因为 如果 尽管 否则 如果 并且 , 直到 算法改进: ⒈在模糊聚类的目标函数中Bezdek引入了加权指数m,使Dum的聚类准则变成m=2时候的特例,从数学上说m的出现不自然且没有必要,但如果不给以虑属度乘以权值,那么从硬聚类准则函数到软聚类目标函数的推广准则是无效的,参数m又称为平滑因子,控制着模式早模糊类间的分享程度,因此,要实现模糊c聚类就要选择一适合的m,然而最佳的m的选取目前还缺乏理论,监管存在一些经验值或经验范围,但没有面向问题的优选方法,也缺少参数m的有效性评价准则 ⒉尽管模糊聚类是一种无监督的分类,但现在的聚类算法却=需要应用聚类原型的先验条件,否则算法会产生误导,从未破坏算法的无监督性和自动化。 ⒊因为模糊聚类目标是非凸的,而模糊C均值聚类算法的计算过程又是迭代爬山,一次很容易陷入局部极值点,从而得不到最优解或满意解,同时,大数据量下算法耗时也是困扰人们的一大难题,这两个问题目前还不能得到全面的解决。 ⒋FCM类型的聚类算法属于划份方法,对于一组给定的样本集,不管数据中有无聚类结构,也不问分类结果是否有效,总把数据划分到C个子类中,换言之,现有的聚类分析与聚类趋势,以及有效分析是隔离的分离得。 ⒌FCM的聚类算法是针对特征空间中的点集设计的,对于特殊类型的数据,比如在样本每维特征的赋值不是一个数,而是一个区间。 集合和模糊数时,FCM类型的算法无法直接处理 模糊C均值聚类算法存在上述缺点,改进的算法正确率能达到更高。 FCM算法在处理小数据集的时候是有效的,但随着数据容量和维数的增加,迭代步骤会显著增加,而且在迭代的每一步都要对整个数据集进行操作,无法满足数据挖掘时的需要。 改进算法的思想是首先采用随机抽样的办法,从数据集中选取多个样本,对每个样本应用FCM算法,将得到的结果作为初始群体,然后再利用遗传算法对聚类结果进行优化,选取其中的最优解做为问题的输出,由于采样技术显著的压缩了问题的规模,而遗传又可以对结果进行全局最优化处理,因此在时间性能和聚类质量上都能获得较满意的结果。 遗传算法是美国Michigon大学的JohnHolland研究机器学习时创立的一种新型的优化算法,它的主要优点是: 遗传算法是从一系列点的群体开始搜索而不是从单个样本点进行搜索,遗传算法利用适应值的相关信息,无需连续可导或其他辅助信息,遗传算法利用转移概率规则,而非确定性规则进行迭代,遗传算法搜索过程中,以对群体进行分化以实现并行运算,遗传算法经过遗传变异和杂交算子的作用,以保证算法以概率1收敛到全局最优解—具有较好的全局特性,其次遗传算法占用计算机的内存小,尤其适用计算复杂的非线性问题。 3.5遗传算法的设计部分 1种群中个体的确定 聚类的关键问题是聚类中心的确定,因此可以选取聚类中心作为种群的个体,由于共有C个聚类中心,而每个聚类中心是一个S维的实数向量,因此每个个体的初始值是一个c*s维的市属向量。 2编码 常用的编码方式有二进制与实数编码,由于二进制编码的方式搜索能力最强,且交叉变异操作简单高效,因此采用二进制的编码方式,同时防止在进行交叉操作时对优良个体造成较大的破坏,在二进制编码的方式中采用格雷码的编码形式。 每个染色体含c*s个基因链,每个基因链代表一维的数据,由于原始数据中各个属性的取值可能相差很大,因此需首先对数据进行交换以统一基因链的长度,可以有以下两种变换方式。 1扫描整个数据集,确定每维数据的取值范围,然后将其变换到同一量级,在保留一定有效位的基础上取整,根据有效位的个数动态的计算出基因链的长度。 2对数据进行正规化处理,即将各维数据都变换到相同的区间,可以算出此时的基因链长度为10。 3适应度函数 由于在算法中只使用了聚类中心V,而未使用虑属矩阵u,因此需要对FCM聚类算法的目标函数进行改进,以适用算法的要求, 和目标函数是等价的,由于遗传算法的适用度一般取值极大,因此可取上式的倒数作为算法的使用度函数。 4初始种群的确定 初始种群的一般个体由通过采样后运行FCM算法得到的结果给出,另外的一般个体通过随机指定的方法给出,这样既保证了遗传算法在运算之初就利用背景知识对初始群体的个体进行了优化,使算法能在一个较好的基础上进行,又使得个体不至于过分集中在某一取值空间,保证了种群的多样性。 5遗传操作 选择操作采用保持最优的锦标赛法,锦标赛规模为2,即每次随机取2个个体,比较其适应度,较大的作为父个体,并保留每代的最优个体作为下一代,交叉方式一般采用单点交叉或多点交叉法进行,经过试验表明单点交叉效果较好,因此采用单点交叉法,同时在交叉操作中,应该对每维数据分开进行,以保证较大的搜索空间和结果的有效性,变异操作采用基本位变异法。 6终止条件的确定 遗传算法在以下二种情况下终止 a最佳个体保持不变的代数达到设定的阈值 b遗传操作以到达给定的最大世代数 算法具体步骤如下: 1确定参数,如聚类个数﹑样本集大小﹑种群规模﹑最大世代数﹑交叉概率和变异概率等。 2对数据集进行多次采样并运行FCM算法,得到初始种群的一般个体,通过随机制定产生另一半个体。 3对数据集进行正规化处理并编码。 4计算初始种群中个体的适应度。 5对种群进行遗传操作产生下一代,在操作的过程中,应该排除产生的无效个体。 6计算个体的适应度,如果满足终止条件,则算法结束,否则转到5继续。 在理论上讲进行遗传操作的样本容量越大,聚类的误差越小,由于采样技术显著压缩了问题规模,而遗传算法又可以对全局进行最优化处理,因此改进的算法在时间与性能上都能获得较满意的结果,此算法利用采样技术来提高算法的运行速度,利用遗传算法对聚类进行优化,避免陷入局部最优解,在性能上相比于传统的模糊C均值聚类算法获得较大提高。 3.6FCM算法的应用 从算法的推导过程中我们不难看出,算法对于满足正态分布的数据聚类效果会很好,另外,算法对孤立点是敏感的。 聚类算法是一种比较新的技术,基于曾次的聚类算法文献中最早出现的Single-Linkage层次聚类算法是1957年在Lloyd的文章中最早出现的,之后MacQueen独立提出了经
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模糊 方法 及其 数据 分类 中的 应用 研究