一种分布式Web文档聚类方法

摘要

本申请提出一个分布式Web文档聚类系统DCS(Distributed Clustering System)，该系统采用的主要方法称之为DACWD(Distributed Approach to Clustering Web Documents)。DACWD方法的核心是一个基于信息瓶颈理论的文档聚类方法DCIB(Document Clustering using Information Bottleneck)。DACWD的局部聚类和全局聚类过程迭代使用了DCIB方法。

主权项

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上各文档的向量表示形式，根据文档中特征词的分布情况，文档的向量形式表示为${\overrightarrow{d}}_j^i=\{p\left(t_1\right|d_j^i),p\left(t_2\right|d_j^i),···,p\left(t_m\right|d_j^i)\}$其中，1≤j≤s_i，表示文档中特征词t_a出现的条件概率，1≤a≤m，其计算方法为表示文档中特征词t_a的出现次数；2)将节点N_i上的文档表示为一个集合从中随机取一个文档表示为将其初始化为一个簇，记为存放在簇集合Cⁱ中，即同时将从Xⁱ中删除，簇的向量形式表示为：${\overrightarrow{c}}_0^i=\{p\left(t_1\right|c_0^i),p\left(t_2\right|c_0^i),···,p\left(t_m\right|c_0^i)\}=\{p\left(t_1\right|x_0^i),p\left(t_2\right|x_0^i),···,p\left(t_m\right|x_0^i)\}$其中，表示簇中特征词t_a出现的条件概率，(1≤a≤m)表示文档中特征词t_a出现的条件概率；3)从Xⁱ中取一个文档xⁱ，并将其初始化为一个簇从Cⁱ中寻找簇cⁱ，使得其中表示合并和两个簇时产生的共有信息损失，其计算方法如下：$D(c_e^i,c_f^i)=\underset{u=e,f}{\Sigma }\frac{\left|c_u^i\right|}{\left|X^i\right|}\underset{a=1}{\overset{m}{\Sigma }}p\left(t_a\right|c_u^i)\log \frac{p\left(t_a\right|c_u^i)}{p\left(t_a\right|c_e^i\cup c_f^i)}$其中，|Xⁱ|表示集合Xⁱ中文档的个数，表示合并和两个簇所得到的新簇中特征词t_a出现的条件概率，$p\left(t_a\right|c_e^i\cup c_f^i)=\frac{\left|c_e^i\right|}{|c_e^i\cup c_f^i|}p\left(t_a\right|c_e^i)+\frac{\left|c_f^i\right|}{|c_e^i\cup c_f^i|}p\left(t_a\right|c_f^i)$得到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=C^1\cup C^2\cup ···\cup C^n=\{c_1^1,c_2^1,···,c_{k_1}^1,c_1^2,c_2^2,···,c_{k_2}^2,···c_1^n,c_2^n,···,c_{k_n}^n\}=\{c_1{c}_2,···,c_r\}$其中，从集合C中随机取一个簇表示为c₀，存放在簇集合C′中，即C′＝{{c₀}}，其中集合C′的元素为簇，这些簇由局部聚类阶段产生的簇组成，即C′＝{{c₁，c₂}，{c₃，c₄}，{c₅，c₆}})，同时将c₀从C中删除；簇c₀的向量形式表示为：${\overrightarrow{c}}_0=\{p\left(t_1\right|c_0),p\left(t_2\right|c_0),···,p\left(t_m\right|c_0)\}$其中，p(t_a|c₀)表示簇c₀中特征词t_a出现的条件概率；3)从集合C中取一个簇记为c_e，从C′中寻找簇c，使得其中D(c_e，c_f)表示合并c_e和c_f两个簇时产生的共有信息损失，其计算方法如下：$D(c_e,c_f)=\underset{u=e,f}{\Sigma }\frac{\left|c_u\right|}{r}\underset{a=1}{\overset{m}{\Sigma }}p\left(t_a\right|c_u)\log \frac{p\left(t_a\right|c_u)}{p\left(t_a\right|c_e\cup c_f)}$其中，|c_u|表示簇c_u所包含簇的个数，表示合并c_e和c_f两个簇所得到的新簇中特征词t_a出现的条件概率，$p\left(t_a\right|c_e\cup c_f)=\frac{\left|c_e\right|}{|c_e\cup c_f|}p\left(t_a\right|c_e)+\frac{\left|c_f\right|}{|c_e\cup c_f|}p\left(t_a\right|c_f)$得到c之后，若D(c_e，c)＜α×aver，将D(c_e，c)的值加入到最小值列表L中，将c_e添加到簇c中；否则，为c_e新建一个簇保存，并将新建的簇添加到集合C中，其中α为调节系数，aver为最小值列表L中所有最小值的算术平均，L在初始时为空；4)若C中还有簇未处理，则重复步骤3)；5)对上述聚类结果进行调整，依次从C的每个簇中取每个簇c构成一个新的簇{c}，根据共有信息损失最小原则，将{c}合并到C包含的一个簇中，从而完成对聚类结果的一次调整；将上述针对调整过程循环sum次后，聚类过程完成。