❶ Kmeans聚类算法简介（有点枯燥）
1. Kmeans聚类算法简介
由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最着名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重心(centroids)，移动到其包含成员的平均位置，然后重新划分其内部成员。k是算法计算出的超参数，表示类的数量；Kmeans可以自动分配样本到不同的类，但是不能决定究竟要分几个类。k必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我将会详细介绍一些方法来估计最优聚类数量。
Kmeans的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，Kmeans参数的最优解也是以成本函数最小化为目标。Kmeans成本函数公式如下：
μiμi是第kk个类的重心位置。成本函数是各个类畸变程度(distortions)之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，Kmeans会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。
2. K值的确定
2.1 根据问题内容确定
这种方法就不多讲了，文章开篇就举了一个例子。
2.2 肘部法则
如果问题中没有指定kk的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同kk值的成本函数值画出来。随着kk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着kk值继续增大，平均畸变程度的改善效果会不断减低。kk值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kk值就是肘部。为了让读者看的更加明白，下面让我们通过一张图用肘部法则来确定最佳的kk值。下图数据明显可分成两类：
从图中可以看出，k值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显着降低。因此最佳的k是2。
2.3 与层次聚类结合
经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
2.4 稳定性方法
稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有kk个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明kk个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个kk，找到合适的k值。
2.5 系统演化方法
系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为kk个聚类时称系统处于状态kk。系统由初始状态k=1k=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 kiki ，其所对应的聚类结构决定了最优类数 kiki 。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。
2.6 使用canopy算法进行初始划分
基于Canopy Method的聚类算法将聚类过程分为两个阶段
(1) 聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；
(2) 在各个Canopy内使用传统的聚类方法(如Kmeans)，不属于同一Canopy的对象之间不进行相似性计算。
从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于Kmeans这样的聚类方法是需要人为指出K的值的，通过(1)得到的Canopy个数完全可以作为这个k值，一定程度上减少了选择k的盲目性。
其他方法如贝叶斯信息准则方法(BIC)可参看文献[4]。
3. 初始质心的选取
选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始中心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE(误差的平方和)的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。
第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取kk个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：(1)样本相对较小，例如数百到数千(层次聚类开销较大)；(2) kk相对于样本大小较小。
第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少(多了就不是离群点了)，它们多半不会在随机样本中出现。计算量也大幅减少。
第四种方法就是上面提到的canopy算法。
4. 距离的度量
常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。
欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。
借助三维坐标系来看下欧氏距离和余弦相似度的区别：
从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。
根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。
因为欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？
从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。
5. 聚类效果评估
我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数(Silhouette Coefficient)。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：
aa是每一个类中样本彼此距离的均值，bb是一个类中样本与其最近的那个类的所有样本的距离的均值。
6. Kmeans算法流程
输入：聚类个数k，数据集XmxnXmxn。
输出：满足方差最小标准的k个聚类。
(1) 选择k个初始中心点，例如c[0]=X[0] , … , c[k-1]=X[k-1]；
(2) 对于X[0]….X[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；
(3) 对于所有标记为i点，重新计算c[i]={ 所有标记为i的样本的每个特征的均值}；
(4) 重复(2)(3)，直到所有c[i]值的变化小于给定阈值或者达到最大迭代次数。
Kmeans的时间复杂度：O(tkmn)，空间复杂度：O((m+k)n)。其中，t为迭代次数，k为簇的数目，m为样本数，n为特征数。
7. Kmeans算法优缺点
7.1 优点
(1). 算法原理简单。需要调节的超参数就是一个k。
(2). 由具有出色的速度和良好的可扩展性。
7.2 缺点
(1). 在 Kmeans 算法中 kk 需要事先确定，这个 kk 值的选定有时候是比较难确定。
(2). 在 Kmeans 算法中，首先需要初始k个聚类中心，然后以此来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。
(3). 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
(4). 对离群点很敏感。
(5). 从数据表示角度来说，在 Kmeans 中,我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster的数据是呈圆形(或者高维球形)或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在 GMM 中，使用了一种更加一般的数据表示，也就是高斯分布。
(6). 从数据先验的角度来说，在 Kmeans 中,我们假设各个 cluster 的先验概率是一样的,但是各个 cluster 的数据量可能是不均匀的。举个例子,cluster A 中包含了10000个样本,cluster B 中只包含了100个。那么对于一个新的样本,在不考虑其与A cluster、 B cluster 相似度的情况,其属于 cluster A 的概率肯定是要大于 cluster B的。
(7). 在 Kmeans 中，通常采用欧氏距离来衡量样本与各个 cluster 的相似度。这种距离实际上假设了数据的各个维度对于相似度的衡量作用是一样的。但在 GMM 中，相似度的衡量使用的是后验概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通过引入协方差矩阵,我们就可以对各维度数据的不同重要性进行建模。
(8). 在 Kmeans 中，各个样本点只属于与其相似度最高的那个 cluster ，这实际上是一种 hard clustering 。
针对Kmeans算法的缺点，很多前辈提出了一些改进的算法。例如 K-modes 算法，实现对离散数据的快速聚类，保留了Kmeans算法的效率同时将Kmeans的应用范围扩大到离散数据。还有K-Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。当然还有其它的一些算法，这里我 就不一一列举了。
Kmeans 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后,再来进行数据的聚类。而 hierarchical clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。
❷ kmeans聚类算法是什么
K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。
(2)kmeans算法ppt扩展阅读：
k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
❸ Kmeans算法原理
Kmeans是一种无监督的基于距离的聚类算法，其变种还有Kmeans++。
注意，某些聚类中心可能没有被分配到样本，这样的聚类中心就会被淘汰（意味着最终的类数可能会减少）
和其他机器学习算法一样，K-Means 也要评估并且最小化聚类代价，在引入 K-Means 的代价函数之前，先引入如下定义：
引入代价函数：
5） 对噪音和异常点比较的敏感。
数据呈圆形、凸型、在一起的簇的数据形状近似高斯分布的这些数据是kmeans喜欢的数据。
❹ K-means改进算法(一)：K-means++
在普通的K-means算法中，会存在以下的缺点：
1). 只能收敛到局部最优，受到初始值较大；
2). K不确定，需自己确定；
3). 受noise影响较大。
为了改进k-means算法，出现了K-means++，ISODATA和Kernel K-means等方法。
其中K-means++算法是对初始值选择进行了改进。
普通k-means算法的步骤大概如下所示（假设k=3）：
普通的K均值算法是随机选取K个点作为聚类的中心，而K-means++按照如下的思想选取K个聚类中心，其基本的思想是，K个初始聚类中心相互之间应该分得越开、离得越远越好（图片来自 https://www.cnblogs.com/yixuan-xu/p/6272208.html ）：
❺ 大数据十大经典算法之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;
}