[發明專利]分布式Web文檔聚類系統

無效

• 申請號: 201110083090.1
• 申請日: 2011-03-31
• 公開（公告）號: CN102110172A
• 公開（公告）日: 2011-06-29
• 發明（設計）人: 劉永利
• 申請（專利權）人: 河南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種分布式Web文檔聚類系統，該系統包括多個局部數據節點服務器和一個中心數據節點服務器，每個局部數據節點服務器負責存儲Web文檔及完成局部聚類，中心數據節點服務器負責完成全局聚類，其特征在于：該系統采取以下步驟進行聚類：

①設在一個分布式的環境中，Web文檔分布在n個數據節點N₁，N₂，…，N_n上，各個節點上的文檔數目分別為s₁，s₂，…，s_n，節點N_i上的文檔表示為假設文檔的特征詞集合為{t₁，t₂，…，t_m}，其中n、i和m為自然數，且m為特征詞個數，1≤i≤n。

②針對每個節點N_i，使用下述方法進行局部聚類：

1)得到節點N_i上各文檔的向量表示形式，根據文檔中特征詞的分布情況，文檔的向量形式表示為

d→ji={p(t1|dji),p(t2|dji),···,p(tm|dji)}]]>

其中，1≤j≤s_i，表示文檔中特征詞t_a出現的條件概率，1≤a≤m，其計算方法為表示文檔中特征詞t_a的出現次數；

2)將節點N_i上的文檔表示為一個集合從中隨機取一個文檔表示為將其初始化為一個簇，記為存放在簇集合Cⁱ中，即同時將從Xⁱ中刪除，簇的向量形式表示為：

c→0i={p(t1|c0i),p(t2|c0i),···,p(tm|c0i)}={p(t1|x0i),p(t2|x0i),···,p(tm|x0i)}]]>

其中，表示簇中特征詞t_a出現的條件概率，表示文檔中特征詞t_a出現的條件概率；

3)從Xⁱ中取一個文檔xⁱ，并將其初始化為一個簇從Cⁱ中尋找簇cⁱ，使得其中表示合并和兩個簇時產生的共有信息損失，其計算方法如下：

D(cei,cfi)=Σu=e,f|cui||Xi|Σa=1mp(ta|cui)logp(ta|cui)p(ta|cei∪cfi)]]>

其中，|Xⁱ|表示集合Xⁱ中文檔的個數，表示合并和兩個簇所得到的新簇中特征詞t_a出現的條件概率，

p(ta|cei∪cfi)=|cei||cei∪cfi|p(ta|cei)+|cfi||cei∪cfi|p(ta|cfi)]]>

得到cⁱ之后，若將的值加入到最小值列表Lⁱ中，將xⁱ添加到簇cⁱ中；否則，為xⁱ新建一個簇保存，并將新建的簇添加到集合Cⁱ中，其中αⁱ為調節系數，averⁱ為最小值列表Lⁱ中所有最小值的算術平均，Lⁱ在初始時為空；

4)若Xⁱ中還有文檔未處理，則重復步驟3。

5)對上述聚類結果進行調整，依次從Cⁱ的每個簇中取每個文檔x構成一個新的簇{x}，根據共有信息損失最小原則，將{x}合并到Cⁱ包含的一個簇中，從而完成對聚類結果的一次調整，將上述針對調整過程循環sum次后，聚類過程完成，其中sum為一個自然數；

③綜合各節點的聚類結果，使用DCIB方法進行全局聚類

1)節點N_i上的文檔經局部聚類后產生的簇集合表示為k_i表示節點N_i上的聚類結果所包含的簇數目，由局部聚類的過程可知，簇的向量表示形式為其中表示簇中特征詞t_a出現的條件概率，v為一個自然數，1≤v≤k_i；

2)將所有節點上聚類得到的簇集合進行合并，得到所有簇組成的集合C，即

C=C1∪C2∪···∪Cn={c11,c21,···,ck11,c12,c22,···,ck22,···c1n,c2n,···,cknn}={c1,c2,···,cr}]]>

其中，從集合C中隨機取一個簇表示為c₀，存放在簇集合C′中，即C′＝{{c₀}}，其中集合C′的元素為簇，這些簇由局部聚類階段產生的簇組成，即C′＝{{c₁，c₂}，{c₃，c₄}，{c₅，c₆}})，同時將c₀從C中刪除；簇c₀的向量形式表示為：

c→0={p(t1|c0),p(t2|c0),···,p(tm|c0)}]]>

其中，p(t_a|c₀)表示簇c₀中特征詞t_a出現的條件概率；

3)從集合C中取一個簇記為c_e，從C′中尋找簇c，使得其中D(c_e，c_f)表示合并c_e和c_f兩個簇時產生的共有信息損失，其計算方法如下：

D(ce,cf)=Σu=e,f|cu|rΣa=1mp(ta|cu)logp(ta|cu)p(ta|ce∪cf)]]>

其中，|c_u|表示簇c_u所包含簇的個數，p(t_a|c_e∪c_f)表示合并c_e和c_f兩個簇所得到的新簇中特征詞t_a出現的條件概率，

p(ta|ce∪cf)=|ce||ce∪cf|p(ta|ce)+|cf||ce∪cf|p(ta|cf)]]>

得到c之后，若D(c_e，c)＜α×aver，將D(c_e，c)的值加入到最小值列表L中，將c_e添加到簇c中；否則，為c_e新建一個簇保存，并將新建的簇添加到集合C′中，其中α為調節系數，aver為最小值列表L中所有最小值的算術平均，L在初始時為空；

④若C中還有簇未處理，則重復步驟3；

⑤對上述聚類結果進行調整，依次從C′的每個簇中取每個簇c′構成一個新的簇{c′}，根據共有信息損失最小原則，將{c′}合并到C′包含的一個簇中，從而完成對聚類結果的一次調整；將上述針對調整過程循環sum次后，聚類過程完成。