基于 K- m e a n s 算法和 F C M 算法的聚类研究(1)

现 代 计 算 机 (总 第 二 六 九 期 ) MODERN COMPUTER2007.10 研究与开发 0 引 言 随着计算机的发展和实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的需要,基于目标 函数的聚类方法已成为聚类 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的主流。这一方面是 由于将聚类问题表述成优化问题易于与经典数学的 非线性规划领域联系起来,可用现代数学方法来求 解。另一方面是由于算法的求解过程比较容易用计算 机来实现。 1 K-means算法的原理 K-means算法的工作原理:算法首先随机从数据 集中选取K个点作为初始聚类中心,然后计算各个 样本到聚类中心的距离,把样本归到离它最近的那个 聚类中心所在的类。计算新形成的每一个聚类的数据 对象的平均值来得到新的聚类中心,如果相邻两次的 聚类中心没有任何变化,说明样本调整结束,聚类准 则函数Jc已经收敛。本算法的一个特点是在每次迭 代中都要考察每个样本的分类是否正确。若不正确, 就要调整,在全部样本调整完后,再修改聚类中心,进 入下一次迭代。如果在一次迭代算法中,所有的样本 被正确分类,则不会有调整,聚类中心不会再有变化。 K-means聚类算法的步骤为(如图 1所示)。 输入n个数据对象集合Xi;输出k个聚类中心Zj 及K个聚类数据对象集合Cj。 ProcedureK-means(s,k) S={x1,x2,⋯ ,xn}; m=1;forj=1tok初始化聚类中心Zj; do { fori=1ton forj=1tok { D(Xi,Zj)=|Xi-Zj|;ifD(Xi,Zj)Min{D(Xi,Zj)} thenXi∈Cj; }//归类 ifm=1thenJc(m)=∑kj=1∑ |Xi-Zj|2 m=m+1;forj=1tok Zj=(∑ni=1(Xi)j)/n;//重置聚类中心 }while|Jc(m)-Jc(m-1)|>ξ 图1K-means聚类过程 2 FCM算法的原理 由于 FCM算法中 m的选择必须与所应用的数 据集相关联,没有一个通用的对任何数据都合理的m 值。对每个数据集,应该根据数据集本身选择合理的 权指数。下面,根据上面讨论的权指数m的选择方法 给出一种实现FCM算法的具体方式,步骤如下: (1)选定将要聚类的数据集D; 基于K-means算法和FCM算法的聚类研究 崔文迪 , 蔡佳佳 (厦门大学信息学院计算机系,厦门 361005) 摘 要: 关键词:模糊聚类;K-means;FCM 采用 K-means算法和 FCM算法实现对 47个城市竞争力的聚类分析,选择较为简便的 聚类有效性函数用于聚类结果的检验,得到了两种有效的聚类算法的实现方式,并验证 该方法的合理性。 收稿日期:2007-07-19 修稿日期:2007-09-05 作者简介:崔文迪(1983-),男,福建厦门人,硕士,研究方向为语音识别 ! MODERN COMPUTER 2007.10 现 代 计 算 机 (总 第 二 六 九 期 ) 研究与开发 (2)根据数据集D计算: Cx= n k=1 !(xk-x")(xk-x")T n||xk-x"||2 并求出Cx的最大特征值λmax(Cx); (3)如果 λmax(Cx)<0.5则取 m≤ 1 1-2λmax(Cx) ;如 果λmax(Cx)≥0.5则该方法无法确定合适的 m,需由用 户来确定m的值; (4)根据选定的m用FCM算法对数据集D聚类。 图2FCM聚类过程 3 算法实验及其结果 3.1数据处理及其标准化 本实验的数据来源于网上收集的47个城市的竞 争力指标。该表格中包含有人才竞争力、资本竞争力、 科学技术竞争力、结构竞争力、基础设施竞争力、区位 竞争力、环境竞争力、文化竞争力、 制度 关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载 竞争力、政府 竞争力、企业管理竞争力和开放竞争力等12个字段。 其中前7个为硬竞争力指标,其余为软竞争力指标。 图3城市竞争力指标 3.2实验工具 本实验采用 MicrosoftVisualC#连接 Access数 据库的方法编程实现的聚类分析功能,基本界面如图 4所示。 3.3实验结果 实验取了人力竞争力分别用 K-means与 FCM 算法进行聚类,聚类的结果如下: ●K-means: 第 0类:重庆 成都 福州 宁波 青岛 西安 苏州 第 1类:深圳 杭州 南京 武汉 天津 第 2类:济南 郑州 石家庄 哈尔滨 长沙 合 肥 长春 沈阳 南昌 第 3类:南通 昆明 烟台 徐州 秦皇岛 泉州 威海 珠海 第 4类:常州 大连 无锡 厦门 海口 第 5类: 第 6类:佛山 东莞 温州 中山 绍兴 嘉兴 惠州 台州 湖州 舟山 第 7类:北京 上海 广州 图4VC#聚类界面设计 表1K-means聚类分布结果 ●FCM: 第 0类: 第 1类:北京 上海 深圳 杭州 广州 重庆 成都 南京 武汉 福州 宁波 哈尔滨 青岛 西安 苏州 天津 大连 沈阳 第 2类:郑州 石家庄 长沙 合肥 常州 佛山 东莞 长春 南通 温州 昆明 烟台 徐州 南昌 中 山 厦门 绍兴 秦皇岛 嘉兴 泉州 惠州 台州 威 海 珠海 海口 湖州 舟山 第 3类: 第 4类:无锡 第 5类: 第 6类: ! 现 代 计 算 机 (总 第 二 六 九 期 ) MODERN COMPUTER2007.10 研究与开发 ResearchonClusterBasedon K-meansAlgorithmandFCMAlgorithm CUIWen-di , CAIJia-jia (DepartmentofComputerScience,XiamenUniversity,Xiamen361005) Abstract: Keywords:FuzzyClusterAnalysis;K-meansAlgorithm;FuzzyC-Means(FCM)Algorithm Proposesaneffectiveimplementmethodoftheclusteranalysisforcompetitivepoweron47 citiesbyFuzzyC-Means(FCM)algorithmandK-meansalgorithm,selectsaclusteringva- lidityfunctionforvalidatingtheresultsoftheclustering,validatestheeffectivenessofthis methodbyexperiments. 第 7类:济南 表2FCM聚类分布结果 从以上几个图表中可得,在定义将47个城市分 为5类时,采用K-means算法能很好地分成5类,每 一类型中都有相应的城市,总体上分配比较均匀,而 采用FCM算法则出现0类和4类都是空类的现象。 FCM算法的实现大多采用由用户根据经验或实 验来确定FCM算法中的所有参数,然后用选定的参 数值运行FCM算法实现聚类。但是,由于缺乏理论指 导,这种启发式的FCM算法实现往往需要进行较长 的时间才能产生令人满意的聚类结果。以下是不同模 糊度聚类的结果,从表中数据可得,当模糊度指数在 一定范围内取值时,随着模糊度指数的增加,分类数 量也明显增加,聚合的能力下降,尽管有些情况下分 类数目相同,但详细信息中各分类的具体城市也有所 不同,由此可知在运用FCM算法实现多城市的竞争 力分析时模糊度指数是一个很关键的参数。 4 结 语 本文分析了K-means算法与FCM算法的原理及 实现过程,并且通过实例数据演示了他们在聚类过程 中的特点。根据实验结果分析,K-means算法对聚类 的分布实现更为精确,但存在着产生孤立点敏感问 题,而 FCM算法对聚类的均匀分布效果不好,而且, 在FCM算法中模糊度指数需用户自己定义,因此在 没有经验的情况下效果也可能比较不好。 参考文献 [1]JiaweiHan.数据挖掘:概念与技术.范明,孟小峰等译. 北京.机械工业出版社,2001 [2]石洪波,于剑,黄厚宽等.一种有效的 FCM算法的实 现方式.北京:北京交通大学 [3]RAgrawal,TImielinski,ASwami.MiningAssociation RulesBetweenSetsofItemsInLargeDatabase.Proc.ACM SIGMDO.Apr.1993:207~216 [4]孙才志,王敬东,潘俊.模糊聚类分析最佳聚类数的确定方 法研究.模糊系统与数学,Vol.15.No.1.Mar.2001:53~56 [5]李昕,郑宇,江芳泽.用改进的 RPCL算法提取聚类的最 佳数目.上海大学学,Vol.5.No.5.Oct.1999:120~122 [6]XuL,KrzyzakA,OjaE.RivalPenalizedCompetitiveLear- ningforClusteringAnalysisRBFNetandCurveDetection. IEEETransactionsonNeuralNetworks,Apr.1993:636~649 [7]唐立新,杨自厚,王梦光.用遗传算法改进聚类分析中的 K-平均算法.数理统计与应用概率,Vol.12.No.4.Dec.1997: 45~48 [8]KhaledAlsabti,SanjayRanka,VineetSingh.AnEfficient K-meansClusteringAlgorithm,Vol.24.Issue7.July.2002: 65~72 [9]Danpelleg,AndrewMoore.AcceleratingExactK-means AlgorithmswithGeometricReasoning.CMU.CS.Jan,2000: 105 !