Kmean Cluster是一种机器学习中常用的无监督分析方法,例如,在最近的项目中,要从数以百万、千万计的高维图像特征中提取具有代表性的视觉词,就用到了此类技术。
Kmean并不是一种高效的算法,理论可以证明,在欧几里得空间中的Kmean问题是NP-Hard(即使聚类数仅为2)。假设单个向量维度为d,向量数为n,目标聚类数为k,则算法的时间复杂度=n^(dk+1)*logn。
kmean的示意图如下:
一些启发式的算法对Standard Kmean的效率进行了优化,常见的包括:
- 基于最大期望的算法(EM algorithm):采用概率的方式将输入向量分配到各个聚类当中(而非Standard Kmean中的绝对分配),并且采用高斯分布代替Standard Kmean中的算术平均值计算聚类中心。
- Kmean++:通过选取初始聚类集合来达到更好的效果
- filtering algorithm:通过使用kd树来加速Kmean效率
- 其它优化算法:诸如coresets、triangle inequ以及Escape local optima等算法
尽管如此,经典的Standard Kmean仍然是使用频率较高的聚类算法,在数据量不大或者demo阶段被广为使用,下面给出java实现的代码:
public Cluster[] cluster(final List<Clusterable> values, int numClusters) {
Cluster[] clusters = calculateInitialClusters(values, numClusters);
boolean recalculateClusters = true;
int numIterations = 0;
while (recalculateClusters) {
// add all items to nearest cluster
clusters = assignClusters(clusters, values);
// see if the cluster distance hasn't moved
recalculateClusters = mChecker.recalculateClusters(clusters);
// if it needs to be run again, set up new clusters on the updated
// centers
if (recalculateClusters) {
if (numIterations > mMaxReclustering) {
recalculateClusters = false;
}
clusters = getNewClusters(clusters);
numIterations++;
}
}
return clusters;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class KMeansClusterer extends AbstractKClusterer {
public KMeansClusterer() {
super();
}
protected Cluster[] assignClusters(Cluster[] clusters,final List<Clusterable> values){
assignClustersByDistance(clusters, values);
return clusters;
}
protected void assignClustersByDistance(Cluster[] clusters, List<Clusterable> values){
for ( int j = 0; j < values.size(); j++ ){
Clusterable val = values.get(j);
Cluster nearestCluster = null;
double minDistance = Float.MAX_VALUE;
for ( int i = 0; i < clusters.length; i++ ){
Cluster cluster = clusters[i];
double distance = ClusterUtils.getEuclideanDistance(val,cluster);
//System.out.println("cluster " + i + ", point " + j + ",distance: " + distance);
if ( distance < minDistance ){
nearestCluster = cluster;
minDistance = distance;
}
}
nearestCluster.addItem(val);
}
}
protected Cluster[] getNewClusters(Cluster[] clusters){
for ( int i = 0; i < clusters.length; i++ ){
if ( clusters[i].getItems().size() > 0 )
clusters[i] = new Cluster(clusters[i].getClusterMean(),i);
}
return clusters;
}
public static void main(String args[]){
Random random = new Random(System.currentTimeMillis());
int numPoints = 50;
List<Clusterable> points = new ArrayList<Clusterable>(numPoints);
for ( int i = 0; i < numPoints; i++ ){
int x = random.nextInt(1000) - 500;
int y = random.nextInt(1000) - 500;
points.add(new Point((float)x,(float)y));
}
KClusterer clusterer = new KMeansClusterer();
Cluster[] clusters = clusterer.cluster(points,10);
for ( Cluster c : clusters ){
System.out.println(c.getItems().size());
}
}
public static boolean hasBadValue(double[] values){
for ( double value : values ){
if ( !(value < 1 && value > -1) ){
System.out.println(value + " is 'bad'");
return true;
}
}
return false;
}
}
Standard Kmean在大数据量时其表现往往不尽如人意,后续我会附上kd random forest的优化算法
- 大小: 46.6 KB
分享到:
相关推荐
1.版本:matlab2019a,不会运行可私信 2.领域:【图像分割】 3.内容:基于Kmean聚类实现乳腺肿瘤分割附matlab代码 4.适合人群:本科,硕士等教研学习使用
1.版本:matlab2019a,内含运行结果,不会运行可私信 2.领域:【图像压缩】 3.内容:基于Kmean实现图像压缩附matlab代码.zip 4.适合人群:本科,硕士等教研学习使用
model = KMeans(algorithm='lloyd', n_clusters=8, init = 'k-means++', n_init=10, max_iter=17, random_state=2022, verbose=False ) model.fit(train) # 可视化聚类结果————对输入数据标准化处理,...
kmean算法实现数据分析
knn/kmean的python实现及可视化
python简单实现kmean聚类算法
kmean聚类(实现)和层次聚类实验代码,仅供参考和学习
1.版本:matlab2014/2019a,内含运行结果,不会运行可私信 2.领域:智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,更多内容可点击博主头像 ...
比如给出1千个坐标,求出这1千个坐标的重心点。 本人从pascal算法转成java
Kmean matlab 中心聚类 基于lab图像空间
基于kmean的图像分割方法,需要的可以下载
使用vc6.0实现数据挖掘经典算法之kmean。程序中k由用户自己输入,测试数据个数,维数存放在1.txt文件中并从中读取,数据类型为double,个数.维数.大小都可以从文件中更改。
kmean算法源代码,java.朋友介绍的可能有错误自己看吧
使用标签label分解聚类中心,file The K-Means algorithm.
基于kmean算法的用于RGB图像分割的matlab代码,用来遥感,街景,物体分类识别,按分类事物规定初始中心值,自定义分类数和分类色彩。
使用kmean 和 slc的聚类算法,内附详细的实验报告和实验结果图。
Kmean 算法Matlab实现,数据为二维高斯随机分布点
Kmean演示程序,仅供交流和学习。有代码。
1.版本:matlab2014/2019a,内含运行结果,不会运行可私信 2.领域:智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,更多内容可点击博主头像 ...
Kmean数据.xlsx