「k均值算法java」k均值算法的基本思想

本篇文章给大家谈谈k均值算法java，以及k均值算法的基本思想对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、K均值聚类
• 2、K均值算法的计算耗
• 3、K均值算法
• 4、k均值加速JAVA代码多少行
• 5、大数据十大经典算法之k-means

K均值聚类

k均值聚类算法是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。

聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。

这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

k均值聚类是最著名的划分聚类算法，由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k，k由用户指定，k均值算法根据某个距离函数反复把数据分入k个聚类中。

K均值算法的计算耗

您问的是K均值算法的计算吧。计算过程有6步。

传统K均值的计算过程：

1.从D中随机取K个元素，作为K个簇的各自的中心。

2.计算剩下的元素到各个中心点的相异度（一般按照欧式距离的远近），将这些元素归纳到相异度最低的簇。

3.根据聚类结果，重新计算K个簇各自的中心，计算方法是取簇中所有元素各自维度的算数平均数（一般为簇内所有元素点到簇中心的距离和的平均数）。

4.将D中所有的元素按照新的中心重新聚类。

5.重复第4步，直到聚类结果不再变化。

6.将结果输出。

K均值属于比较简单的聚类问题，所谓的聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D分成K个子集，要求每个子集内部的元素之间的相异度尽可能的小，而不同子集的元素相异度尽可能的大。其中每一个子集叫做一个簇。

K均值算法

代价函数可以定义为各个样本距离所属簇中心点的误差平方和

K均值算法有一些缺点，例如受初值和离群点的影响每次的结果不稳定、结果 通常不是全局最优而是局部最优解、无法很好地解决数据簇分布差别比较大的情 况(比如一类是另一类样本数量的100倍)、不太适用于离散分类等。但是瑕不掩 瑜，K均值聚类的优点也是很明显和突出的，主要体现在:对于大数据集，K均值 聚类算法相对是可伸缩和高效的，它的计算复杂度是O(NKt)接近于线性，其中N是 数据对象的数目，K是聚类的簇数，t是迭代的轮数。尽管算法经常以局部最优结 束，但一般情况下达到的局部最优已经可以满足聚类的需求。

其实书中也少讲了缺点，那就是关于k的选择，当维度很高的时候，你很难判断选择k多少比较合适。

不过书中在算法调优中说了。所谓的调优其是也是变相的说那些缺点。

K均值算法的调优一般可以从以下几个角度出发。

(1)数据归一化和离群点处理。

K均值聚类本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的 维度将对数据的聚类结果产生决定性的影响，所以未做归一化处理和统一单位的 数据是无法直接参与运算和比较的。同时，离群点或者少量的噪声数据就会对均 值产生较大的影响，导致中心偏移，因此使用K均值聚类算法之前通常需要对数据 做预处理。

（2)合理选择K值。

K值的选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺 点。实际上，我们希望能够找到一些可行的办法来弥补这一缺点，或者说找到K值 的合理估计方法。但是，K值的选择一般基于经验和多次实验结果。例如采用手肘 法，我们可以尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴 为K的取值，纵轴为误差平方和所定义的损失函数，如图5.3所示

由图可见，K值越大，距离和越小;并且，当K=3时，存在一个拐点，就像人 的肘部一样;当K (1,3)时，曲线急速下降;当K3时，曲线趋于平稳。手肘法认 为拐点就是K的最佳值。

手肘法是一个经验方法，缺点就是不够自动化，因此研究员们又提出了一些 更先进的方法，其中包括比较有名的Gap Statistic方法[5]。Gap Statistic方法的优点 是，不再需要肉眼判断，而只需要找到最大的Gap statistic所对应的K即可，因此该 方法也适用于批量化作业。在这里我们继续使用上面的损失函数，当分为K簇时， 对应的损失函数记为Dk。Gap Statistic定义为

Gap(K)=E(logDk)−logDk

内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本

做K均值，得到一个Dk;重复多次就可以计算出E(logDk)的近似值。那么Gap(K)有

什么物理含义呢?它可以视为随机样本的损失与实际样本的损失之差。试想实际 样本对应的最佳簇数为K，那么实际样本的损失应该相对较小，随机样本损失与实 际样本损失之差也相应地达到最小值，从而Gap(K)取得最大值所对应的K值就是最 佳的簇数。根据式(5.4)计算K =1,2,...,9所对应的Gap Statistic

(3)采用核函数。

采用核函数是另一种可以尝试的改进方向。传统的欧式距离度量方式，使得K 均值算法本质上假设了各个数据簇的数据具有一样的先验概率，并呈现球形或者 高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时， 可能需要引入核函数来优化，这时算法又称为核K均值算法，是核聚类方法的一种 [6]。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到 高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线 性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到 更为准确的聚类结果。

K均值算法的主要缺点如下。

(1)需要人工预先确定初始K值，且该值和真实的数据分布未必吻合。

(2)K均值只能收敛到局部最优，效果受到初始值很大。

(3)易受到噪点的影响。

(4)样本点只能被划分到单一的类中。

■ K-means++算法

K均值的改进算法中，对初始值选择的改进是很重要的一部分。而这类算法 中，最具影响力的当属K-means++算法。原始K均值算法最开始随机选取数据集中 K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心。假设已经 选取了n个初始聚类中心(0nK)，则在选取第n+1个聚类中心时，距离当前n个 聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中 心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉，聚类中心当然是 互相离得越远越好。当选择完初始点后，K-means++后续的执行和经典K均值算法 相同，这也是对初始值选择进行改进的方法等共同点。

■ ISODATA算法

当K值的大小不确定时，可以使用ISODATA算法。ISODATA的全称是迭代自 组织数据分析法。在K均值算法中，聚类个数K的值需要预先人为地确定，并且在 整个算法过程中无法更改。而当遇到高维度、海量的数据集时，人们往往很难准 确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进，它的思想也 很直观。当属于某个类别的样本数过少时，把该类别去除;当属于某个类别的样 本数过多、分散程度较大时，把该类别分为两个子类别。ISODATA算法在K均值 算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数;二是 合并操作，对应着减少聚类中心数。ISODATA算法是一个比较常见的算法，其缺 点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量Ko，还需要制定3个

阈值。下面介绍ISODATA算法的各个输入参数。

(1)预期的聚类中心数目Ko。在ISODATA运行过程中聚类中心数可以变 化，Ko是一个用户指定的参考值，该算法的聚类中心数目变动范围也由其决定。 具体地，最终输出的聚类中心数目常见范围是从Ko的一半，到两倍Ko。

(2)每个类所要求的最少样本数目Nmin。如果分裂后会导致某个子类别所包 含样本数目小于该阈值，就不会对该类别进行分裂操作。

(3)最大方差Sigma。用于控制某个类别中样本的分散程度。当样本的分散 程度超过这个阈值时，且分裂后满足(1)，进行分裂操作。

(4)两个聚类中心之间所允许最小距离Dmin。如果两个类靠得非常近(即这 两个类别对应聚类中心之间的距离非常小)，小于该阈值时，则对这两个类进行

合并操作。

如果希望样本不划分到单一的类中，可以使用模糊C均值或者高斯混合模型， 高斯混合模型会在下一节中详细讲述。

K均值聚类的迭代算法实际上是一种最大期望算法 (Expectation-Maximization algorithm)，简称EM算法。EM算法解决的是在概率模 型中含有无法观测的隐含变量情况下的参数估计问题。

EM算法只保证收敛到局部最优解

k均值加速JAVA代码多少行

五十多行

K均值（K-Means）是聚类算法中最为简单、高效的，属于无监督学习算法。聚类算法有K均值聚类、基于密度的聚类、最大期望聚类三种类型。

核心思想是由用户指定K个初始质心（initial centroids），以作为聚类的类别（cluster），重复迭代直至算法收敛。对每个样本点，计算得到距其最近的质心，将其类别标为该质心所对应的cluster；重新计算K个cluster对应的质心。

大数据十大经典算法之k-means

大数据十大经典算法之k-means

k均值算法基本思想：

K均值算法是基于质心的技术。它以K为输入参数，把n个对象集合分为k个簇，使得簇内的相似度高，簇间的相似度低。

处理流程：

1、为每个聚类确定一个初始聚类中心，这样就有k个初始聚类中心；

2、将样本按照最小距离原则分配到最邻近聚类

3、使用每个聚类中的样本均值作为新的聚类中心

4、重复步骤2直到聚类中心不再变化

5、结束，得到K个聚类

划分聚类方法对数据集进行聚类时的要点：

1、选定某种距离作为数据样本间的相似性度量，通常选择欧氏距离。

2、选择平价聚类性能的准则函数

用误差平方和准则函数来评价聚类性能。

3、相似度的计算分局一个簇中对象的平均值来进行

K均值算法的优点：

如果变量很大，K均值比层次聚类的计算速度较快（如果K很小）；

与层次聚类相比，K均值可以得到更紧密的簇，尤其是对于球状簇；

对于大数据集，是可伸缩和高效率的；

算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。

K均值算法缺点：

最后结果受初始值的影响。解决办法是多次尝试取不同的初始值。

可能发生距离簇中心m最近的样本集为空的情况，因此m得不到更新。这是一个必须处理的问题，但我们忽略该问题。

不适合发现非凸面形状的簇，并对噪声和离群点数据较敏感，因为少量的这类数据能够对均值产生较大的影响。

K均值算法的改进：

样本预处理。计算样本对象量量之间的距离，筛掉与其他所有样本那的距离和最大的m个对象。

初始聚类中心的选择。选用簇中位置最靠近中心的对象，这样可以避免孤立点的影响。

K均值算法的变种：

K众数（k-modes）算法，针对分类属性的度量和更新质心的问题而改进。

EM（期望最大化）算法

k-prototype算法

这种算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。

k均值算法用途：

图像分割；

衡量足球队的水平；

下面给出代码：

#include iostream

#include vector

//auther archersc

//JLU

namespace CS_LIB

{

using namespace std;

class Kmean

{

public:

//输入格式

//数据数量N 维度D

//以下N行，每行D个数据

istream loadData(istream in);

//输出格式

//聚类的数量CN

//中心维度CD

//CN行，每行CD个数据

//数据数量DN

//数据维度DD

//以下DN组，每组的第一行两个数值DB, DDis

//第二行DD个数值

//DB表示改数据属于一类，DDis表示距离改类的中心的距离

ostream saveData(ostream out);

//设置中心的数量

void setCenterCount(const size_t count);

size_t getCenterCount() const;

//times最大迭代次数， maxE ,E(t)表示第t次迭代后的平方误差和，当|E(t+1) - E(t)| maxE时终止

void clustering(size_t times, double maxE);

private:

double calDistance(vectordouble v1, vectordouble v2);

private:

vector vectordouble m_Data;

vector vectordouble m_Center;

vectordouble m_Distance;

vectorsize_t m_DataBelong;

vectorsize_t m_DataBelongCount;

};

}

#include "kmean.h"

#include ctime

#include cmath

#include cstdlib

//auther archersc

//JLU

namespace CS_LIB

{

templateclass T

void swap(T a, T b)

{

T c = a;

a = b;

b = c;

}

istream Kmean::loadData(istream in)

{

if (!in){

cout "input error" endl;

return in;

}

size_t dCount, dDim;

in dCount dDim;

m_Data.resize(dCount);

m_DataBelong.resize(dCount);

m_Distance.resize(dCount);

for (size_t i = 0; i dCount; ++i){

m_Data[i].resize(dDim);

for (size_t j = 0; j dDim; ++j){

in m_Data[i][j];

}

}

return in;

}

ostream Kmean::saveData(ostream out)

{

if (!out){

cout "output error" endl;

return out;

}

out m_Center.size();

if (m_Center.size() 0)

out m_Center[0].size();

else

out 0;

out endl endl;

for (size_t i = 0; i m_Center.size(); ++i){

for (size_t j = 0; j m_Center[i].size(); ++j){

out m_Center[i][j] ;

}

out endl;

}

out endl;

out m_Data.size();

if (m_Data.size() 0)

out m_Data[0].size();

else

out 0;

out endl endl;

for (size_t i = 0; i m_Data.size(); ++i){

out m_DataBelong[i] m_Distance[i] endl;

for (size_t j = 0; j m_Data[i].size(); ++j){

out m_Data[i][j] ;

}

out endl endl;

}

return out;

}

void Kmean::setCenterCount(const size_t count)

{

m_Center.resize(count);

m_DataBelongCount.resize(count);

}

size_t Kmean::getCenterCount() const

{

return m_Center.size();

}

void Kmean::clustering(size_t times, double maxE)

{

srand((unsigned int)time(NULL));

//随机从m_Data中选取m_Center.size()个不同的样本点作为初始中心。

size_t *pos = new size_t[m_Data.size()];

size_t i, j, t;

for (i = 0; i m_Data.size(); ++i){

pos[i] = i;

}

for (i = 0; i (m_Data.size() 1); ++i){

size_t s1 = rand() % m_Data.size();

size_t s2 = rand() % m_Data.size();

swap(pos[s1], pos[s2]);

}

for (i = 0; i m_Center.size(); ++i){

m_Center[i].resize(m_Data[pos[i]].size());

for (j = 0; j m_Data[pos[i]].size(); ++j){

m_Center[i][j] = m_Data[pos[i]][j];

}

}

delete []pos;

double currE, lastE;

for (t = 0; t times; ++t){

for (i = 0; i m_Distance.size(); ++i)

m_Distance[i] = LONG_MAX;

for (i = 0; i m_DataBelongCount.size(); ++i)

m_DataBelongCount[i] = 0;

currE = 0.0;

for (i = 0; i m_Data.size(); ++i){

for (j = 0; j m_Center.size(); ++j){

double dis = calDistance(m_Data[i], m_Center[j]);

if (dis m_Distance[i]){

m_Distance[i] = dis;

m_DataBelong[i] = j;

}

}

currE += m_Distance[i];

m_DataBelongCount[m_DataBelong[i]]++;

}

cout currE endl;

if (t == 0 || fabs(currE - lastE) maxE)

lastE = currE;

else

break;

for (i = 0; i m_Center.size(); ++i){

for (j = 0; j m_Center[i].size(); ++j)

m_Center[i][j] = 0.0;

}

for (i = 0; i m_DataBelong.size(); ++i){

for (j = 0; j m_Data[i].size(); ++j){

m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];

}

}

}

}

double Kmean::calDistance(vectordouble v1, vectordouble v2)

{

double result = 0.0;

for (size_t i = 0; i v1.size(); ++i){

result += (v1[i] - v2[i]) * (v1[i] - v2[i]);

}

return pow(result, 1.0 / v1.size());

//return sqrt(result);

}

}

#include iostream

#include fstream

#include "kmean.h"

using namespace std;

using namespace CS_LIB;

int main()

{

ifstream in("in.txt");

ofstream out("out.txt");

Kmean kmean;

kmean.loadData(in);

kmean.setCenterCount(4);

kmean.clustering(1000, 0.000001);

kmean.saveData(out);

return 0;

}

关于k均值算法java和k均值算法的基本思想的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。