总体的分离系数为
2016/5/9
2、熵法(Entropy) 类 的熵为
熵值范围是[0,1] 总体熵值为
熵值越小说明聚类效果越好
2016/5/9
函数xlog(x)的图像
2016/5/9
3、信息差异指标(variation of information) 说明了聚类结果从 信息差异指标公式： 这里 是给定 下， 的条件熵。 改变到 所增加和减少的信息。
4.评估输出：评估聚类结果的质量
聚类分析计算方法
划分方法(partitioning methods)：如K-Means算法 层次聚类法(hierarchical methods)： 如Clarans算法
基于密度的聚类方法(density-based methods)
相关性分析法、布尔矩阵法、传递闭包法和基于 统计的聚类方法等
2016/5/9
统计分析软件包：
SPSS SAS R里函数hclust(),kmeans()
二、文本聚类
文本聚类（Text clustering）文档聚类主要 是依据著名的聚类假设：同类的文档相似度 较大，而不同类的文档相似度较小。 划分方法(partitioning methods)：如K-Means方法 层次聚类法(hierarchical methods)
Fitness function:
改进后的DE算法描述
第一步：给定文档集合D,随机选取K个不同的文本向 量作为质心的初值。 第二步：计算相似度，对每个文档向量分配类 第三步：最小化适应度函数计算最优结果。 第四步：用改进后的交叉和变异程序计算差异得到 子代 第五步：对子代再次计算适应度函数，若差异要优 于上一代，则取而代之，否则上代仍保存。 第六步：重复步骤二到五，直至到达计算适应度的 最大时间 第七步：输出适应度最优的分类结果。
得出的聚类结果为
两类方法： 1、基于点对(point pairs)的评价方法
2、基于信息论(information-theoretic)的评价方法
2016/5/9
基于点对的评价方法
1、purity
表示计算正确聚类的文档数占总文档数的比例，类 式如下：
的purity计算公
purity的取值范围是 全部文档的purity为每一类purity的加权平均：
Step2:文本相似度的计算
a.样本相似度: 内积法、余弦法、距离法。
b.簇间相似度：质心法、离差平方和法等
文本聚类步骤
step3:聚类算法
绝大多数划分算法都是基于对象之间的距离进 行聚类，这类方法只能发现圆形或球状的簇，较难 发现任意形状的簇。为此，提出了基于密度的聚类 算法。
聚类质量的评价方式： 1.内部评价标准。耦合性（separation）与紧凑性 （compactness） 2.外部评价标准。存在测试集情况下的质量评价
2.原则：聚类所生成的簇是一组数据对象的集合， 这些对象与同一个簇中的对象彼此相似，与其他簇 中的对象相异。
3.应用：数据挖掘、信息检索、主题检测、文本 概括等
聚类步骤
1.数据预处理：选择数量、类型和特征的标度 （特征选择与抽取，避免“维数灾难”） 2.为衡量数据点间的相似度定义判别函数。 3.聚类或分组。用聚类分析算法
基于密度聚类算法的效果评价
目 录
基于密度的聚类算法及相关改进
介绍聚类效果的度量指标
实验验证及结果分析
基于密度的聚类算法及改进
一、聚类算法简介 二、文本聚类 三、差分进化（DE）算法
一、聚类分析
1.概念： 聚类分析（又称群分析），它是研究 （样品或指标）分类问题的一种统计分析方法。注 意：它与分类的不同。
四、聚类效果的度量指标
1、内部评价法
2、外部评价法 3、相对评价法
2016/5/9
内部评价法
基于内部标准，这是通过评估每一类的结构性质来判断聚类效果。这种方法 的使用情况一般为没有实际的集群信息。 评价准则： 凝聚度：同一类中的文档要尽可能相似 分离度：不同的类的距离要足够大
n wij nij log( ) nj
文档集合：D ( D1，D2， Dn ) 词的集合：T=(T1 ,T2 , Tm ) Di ( wi1 , wi 2 , wim ), i 1, 2, n
文ቤተ መጻሕፍቲ ባይዱ聚类步骤
利用特征的词频信息建立文本向量，文本 向量与文本向量之间的相似度来进行聚类分析。
2016/5/9
大多数内部验证方法并不能很好地判断具有不同密度的类的方法的优 劣，这是由于低密度的类容易被忽略。可以通过将类内分散程度的和 与类间离散程度做比来衡量聚类结果的优劣。
2016/5/9
y
cosA
cos D
cosB
x
2016/5/9
外部评价法
基于外部标准，这是通过比较聚类结果和真实情况的差异 来判断聚类效果。 假设：数据集的真实分类为
创新点：为了得到点的分布信息，提出计算 点的相对位置，即该点与数据集中心位置度 量。 不仅考虑到簇间耦合性，还考虑到了簇与整 体数据集的耦合性。
i

i
sim( Di , O )
n l 1
sim( Dl , O )

, i 1, 2, n

i 1
n
1, C p

Di C p

2016/5/9
DBSCAN算法描述
输入：包含n个对象的数据库，半径ε ，最 少数目MinPts。 输出：所有生成的簇，达到密度要求。 1.REPEAT 2. 从数据库中抽取一个未处理过的点 3. IF 抽出的点是核心点 THEN找出所有 从该点密度可达的对象，形成一个簇 4. ELSE 抽出的点是边缘点(非核心对象) 跳出本次循环，寻找下一点 5. UNTIL 所有点都被处理
purity的数值越大说明聚类结果与真实情况越相似，即说明聚类效果 良好。
2016/5/9
2、Mirkin Metric
注意到括号前面
1 的是为了限制取值范围是[0,1] 2 n
2016/5/9
3、F-mearure
采用信息检索当中的查准率(Precision)和查全率(recall)的思想，又称聚类精度，
i
文本聚类步骤
评价聚类质量的判别函数（加权与不加权） 1.内部判别函数。
2.外部判别函数。
3.混合判别函数。
三、差分进化（DE）算法
DE 算法主要用于求解连续变量的全局优 化问题。 变异：从某一随机产生的初始群体开始， 随机选取两个体的差向量作为第三个个体的 随机变化源，将差向量加权后按照一定的规 则与第三个个体求和而产生变异个体。 交叉：变异个体与某个预先决定的目标个 体进行参数混合，生成试验个体 选择：如果试验个体的适应度值优于目标 个体的适应度值，则在下一代中试验个体取 代目标个体，否则目标个体仍保存下来。
V-measure：
2016/5/9
基于密度的聚类方法
密度聚类方法的指导思想是，只要一个区域中的 点的密度大于某个域值，就把它加到与之相近的聚 类中去。对于簇中每个对象，在给定的半径ε的邻 域中至少要包含最小数数目（MinPts）个对象。 这类算法能克服基于距离的算法只能发现“类圆 形”的聚类的缺点，可发现任意形状的聚类，且对 噪声数据不敏感。 代表算法有：DBSCAN、OPTICS、DENCLUE算 法等。
这里
，
，
2016/5/9
VI也可表示为 VI取值越小说明聚类效果越好。
2016/5/9
4、V-measure 通过考虑同质性(homogeneity)和(completeness)来 判断聚类效果 homogeneity：
这里
2016/5/9
completeness： 这里
基于密度的聚类方法(density-based methods)
文本聚类步骤
step1:文本表示及特征权重的计算 1）文本表示：特征的提取。 特征定义和筛选考虑以什么作为文本的特征，并 不是所有的词和字都要求或者可以成为特征。 2）特征权重的定义及计算。特征向量空间（VSM） 模型，Salton教授。
查准率： 体现 相对于 来说的同质性(homogeneity)大小
查全率：
来说的完备性(completenss)大小
体现
相对于
定义
和
的F值为
2016/5/9

的F值为
总体的F值为
F值越大说明聚类效果越好
2016/5/9
基于信息论的评价方法
1、分离系数 (Partiotion coefficient) 描述不同类的重叠度 类 的分离系数为