分群算法.doc

1. 什么是 k-means 聚类算法？ 从网上找到了很多定义，这里选取比较典型的几个； K-Mean 分群法是一种分割式分群方法，其主要目标是要在大量高纬的资料点中找出 具有代表性的资料点；这些资料点可以称为群中心，代表点；然后再根据这些 群中心，进行后续的处理，这些处理可以包含 1 ）资料压缩：以少数的资料点来代表大量的资料，达到资料压缩的功能； 2 ）资料分类：以少数代表点来代表特点类别的资料，可以降低资料量及计算量； 分割式分群法的目的是希望盡量減小每個群聚中，每一點與群中心的距離平方差（square error）。 假設我們現在有一組包含c個群聚的資料，其中第 k 個群聚可以用集合 Gk來表示，假設 Gk包含nk筆 資料 x1, x2, , xnk），此群聚中心為yk，則該群聚的平方差 ek可以定義為： ek = S i |xi-yk|2 ，其中 xi是屬於第 k 群的資料點。 而這c個群聚的總和平方差E便是每個群聚的平方差總和： E = S k=1c ek 我們分群的方法，就變成是一個最佳化的問題，換句話說，我們要如何選取 c 個群聚以及相關的群中心， 使得 E 的值為最小。 2 处理流程 （ 1 ） 从 c 个数据对象任意选择 k 个对象作为初始聚类中心； （ 2 ） 循环（ 3 ）到（ 4 ）直到每个聚类不再发生变化为止； （ 3 ） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （ 4 ） 重新计算每个（有变化）聚类的均值（中心对象） 3. java 算法的实现说明 1) 假设给点一组 c 点资料 X = x1, ., xc ，每一点都有 d 维；给定一个群聚的数目 k, 求其 最好的聚类结果。 2 ） BasicKMeans.java 主类 int coordCount = 250;/ 原始的资料个树 int dimensions = 100;/ 每个资料的纬度数目 double coordinates = new doublecoordCountdimensions; 这里假设 c 点资料为 coordinates 对象，其中 c 为 coordCount,d 为 dimensions 相应值。 int mk = 30; / 想要群聚的数目 根据群聚数目定义 mk 个群聚类对象 mProtoClusters = new ProtoClustermK;/ 见 ProtoCluster 类说明 / 首先随机选取 mk 个原始资料点作为群聚类 mProtoClustersi= new ProtoCluster (coordinatesj );/i 依此为 0 到 mk 的值； j 为 0 到 coordCount 的值 定义一个变量用于记录和跟踪每个资料点属于哪个群聚类 mClusterAssignments = new intcoordCount; mClusterAssignmentsj=i;/ 表示第 j 个资料点对象属于第 i 个群聚类 / 开始循环 / 依次调用计算每个群聚类的均值 mProtoClustersi.updateCenter(mCoordinates);/ 计算第 i 个聚类对象的均值 / 依次计算每个资料点到中心点的距离，然后根据最小值划分到相应的群集类中； 采用距离平方差来表示资料点到中心点的距离； /定义一个变量，来表示资料点到中心点的距离 mDistanceCache = new doublecoordCount mk; /其中mDistanceCacheij表示第i个资料点到第j个群聚对象中心点的距离； /距离算法描述(): a)依次取出每个资料点对象double coord = coordinatesi; b)再依次取出每个群聚类中的中心点对象double center = mProtoClustersj.mCenter; c)计算coord对象与center对象之间的距离 double distance(double coord, double center) int len = coord.length; double sumSquared = 0.0; for (int i=0; ilen; i+) double v = coordi - centeri; sumSquared += v*v;/平方差 return Math.sqrt(sumSquared); d)循环执行上面的流程，把结果记录在mDistanceCacheij中； /比较出最小距离，然后根据最小距离重新对相应对象进行划分 依次比较每个资料点的 最短中心距离， int nearestCluster(int ndx) int nearest = -1; double min = Double.MAX_VALUE; for (int c = 0; c mK; c+) double d = mDistanceCachendxc; if (d min) min = d; nearest = c; return nearest; 该方法返回该资料点对应的最短中心距离的群聚类的索引值； 比较每个 nearestClustercoordCount 的值和mClusterAssignmentscoordCount 的值是否相等，如果全相等表示所有的点已经是最佳距离了，直接返回； 否则需要重新调整资料点和群聚类的关系，调整完毕后再重新开始循环； 调整时需要更新下列数据： a)更新mProtoClustersi中的mCurrentMembership集合； b)更新mClusterAssignmentsi中对应的值； 然后重行开始循环 3 ） ProtoCluster.java 是一个包含代表点的群聚类，该类有两个最主要的属性代表点和群中心； int mCurrentMembership;/ 用于表示每个群聚包含的数据资料点集合 double mCenter;/ 用于表示每个聚类对象的均值，也就是中心对象 void updateCenter(double coordinates) / 该方法计算 聚类对象的均值 ; / 根据 mCurrentMembership 取得原始资料点对象 coord ，该对象是 coordinates 的一个子集；然后取出该子集的均值； 取均值的算法很简单，可以把 coordinates 想象成一个 m*n 的距阵 , 每个均值就是每个纵向列的取和平均值 , 该值保 存在 mCenter 中 for (int i=0; i mCurrentMembership.length; i+) double coord = coordinatesmCurrentMembe