189 8069 5689
K-MEANS算法:
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、虚拟空间、营销软件、网站建设、枞阳网站维护、网站推广。
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
具体如下：
输入：k, data[n];
（1） 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1];
（2） 对于data[0]….data[n], 分别与c[0]…c[n-1]比较，假定与c[i]差值最少，就标记为i;
（3） 对于所有标记为i点，重新计算c[i]=/标记为i的个数；
（4） 重复(2)(3),直到所有c[i]值的变化小于给定阈值。
算法实现起来应该很容易，就不帮你编写代码了。
几种典型的聚类融合算法：
1.基于超图划分的聚类融合算法
(1)Cluster-based Similarity Partitioning Algorithm(GSPA)
(2)Hyper Graph-Partitioning Algorithm(HGPA)
(3)Meta-Clustering Algorithm(MCLA)
2.基于关联矩阵的聚类融合算法
Voting-K-Means算法。
3.基于投票策略的聚类融合算法
w-vote是一种典型的基于加权投票的聚类融合算法。
同时还有基于互信息的聚类融合算法和基于有限混合模型的聚类融合算法。
二、基于关联矩阵的聚类融合算法——Voting-K-Means算法
Voting-K-Means算法是一种基于关联矩阵的聚类融合算法，关联矩阵的每一行和每一列代表一个数据点，关联矩阵的元素表示数据集中数据点对共同出现在同一个簇中的概率。
算法过程：
1.在一个数据集上得到若干个聚类成员；
2.依次扫描这些聚类成员，如果数据点i和j在某个聚类成员中被划分到同一个簇中，那么就在关联矩阵对应的位置计数加1；关联矩阵中的元素值越大，说明该元素对应的两个数据点被划分到同一个簇中的概率越大；
3.得到关联矩阵之后，Voting-K-Means算法依次检查关联矩阵中的每个元素，如果它的值大于算法预先设定的阀值，就把这个元素对应的两个数据点划分到同一个簇中。
Voting-K-Means算法的优缺点：
Voting-K-Means算法不需要设置任何参数，在聚类融合的过程中可以自动地的选择簇的个数 并且可以处理任意形状的簇。因为Voting-K-Means算法在聚类融合过程中是根据两个数据点共同出现在同一个簇中的可能性大小对它们进行划分的，所以只要两个数据点距离足够近，它们就会被划分到一个簇中。
Voting-K-Means算法的缺点是时间复杂度较高，它的时间复杂度是O(n^2);需要较多的聚类成员，如果聚类成员达不到一定规模，那么关联矩阵就不能准确反映出两个数据点出现在同一个簇的概率。
package clustering;import java.io.FileWriter;import weka.clusterers.ClusterEvaluation;import weka.clusterers.SimpleKMeans;import weka.core.DistanceFunction;import weka.core.EuclideanDistance;import weka.core.Instances;import weka.core.converters.ConverterUtils.DataSource;import weka.filters.unsupervised.attribute.Remove;public class Votingkmeans2 extends SimpleKMeans { /** 生成的序列号 */ private static final long serialVersionUID = 1557181390469997876L; /** 划分的簇数 */ private int m_NumClusters; /** 每个划分的簇中的实例的数量 */ public int[] m_ClusterSizes; /** 使用的距离函数，这里是欧几里德距离 */ protected DistanceFunction m_DistanceFunction = new EuclideanDistance(); /** 实例的簇号赋值 */ protected int[] m_Assignments; /** 设定聚类成员融合阀值 */ private final static double THREASOD = 0.5; /** 生成一个聚类器 */ public void buildClusterer(Instances data) throws Exception{ final int numinst = data.numInstances(); // 数据集的大小 double [][]association = new double[numinst][numinst]; // 定义并初始化一个关联矩阵 int numIteration = 40; // 设置生成的聚类成员数 final int k = (int)Math.sqrt(numinst); // 设置K-Means聚类算法参数——簇数 for(int i = 0; i numIteration; i++) { if(data.classIndex() == -1) data.setClassIndex(data.numAttributes() - 1); // 索引是从0开始 String[] filteroption = new String[2]; filteroption[0] = "-R"; filteroption[1] = String.valueOf(data.classIndex() + 1);// 索引是从1开始 Remove remove = new Remove(); remove.setOptions(filteroption); remove.setInputFormat(data); /* 使用过滤器模式生成新的数据集；新数据集是去掉类标签之后的数据集 */ Instances newdata = weka.filters.Filter.useFilter(data, remove); /* 生成一个K-Means聚类器 */ SimpleKMeans sm = new SimpleKMeans(); sm.setNumClusters(k); sm.setPreserveInstancesOrder(true); // 保持数据集实例的原始顺序 sm.setSeed(i); // 通过设置不同的种子，设置不同的簇初始中心点，从而得到不同的聚类结果 sm.buildClusterer(newdata); int[] assigm = sm.getAssignments(); // 得到数据集各个实例的赋值 /* 建立关联矩阵 */ for(int j = 0; j numinst; j++) { for(int m = j; m numinst; m++) { if(assigm[j] == assigm[m]) { association[j][m] = association[j][m] + 1.0 / numIteration ; } } } } System.out.println(); /* 将生成的关联矩阵写入.txt文件（注：生成的txt文本文件在e:/result.txt中） */ FileWriter fw = new FileWriter("e://result.txt"); for(int j = 0; j numinst; j++) { for(int m = j; m numinst; m++) { //由于关联矩阵是对称的，为了改进算法的效率，只计算矩阵的上三角 String number = String.format("%8.2f", association[j][m]); fw.write(number); } fw.write("\n"); } /* 处理关联矩阵，分别考虑了两种情况 ：1.关联矩阵中某个元素对应的两个数据点已经被划分到了不同的簇中 * 2.两个数据点中有一个或者两个都没有被划分到某个簇中。 */ int[] flag = new int[numinst]; int[] flagk = new int[k]; int[] finallabel = new int[numinst]; for(int m = 0; m numinst; m++) { for(int n = m; n numinst; n++) { if(association[m][n] THREASOD) { if(flag[m] == 0 flag[n] == 0) { // 两个数据点都没有被划分到某个簇中， int i = 0; // 将他们划分到同一个簇中即可 while (i k flagk[i] == 1) i = i + 1; finallabel[m] = i; finallabel[n] = i; flag[m] = 1; flag[n] = 1; flagk[i] = 1; } else if (flag[m] == 0 flag[n] == 1) { // 两个数据点中有一个没有被划分到某个簇中， finallabel[m] = finallabel[n]; // 将他们划分到同一个簇中即可 flag[m] = 1; } else if (flag[m] == 1 flag[n] == 0) { finallabel[n] = finallabel[m]; flag[n] = 1; } else if (flag[m] == 1 flag[n] == 1 finallabel[m] != finallabel[n]) { // 两个数据点已被划分到了不同的簇中， flagk[finallabel[n]] = 0; // 将它们所在的簇合并 int temp = finallabel[n]; for(int i = 0; i numinst; i++) { if(finallabel[i] == temp) finallabel[i] = finallabel[m]; } } } } } m_Assignments = new int[numinst]; System.out.println("基于关联矩阵的聚类融合算法——Voting-K-Means算法的最终聚类结果"); for(int i = 0; i numinst; i++) { m_Assignments[i] = finallabel[i]; System.out.print(finallabel[i] + " "); if((i+1) % 50 == 0) System.out.println(); } for(int i = 0; i k; i++) { if(flagk[i] == 1) m_NumClusters++; } } /** * return a string describing this clusterer * * @return a description of the clusterer as a string */ public String toString() { return "Voting-KMeans\n"; } public static void main(String []args) { try {String filename="e://weka-data//iris.arff"; Instances data = DataSource.read(filename); Votingkmeans2 vk = new Votingkmeans2(); vk.buildClusterer(data); /* 要生成Voting-K-Means的聚类评估结果包括准确率等需要覆盖重写toString()方法； * 因为没有覆盖重写，所以这里生产的评估结果没有具体内容。 */ ClusterEvaluation eval = new ClusterEvaluation(); eval.setClusterer(vk); eval.evaluateClusterer(new Instances(data)); System.out.println(eval.clusterResultsToString()); } catch (Exception e) { e.printStackTrace(); }}}
分析代码时注意：得到的类成员变量m_Assignments就是最终Voting-K-Means聚类结果；由于是采用了开源机器学习软件Weka中实现的SimpleKMeans聚类算法，初始时要指定簇的个数，这里是数据集大小开根号向下取整；指定的阀值为0.5，即当关联矩阵元素的值大于阀值时，才对该元素对应的两个数据点进行融合，划分到一个簇中，考虑两种情况，代码注释已有，这里不再详述。但聚类融合的实验结果并不理想，莺尾花数据集irsi.arff是数据挖掘实验中最常用的数据集，原数据集共有三个类；但本实验进行四十个聚类成员的融合，其最终聚类结果划分成两个簇；其原因可能有两个：一是算法本身的问题，需要使用其他更加优化的聚类融合算法；二是实现上的问题，主要就在聚类结果的融合上，需要进行一步对照关联矩阵进行逻辑上的分析，找出代码中的问题。关联矩阵文本文件
---------------------
本文来自 Turingkk 的CSDN 博客 ，全文地址请点击：
大数据分析之聚类算法
1. 什么是聚类算法
所谓聚类，就是比如给定一些元素或者对象，分散存储在数据库中，然后根据我们感兴趣的对象属性，对其进行聚集，同类的对象之间相似度高，不同类之间差异较大。最大特点就是事先不确定类别。
这其中最经典的算法就是KMeans算法，这是最常用的聚类算法，主要思想是:在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。
KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。
聚类算法实现
假设对象集合为D，准备划分为k个簇。
基本算法步骤如下：
1、从D中随机取k个元素，作为k个簇的各自的中心。
2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。
3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。
4、将D中全部元素按照新的中心重新聚类。
5、重复第4步，直到聚类结果不再变化。
6、将结果输出。
核心Java代码如下：
/**
* 迭代计算每个点到各个中心点的距离，选择最小距离将该点划入到合适的分组聚类中，反复进行，直到
* 分组不再变化或者各个中心点不再变化为止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//为k个分组，分别定义一个聚簇集合，未来放入元素。
boolean centerchange = true;//该变量存储中心点是否发生变化
while (centerchange) {
iterCount++;//存储迭代次数
centerchange = false;
for (int i = 0; i k; i++) {
results[i] = new ArrayListT();
}
for (int i = 0; i players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 计算距离 这里采用的公式是两个对象相关属性的平方和，最后求开方*/
double dist = distance(initP, p);
dists[j] = dist;
}
int dist_index = computOrder(dists);//计算该点到各个质心的距离的最小值，获得下标
results[dist_index].add(p);//划分到对应的分组。
}
/*
* 将点聚类之后，重新寻找每个簇的新的中心点，根据每个点的关注属性的平均值确立新的质心。
*/
for (int i = 0; i k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心点是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}
}
}
return results;
}
上面代码是其中核心代码，我们根据对象集合List和提前设定的k个聚集,最终完成聚类。我们测试一下，假设要测试根据NBA球员的场均得分情况，进行得分高中低的聚集，很简单，高得分在一组，中等一组，低得分一组。
我们定义一个Player类，里面有属性goal，并录入数据。并设定分组数目为k=3。
测试代码如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(“mrchi1”);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);
Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);
Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他对象定义此处略。制造几个球员的对象即可。
KmeansPlayer kmeans = new KmeansPlayer(listPlayers, 3);
ListPlayer[] results = kmeans.comput();
for (int i = 0; i results.length; i++) {
System.out.println("类别" + (i + 1) + "聚集了以下球员：");
ListPlayer list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "---" + p.getGoal()
}
}
算法运行结果：
可以看出中心点经历了四次迭代变化，最终分类结果也确实是相近得分的分到了一组。当然这种算法有缺点，首先就是初始的k个中心点的确定非常重要，结果也有差异。可以选择彼此距离尽可能远的K个点，也可以先对数据用层次聚类算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
第一次迭代下,除了a4点,其他点都归为一类c1:(a1 a2 a3 a5);c2:(a4) 聚类中心：c1:(2,2);c2(5,4)（聚类中心的计算方式是平均类中所有点）
第二次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)
第三次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)结果已经稳定跳出循环
function y=kMeansCluster(m,k,isRand)
%%%%%%%%%%%%%%%%
%
% kMeansCluster - Simple k means clustering algorithm
% Author: Kardi Teknomo, Ph.D.
%
% Purpose: classify the objects in data matrix based on the attributes
% Criteria: minimize Euclidean distance between centroids and object points
% For more explanation of the algorithm, see
% Output: matrix data plus an additional column represent the group of each object
%
% Example: m = [ 1 1; 2 1; 4 3; 5 4] or in a nice form
% m = [ 1 1;
% 2 1;
% 4 3;
% 5 4]
% k = 2
% kMeansCluster(m,k) produces m = [ 1 1 1;
% 2 1 1;
% 4 3 2;
% 5 4 2]
% Input:
% m - required, matrix data: objects in rows and attributes in columns
% k - optional, number of groups (default = 1)
% isRand - optional, if using random initialization isRand=1, otherwise input any number (default)
% it will assign the first k data as initial centroids
%
% Local Variables
% f - row number of data that belong to group i
% c - centroid coordinate size (1:k, 1:maxCol)
% g - current iteration group matrix size (1:maxRow)
% i - scalar iterator
% maxCol - scalar number of rows in the data matrix m = number of attributes
% maxRow - scalar number of columns in the data matrix m = number of objects
% temp - previous iteration group matrix size (1:maxRow)
% z - minimum value (not needed)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if nargin3, isRand=0; end
if nargin2, k=1; end
[maxRow, maxCol]=size(m)
if maxRow=k,
y=[m, 1:maxRow]
else
% initial value of centroid
if isRand,
p = randperm(size(m,1)); % random initialization
for i=1:k
c(i,:)=m(p(i),:)
end
else
for i=1:k
c(i,:)=m(i,:) % sequential initialization
end
end
temp=zeros(maxRow,1); % initialize as zero vector
while 1,
d=DistMatrix(m,c); % calculate objcets-centroid distances
[z,g]=min(d,[],2); % find group matrix g
if g==temp,
break; % stop the iteration
else
temp=g; % copy group matrix to temporary variable
end
for i=1:k
f=find(g==i);
if f % only compute centroid if f is not empty
c(i,:)=mean(m(find(g==i),:),1);
end
end
end
y=[m,g];
end
The Matlab function kMeansCluster above call function DistMatrix as shown in the code below. It works for multi-dimensional Euclidean distance. Learn about other type of distance here.
function d=DistMatrix(A,B)
%%%%%%%%%%%%%%%%%%%%%%%%%
% DISTMATRIX return distance matrix between points in A=[x1 y1 ... w1] and in B=[x2 y2 ... w2]
% Copyright (c) 2005 by Kardi Teknomo,
%
% Numbers of rows (represent points) in A and B are not necessarily the same.
% It can be use for distance-in-a-slice (Spacing) or distance-between-slice (Headway),
%
% A and B must contain the same number of columns (represent variables of n dimensions),
% first column is the X coordinates, second column is the Y coordinates, and so on.
% The distance matrix is distance between points in A as rows
% and points in B as columns.
% example: Spacing= dist(A,A)
% Headway = dist(A,B), with hA ~= hB or hA=hB
% A=[1 2 3; 4 5 6; 2 4 6; 1 2 3]; B=[4 5 1; 6 2 0]
% dist(A,B)= [ 4.69 5.83;
% 5.00 7.00;
% 5.48 7.48;
% 4.69 5.83]
%
% dist(B,A)= [ 4.69 5.00 5.48 4.69;
% 5.83 7.00 7.48 5.83]
%%%%%%%%%%%%%%%%%%%%%%%%%%%
[hA,wA]=size(A);
[hB,wB]=size(B);
if wA ~= wB, error(' second dimension of A and B must be the same'); end
for k=1:wA
C{k}= repmat(A(:,k),1,hB);
D{k}= repmat(B(:,k),1,hA);
end
S=zeros(hA,hB);
for k=1:wA
S=S+(C{k}-D{k}').^2;
end
d=sqrt(S);
rbf神经网络有多种学习策略，首先选取中心，可以随机选，也可采用K均值聚类，然后学习权值，可采用伪逆法（涉及矩阵的奇异值分解），也可以采用最小均方误差法，或者进化算法，上述方法中心是固定的，也可采用梯度下降法同时学习中心、宽度、权值，这个比较复杂。具体参考《神经网络原理》。
你用Java写可以参考Weka，其完全开源，不过我没有看过源码，不知其用何种学习策略。最近用C++写了一个简单的rbf，即固定中心、最小均方误差法学习权值，但我发现采用K均值聚类选中心跟随机选没有什么区别，不知二者有何区别？自己写伪逆法对于我来说基本不可能，及其复杂，我看到过某人写了个天书般的程序，一个函数500行。
希望对你有帮助，如果你有新发现，欢迎与我探讨，国内估计没多少人真正自己写过RBF，都用MATLAB代入了事。