189 8069 5689
以前做项目时候写的代码，数据是一维的，多维的也一样，把距离计算的改一改就行int term = Math.abs(dotlist.get(centerIndex[j]).x- dotlist.get(i).x);
网站建设公司,为您提供网站建设,网站制作,网页设计及定制网站建设服务,专注于成都定制网站,高端网页制作,对社区文化墙等多个行业拥有丰富的网站建设经验的网站建设公司。专业网站设计,网站优化推广哪家好,专业seo优化排名优化,H5建站,响应式网站。
[java] view plaincopy
package uestc.dmlab.call;
import java.io.BufferedReader;
import java.io.FileReader;
import java.security.KeyStore.Entry;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class Clustering {
/**
*
* @param fileName
* 文件中每个字段对应一个概率
* @param k
* 聚成k个类
* @param minDistance
* 聚类中心位移小于minDistance时停止迭代
* @return
*/
public static HashMapString, Integer cluster(String fileName, int k,
int minDistance) {
try {
BufferedReader br = new BufferedReader(new FileReader(fileName));
ListDot dotlist = new LinkedListDot();
String line;
int count = 0;// 行数
while ((line = br.readLine()) != null) {
String s[] = line.split(",");
Dot dot = new Dot();
dot.isCenter = false;
dot.isVirtual = false;
dot.name = s[0];
// if(s.length4){
// System.out.println(line);
// }
dot.x = Integer.parseInt(s[3]);
dotlist.add(dot);
count++;
}
if (count k) {
k = count;
}
// 随机初始化k个聚类中心
int centerIndex[] = new int[k]; // 存储k个中心点在dotlist中的索引
int centerNum = k;
while (centerNum 0) {
int index = new Random().nextInt(count);
if (!dotlist.get(index).isCenter) {
centerNum--;
dotlist.get(index).isCenter = true;
centerIndex[centerNum] = index;
}
}
// K个聚类
Cluster[] clusers = new Cluster[k];
boolean flag = true;
while (flag) {
flag = false;
clusers = new Cluster[k];
for (int i = 0; i clusers.length; i++) {
clusers[i] = new Cluster();
}
//System.out.println(clusers.length);
// 找到离第i个点最近的聚类中心
for (int i = 0; i dotlist.size(); i++) {
// 该点不是中心点也不是虚拟点就计算它与所有中心点的距离并取最小值
// if(!dotlist.get(i).isCenter!dotlist.get(i).isVirtual){
if (!dotlist.get(i).isVirtual) {
int distance = Integer.MAX_VALUE;
int c = 0;// 记录离该节点最近的中心点的索引
for (int j = 0; j k; j++) {
int term = Math.abs(dotlist.get(centerIndex[j]).x
- dotlist.get(i).x);
if (distance term) {
distance = term;
c = j;
}
}
clusers[c].dots.add(i);
}
}
// 重新计算聚类中心
for (int i = 0; i k; i++) {
Cluster cluster = clusers[i];
if (cluster.dots.size() 0) { //若该类中有点
int sum = 0;
for (int j = 0; j cluster.dots.size(); j++) {
sum += dotlist.get(cluster.dots.get(j)).x;
}
Dot dot = new Dot();
dot.x = sum / cluster.dots.size();
dot.isCenter = true;
dot.isVirtual = true;
// 新旧聚类中心的距离
int term = Math.abs(dotlist.get(centerIndex[i]).x
- dot.x);
if (term minDistance)
flag = true;
dotlist.add(dot);
centerIndex[i] = dotlist.indexOf(dot); // 第i个聚类的中心改变
}
}
}
// 生成分类映射
HashMapString, Integer map = new HashMapString, Integer();
for (Dot dot : dotlist) {
if (dot.isVirtual == false) {
int className = -1;
for (int i = 0; i k; i++) {
if (clusers[i].dots.contains(dotlist.indexOf(dot)))
className = i;
}
map.put(dot.name, className);
}
}
return map;
} catch (Exception e) {
e.printStackTrace();
}
return new HashMapString, Integer();
}
public static void main(String[] args) {
MapString, Integer map = Clustering.cluster(
"C:/Documents and Settings/Administrator/桌面/123.txt", 2, 0);
IteratorMap.EntryString, Integer it = map.entrySet().iterator();
while(it.hasNext()){
Map.EntryString, Integer entry = it.next();
System.out.println(entry.getKey()+","+entry.getValue());
}
}
}
class Dot {
String name;
int x;
boolean isCenter;
boolean isVirtual;
}
class Cluster {
// 记录了该类中点的索引值
LinkedListInteger dots = new LinkedListInteger();
你这是四维数据，我这是一维数据kmeans，你试试吧
#includeiostream
#includemath.h
#includestdlib.h
#includestdio.h
using namespace std;
int N; //数据个数
int K; //集合个数
int *CenterIndex; //质心索引集合,即属于第几个参考点
double *Center; //质心集合
double *CenterCopy;
double *DataSet;
double **Cluster;
int *Top;
/*算法描述:
C-Fuzzy均值聚类算法采用的是给定类的个数K,将N个元素(对象)分配到K个类中去使得类内对象之间的相似性最大,而类之间的相似性最小 */
//函数声明部分
void InitData();
void InitCenter();
void CreateRandomArray(int n,int k,int *centerIndex);
void CopyCenter();
void UpdateCluster();
void UpdateCenter();
int GetIndex(double value,double *centerIndex);
void AddtoCluster(int index,double value);
void print();
bool IsEqual(double *center,double *centercopy);
int main()
{
int Flag=1;
InitData();
while(Flag)//无限次循环
{
UpdateCluster();
UpdateCenter();
if(IsEqual(Center,CenterCopy))
{
Flag=0;
}
else
{
CopyCenter();
}
}
print();
getchar();
system("pause");
}
void InitData()
{
int i=0;
int a;
cout"请输入数据元素的个数: ";
cinN;
cout"请输入分类数: ";
cinK;
if(KN)
{
return;
}
CenterIndex =new int [sizeof(int)];
Center =new double [sizeof(double)*K];
CenterCopy =new double [sizeof(double)*K];
DataSet =new double [sizeof(double)*N];
Cluster =new double* [sizeof(double*)*K];
Top =new int [sizeof(int)*K];
//初始化K个类的集合
for(i=0;iK;i++)
{
Cluster[i]=new double [sizeof(double)*N];
Top[i]=0;
}
cout"请输入数据"endl;
for(i=0;iN;i++)
{
cina;
DataSet[i]=a;
}
//初始化质心集合
InitCenter();
UpdateCluster();
}
void InitCenter()//初始化中心点（参照点）
{
int i=0;
//产生随即的K个N的不同的序列
CreateRandomArray(N,K,CenterIndex);
for(i=0;iK;i++)
{
Center[i]=DataSet[CenterIndex[i]];
}
CopyCenter();
}
void CreateRandomArray(int n,int k,int *centerIndex)//产生可以随输出控制的 k与n （可舍弃）
{
int i=0,j=0;
for(i=0;iK;i++)
{
int a=rand()%n;
for(j=0;ji;j++)
{
if(centerIndex[j]==a)
break;
}
if(j=i)
{
centerIndex[i]=a;
}
else
{
i--;
}
}
}
void CopyCenter()//将旧的中心点保留以作比较
{
int i=0;
for(i=0;iK;i++)
{
CenterCopy[i]=Center[i];
}
}
void UpdateCluster()//
{
int i=0;
int tindex;
for(;iK;i++)
{
Top[i]=0;
}
for(i=0;iN;i++)
{
tindex=GetIndex(DataSet[i],Center);
AddtoCluster(tindex,DataSet[i]);
}
}
int GetIndex(double value,double *center)//判断属于哪个参照点
{
int i=0;
int index=i;
double min=fabs(value-center[i]);
for(i=0;iK;i++)
{
if(fabs(value-center[i])min)
{
index=i;
min=fabs(value-center[i]);
}
}
return index;
}
void AddtoCluster(int index,double value)//统计每组个数（用于均值法求新的参照点）
{
Cluster[index][Top[index]]=value;
Top[index]++;
}
void UpdateCenter()//更新参照点
{
int i=0,j=0;
double sum;
for(i=0;iK;i++)
{
sum=0.0;
for(j=0;jTop[i];j++)
{
sum+=Cluster[i][j];
}
if(Top[i]0)
{
Center[i]=sum/Top[i];
}
}
}
bool IsEqual(double *center,double*centercopy)//
{
int i;
for(i=0;iK;i++)
{
if(fabs(center[i]!=centercopy[i]))
return 0;
}
return 1;
}
void print()//
{
int i,j;
cout"===================================="endl;
for(i=0;iK;i++)
{
cout"第"i"组：质心为："Center[i]endl;
cout"数据元素为:\n";
for(j=0;jTop[i];j++)
{
coutCluster[i][j]'\t';
}
coutendl;
}
}
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]值的变化小于给定阈值。
算法实现起来应该很容易，就不帮你编写代码了。
学习内容：无监督聚类算法K-Means
k-means：模型原理、收敛过程、超参数的选择
聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
不同的簇类型： 聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。
基于原型的： 簇是对象的集合，其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。
基于密度的 ：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。
关于更多的簇介绍参考《数据挖掘导论》。
基本的聚类分析算法
1. K均值： 基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。
2. 凝聚的层次距离： 思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。
3. DBSCAN: 一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。
不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：
优点：易于实现
缺点：可能收敛于局部最小值，在大规模数据收敛慢
算法思想：
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑 距离度量和目标函数。
考虑欧几里得距离的数据，使用 误差平方和（Sum of the Squared Error,SSE） 作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。
k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。
这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。
k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：
1. K值需要预先给定 ，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。
2. K-Means算法对初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同
3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。
4. 对离群点的数据进行聚类时，K均值也有问题 ，这种情况下，离群点检测和删除有很大的帮助。
下面对初始质心的选择进行讨论：
当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。
多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。
关于更多，参考《数据挖掘导论》
为了克服K-Means算法收敛于局部最小值的问题，提出了一种 二分K-均值(bisecting K-means)
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2 计算将该簇划分成两个簇后总误差
选择是的误差最小的那个簇进行划分
在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。
使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。
Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。
聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。
聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。
性能度量大概可分为两类： 一是外部指标， 二是内部指标 。
外部指标：将聚类结果和某个“参考模型”进行比较。
内部指标：不利用任何参考模型，直接考察聚类结果。
对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大
初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
优点：
简单， 易于理解和实现 ；收敛快，一般仅需5-10次迭代即可，高效
缺点：
1，对K值得选取把握不同对结果有很大的不同
2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同
3，对于不是凸的数据集比较难收敛
4，对噪点过于敏感，因为算法是根据基于均值的
5，结果不一定是全局最优，只能保证局部最优
6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。
K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。
参考阅读：
1.《 深入理解K-Means聚类算法 》
2.《 K-Means 》