·1414 北京科技大学学报 第36卷 裂后，利用K-means思想随机选取初始簇中心进行 文本对” 二分聚类并多次迭代寻找最优划分.本文提出通过 证明：设算法在n步搜索过程中得到的互不相 搜索簇的“互为最小相似度文本对”选择二分聚类 同的文本组成的序列DSd,d2,,d,…,dn〉 的初始二分簇中心，其中簇的“互为最小相似度文 (n≥3)，即d:+1是文本簇C中与d,相似度最小的 本对”定义如下 文本： 定义4互为最小相似度文本对.文本簇C= SIM (d;,d)min (SIM(d,d)}, {d,d2,…,d,…,d}的“互为最小相似度文本 i=1,2,…,n1, 对”定义为簇C中满足如下条件的两个文本d:,d: 相应的相似度值序列记为SS〈31，s2…,s。-1), SIM (d,,d,)min (SIM(d,,d))= 其中s:=SIM(d:,d:+i). min (SIM (d;,d), (6) 因为 即d是文本簇中与d相似度最小的文本，同时d是 SIM (d;,di)min (SIM(d,,d)}, 该簇中与d相似度最小的文本. SIM(dd)=min(sIM(dd)) 本文提出根据搜索簇的“互为最小相似度文本 i=1,2,…,n-2, 对”确定初始二分簇中心，但根据定义4，显然一个 所以SIM(d,d+1)≥SIM(d+1,d+2）,s:≥s+1,即 文本簇中可能含有多于一对满足式(6)的“互为最 S1≥S2≥≥S:≥Si+1≥"≥$m-1 小相似度文本对”.因此，给出簇的“互为最小相似 (1)由算法终止条件知：若3i=1,2,…,n-2, 度文本”搜索的贪心算法如下 使得s:=s:+1,则算法满足终止条件，停止搜索，输出 算法1“互为最小相似度文本对”搜索算法. “互为最小相似度文本对”d,d 输入：文本簇C={d1,d2,…,d,…,dn},nc为 (2)若i=1,2,…,n-2,s:>5+1即s1>52> 文本簇C中文本的数量. …>S:>S:+1>…>5n-2>Sn-1,算法继续第n+1步 输出：“互为最小相似度文本对”d,d 搜索，设搜索到文本簇C中与dn相似度最小的文本 算法步骤： 为d,则SIM(dn-1'dn）≥SlM(dn,d),即sn-1≥sn 步骤1在文本簇C中随机选取文本d,赋给 ①若SIM(dn-1,dn）=SIM(dn,d),算法满足 d,d←d 终止条件，停止搜索，输出“互为最小相似度文本 步骤2在文本簇C中搜索与文本d,相似度最 对”dn-'dn 小的文本d,即 ②若SM(dn-,dn)>SIM(dn,d),则i=1, SIM(dd,)=min (SIM (dd)) 2,…,n,d4≠d.因为： 步骤3在文本簇C中搜索与文本d,相似度最 首先，若3i=1,2,…,n-2,使得d=d,则 小的文本d,即 s:>s-1>SIM (d,,d)=SIM (d;,di)>SIM(d, SIM (d,,d)min {SIM (d,,d,)}. d)SIM(d:,d+i）>SIM(dn,d:),这与“sIM(d:, d:ec 步骤4判断以下两个条件： d:+i)=min{SlM(d,d,)}(d,1是文本簇C中与d 4.1若d4=d或SM(d,d,)=SM(d,d,), 相似度最小的文本)”矛盾： 则算法结束，输出d,d,为“互为最小相似度文本 其次，显然有d≠dn,dn-1… 对”，即文本簇C的初始簇中心； 即d与DS中所有文本均不相同，因此不存在 4.2若d≠d且SIM(d,d,)≠SM(d,d,), 因出现文本序列循环回路而无法终止算法的情况， 则赋值d←d,d,←d,返回步骤3重新搜索 可将新搜索的文本d,加入DS后继续搜索 步骤5结束. 由①和②知在算法第n+1步搜索中，新搜索到 由算法1的步骤可知，搜索文本的过程中可能 的文本d或满足终止条件①，算法搜索结束：或与 会出现循环，即无法收敛得到“互为最小相似度文 已搜索到的长度为n的互不相同文本序列DS中所 本对”的结果.下面通过定理证明算法1的收敛性. 有文本均不为同一文本，可添加到DS中形成长度 定理1算法1的收敛性.经过有限步骤，算法 为n+1的互不相同文本序列继续搜索；最坏的情 1必收敛，即对于任意文本簇C={d,d2,…,d,…, 况，当DS长度达到nc时，由于不存在与DS中所有 dnc},nc≥2，在有限的n步(n≤nc,nc为文本簇C 文本均互不相同的文本，无法满足②，此时必满足终 中文本的数量)之内，总能寻找到“互为最小相似度 止条件①，算法搜索结束北 京 科 技 大 学 学 报 第 36 卷 裂后，利用 K-means 思想随机选取初始簇中心进行 二分聚类并多次迭代寻找最优划分． 本文提出通过 搜索簇的“互为最小相似度文本对”选择二分聚类 的初始二分簇中心，其中簇的“互为最小相似度文 本对”定义如下． 定义 4 互为最小相似度文本对． 文本簇 C = { d1，d2，…，di，…，dnC } 的“互为最小相似度文本 对”定义为簇 C 中满足如下条件的两个文本 di，dj : SIM( di，dj ) = min dk∈C { SIM( di，dk ) } = min dk∈C { SIM( dj ，dk ) } ， ( 6) 即 di是文本簇中与 dj相似度最小的文本，同时 dj是 该簇中与 di相似度最小的文本． 本文提出根据搜索簇的“互为最小相似度文本 对”确定初始二分簇中心，但根据定义 4，显然一个 文本簇中可能含有多于一对满足式( 6) 的“互为最 小相似度文本对”． 因此，给出簇的“互为最小相似 度文本”搜索的贪心算法如下． 算法 1 “互为最小相似度文本对”搜索算法． 输入: 文本簇 C = { d1，d2，…，di，…，dnC } ，nC为 文本簇 C 中文本的数量． 输出: “互为最小相似度文本对”dx，dy ． 算法步骤: 步骤 1 在文本簇 C 中随机选取文本 di 赋给 dx，dx←di ． 步骤 2 在文本簇 C 中搜索与文本 dx相似度最 小的文本 dy，即 SIM( dx，dy ) = min dj ∈C { SIM( dx，dj ) } ． 步骤 3 在文本簇 C 中搜索与文本 dy相似度最 小的文本 dk，即 SIM( dy，dk ) = min dj ∈C { SIM( dy，dj ) } ． 步骤 4 判断以下两个条件: 4. 1 若 dk = dx或 SIM( dx，dy ) = SIM( dk，dy ) ， 则算法结束，输出 dx，dy 为“互为最小相似度文本 对”，即文本簇 C 的初始簇中心; 4. 2 若 dk≠dx且 SIM( dx，dy ) ≠SIM( dk，dy ) ， 则赋值 dx←dy，dy←dk，返回步骤 3 重新搜索． 步骤 5 结束． 由算法 1 的步骤可知，搜索文本的过程中可能 会出现循环，即无法收敛得到“互为最小相似度文 本对”的结果． 下面通过定理证明算法 1 的收敛性． 定理 1 算法 1 的收敛性． 经过有限步骤，算法 1 必收敛，即对于任意文本簇 C = { d1，d2，…，di，…， dnC } ，nC≥2，在有限的 n 步( n≤nC，nC为文本簇 C 中文本的数量) 之内，总能寻找到“互为最小相似度 文本对”． 证明: 设算法在 n 步搜索过程中得到的互不相 同的文本组成的序列 DS =? d1，d2，…，di，…，dn ? ( n≥3) ，即 di + 1 是文本簇 C 中与 di 相似度最小的 文本: SIM( di，di + 1 ) = min dj ∈C { SIM( dj ，di ) } ， i = 1，2，…，n ’1， 相应的相似度值序列记为 SS =? s1，s2 … ，sn － 1 ?， 其中 si = SIM( di，di + 1 ) ． 因为 SIM( di，di + 1 ) = min dj ∈C { SIM( dj ，di ) } ， SIM( di，di + 2 ) = min dj ∈C { SIM( dj ，di + 1 ) } ， i = 1，2，…，n － 2， 所以 SIM( di，di + 1 ) ≥SIM( di + 1，di + 2 ) ，si≥si + 1，即 s1≥s2≥…≥si≥si + 1≥…≥sn － 1 ． ( 1) 由算法终止条件知: 若i = 1，2，…，n － 2， 使得 si = si + 1，则算法满足终止条件，停止搜索，输出 “互为最小相似度文本对”ds，ds + 1 ． ( 2) 若i = 1，2，…，n － 2，si ＞ si + 1，即 s1 ＞ s2 ＞ … ＞ si ＞ si + 1 ＞ … ＞ sn － 2 ＞ sn － 1，算法继续第 n + 1 步 搜索，设搜索到文本簇 C 中与 dn相似度最小的文本 为 dk，则 SIM( dn － 1，dn ) ≥SIM( dn，dk ) ，即 sn － 1≥sn ． ① 若 SIM( dn － 1，dn ) = SIM( dn，dk ) ，算法满足 终止条件，停止搜索，输出“互为最小相似度文本 对”dn － 1，dn ; ② 若 SIM( dn － 1，dn ) ＞ SIM( dn，dk ) ，则i = 1， 2，…，n，dk≠di ． 因为: 首先，若i = 1，2，…，n － 2，使得 dk = di，则 si ＞ sn － 1 ＞ SIM( dn，dk ) SIM( di，di + 1 ) ＞ SIM( dn， dk ) SIM( di，di + 1 ) ＞ SIM( dn，di ) ，这与“SIM( di， di + 1 ) = min dj ∈C { SIM( dj ，di ) } ( di + 1 是文本簇 C 中与 di 相似度最小的文本) ”矛盾; 其次，显然有 dk≠dn，dn － 1 ． 即 dk与 DS 中所有文本均不相同，因此不存在 因出现文本序列循环回路而无法终止算法的情况， 可将新搜索的文本 dk加入 DS 后继续搜索． 由①和②知在算法第 n + 1 步搜索中，新搜索到 的文本 dk或满足终止条件①，算法搜索结束; 或与 已搜索到的长度为 n 的互不相同文本序列 DS 中所 有文本均不为同一文本，可添加到 DS 中形成长度 为 n + 1 的互不相同文本序列继续搜索; 最坏的情 况，当 DS 长度达到 nC时，由于不存在与 DS 中所有 文本均互不相同的文本，无法满足②，此时必满足终 止条件①，算法搜索结束． · 4141 ·