聚类算法综述


聚类算法综述 Sunstone Zhang 1. 分层次聚类法(最短距离法) .........................................................................................................1 2. 最简单的聚类方法.............................................................................................................................2 3. 最大距离样本.....................................................................................................................................3 4. K 平均聚类法(距离平方和最小聚类法) ......................................................................................3 5. 叠代自组织(ISODATA)聚类法....................................................................................................4 6. ISODATA 法的改进 ...........................................................................................................................5 7. 基于“核”的评估聚类方法 ...............................................................................................................6 聚类(Cluster):相似文档的分组表达方式。在向量空间模型中,用户可以通过 比较查询向量和聚类的中心进行检索,并在聚类中进一步检索以找到最相似的文 档。 向量空间模型(Vector Space Model ):文档和查询的一种表达方式,将它们转 换为向量。向量的特征一般是对应文档或查询中处理过的单词(取过词根并且删 除了 stopword)。这些向量被赋予权重以强调那些与语义相关的词目,这在检索 中很有用。在检索中比较查询向量和文档向量,并将最接近的文档作为相关文档 返回给用户。SMART 是使用向量空间模型的最有名的例子。 1. 分层次聚类法(最短距离法) 思路:寻找“距离”最近的两个样本结合 1. 有 N 个样本的集合 Zs={Z1, Z2, ..., ZN} 2. 若想要聚成 K 个类 (事先给定 K) [1] k=N, Ci={Zi}, i=1,2,...,N [2] if k=K then END [3] 找到 Ci 与 Cj 之间的距离 d(Ci, Cj)最小的一对 [4] Ci 和 Cj 合成一个类 Ci, 并计算新的 Ci 的中心 [5] 去除 Cj, k=k-1. goto [2] 类间距离 d(Ci, Cj) 1. 类中心间距:d1=||Mi – Mj||,其中 ∑ ∈ = iCZi i ZnM 1 ,ni 是属于 Ci 的样本数。 2. 靠得最近的样本: ||||, min 2 ji jjii ZZCZCZd −∈∈= 3. 离得最远的样本: ||||, max 3 ji jjii ZZCZCZd −∈∈= 4. 类间平均距离: ∑∑ ∈∈ −= iijjCZCZ ji ji ZZnnd ||||1 4 距离计算的次数: 2/)1(2 −= NNCN 。组合 2 1−NC , 2 2−NC ,... 2. 最简单的聚类方法 相似性尺度(距离)阈值,不需要事先给定 K。 有 N 个样本,Zs={Z1, Z2, ..., ZN} 给定一个阈值 T。 任取一个样本,例如 Z1,把 Z1 作为第一个类的中心,Z1=Z1 然后依次取 Zi(i=2,3,...,N),计算 Z1 与 Zi 的距离 D1i 若 D1i≤T,则判定 Zi 属于 Z1 为中心的那个类; 若 D1i>T,则把 Zi 作为新的类中心 Z2。 然后对剩下的样本 Zi 分别计算与 Z1,Z2 的距离 D1i,D2i 若其中较小者≤T,则判定 Zi 属于较小的那一类 否则,就把 Zi 作为新的一个类的中心 Z3 如此,继续...,直至对全体样本做完处理。 特点:不需要事先决定类数。适用于类内距离小,类间距离大的情况。否则结果与取样本的 顺序有关,亦与 T 相关。 C1 C2 C3 C4 C5 C6 100 80 70 90 60 相似性尺度(%) > T > T > T 3. 最大距离样本 思路:取尽可能离得远的样本做中心。 有 N 个样本,Zs={Z1, Z2, ..., ZN} [1] 任取一个样本,例如 Z1,把 Z1 作为第一个类的中心,Z1=Z1 [2] 从集合 Zs 中找出到 Z1 距离最大的样本作为 Z2 [3] 对 Zs 中剩余样本 Zi,分别计算到 Z1,Z2 的距离。令其中较小的那个为 izD [4] 计算 }{max iZ s DZ 。若其值大于某一计算值或给定阈值,则取此 Zi 为新的类中心。计 算值可取:大于等于 Z1 和 Z2 间距离的 n/m 倍( 1/2 1 <≤ mn )。 [5] 重复同样的处理,直到再也找不到符合条件的新的类中心。 [6] 把剩余样本分配到离它最近的那个中心所属的类 缺点:与首先选取哪个样本有关。 4. K 平均聚类法(距离平方和最小聚类法) [1] 假设要聚成 K 个类。由人为决定 K 个类中心 Z1(1), Z2(1), ..., Zk(1)。 [2] 在第 k 次叠代中,样本集{Z}用如下方法分类: 对所有 i=1,2,..,K,i≠j 若 ||)(||||)(|| kZZkZZ ij −<− ,则 )(kSZ j∈ [3] 令由[2]得到的 Sj(k)的新的类中心为 Zj(k+1) 令 ∑ ∈ +−= )( 2||)1(|| kSZ jj j kZZJ 最小。 j=1,2,...,K 则 ∑ ∈ =+ )( 1)1( kSZj j j ZNkZ ,Nj : Sj(k)中的样本数。 [4] 对于所有的 j=1,2,...,K,若 Zj(k+1)=Zj(k),则终止。否则 goto [2]。 开始时 K 的选择:最初选择哪些样本作为中心,将对叠代产生影响。多次叠代,多次修正。 5. 叠代自组织(ISODATA)聚类法 Iterative Self-Organizing Data Analysis Technology Algorithm 思路:给定一些大致参数(根据目的)。 原则:①样本数太少的类 - 取消;②类内离散太大的类 - 分裂;③距离近的类 - 合并。 1) 给一些参数 K:期望分类个数的大致范围 Kθ :一个类内的最少样本数 Sθ :关于类内分散程度的参数 Cθ :关于类间距离(最小)的参数 L:每次叠代允许合并的类数 I:允许叠代的最大次数 2) 适当选取类中心{Z1, Z2, ..., ZNc},Nc:类数 2)’分配样本。如果有{i=1,2,...,Nc} |||||||| ij ZZZZ −≤− ,则 cj NjSZ ,...,2,1, =∈ 3) 如果 Sj 类样本数 kjN θ< ,则取消 Sj 类。Nc=Nc-1, goto 2)’ 4) 重新计算各类中心 c SZj j NjZNZ j ,...,2,1,1 == ∑ ∈ 5) 计算类 Sj 内平均距离 ∑ ∈ =−= jSZ cj j j NjZZND ,...,2,1||,||1 6) 对全体样本求类内距离平均值 ∑∑ == =⋅= cc N j j N j jj NNDNND 11 ,1 7) [a]如果叠代次数≥I,则转向 11)(合并) [b]若 2/KN c ≤ ,则转向 8)(分裂) [c]若偶数次叠代或 KNc 2≥ ,则转向 11)(合并) 8) 计算各类中各分量的标准差 ∑ ∈ −= jSZ ijik j ij zxN 2)(1σ ,i=1,2,...,n,j=1,2,...,Nc,k=1,2,...,Nj xik 为 jSZ ∈ 的第 i 个分量,zij 为 Zj 的第 i 个分量。 ijσ 为第 j 类第 i 个分量标准差 9) 找到各类的标准差最大的分量 cnjjjj Nj ,...2,1},,...,,max{ 21max == σσσσ 10) 分裂:条件 1. Sj θσ >max 且 DD j > 且 )1(2 +> kjN θ 条件 2. Sj θσ >max 且 2/KN c ≤ 若满足两条件之一,则分裂 Sj (a) 建立 + jZ 和 − jZ ,2 个新的类中心,Nc=Nc+1 其中 + jZ 和 − jZ 是沿着 maxjσ 轴,在原来的 Zj 位置上,分别加上和减去一个数 )10(max ≤< kk jσ 。k 是经验值。 (b) goto 2)’(分配样本)。 11) 计算所有各类中心的相互距离 ccjiij NijNiZZD ,...,1,,...,2,1||,|| 1 +==−= − 12) 对于比 cθ 小的 Dij 从小到大排队。假定为 LL jijiji DDD ≤≤≤ ...2211 13) 按 l=1,2,...,L 的顺序,把 ll jiD 对应的 liZ 和 ljZ 合并 []1,1* −=++= ccjjii ji l NNZNZNNNZ llll ll 计算 ll jiD 时的 Zi,Zj,若至少其中一个是在本次叠代中合并取得类中心,则越过此项。 14) 若叠代次数≥I,或参数无改变,则终止。 否则 goto 2)’,需要时可返回 1)修改参数。 6. ISODATA 法的改进 聚类好:满足客观需要,客观标准 客观性:类内近可能相似(类内距小),类间相似性尽可能小(类间距大) 定义一个类间相似性: 定义:Dii 是类 i 的类内离散程度,例如 2/1 1 2||||1 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ −= ∑ = iN j ij i ii ZZND ,其中 Ni 为 i 类中样 本数,Zi 为 i 类的中心。 类间距: 2/1 1 2)( ⎥⎦ ⎤ ⎢⎣ ⎡ −= ∑ = n k kjkiij zzD ,其中 kiz 为 Zi 中的第 k 个分量。 情况⑴ 若 Djj=Dkk,且 Dij ,其中 Rij, Rik 为相 似度。 情况⑵ 若 Dij=Dik,且 Djj 。 定义:类间相似性(测度) ij jjii ij D DDR += ,其中 Dii, Djj, Dij 有各种定义。 在 ISODATA 每次分配样本后,评估某一类 i,与其它所有各类的相似性计算,i=1,2,...,Nc, Nc 为当前类数。 当 ji ≠ ,令 {}iji RijjR ≠= , max 计算 ∑ = = cN i i c RNR 1 1 :各类相似性最大值的平均。 当 R 最小时,可以认为聚类最优。 本方法作为一种评估标准,用于调整聚类情况。 而 ISODATA 法是一种手段,一种过程 手段和评估可以分离,即该评估标准不一定要用 ISODATA 法。 例:某 225 个样本 一般,每类我们用一个点作为中心,例如 Zi, Mi 等(平均值)。如果分布对于中心非完美对 称,则结果有时不能令人满意。 7. 基于“核”的评估聚类方法 例: R Nc min 类内距离(离散程度) 属于该类样本 SZ ∈ ,Z 到 Sj 类“核”的距离 *假定全部样本已聚成 Nc 类 { }NcSSSS ,...,, 21= 当 ji ≠ 时, φ=∩ ji SS 每个类都有自己的“核”, },...,,{ 21 NcEEEE = 每个核内样本数,M1,M2,...,MNc 每个类内样本数,N1,N2,...,NNc 定义:样本 Z 到核内一点 Z 距离为 d(X, Z),例如欧氏距离 样本 Z 到 i 类“核”的距离 ∑ ∈ = iEZ i ZXdEZD ),(),( 定义每一个类内距离和: ∑ ∑ ∈∈ = iiSXEZ ii ZXdSED ),(),( X 分配到各类的原则:若 ),(),( ji EXDEXD ≤ ,则判定 iSX ∈ 。 如何确定 Ei? 目前为计算方便,各类核的点数一般相同。对属于 Si 类的 Ni 个样本,每次取 M 个样本,计算类内距离 i i M NC 哪一组 Ei 类内距离小,但计算量大。 每类中心(核),可 有多个点
还剩6页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

jingbo158

贡献于2014-04-23

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf