聚类算法的评价
-
纯度：每个簇被分配给该簇当中出现数目最多的文档所在的类别，然后可以通过正确分配的文档数除以文档集中的文档总数N来得到该分配的精度。
-
TP:将两篇相似文档归入一个簇
TN:将两篇不相似文档归入不同的簇
FP:将两篇不相似文档归入同一簇
FN:将两篇相似文档归入不同的簇
-
例
K-均值算法
最小化文档到其簇中心的欧式距离平方的平均值
-
k-means的损失函数是平方误差：
其中ωk表示第k个簇，u(ωk)表示第k个簇的中心点，RSSk是第k个簇的损失函数，RSS表示整体的损失函数。优化目标就是选择恰当的记录归属方案，使得整体的损失函数最小。
-
K-均值终止条件：
- 当迭代一个固定次数I后停止
- 当文档到簇的分配结果（即划分函数y）不再改变后停止
- 当质心向量不再改变后停止
- 当RSS低于某个阈值时停止
- 当RSS的减小值低于某个阈值时迭代停止
-
种子文档选取的高效启发式策略：
- 从种子集合中排除离群点
- 尝试多种可能初始点，并选择代价最小的聚类结果
- 借助其他方法（如层次聚类）来获得种子
- 为每个簇都选出i个随机向量，然后将它们的质心向量作为该簇的种子向量，该方法对很多文档都具有鲁棒性
-
k-均值算法中簇的个数
- 选取使目标函数最优的K值，即使RSS极小化的K
- RSS_min(k)会随着K的增大而单调递减，当K=N（文档数目）时RSS_min=0
- 方法
-
进行i（10）次聚类过程，每次聚类的结果都包含K个簇，计算每次聚类结果的RSS，取i个RSS中的最小值RSS_min(K)。将K增大，根据RSS_min(K)的值的变化来寻找曲线中的拐点，过了该点后RSS_min(K)的减小量会明显降低。只存在一个最佳的簇数目不常见，必须要借助外部的约束条件从多个可能的K值中进行选择。
-
对每个新簇给与一定的惩罚：首先将所有文档归入单个簇中，然后不断地连续增大K值并从中寻找出最优的K值。
确定λ比直接确定k还难，还不如直接确定K值。某种情况下，可以选择在以前的相似数据集上效果很好的λ值。
