k均值算法终止

1. 聚类算法--KMeans

    与分类、序列标注等任务不同，聚类是在事先并不知道任何样本标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低(即增大类内聚，减少类间距)。    

    聚类属于非监督学习，K均值聚类是最基础常用的聚类算法。它的基本思想是，通过迭代寻找K个簇(Cluster)的一种划分方案，使得聚类结果对应的损失函数最小。其中，损失函数可以定义为各个样本距离所属簇中心点的误差平方和。

其中 代表第i个样本， 是 所属的簇，  代表簇对应的中心点，M是样本总数。

相关概念：

    K值： 要得到的簇的个数。

    质心： 每个簇的均值向量。即向量各维取平均即可。

    距离量度： 常用欧几里得距离和余弦相似度(先标准化)。

    KMeans的主要思想是：在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。

    KMeans的核心目标是将给定的数据集划分成K个簇(K是超餐)，并给出每个样本数据对应的中心点。具体步骤非常简单：

    （1）首先确定一个K值，即我们希望将数据集经过聚类得到k个集合。

    （2）从数据集中随机选择K个数据点作为质心。

    （3）对数据集中每一个点，计算其与每一个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合。

    （4）把所有数据归好集合后，一共有K个集合。然后重新计算每个集合的质心。

    （5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。

    （6）如果新质心和原质心距离变化很大，需要迭代3-5步骤。

KMeans最核心的部分是先固定中心点，调整每个样本所属的类别来减少J；再固定每个样本的类别，调整中心点继续减小J。两个过程交替循环，J单调递减直到极小值，中心点和样本划分的类别同时收敛。

KMeans的优点 ：

 高效可伸缩，计算复杂度为O(NKt)接近于线性(N是数据量，K是聚类总数，t是迭代轮数)。

 收敛速度快，原理相对通俗易懂，可解释性强。

当结果簇是密集的，而簇与簇之间区别是明显时，他的效果较好。主要需要调参的参数仅仅是簇数K。

缺点 ：

 受初始值和异常点影响，聚类结果可能不是全局最优而是局部最优。K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同，对结果影响很大。

 K是超参数，一般需要按经验选择。

 对噪音和异常点比较的敏感，用来检测异常值。

 只能发现球状的簇。在K-Means中，我们用单个点对cluster进行建模，这实际上假设各个cluster的数据是呈高维球型分布的，但是在生活中出现这种情况的概率并不算高。例如，每一个cluster是一个一个的长条状的，K-Means的则根本识别不出来这种类别( 这种情况可以用GMM )。实际上，K-Means是在做凸优化，因此处理不了非凸的分布。

根据以上特点，我们可以从下面几个角度对算法做调优。

（1）数据预处理：归一化和异常点过滤

    KMeans本质是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响 。所以在聚类前对数据( 具体的说是每一个维度的特征 )做归一化和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致 中心偏移 ，这些噪声点最好能提前过滤。

（2）合理选择K值

    K值的选择一般基于实验和多次实验结果。例如采用 手肘法 ，尝试不同K值并将对应的损失函数画成折线。手肘法认为图上的 拐点就是K的最佳值 (k=3)。

为了将寻找最佳K值的过程自动化，研究人员提出了Gap Statistic方法。不需要人们用肉眼判断，只需要找到最大的Gap Statistic对应的K即可。

       损失函数记为  ，当分为K类时，Gap Statistic定义为：  。 是 的期望 ，一般由蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做KMeans，得到一个 ，重复多次就可以计算出 的近似值。

       的物理含义是随机样本的损失与实际样本的损失之差。Gap越大说明聚类的效果越好 。一种极端情况是，随着K的变化 几乎维持一条直线保持不变。说明这些样本间没有明显的类别关系，数据分布几乎和均匀分布一致，近似随机。此时做聚类没有意义。

（3）改进初始值的选择

    之前我们采用随机选择K个中心的做法，可能导致不同的中心点距离很近，就需要更多的迭代次数才能收敛。如果在选择初始中心点时能 让不同的中心尽可能远离 ，效果往往更好。这类算法中，以K-Means++算法最具影响力。

（4）采用核函数

    主要思想是通过一个非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的空间进行聚类。非线性映射增加了数据点线性可分的概率(与SVM中使用核函数思想类似)对于非凸的数据分布可以达到更为准确的聚类结果。

 (1）初始的K个质心怎么选？

    最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更合理，就用哪个结果。当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果，从结果中每个分类选一个点

（2）关于离群值？

    离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些"极大""极小"之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离散值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。

（3）单位要一致！

（4）标准化

    数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里得距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化(normalization)，即将数据按比例缩放，使之落入一个小的特定区间。

    K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出 。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的K个点，用这最近的K个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到K个类别的最佳质心，从而决定样本的簇类别。当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。 两周都利用了最近邻的思想 。

2. K-均值算法（K-means algorithm）

K-均值算法概述：

首先，我们有一个无标签数据集，我们想要把它们分成两个类，然后我们使用k-均值算法来做：

1、我们选取两个点，称为聚类中心（cluster centroids）：

2、遍历所有的点，更靠近哪个聚类中心，就把它归为那一个类中：

3、移动聚类中心到它们察态自己类的均值处：

4、然后我们继续第2步，遍历所有的点，看它离哪个聚类中心更近就把它归到那一类中：

5、继续第3步，移动聚类中心到它们自己类的均值处：

6、继续第2步：

7、肢族继续第3步：

8、继续第2步：

如此反复，当点的颜色不再变化，我们便认为K均值方法已经收敛了。

输入：

对于没有明显区分的数据也可以很好败饥源的分开：

3. k均值聚类算法原理

 算法：
第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算斗高并的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。
第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。
假设i=j时， ，则 ，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。
第三步：计算各个聚类中心空迹的新的向量值，zj(k+1)，j=1,2,…,K
求各聚类域中所包含样本的均值向量：

其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：

在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。
第四步：若 ，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；
若 ，j=1,2,…,K，则算念碧法收敛，计算结束。

4. K均值算法介绍

从没有标记过的数据中学习称之为非监督学习。
在非监督学习中，通过算法来定义一些数据的结构，将数据分别聚合到这些子集中，这种算法称之为聚类算法。

K均值 (K-means) 算法是最常用的一种聚类算法。

假设有槐闭运如上的数据集，可以看到只有输入 ，没有输出 。

下面说明一下K均值算法的过程

K均值算法的代价函数为：

优化目标就是使用上面的代价函数最小化所有参数。

上述步骤中
第3步集群分配，是通过找到离样本最近的聚类中心点来最小化代价函数；
第4步移动质心，是通过改变样本和聚类中心点的距离来最小代价函数。
在K均值算法中，代价函数是一直下降的，不可能出现上升的情况。

聚类中心的个数 一般都是小于样本数量 的，因此可以随机取 个样本来作为聚类中心。

步骤

这样做的优点是方便快捷，缺点是不一定能够找到最佳的聚类中心，容易陷入局部最优。铅梁
这种陷入局部最优的情况在聚态行类中心过少时一般会出现，一般在 的情况下，解决办法是多次执行该步骤，比较代价函数的值，取最小值。

聚类中心数量的选择没有固定的方法，跟主观上的判断有很大关系，也跟业务，以及一些客观条件，以及使用K均值算法的目标有关。

5. 简述K-均值算法的工作流程

K-均值算法（K-means clustering algorithm）是一种常见的聚类算法，用于将一组数据划分为K个不同的簇或组。其工作流程如下：

• 初始化：随机选择K个点作为初始的簇中心（centroid）。

• 分配数据点：对于每个数据点，计算它与每个簇中心的距离，并将它分配到距离最近的簇中心所在的簇。

• 更新簇中心：对于每个簇，计算其所有成员的平均值，并将该平均值作为新的簇中心。

• 重复步骤2和步骤3，直到满足某个停止准则，例如簇中心不再发生变化，簇内平方和达到最小值，或达到预定的迭代次数。

• 输出：算法输出K个簇及其对应的簇中心。

K-均值算法是一种迭代算法，通过不断地更新簇中心和重新分配数据点，最终将数据点划分为K个不同的卖猜簇。该算法的性能与初始的簇中罩型中心的选择有关，不同的初始选择可能会导致不同的结果。因此，通常会进行多次运行，选择最终结果最优的一次运行作为算法的闷颤输出。

6. 如何更加有效地选择的k均值聚类中的k

K均值聚类法分为如下几个步骤：
一、初慎高始化聚类中心
1、根据具体问题,凭经验从样本集中选出C个比较合适的样本作为初始聚类中心.
2、用前C个样本作为初始聚类中心.
3、将全部样本随机地分成C类,计算每类的样本均值,将样凯毕本均值作为初始聚类中心.
二、初始聚类
1、按就近原则将样本归入各聚类中心所代表的类中.
2、取一样本,将其归入与其最近的聚类中心的那一类中,重新计算样本均值,更宽孙尺新聚类中心.然后取下一样本,重复操作,直至所有样本归入相应类中.
三、判断聚类是否合理
采用误差平方和准则函数判断聚类是否合理,不合理则修改分类.循环进行判断、修改直至达到算法终止条件.

7. 大数据十大经典算法之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(vector<double>& v1, vector<double>& v2);

private:
vector< vector<double> > m_Data;
vector< vector<double> > m_Center;
vector<double> m_Distance;
vector<size_t> m_DataBelong;
vector<size_t> m_DataBelongCount;
};
}
#include "kmean.h"

#include <ctime>
#include <cmath>
#include <cstdlib>
//auther archersc
//JLU

namespace CS_LIB
{
template<class 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(vector<double>& v1, vector<double>& 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;
}

8. 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)时，曲线急速下降;当K>3时，曲线趋于平稳。手肘法认 为拐点就是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个初始聚类中心(0<n<K)，则在选取第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算法只保证收敛到局部最优解

9. k-means聚类算法常用的终止条件有哪些

K-means 算法属于聚类分析方法中一种基本的且应用最广泛的划分算法，它是一种已知聚类类别数的聚类算法。指定类别数为K，对样本集合进行聚类，聚类的结果由K 个聚类中心来表达，基于给定的聚类目标函数（或者说是聚类效果判别准则），算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减小的方向进行，最终的聚类结果使目标函数值取得极小值，达到较优的聚类效果。使用平均误差准则函数E作为聚类结果好坏的衡量标准之一，保证了算法运行结果的可靠性和有效性。

10. 什么是k均值聚类算法

适用条件：系统聚类法适于二维有序样品聚类的样品个数比较均匀。K均值聚类法适用于快速高效，特别是大宴滚裤量数据时使用。

两者区别如下：

一、指代不同

1、K均值聚类法：是一种迭代求解的聚类分析算法。

2、系统聚类法：又叫分层聚晌简类法，聚类分析的一种方法。

二、步骤不同

1、K均值聚类法：步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。

2、系统聚类法：开始时把每个样品作为一类，然后把最靠近的样品（即距离最小的群品）首先聚为小类，再将已聚合的小类按其类间距离再合并，不断继续下去，最后把一切子类都聚合到一个大类。

三、目的不同

1、K均值聚类法：终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

2、系统聚类法：是以距离为相似统计量时，确定新类与其他各类之间距离的方法，如最短距离法、最长距离法备滚、中间距离法、重心法、群平均法、离差平方和法、欧氏距离等。