1、 样本预处理
K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
我的聚类对象是一系列非法网站。前期通过爬虫、解析主文本、分词、统计得到了约5000个样本。目前需要将其按行业分为多个网站样本，故采用聚类的方法。预计大约有10个类别左右。
对于非法网站样本，将网页文本中的词频作为特征。
采用基于文档出现频率过滤的特征选择方法：
首先统计所有词的文档出现频率；然后过滤掉文档出现频率高于文档总数的50%、小于1的单词。
经过滤之后，特征维度减小为177696。
2、 K-means聚类步骤
1）适当选择K个初始中心点。
对于每一维特征，统计其最大值和最小值。每次选择初始中心点时，在每个特征的最大值和最小值中生成一个随机值，作为该特征的值。重复该步骤直到K个初始中心点生成完毕。
2）迭代地将剩下点划分到各个聚类。
对于剩下的每个点，计算其到K个中心点的距离，从中选择距离最近的中心点，将其划分到该中心点所属的聚类中。
两点间的距离计算，对欧式空间中的点使用欧式距离、对文档用余弦相似度、皮尔逊相关度、Jaccard等。
皮尔逊相关度可定义为两个向量之间的协方差和标准差的商。
3）计算每个聚类新的中心点。
计算方法是取聚类中所有点各自维度的算术平均值。
4）判断本次迭代的聚类结果是否与上次一致。
比较K个聚类中的中的点是否发生了变化，依次比较每个聚类即可。如果两次聚类结果没有发生变化，则停止迭代，输出聚类结果；如果发生了变化，则重复2、3步，继续迭代。
时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数
空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数
3、 K如何确定
1）与层次聚类结合
经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果簇的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。
缺点：只对下列情况有效：1.样本相对较小；2.K相对于样本大小较小。
一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上的还是自顶向下形成的，层次的聚类方法可以进一步分为凝聚的（agglomerative）和分裂的（divisive）层次聚类。
（1）凝聚的层次聚类：这种自底向上的策略首先将每个对象作为单独的一个簇，然后和并这些原子簇为越来越大的簇（找距离最近的两个原子簇），直到所有的对像都在一个簇中，或者达到某个终止条件。代表算法AGNES。
（2）分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类相反，它首先将所有的对象置于一个簇中。然后逐渐细分为越来越小的簇，直到每个对象在单独的一个簇中，或者达到一个终止条件，例如打到了某个希望的簇数目后者两个簇之间的距离超过了某个阀值。代表算法DIANA。
凝聚的层次聚类描述起来比较简单，但是计算复杂度比较高，为了寻找距离最近/远和均值，都需要对所有的距离计算个遍，需要用到双重循环。另外从算法中可以看出，每次迭代都只能合并两个子类，这是非常慢的。
分裂的层次聚类过程恰好是相反的，一开始把所有的样本都归为一类，然后逐步将他们划分为更小的单元，直到最后每个样本都成为一类。在这个迭代的过程中通过对划分过程中定义一个松散度，当松散度最小的那个类的结果都小于一个阈值，则认为划分可以终止。
2）稳定性方法[3]
稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有k个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个k，找到合适的k值。
3）系统演化方法[3]
系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为K个聚类时称系统处于状态K。系统由初始状态K=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态Ki，其所对应的聚类结构决定了最优类数Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。
4）使用canopy算法进行初始划分[4]
基于Canopy Method的聚类算法将聚类过程分为两个阶段
Stage1、聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy ，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；
Stage2、在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。
从这个方法起码可以看出两点好处：首先，Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy 个数完全可以作为这个K值，一定程度上减少了选择K的盲目性。
5）对聚类结果合并、分裂——ISODATA
ISODATA算法是在k-均值算法的基础上，增加对聚类结果的“合并”和“分裂”两个操作，并设定算法运行控制参数的一种聚类算法。
全称：Iterative Selforganizing Data Analysis Techniques Algorithm
即：迭代自组织数据分析算法
“合并”操作：
当聚类结果某一类中样本数太少，或两个类间的距离太近时，进行合并。
“分裂”操作：
当聚类结果某一类中样本某个特征类内方差太大，将该类进行分裂。
（0）初始化，然后聚类
c：预期的类数；
Nc：初始聚类中心个数（可以不等于c）；
TN：每一类中允许的最少样本数目（若少于此数，就不能单独成为一类）；
TE：类内各特征分量分布的相对标准差上限（大于此数就分裂）；
TC：两类中心间的最小距离下限（若小于此数，这两类应合并）；
NT：在每次迭代中最多可以进行“合并”操作的次数；
NS：允许的最多迭代次数。
（1）一次迭代聚类后，判断停止、分裂或合并。
a、若迭代次数Ip =NS，则算法结束；
b、若Nc ≤c/2，则转到（2）（分裂）；
c、若Nc ≥2c，则转至（3）（合并）；
d、若c/2< Nc<2c，当迭代次数Ip是奇数时转至（2）；迭代次数Ip是偶数时转至（3）。
（2）分裂操作
计算各类内样本到类中心的标准差向量
σj=(σ1j, σ2j,…., σnj)T , j=1,2,…..,Nc
计算其各个分量。
求出每一类内标准差向量σj中的最大分量
若有某一类中最大分量大于TE，同时又满足下面两个条件之一：
则将该类ωj分裂为两个类，原zj取消且令Nc=Nc+1。
两个新类的中心zj+和zj-分别是在原zj中相应于的分量加上和减去，而起它分量不变，其中0<k≤1。
分裂后，Ip=Ip+1, 重新聚类。
（3）合并操作
计算各类中心间的距离Dij，i=1,2,…,Nc-1; j=1,2,…,Nc
依据TC判断合并。将Dij与TC比较，并将小于TC的那些Dij按递增次序排列，取前NT个。
从最小的Dij开始，将相应的两类合并，并计算合并后的聚类中心。
在一次迭代中，某一类最多只能合并一次。
Nc=Nc-已并掉的类数。
（4）如果迭代次数Ip=NS或过程收敛，则算法结束。否则，Ip=Ip+1，转至（1）。
4、 准则函数——SSE
误差平方和SSE
1）欧氏空间
误差即每个数据点到最近质心的欧氏距离，然后计算误差的平方和。
dist是两点的欧氏距离。
可以证明：使簇的SSE最小的质心是均值。但是K-means只能保证关于SSE的局部最优，因为它们是对选定的质心和簇，而不是对所有可能的选择来优化SSE。
2）文档数据
目标是最大化簇中文档与簇的质心的相似度，该量称作簇的凝聚度。可以证明，簇的质心是均值。
3）其它
曼哈顿距离（L1）和最小化距离中，合适的质心是簇中各点的中位数。
5、 优化初始中心点选择——K-means++
上一节算法的第一步中采用随机特征值的方法生成初始中心点，这种方法具有很大的随机性。K-means对初始中心点很敏感，初始点选的不好很容易得出错误的聚类结果，导致聚类效果不稳定。K-means++算法可以优化初始中心点的选择。
K-means++算法选择初始中心点的基本思想是：初始中心点之间的相互距离要尽可能的远。
1） 从输入的数据点集合中随机选择一个点作为第一个中心点
2）计算每个点与最近一个中心点的距离
对于一个点，计算其与所有已有中心点的距离，选出最短的距离D(X)，保存到数组中。计算这个数组中元素的总和Sum(D(x))。
3）取一个随机值，用权重的方式来计算下一个中心点。
先取一个介于[0, Sum(D(x))]的随机值Random；将Random依次减去数组元素D(X)，若Random<=0，则当前数组元素对应的点即为下一个中心点，否则重复2、3步。
6、 奇异值分解降维——SVD
奇异值分解（Singular valuedecomposition，简称SVD）是线性代数中一种重要的矩阵分解，它可用于对文本特征的降维。
经过SVD得到的三个矩阵，有非常清楚的物理含义。第一个矩阵中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章之间的相关性。因此，我们只要对关联矩阵进行一次奇异值分解，我们就可以同时完成了近义词分类和文章的分类。
SVD用于聚类的一种方法是使用第三个矩阵作为文档的特征，然后再聚类。因为第三个矩阵中每一列表示一篇文档在不同角度的特征值。在文本聚类中，使用这种方法将大大降低特征维度，加快了聚类速度，但同时也丧失了很多精度。
另一种方式是利用协方差矩阵。
奇异值分解融合到k-means算法的主要步骤：
1） 对原始特征矩阵做奇异值分解，得到三个矩阵
2）对三个矩阵做逆向乘法：
得到一个协方差矩阵，它的第i行第j列表示文档i和j的相关度。
3）在k-means算法中，相关度矩阵中的元素即可表示两点间的距离。
不同的是，每个点在选择聚类中心的时候，选择的是相关度最大的点；
另外重新计算聚类中心的方法需要修改：统计每个点到其它点的相关度总和，选择相关度总和最大的点作为新的聚类中心。
7、适用范围和缺点
Kmenas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tKmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。
但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点（离群点）敏感，并且该方法不能处理非球形簇（非凸面形状的簇）、不同尺寸（大小差别较大）、不同密度的簇。
8、聚类效果
1）对K-means聚类出的20个簇，经过人工标注，得到了色情、办假证、发票买卖、赌博、武器买卖、游戏私服等几个大类。其中色情类包括色情图片、色情视频、色情按摩等小的聚类；赌博包括博彩娱乐城、六合彩等小聚类；办假证包括办毕业证、办四六级证；武器买卖包括刀具买卖、弓弩买卖、枪支买卖。
2）得到的20个簇中，15个簇的效果很好，3个簇的效果一般，2个簇的效果较差。
融入SVD的聚类效果不如使用原始特征，说明该协方差矩阵代表的相似度不准确，观察该矩阵，对角线元素并不是最大。该算法有待改进。