一种应用于社区发现的可覆盖聚类方法

摘要

本发明公开了一种应用于社区发现的可覆盖聚类方法，在得到原始数据之后，将其转化为“用户—属性图”，它的基本单元是“用户—属性对”。在初始化“用户—属性图”之后，首先对其中的“用户—属性对”进行初步的分类，每一个类即为一个候选子图。其次，计算出每个候选子图的发生概率；同时计算出每个用户和各个候选子图之间的相关性。之后，建立概率统计模型，计算每个“用户—属性对”和候选子图之间的相关性。最后，根据数据环境中的这些候选子图的建立，对于数据中的各个“用户—属性图”对进行合理的分类，发现拥有多种属性的关键用户。本发明用于同时处理内容性数据和相关性数据，更好的适应真实网络环境中的社区发现需求。

主权项

一种应用于社区发现的可覆盖聚类方法，其特征在于，包括以下步骤：步骤1，给出所需要的数据输入，具体包括以下子步骤，步骤11，设立数据环境中的用户集合为U＝{u₁,u₂,u₃,……u_N}，一共有N个；设立数据环境中的属性集合为A＝{a₁,a₂,a₃,……a_M}，一共有M个；用u_i→a_j代表第i个用户拥有第j个属性；步骤12，用属性矩阵E代表用户和属性之间的关系，即为内容性数据，在数据环境中，定义E∈R^N×M，e_ij∈{0,1}，1≤i≤N，1≤j≤M，当e_ij＝1时，表示第i个用户拥有第j个属性，e_ij＝0时，表示第i个用户不拥有第j个属性；步骤13，用邻接矩阵W来代表用户和用户之间的关系，即为相关性数据，在数据环境中，定义W∈R^N×N，W_ij≥0，1≤i≤N，1≤j≤N，w_ij的大小代表了第i个用户和第j个用户之间的关系紧密度；步骤2，建立候选子图，分为以下子步骤，步骤21，建立“用户—属性图”，“用户—属性图”是建立同时具有内容性数据和相关性数据基础上的数据结构，按照所述步骤1的定义可以表示为G＝(U，A，W，E)，其中U是数据环境中用户的集合，A是数据环境中属性的集合，W代表了用户和用户之间的相关性的度量，而E代表了用户和属性之间的关联性质，步骤22，在给出所述“用户—属性图”的基础上，一系列候选子图被定义为S_l＝(U_l,A_l,W_l,E_l)，其中l∈{1,2,…,L}，每一个候选子图实际上为“用户—属性图”的部分结构，并且所有的候选子图的用户的总和即是原有数据环境中的所有用户总和；各个候选子图不会占有同一个用户，步骤3，评估候选子图，建立起测量用户或属性和这些候选子图之间相关性的准则，步骤31，度量属性和候选子图之间的相关性$p\left(a_i\right|S_l)=\frac{1}{H_i}\times \left\{\begin{array}{ccc}\exp \left({\lambda }_a(r\left(a_i\right|S_l)-t_l)\right)& \mathrm{for}& r\left(a_i\right|S_l)\ge t_l\\ P_s& \mathrm{for}& \mathrm{other}\end{array}\right.$   公式1在上式中r(a_i|S_l)是一种度量属性和候选子图之间相关性的核心技术，其具体定义为$r\left(a_i\right|S_l)=\frac{1}{{2m}_l}\underset{u_t,u_g\to a_i}{\underset{u_t,u_h\in S_l}{\Sigma }}(w_{\mathrm{tg}}-\frac{d_t{d}_g}{{2m}_l})$在上式中，m_l是W_l内所有元素的权重之和；d_t和d_g分别代表用户u_t和用户u_g的度数，为了更清晰明了的表达上式的含义，将其转化为下面的描述，$r\left(a_i\right|S_l)=\frac{\mathrm{Cut}(U_l^{a_i},U_l^{a_i})}{{2m}_l}-{\left(\frac{\mathrm{Cut}(U_l^{a_i},U_l)}{{2m}_l}\right)}^2$上式中，U_l^ai代表在第l个候选子图中，所有拥有属性a_i的用户的集合；Cut(A，B)代表集合A和集合B之间所有连接关系权重的总和，公式1的其他参数的定义如下所示，t_l是一个门限参数，它是由所有属性与候选子图做相关性测量后，再取均值所得到的；Hi是一个归一化参数；λ_a是一个控制参数，而p_a是一较小的正常数，如果属性和该候选子图的相关性较高，那么该属性从属于该子图的概率也就很高，并和相关性成指数关系，反之该属性从属的概率就很小，并取一个较小的正常数p_a；步骤32，度量用户和候选子图的相关性采用一种马尔科夫随机场的变形来测量用户和候选子图之间的相关性，具体的测量准则如下所示：公式2在上式中Hi是一个归一化参数，N_(i)是用户u_i所有邻居用户的集合；λ_n是一个控制参数，而p_n是一个正常数；对于特定用户，他的邻居用户和某个候选子图的相关性较高，那么该用户从属于该子图的概率也就很高，并和相关性成对数关系，反之该属性从属的概率就很小，并取一个较小的正常数p_n；步骤33，度量“用户—属性对”和候选子图的相关性在分别定义好属性和用户与候选子图的相关性之后，建立起度量“用户—属性对”和候选子图之间的相关性，具体如下所示：p(u_i→a_j|S_l)∝p(u_i|S_l)p(a_j|S_l)   公式3步骤4，可覆盖社区发现步骤41，通过建立概率统计模型来求解具有可覆盖性的社区，先假设用户和属性是已知的变量，而候选子图可表示为隐藏的变量s＝{s_l}^L _l＝1，L表示候选子图的数量，因此，每一个“用户—属性对”可以在概率上从属于多个候选子图，于是可以用下面的公式来描述“用户—属性对”，$p(u_i\to a_j)=p\left(e_{\mathrm{ij}}\right)=\underset{l=1}{\overset{L}{\Sigma }}{\pi }_{l}p\left(e_{\mathrm{ij}}\right|s_l=1)$   公式4步骤42，采用EM算法来最大化似然函数p(E|π)，于是基于完整数据集{E，S}，定义似然函数如下：$\begin{array}{c}p(E,S|\pi )=\underset{i=1}{\overset{N}{\Pi }}\underset{j=1}{\overset{M}{\Pi }}\underset{l=1}{\overset{L}{\Pi }}p{(e_{\mathrm{ij}},s_l)}^{w_{\mathrm{ij}}}\\ =\underset{i=1}{\overset{N}{\Pi }}\underset{j=1}{\overset{M}{\Pi }}\underset{l=1}{\overset{L}{\Pi }}{\left({\pi }^{s_{\mathrm{ijl}}}p{\left(e_{\mathrm{ij}}\right|s_l=1)}^{s_{\mathrm{ijl}}}\right)}^{w_{\mathrm{ij}}}\end{array}$   公式5为了方便推导公式，将上式转移成log形式，$\ln p(E,S|\pi )=\underset{i=1}{\overset{N}{\Sigma }}\underset{j=1}{\overset{M}{\Sigma }}\underset{l=1}{\overset{L}{\Sigma }}{w}_{\mathrm{ij}}{s}_{\mathrm{ijl}}\{{\ln \pi }_l+\ln p\left(e_{\mathrm{ij}}\right|s_l=1)\}$   公式6(3)给出了基于EM算法的公式推导E步：对于候选子图的后验概率推导，可以由下式表达：$\ln p(W,S|\pi )\propto \underset{i=1}{\overset{N}{\Pi }}\underset{j=1}{\overset{M}{\Pi }}\underset{l=1}{\overset{L}{\Pi }}{\left[{\pi }_{l}p\left(e_{\mathrm{ij}}\right|s_l)\right]}^{s_{\mathrm{ijl}}}$   公式7之后，求取s_ijl的期望值，具体的推导如下：$E\left[s_{\mathrm{ijl}}\right]=\left\{\begin{array}{c}\frac{{\Sigma }_{s_{\mathrm{ijl}}}{s}_{\mathrm{ijl}}{\left[{\pi }_{l}p\left(e_{\mathrm{ij}}\right|s_l=1)\right]}^{s_{\mathrm{ijl}}}}{{\Sigma }_{s_{\mathrm{ijl}}}{\left[{\pi }_{l}p\left(e_{\mathrm{ij}}\right|s_l=1)\right]}^{s_{\mathrm{ijl}}}}\\ =\frac{{\pi }_{l}p\left(e_{\mathrm{ij}}\right|s_l=1)}{{\Sigma }_{l=1}^L{\pi }_{l}p(e_{\mathrm{ij}}{|S}_{\mathrm{sl}}=1)}=\gamma \left(s_{\mathrm{ijl}}\right)\end{array}\right.$   公式8在上式中，p(e_ij|s_l＝1)可以由公式3计算得出，而γ(s_ijl)则是代表一种可信度，M步：在M步中，将要推导模型的相关参数，首先来看模型参数π^new，${\pi }^{\mathrm{new}}=\underset{\pi }{\arg \max }Q(\pi ,{\pi }^{\mathrm{old}})$$\begin{array}{c}Q(\pi ,{\pi }^{\mathrm{old}})\\ =\underset{s}{\Sigma }p\left(S\right|E,{\pi }^{\mathrm{old}})\ln p(E,S|\pi )\\ =E_s\left[\ln p(E,S|\pi )\right]\\ =\underset{i=1}{\overset{N}{\Sigma }}\underset{j=1}{\overset{M}{\Sigma }}\underset{l=1}{\overset{L}{\Sigma }}{w}_{\mathrm{ij}}\gamma \left(s_{\mathrm{ijll}}\right)\{\ln {\pi }_l+\ln p\left(e_{\mathrm{ij}}\right|s_l=1)\}\end{array}$   公式9上式是模型参数的求解公式，其中π^new表示的是下一次迭代中的参数π，而π^old表示的是当前迭代中的参数π，为了求解出模型参数，采用了拉格朗日乘子法，具体如下：$\begin{array}{c}\frac{\partial }{{\partial \pi }_l}\{Q(\pi ,{\pi }^{\mathrm{old}})-\lambda (\underset{l=1}{\overset{L}{\Sigma }}{\pi }_l-1)\}=0\\ \Rightarrow \underset{i=1}{\overset{N}{\Sigma }}\underset{j=1}{\overset{M}{\Sigma }}\frac{w_{\mathrm{ij}}\gamma \left(s_{\mathrm{ijl}}\right)}{{\pi }_l}=\lambda \\ \Rightarrow {\pi }_l=\frac{{\Sigma }_{i=1}^N{\Sigma }_{j=1}^M{w}_{\mathrm{ij}}\gamma \left(s_{\mathrm{ijl}}\right)}{{\Sigma }_{i=1}^N{\Sigma }_{j=1}^M{w}_{\mathrm{ij}}}\end{array}$   公式10采用p(S|U)去重新确立候选子图，即根据用户相对于候选子图的归属，并以此来重新建立候选子图，$p(s_l=1|u_i)=\frac{{\pi }_{l}p\left(u_i\right|s_l-1)}{{\Sigma }_{t=1}^L{\pi }_{t}p\left(u_i\right|s_t=1)}$   公式11具体而言，本发明中使用向量{p(s_l＝1|u_i)}^L_l＝1来表征用户u_i，然后使用这种信息对所有的用户做聚类处理，并得到新的一系列候选子图，在新的候选子图的基础上，EM算法进行下一次的迭代运算，最终就可以得到稳定而可信的L个候选子图，最后，对“用户—属性对”的聚类分析，会有一部分拥有多个“用户—属性对”的用户从属于多个不同的类，即具有可覆盖性的社区发现的完成。