3
聚类图示
聚类中没有任何指导信息，完全按照数据的分布进行类别划分
4
什么是分类?
• 数据集合D a ta ，类别标记集合 C
x D a ta , C la ss(x ) C
• 数据集合： 训练数据 TrainData 待分类数据 ClassData
• 已知 x T r a i n D a t a ; k o n w C l a s s ( x ) & & C l a s s ( x ) C • 问题： t C la s s D a ta ;C la s s (t) ？ • 方法：根据训练数据获得类别划分标准 f ( x )
14
Rand
• Set any two data in testing corpus as a pair-point; • If testing corpus has n data, there is n*(n-1)/2 pair-points • a) One pair-point is in same cluster in testing corpus, and in
属于不同维度的特征的关系以 Semantic(Aim,Ajn)表示
• Unbalance Similarity
r
U nbalance(A i,A j) w m (A imA jm )2 m 1
不同特征在数据相似度计算中的作用不同
10
聚类有效性函数（一）
• 最小误差（J e ）:
c个 类 别 ， 待 聚 类 数 据 x， m i为 类 别 Ci的 中 心 ，
• Precision and Recall • Purity • Rand Value • Intra-cluster similarity
Inter-cluster similarity
13
Purity
测试数据首先被人工标注为不同的类别;
测试数据在聚类结果中又被重新划分为多个类别;
nq
测试语料中被标记为第 q个类别的数据数;
clustering results it is in same cluster; • b) One pair-point is in same cluster in testing corpus, and in
clustering results it isn’t in different cluster; • c) One pair-point is in different cluster in testing corpus,
通过何种类别划分方式使类别划分结果达到有效性函数;
8
相似度分类（一）
• Euclidean Distance
r
Euclidean(Ai,Aj) (AimAjm)
• 交叉熵
m1
H ( A i ,A j ) - i r 1 ( A i m 2 A j m ) l o g 2 ( A i m A j m ) 1 2 i n 1 ( A i m * l o g 2 A i m ) i n 1 ( A j m * l o g 2 A j m )
nr
在聚类结果中被划分到 第r个类别的数据数;
nrq nq nr
聚类结果的第r个类别中，被标记为第q个 类别的数据数;
寻找具有最大数据数的
n
q r
作为类别 C
r 的代表;
类别 C r 的Purity:
P(Cr )
1 nr
c
mqa1x(nrq)
聚类算法的Purity:
Purity
c q1
nr n
max(nrq)
x
m ix Ci |Ci|
c
Je ||xm i||2 Je越 小 聚 类 结 果 越 好 i1 x Ci
J e 衡量属于不同类别的数据与类别中心的的误差和;
• 最小方差:
Si
1
n2
xCi
||
x'Ci
xx'
||2
S i 衡量同一类别内数据的平均误差和;
11
聚类的有效性函数（二）
聚类熵（CE）:
pij Cj;
nj
pij
poj
i 1
nj
;
k
poj
Co
j 1
nj
;
k nj
k
En (
e( pij , poj )) e( poj , Co )
j 1 i 1
j 1
E n 第一部分衡量算法的类内相似度,类内相似度越大越好; 第二部分衡量算法的类间相似度,类间相似度越小越好; 12
聚类评价
聚类算法简介
报告人： 刘铭
1
什么是聚类?
• 聚类就是对大量未知标注的数据集，按 数据的内在相似性将数据集划分为多个 类别，使类别内的数据相似度较大而类 别间的数据相似度较小;
2
对相似的 文档或超 链接进行 聚类，由 于类别数 远小于文 档数，能 够加快用 户寻找相 关信息的 速度;
为什么需要聚类?
and in clustering results it is in different cluster; • d) One pair-point is in different cluster in testing and in
7
聚类的基本要素
• 定义数据之间的相似度; • 聚类有效性函数（停止判别条件）;
1. 在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数 来判断多个划分结果中哪个是有效的; 2. 使用有效性函数作为算法停止的判别条件，当类别划分结果达到聚类有效性函 数时即可停止算法运行;
• 类别划分策略（算法）;
• Cosine
Cos(Ai, Aj)
r
AimAjm
m1
r
r
Aim2
Ajm2
m1
m1
数据表示为向量，向量中某一维对应数据某一特征或属性
仅计算了数据向量中属于同一维度特征的权值差距;
9
相似度分类（二）
• Based on Semantic
rr
S e m a n tic (A i,A j) S e m a n tic (A im ,A jn )(A im A jn )2 m 1 n 1
t C l a s s D a t a ; C l a s s ( t) f( t)
5
分类图示
训练数据
待分类数据12346
聚类与分类的区别
• 有类别标记和无类别标记; • 有监督与无监督; （有训练语料与无训练语料） • Train And Classification （分类）; • No Train（聚类）;