第九章聚类算法
9.1 K-means聚类
　　K-means需要用户设定一个聚类个数（k）作为输入数据，有时k值可能非常大（10,000），这是Mahout闪光的（shines）地方，它确保聚类的可测量性。
　　为了用k-means达到高质量的聚类，需要估计一个k值。估计k值一种近似的方法是根据你需要的聚类个数。比如100万篇文章，如果平均500篇分为一类，k值可以取0/500）。这种估计聚类个数非常模糊，但k-means算法就是生成这种近似的聚类。
9.1.1 All you need to know about k-means
　　下面看一下k-means算法的细节，K-means算法是硬聚类算法，是典型的局域原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。算法采用误差平方和准则函数作为聚类准则函数。K-means算法是很典型的基于距离的算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。k个初始类聚类中心点的选取对聚类结果具有较大的。
　　算法步骤：
　　（1）随机选取任意k个对象作为初始聚类中心，初始代表一个簇；
　　（2）计算点到质心的距离，并把它归到最近的质心的类；
　　（3）重新计算已经得到的各个类的质心；
　　（4）迭代2~3步直至新的质心与原质心相等或小于指定阈值，算法结束。
　　这种两步算法是最大期望算法（EM）的典型例子，
　　第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
　　第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。
　　M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。
9.1.2 Running k-means clustering
　　K-mean聚类用到KMeansClusterer或KMeansDriver类，前一个是在内存（in-memory）里对节点聚类，后者采用MapReduce任务执行。这两种方法都可以就像一个普通的Java程序运行,并且可以从硬盘读取和写入数据。它们也可以在hadoop上执行聚类，通过分布式文件系统读写数据。
　　下面举例,使用一个随机点生成器函数来创建一些点。这些点生成矢量格式的点作为一个正态分布围绕着一个中心。使用Mahout的in-memory K-means 聚类方法对这些点聚类。
　　创建节点：generateSamples方法，取（1,1）为中心点，标准差为2,400个围绕着（1,1）的随机点，近似于正态分布。另外又取了2个数据集，中心分别为（1,0）和（0,2），标准差分别为0.5和0.1。
　　KMeansClusterer.clusterPoints()方法用到一下参数：
List&Vector&作为输入；
距离算法DistanceMeasure采用EuclideanDistanceMeasure；
聚类的阈值Threshold为0.01；
聚类的个数为3；
聚类的中心点采用RandomPointsUtil，随机选取的节点。
　　Mahout-example里的DisplayKMeans类可以直观的看到该算法在二维平面的结果，9.2节将介绍运行一个Java Swing application的DisplayKMeans。
　　如果数据量很大时，应采取MapReduce运行方式，将聚类算法运行在多个机器上，每个mapper得到一个子集的点，每个子集运行一个mapper。这些mapper任务计算出最近的集群作为输入流。
　　K-means聚类的MapReduce Job
　　采用KMeansDriver类的run()方法，需要输入的参数有：
Hadoop的配置conf；
输入Vectors的路径，SequenceFile格式；
初始化聚类中心的路径，SequenceFile格式；
输出结果的路径，SequenceFile格式；
求相似距离时采用的方法，这里采用EuclideanDistanceMeasure；
收敛的阈值，没有超过该阈值的点可移动时，停止迭代；
最大迭代次数，这是硬性限制，到达该最大迭代次数时，聚类停止；
true-迭代结束后聚类；
true-串行执行该算法，false-并行执行该算法；
　　public static void run(Configuration conf,Path input,Path clustersIn,Path output,
　　　　　　　　　　　　　　DistanceMeasure measure,
　　　　　　　　　　　　　　double convergenceDelta,
　　　　　　　　　　　　　　int maxIterations,
　　　　　　　　　　　　　　boolean runClustering,
　　　　　　　　　　　　　　boolean runSequential)
　　采用SparseVectorsFromSequenceFile工具，将sequenceFile转换成Vector，因为K-means算法需要用户初始化k个质心。
阅读(...) 评论() &基于阈值参数距离的模糊C均值聚类算法及应用_论文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基于阈值参数距离的模糊C均值聚类算法及应用
|0|0|暂无简介
中国最大最早的专业内容网站|
总评分0.0|
试读已结束，如果需要继续阅读或下载，敬请购买
定制HR最喜欢的简历
你可能喜欢
您可以上传图片描述问题
联系电话：
请填写真实有效的信息，以便工作人员联系您，我们为您严格保密。您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
张素文-第2章聚类学案.ppt 55页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：350 &&
你可能关注的文档：
··········
··········
此例中{X1，X3，X4}∈Z1=X1{X2，X6}∈Z2=X6{X5，X7，X8，X9，X10}∈Z3=X7§2.4分级聚类法（HierarchicalClusteringMethod）（系统聚类法、层次聚类法）思路：每个样本先自成一类，然后按距离准则逐步合并，减少类数。一、算法：1、N个初始模式本自成一类，即建立N类：计算各类之间（即各样本间）的距离，得一N×N维距离矩阵D(0)。标号(0)表示初始状态。(G_Group)2、如在前一步聚类运算中，已求得距离矩阵D(n)（n为逐次聚类合并的次数），则找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：。3、计算合并后新类别之间的距离，得D(n+1)。4、跳至第2步，重复计算及合并。结束条件：取距离阀值T，当D(n)的最小分量超过给定值T时，算法停止。所得即为聚类结果。(2)或不设阀值T，一直将全部样本聚成一类为止，输出聚类的分级树。类间距离计算准则：HK最短距离法：如H、K是两个聚类，则两类间的最短距离定义为：：H类中的某个样本和K类中的某个样本之间的欧氏距离。：H类中所有样本与K类中所有样本之间的最小距离。其中，如果K类由I和J两类合并而成，则得到递推公式：√HKIJ②最长距离法：若K类由I、J两类合并而成，则有：③中间距离法：介于最长与最短的距离之间。④重心法：将每类中包含的样本的数目考虑进去。⑤类平均距离法：定义类间距离的方法不同，则分类结果不太一致。实际问题中常用几种不同的方法进行计算，比较其分类结果，选择一个比较切合实际的分类。粗略思路自成一类，计算两两元素间距离。最近者合并为一类，再计算所有类两两间的距离。重复此步骤。最近者的距离比规定的距离还要远时停止。或输出分级数例：给出6个五维模式样本如下，按最小距离准则进行系统聚类分类。阀值为。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：……；；得距离矩阵D(0):)＊（2）将最小距离对应的类和合并为1类，得新的分类。计算聚类后的距离矩阵D(1)：由D(0)递推出D(1)。**第二章聚类分析(Clustering)§2.1引言§2.2相似性测度和聚类准则§2.3基于距离阈值的聚类算法1.邻近聚类法2.最大最小距离算法§2.4分级聚类法§2.5动态聚类法1.K-均值算法（或C－均值算法）2.ISODATA算法（略提）§2.1引言二、说明：（1）“相似性”含义：有n个特征值则组成n维向量，称为该样本的特征向量。它相当于特征空间中的一个点，以特征空间中点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”。一、概念：“物以类聚”聚类分析：根据模式之间的相似性对模式进行分类，是一种无导师的学习和分类方法。·特征矢量：设一个研究对象n个特征量测值分别为，它们构成n维特征矢量x，即x为原对象的模式对模式分类识别即对特征矢量分类识别·特征空间：各种不同取值的x的全体构成n维空间，它称为n维特征空间，记为·相似性若两个模式的特征仅存在微小的差别，则称两个模式是相似的。·相似性度量用相似性函数，主要有距离函数x1亮度甲类工件乙类工件分界线（n≥3时为分界面）被分类样品落在那个区域，即被分类于该类。x2纹理显著性（2）聚类分析是否有效，与模式特征向量的分布形式有很大关系。对具体对象作聚类分析时，选取的特征向量是否合适非常关键。例：酱油与可乐。§2.2相似性测度和聚类准则一、相似性测度：衡量模式之间相似性的一种尺度。距离就是一种相似性的测度。复习：已知向量，则:1、欧氏距离（Euclid，欧几里德）——简称距离设、为两个n维模式样本，，，则欧氏距离定义为：距离越小，越相似。使用时应注意模式各特征分量的量纲：(D_Distance)①各特征向量对应的维上，应取相同量纲，且相同的量纲要取相同的单位；同一向量的某几维是相同的物理量时，量纲相同，应取相同的单位。否则分类发生错误。b(5,0)d(4,5)c(1,4)a(0,1)(a)②最好使特征数据标准化，使其与变量的量纲无关。d(0.4,5)c(0.1,4)a(0,1)b(0.5,0)(c)b(5,0)c(1,0.4)d(4,0.5)a(0,0.1)(b)即相同物理量取相同单位。对n维向量：,2、马氏距离(Maharanobis)平方表达式：式中X为模式向量，M为其均值向量，C为该类模式总体的协方差矩阵。(M_Mean)(C_covariance)表示的概念是各分量上模式样本到均值的距离，也就是在各维上模式的分散情况。越大，离均值越远。优点：排除了模式样本之间的相关影响当C=单位矩阵I时，马氏距离为欧氏距离。当m=2时，明氏距离即为欧氏距离。3、明氏距离
正在加载中，请稍后...工具类服务
编辑部专用服务
作者专用服务
基于阈值参数距离的模糊C均值聚类算法及应用
针对提出一种基于阈值参数距离的模糊C均值聚类算法，其思想是在对设定阈值参数对样本数据到聚类中心的距离进行分段，距离大于阈值参数的点相对聚类中心的隶属度为0，距离小于阈值参数的点相对聚类中心的隶属度不同且服从特定的隶属函数。理论推导该算法有效时模糊度指数应介于0到1之间，仿真结果表明该算法相比较传统的FCM算法具有更好的收敛性与聚类准确性。
Abstract：
Presents a kind of fuzzy C Means clustering algorithm based on distance threshold parameter is in. The attach degree of distance greater than the threshold value of the parameter point opposite the center of the cluster will be 0 ,oppositely belong with an approach function since the distance less than the threshold value of the parameter point opposite the center of the cluster by setting a threshold parameter. Theoretical derivation of the algorithm is effective when ambiguity index should be between 0 and 1. Simulation results show that the al-gorithm has better convergence and clustering accuracy compared to traditional FCM algorithm.
作者单位：
空军工程大学,西安,710138
年，卷(期)：
Keywords：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社【图文】聚类分析_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
上传于|0|0|暂无简介
大小：1.42MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢}