总是有废话要先说~~
二妹原创，转载请注明出处，大家讨论~
上次面试，写自我评价的缺点，我写的比较胖~~然后拿offer了，人啊 就是要看得见的实诚！
----------------------------------------我是废话分割线
-------------------------------------------------------------
web上大量的数据，希望对这些数据进行聚类，而事先并不知道该怎么聚类，k-均值算法则是将大数据聚为k类。
关键要素：
1:用户事先要确定K的值，这个可能需要大量的测试优化k值。k值代表将数据聚为k类，那么将会产生k个簇的质心（均值所在的位置）。
2：聚类的的数据节点之间必须是可以计算平均值。K均值的思想就是某一堆数据都在一个均值的附近，那么将这一堆数据划为一簇。
3：适用于球状分布的数据。例如如果数据是环形分布的，直观上应该将同一环形的数据归为一类，而用k均值则可能分为扇形簇。
4：初始的质心选择得不同，则得到的聚类也会不同。
例如如下图，当k为3的时候，下面红黄蓝是正确的分类，使用k均值算法可以正确的分类第一类，而第二类则会出现错误。
以Person为例，现在有一堆人的集合，将他们分为三类，按年龄相近来分类。
Person对象，相当于集合中的节点。
package com.zyp.learn.datamining.algorithm;
public class Person {
private int age;
private String name;
public Person(String name,int age){
this.name = name;
this.age = age;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
算法实现类：
package com.zyp.learn.datamining.algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* K均值算法
* @author 卓二妹 2012/10/31
*
*/
public class KAverageAlgorithm {
public static void main(String[] args){
//生成集合，年龄随机生成0-99的数字
// Set<Person> personSet= initSet(5);
//生成固定值集合，便于调试
Set<Person> personSet= initSet();
System.out.print("集合元素：");
for(Person p : personSet){
System.out.print(p.getAge()+" ");
}
System.out.println();
// 调用无监督学习的k均值算法，将这50人按年龄分为3类，如老、中、青
Person[] centerArray = cluster(3,personSet);
System.out.print("质心：");
for(Person center : centerArray){
System.out.print(center.getAge()+" ");
}
//标记元素所属质心
Map<String,List> map = new HashMap();
//集合中的某个元素所属的质心，加到该质心对应的数组上
for(Person p: personSet){
int index = nearestIndex(centerArray,p);//p属于centerArray[index]质心
List<Person> lst = map.get(centerArray[index].getAge()+"");
if(lst==null){
lst = new ArrayList();
map.put(centerArray[index].getAge()+"",lst);
}
lst.add(p);
}
System.out.println("\n质心包含的元素：");
for(Person center : centerArray){
System.out.print(center.getAge()+" ：");
List<Person> lst = map.get(center.getAge()+"");
if(lst!=null){
for(Person p : lst){
System.out.print(p.getAge()+" ");
}
}
System.out.println("\n");
}
}
/**
* 将person集合分类，按照person的年龄维度来分类。
* 分为k个年龄段，而每个年龄段是事前并不知道。
* 用k-均值算法的硬盘版本，只需要遍历一次全集。
* @param k：簇的数量
* @param personSet：要划分簇的全集
* @return 质心的数组
*/
public static Person[] cluster(int k,final Set<Person> personSet){
Person[] centerArray = new Person[k];
//由于集合是无序的，因此在集合中选前k个点做初始的质心（任意k个点）
int i = 0;
for(Person p:personSet){
centerArray[i++] = p;
if(i==k){
break;
}
}
//进行一遍执行的调整,本次调整中，改变了所属簇的节点的数量为chanedPointNum
int chanedPointNum = -1;
//直到没有任何person所属簇都不再变化后，结束分类
boolean isExit = false;
while(isExit){
Person[] newCenterArray = adjustCenteroid(centerArray,personSet);
isExit = exit(newCenterArray,centerArray,personSet);
}
return centerArray;
}
/**
* 进行一遍质心的调整
* @param centerArray 质心数组
* @param personSet 全集
* return 返回本轮调整质心，改变了所属簇的Person的个数
*/
public static Person[] adjustCenteroid(final Person[] centerArray,final Set<Person> personSet){
int changedPointNum = 0;//本次调整质心，改变了所属的簇的节点的个数
int oldIndex = -1;
int newIndex = -1;
int k = centerArray.length;
//distArray[i]代表该划划分到第i类的年龄的总和
int[] distArray = new int[k];
//numberArray[i]代表划分到第i类的年龄有多少个
int[] numberArray = new int[k];
//待返回的新质心
Person[] newCenterArray = new Person[k];
//将数组元素初始化为0
initArray(distArray);
initArray(numberArray);
for(Person tempPerson:personSet){
//计算该tempPerson到centerArray的第index质心最近
int index = nearestIndex(centerArray,tempPerson);
//则该tempPerson被划为第index质心代表的簇中
distArray[index] = distArray[index] + tempPerson.getAge();
numberArray[index] ++;
}
//已将每个元素分到k个质心中，重新计算每个簇的均值，得到新的质心
for(int index = 0; index<k;index++){
newCenterArray[index] = new Person("",distArray[index]/numberArray[index]);
}
return newCenterArray;
}
/**
* 质心调整的退出标准
* @param centerArray当前的质心
* @param oldCenterArray 调整前的质心
* @param personSet 数据集合
* @return 数据集合的簇在质心调整前后无变化，则返回true
*/
public static boolean exit(final Person[] centerArray,final Person[] oldCenterArray,final Set<Person> personSet){
boolean isExit = false;
int changedPointNum = 0;
//遍历person集合，看质心调整后，person的所属簇是否改变
for(Person tempPerson:personSet){
int newIndex = nearestIndex(centerArray,tempPerson);
int oldIndex = nearestIndex(oldCenterArray,tempPerson);
if(oldIndex!=newIndex){
changedPointNum++;
}
}
if(changedPointNum==0){
isExit = true;
}
return isExit;
}
public static void initArray(int array[]){
for(int i = 0;i<array.length;i++){
array[i] = 0;
}
}
public static int nearestIndex(final Person[] centerArray,final Person tempPerson){
int minIndex = 0;//与该点距离最近的质心的index
int minValue = 100;//与最近的质心的距离
for(int i = 0;i<centerArray.length;i++){
int centerAge = centerArray[i].getAge();
int temp = Math.abs(tempPerson.getAge()-centerAge);//数据点的年龄与质心距离
if(temp<=minValue){
minValue = temp;//
minIndex = i;
}
}
return minIndex;
}
/**
* 初始化集合中的数据
* @param count：需要生成的集合的元素个数
* @return
*/
public static Set<Person> initSet(int count){
Set<Person> set = new HashSet();
// System.out.print("初始集合：");
for(int i=0;i<count;i++){
String name = "person"+i;
//随即生成0--99的人的年龄
int age = (int)(Math.random()*100);
// System.out.print(age+" ");
set.add(new Person(name,age));
}
System.out.println();
return set;
}
/**
* 初始化集合中的数据，指定一些出错的数据，便于调试
* @return
*/
public static Set<Person> initSet(){
Set<Person> set = new HashSet();
set.add(new Person("", 69));
set.add(new Person("", 30));
set.add(new Person("", 75));
set.add(new Person("", 12));
set.add(new Person("", 14));
return set;
}
}
运行一下main方法，随机生成5个人，按年龄分为3类，打印结果如下：
集合元素：75 69 14 12 30
质心：75 69 14
质心包含的元素：
75 ：75
69 ：69
14 ：14 12 30
二天空了再来解释算法，敬请期待~
分享到：
相关推荐
k-均值算法的高斯计分布随机聚类的划分，用vc编程的，希望能帮助大家学习。
新的K-均值算法最佳聚类数确定方法,对均值聚类算法有极大地优化
针对传统K-均值聚类算法对初始聚类中心敏感、现有初始聚类中心优化算法缺乏客观性，提出一种基于样本空间分布密度的初始聚类中心优化K-均值算法。该算法利用数据集样本的空间分布信息定义数据对象的密度，并根据整个...
由于其算法思想简便,又容易实现对大规模数据的聚类,因此K-均值算法已成为一种最常用的聚类算法之一K-均值算法能找到关于聚类误差的局部的最优解,是一个能应用在许多聚类问题上的快速迭代算法。它是一种以点为基础的...
介绍了在聚类中广泛应用的经典k-均值算法,并针对其易受随机选择初始聚类中心和孤立点的影响的不足,给出了改进的k-均值算法。首先使用距离法移除孤立点,然后采用邻近吸收法对初始聚类中心的选择进行了改进。并做了...
针对传统k-均值算法对初始聚类中心敏感的问题，提出了启发式初始化独立的k-均值算法。该算法引入prim算法选择k个初始聚类中心，且通过设置阈值参数θ，避免同一类中的多个数据对象同时作为初始聚类中心，否则将导致...
K-Means算法是典型的基于距离的聚类算法，其中k代表类簇个数，means代表类簇内数据对象的均值（这种均值是一种对类簇中心的描述），因此，K-Means算法又称为k-均值算法。K-Means算法是一种基于划分的聚类算法，以...
定义了一个欧氏距离和监督信息相混合的新的最近邻计算函数,从而将K-均值算法很好地应用于半监督聚类问题。针对K-均值算法初始质心敏感的缺陷,用粒子群算法的搜索空间模拟聚类的欧氏空间,迭代搜索找到较优的聚类质心...
该方案可有效降低K-均值算法对初始中心点的依赖，从而获得较高的聚类质量。在此基础上，可进一步通过选择合适的聚类有效性指标Silhouette指标分析不同k值下的每次聚类结果，确定最佳聚类数，则可有效改善k值无法预先...
针对粗糙K-均值算法的执行效率较低和对数据对象的处理不准确问题，提出了基于加权距离计算的自适应粗糙K-均值算法。该算法在粗糙集理论应用的基础上修正数据集合的隶属度函数，结合属性约简方法，根据数据属性对聚类...
NULL 博文链接：https://ghostfromheaven.iteye.com/blog/851516
基于神经网络建模和K-均值算法的电池健康状态评估 本文旨在解决电池健康状态评估中的难题，通过对锂离子电池外特性的分析，采用BP神经网络算法对锂离子电池进行建模，并将其模型带入K-均值算法中，以实现对电池健康...
：将核学习方法的思想应用于K-均值聚类中，提出了一种核K-均值聚类算法，算法的主要思想是：首先将原空间中待聚类的样本经过 一个非线性映射，映射到一个高维的核空间中，突出各类样本之间的特征差异，然后在这个核...
基于python实现K-均值算法与高斯混合模型及对应简单应用源码+项目说明+详细注释.zip （K-均值算法与高斯混合模型） 1.采用两分量的高斯混合模型建模一组观测数据的分布，并用 EM 算法估计相关的 5 个参数，得到了...
采用k-均值算法解决多维空间中点的聚类分析问题，由于算法比较简单，这里不再赘述
针对K-均值算法在随机选取初始类中心时存在不足、对噪声和孤立点敏感、不适用于发现大小差别很大的类的问题，借鉴分子间的相互作用力模型，将文本模拟成数据场中的数据点，综合考虑文本间的相似度和相异度，提出一个...
使用Weka进行K-近邻算法和K-均值算法的使用-附件资源