论文部分内容阅读
摘 要：Web2.0时代的到来让社会媒体以前所未有的方式逐步改变着人们的生活，并颠覆了人们获取信息的方式，用户不仅可以接收信息，同时还可以参与发布信息和传播信息，更加重要的是用户不再是独立的个体，他们通过互相交互而产生关系。目前大部分研究人员对于社会网络关系的研究都是从关系的意义和价值的角度出发的，即利用已存在的关系去分析其他问题，比如关键人物挖掘、信息传播路径和信息分享机制等，而很少去研究社会关系本身，但是研究分析用户的关系链，不仅能够实现用户对好友的快速定位和管理，还能方便地从海量的关注对象中找到自己感兴趣的好友。本文针对这一问题，重点研究了社会媒体中用户之间社会关系挖掘的相关问题，包括对已有关系的研究和对未知潜在关系的研究。通过对社会关系进行计算研究，能够提取用户之间的关系，对用户进行内容的推荐。
关键词：微博；社群挖掘；推荐系统；用户关系
中图分类号：TP311.13 文献标识码： B 文章编号： 2095-8595 （2016） 06-746-04电子科学技术 URL： http//www.china-est.com.cn DOI： 10.16453/j.issn.2095-8595.2016.06.019
引言
本文从用户节点间的交互行为出发，同时构造关系社群挖掘模型，并对挖掘出的社群进行语义描述，从而识别出各个用户间社会关系类型。本实验旨在验证该识别框架是否能准确识别出各种关系类型，验证挖掘得出的关系社群具有较高的社群紧密度以及模型是否具有较好的推广性。同时通过已挖掘的用户关系对用户进行个性化的推荐。
1 研究意义
基于交互行為的用户关系类型挖掘：
不同于传统的实体关系抽取以及基于Web信息的社会关系识别，在社会媒体上，用户是信息的产生者，因此不必进行实体的抽取，而信息是依靠用户之间的链接关系来进行传播的，因此用户间交互内容的主题能在某种程度上代表两人之间的关系类型。
该系统是基于用户的交互行为建立起一个联合框架，用于挖掘微博中不同用户之间的社会关系类型[1]。该框架主要包括两个部分：社群发现和社群描述。在社群发现阶段，由于与传统的用于文本挖掘的新闻语料库不同，微博语料中的信息都是短文本，因此该系统基于LDA（Latent Dirichlet Allocation）主题模型的扩展对社群、用户以及主题进行统一建模，在已观察到的微博的单词和参与用户的基础上，挖掘出每个关系社群中最可能的主题和用户。接着在社群描述阶段借助外部资源（维基百科）确定社群所属的具体关系主题类别，从而实现对关系社群的语义描述，本课题将关系主题类别划分为六类：经济、教育、社会政治、娱乐、生活和科技[2]。
基于聚类和相似度传播的用户关系推荐：
社会媒体上的推荐问题，不同于传统的推荐系统，其一大挑战在于它极端的数据稀疏性。因此对于如此稀疏的数据，协同过滤这样单纯的基于二元关系的方法就难以达到理想的推荐效果。该系统通过研究微博网络中用户的特性，以及用户之间的交互行为来深入理解用户间关注链接关系形成所需要的条件。继而利用这种条件构造规则进行推荐，这样可以从本质上提高推荐质量。首先基于人物实体建模计算用户间相似度，根据相似度对用户进行聚类，并将链接拓扑图转换为有向加权图。然后，根据结构相似度算法，提出加权SimRank算法来迭代计算图中非好友用户节点之间的相似度，最终依据排序后的相似度进行关注好友推荐。
2 技术路线
运用Kernighan-Lin算法进行社会群体的发现，并分析其中用户与用户之间的关系。其中Kernighan-Lin算法是通过其迭代优化社群内部结构以及社群间链接边数目来对网络结构进行划分。算法的核心是在划分网络结构的过程中引入一个增益函数Q。Q等于两个社群内部的链接边的数目减去两个社群之间链接边的数目。
通过社群结构挖掘技术，从复杂网络中挖掘出多个内部紧密联系的群组，通过概率主题模型技术，来挖掘给定语料库的潜在主题信息。通过对各个社会媒体用户间的行为与关系的数据进行挖掘，进行社会关系模型的构建，并验证此模型对社会用户行为与关系的有效性[5]。
通过分析用户间的相似度，根据相似度对用户进行聚类，最后根据相似度排序顺序进行关注好友的推荐。其算法流程如下：
a） 根据指定规模或者随机将网络中的所有节点划分为两个社群C1和C2。
b） 分别从两个社群中各取一个节点凑成一个节点对，然后计算这对节点的增益函数变化量?Q，?Q=节点对交换后的增益Q -节点对交换前的增益Q。交换令?Q取到最大值时对应的节点对。
c） 不再选择已交换过的节点，重复进行步骤b），直至社群C1或C2中的所有节点都被交换过一次。
d） 最终得到的社群结构即为对该网络的最佳划分。
所以基于Kernighan-Lin算法可以得到社群结构即为对该网络的最佳划分。
针对聚类分析的相关研究进行分析可知现在聚类算法可以分为四种：划分法、层次法、基于密度的方法、基于网格的方法。本课题将对相似性网络用户进行聚类分析，并对相似度矩阵的用户进行聚类，并采用传递闭包法对用户进行聚类处理。首先根据计算好的相似度值以用户节点为行和列构建相似度矩阵SSM，矩阵元素代表用户两两之间的相似度，显然矩阵满足自反性、对称性，但不满足传递性。因此要求得等价矩阵只用考虑求其传递闭包：即依次计算，m代表用户数量且k在1000以内，若中途出现则中断，此时可以得到SSM的等价矩阵，接着定义一个阈值，在等价矩阵的基础上将低于阈值的相似度置为0，反之置为1；根据最终矩阵中的1进行聚类[4]。用户聚类算法描述如图1所示。
输入值：用户微博文本以及关注网络；输出值：用户聚类模式。 步骤：
1）根据文本相似度和结构相似度计算用户两两之间的相似度值；
2）根据相似度值构建用户相似度矩阵SSM；
3）求得矩阵SSM的传递闭包，得到等价矩阵SSM*；
4）根据实际情况确定聚类数目，进而调节阈值 到合适值进行模糊聚类；
5）输出最终用户聚类模式。
LDA 的概率图模型如图2所示：结合概率主题模型中代表模型LDA（Latent Dirichlet Allocation）[3]，LDA模型是主题模型最简单的一种实现，其基础是假设每篇文本是由多个主题构成的模型进行分析，达到对模型内部性能评估和模型外在表现评估。
Gibbs抽样是马尔科夫链蒙特卡洛MCMM（Markov-Chain Monte Carlo）算法的一个特例。该算法迭代选取概率向量的一个维度，在其他维度的变量值指定的前提下来抽样当前该维度的值，直到收敛，最终输出待估计的参数的近似值。采样流程如图3所示。
a） 初始化：为语料库中每篇文档的每个单词随机赋予一个所属主题z（0） ；
b） 统计工作：统计每个主题z下出现单词t的数量n（t | z），以及每个文档m下出现主题z中的词的数量n（z | m）；
c） 当前单词维度的主题采样：对于语料库中的每篇文档中的每個单词wi，根据公式（2.4）计算p（zi=k|z-i，d，wi），即排除当前词的主题分配，根据其他所有词的主题分配来估计当前词分配各个主题的概率。然后根据这个概率分布为当前词随机抽样获取一个新的主题分配z（a）；按照顺序对语料库中的每篇文档中的每个单词重复上面的步骤；
d） 重复迭代步骤（c），直至发现每个文档下主题分布θ和每个主题下单词的分布 收敛，算法停止，输出待估计的参数θ和Φ。
建立随机游走模型系统，以基于用户聚类和相似度传播的两阶段关系推荐用于潜在好友推荐。随机游走模型是一种衡量结构上下文（Structual-Context）相似性的算法，即它利用图的结构信息来计算上下文中各个对象之间的相似度：如果两个节点所连接的节点相似，那么这两个节点也相似。换句话说，节点间的相似性依赖于其邻居节点间的相似性，用户之间的相似度沿用用户的关注链接网络进行传播，这样就充分考虑了已关注的对象对用户交友过程的影响，进而通过这种影响与关联实现对相似信息的推荐。最后通过实验进行对比，验证该模型系统的有效性。
1） 基于主题内容相似度（Content-based）的K近邻关注对象推荐算法：对用户的微博进行主题建模，根据主题相似度进行排序后推荐。
2） 基于共同邻居（Common Neighbors）的关注对象推荐算法：仅考虑两个用户间的共同邻居数来度量相似度，排序后推荐。
3） 基于随机游走算法：不考虑相邻用户间的权重信息，直接进行随机游走更新相似度，排序后推荐。
3 系统实现功能
实现一个基于聚类与传播的微博用户关系提取与推荐的软件系统，系统能够完成以下功能。
对微博用户中现有关系群的挖掘功能：本系统通过分析微博网络中用户的特性以及用户之间的交互行为来深入解析链接关系，继而基于Kernighan-Lin算法完成交互行为的用户关系类型挖掘[6]。
对潜在关系的推荐功能：系统通过实现基于传递闭包的用户聚类方法、基于LDA模型的数据处理、以及通过随机游走模型的计算，完成相似度的传播与微博用户潜在关系的推荐。
4 结束语
本文在基于数据挖掘以及聚类方法的基础上，对微博用户关系进行挖掘，并通过挖掘的关系对用户进行个性化的推荐。通过此系统，不仅能对用户进行关系化的管理，而且还可以通过用户关系对用户进行推荐，使用户获得的被推荐内容更加有效，也提高用户获取信息以及新闻的效率。
参考文献
何黎，何跃，霍叶青.微博用户特征分析和核心用户挖掘[J].情报理论与实践，2011，11：121-125.
王晓光. 微博客用户行为特征与关系特征实证分析—以“新浪微博”为例[J].竞争情报，2010，54（14）：66-70.
张晨逸，孙建伶，丁轶群.基于MB-LDA模型的微博主题挖掘[J].计算机研究与发展. 2011（10）.
贾彩燕，陆汝钤.关联规则挖掘的取样误差量化模型和快速估计算法[J].计算机学报. 2006（04）.
Han JW，Kameber M，数据挖掘概念与技术（范明，孟小峰等译）[M].北京，机械工业出版社，2001：223～261.
胡可云，陆玉昌，石纯一. 基于概念格的分类和关联规则的集成挖掘方法[J]. 软件学报. 2000（11）.
关键词：微博；社群挖掘；推荐系统；用户关系
中图分类号：TP311.13 文献标识码： B 文章编号： 2095-8595 （2016） 06-746-04电子科学技术 URL： http//www.china-est.com.cn DOI： 10.16453/j.issn.2095-8595.2016.06.019
引言
本文从用户节点间的交互行为出发，同时构造关系社群挖掘模型，并对挖掘出的社群进行语义描述，从而识别出各个用户间社会关系类型。本实验旨在验证该识别框架是否能准确识别出各种关系类型，验证挖掘得出的关系社群具有较高的社群紧密度以及模型是否具有较好的推广性。同时通过已挖掘的用户关系对用户进行个性化的推荐。
1 研究意义
基于交互行為的用户关系类型挖掘：
不同于传统的实体关系抽取以及基于Web信息的社会关系识别，在社会媒体上，用户是信息的产生者，因此不必进行实体的抽取，而信息是依靠用户之间的链接关系来进行传播的，因此用户间交互内容的主题能在某种程度上代表两人之间的关系类型。
该系统是基于用户的交互行为建立起一个联合框架，用于挖掘微博中不同用户之间的社会关系类型[1]。该框架主要包括两个部分：社群发现和社群描述。在社群发现阶段，由于与传统的用于文本挖掘的新闻语料库不同，微博语料中的信息都是短文本，因此该系统基于LDA（Latent Dirichlet Allocation）主题模型的扩展对社群、用户以及主题进行统一建模，在已观察到的微博的单词和参与用户的基础上，挖掘出每个关系社群中最可能的主题和用户。接着在社群描述阶段借助外部资源（维基百科）确定社群所属的具体关系主题类别，从而实现对关系社群的语义描述，本课题将关系主题类别划分为六类：经济、教育、社会政治、娱乐、生活和科技[2]。
基于聚类和相似度传播的用户关系推荐：
社会媒体上的推荐问题，不同于传统的推荐系统，其一大挑战在于它极端的数据稀疏性。因此对于如此稀疏的数据，协同过滤这样单纯的基于二元关系的方法就难以达到理想的推荐效果。该系统通过研究微博网络中用户的特性，以及用户之间的交互行为来深入理解用户间关注链接关系形成所需要的条件。继而利用这种条件构造规则进行推荐，这样可以从本质上提高推荐质量。首先基于人物实体建模计算用户间相似度，根据相似度对用户进行聚类，并将链接拓扑图转换为有向加权图。然后，根据结构相似度算法，提出加权SimRank算法来迭代计算图中非好友用户节点之间的相似度，最终依据排序后的相似度进行关注好友推荐。
2 技术路线
运用Kernighan-Lin算法进行社会群体的发现，并分析其中用户与用户之间的关系。其中Kernighan-Lin算法是通过其迭代优化社群内部结构以及社群间链接边数目来对网络结构进行划分。算法的核心是在划分网络结构的过程中引入一个增益函数Q。Q等于两个社群内部的链接边的数目减去两个社群之间链接边的数目。
通过社群结构挖掘技术，从复杂网络中挖掘出多个内部紧密联系的群组，通过概率主题模型技术，来挖掘给定语料库的潜在主题信息。通过对各个社会媒体用户间的行为与关系的数据进行挖掘，进行社会关系模型的构建，并验证此模型对社会用户行为与关系的有效性[5]。
通过分析用户间的相似度，根据相似度对用户进行聚类，最后根据相似度排序顺序进行关注好友的推荐。其算法流程如下：
a） 根据指定规模或者随机将网络中的所有节点划分为两个社群C1和C2。
b） 分别从两个社群中各取一个节点凑成一个节点对，然后计算这对节点的增益函数变化量?Q，?Q=节点对交换后的增益Q -节点对交换前的增益Q。交换令?Q取到最大值时对应的节点对。
c） 不再选择已交换过的节点，重复进行步骤b），直至社群C1或C2中的所有节点都被交换过一次。
d） 最终得到的社群结构即为对该网络的最佳划分。
所以基于Kernighan-Lin算法可以得到社群结构即为对该网络的最佳划分。
针对聚类分析的相关研究进行分析可知现在聚类算法可以分为四种：划分法、层次法、基于密度的方法、基于网格的方法。本课题将对相似性网络用户进行聚类分析，并对相似度矩阵的用户进行聚类，并采用传递闭包法对用户进行聚类处理。首先根据计算好的相似度值以用户节点为行和列构建相似度矩阵SSM，矩阵元素代表用户两两之间的相似度，显然矩阵满足自反性、对称性，但不满足传递性。因此要求得等价矩阵只用考虑求其传递闭包：即依次计算，m代表用户数量且k在1000以内，若中途出现则中断，此时可以得到SSM的等价矩阵，接着定义一个阈值，在等价矩阵的基础上将低于阈值的相似度置为0，反之置为1；根据最终矩阵中的1进行聚类[4]。用户聚类算法描述如图1所示。
输入值：用户微博文本以及关注网络；输出值：用户聚类模式。 步骤：
1）根据文本相似度和结构相似度计算用户两两之间的相似度值；
2）根据相似度值构建用户相似度矩阵SSM；
3）求得矩阵SSM的传递闭包，得到等价矩阵SSM*；
4）根据实际情况确定聚类数目，进而调节阈值 到合适值进行模糊聚类；
5）输出最终用户聚类模式。
LDA 的概率图模型如图2所示：结合概率主题模型中代表模型LDA（Latent Dirichlet Allocation）[3]，LDA模型是主题模型最简单的一种实现，其基础是假设每篇文本是由多个主题构成的模型进行分析，达到对模型内部性能评估和模型外在表现评估。
Gibbs抽样是马尔科夫链蒙特卡洛MCMM（Markov-Chain Monte Carlo）算法的一个特例。该算法迭代选取概率向量的一个维度，在其他维度的变量值指定的前提下来抽样当前该维度的值，直到收敛，最终输出待估计的参数的近似值。采样流程如图3所示。
a） 初始化：为语料库中每篇文档的每个单词随机赋予一个所属主题z（0） ；
b） 统计工作：统计每个主题z下出现单词t的数量n（t | z），以及每个文档m下出现主题z中的词的数量n（z | m）；
c） 当前单词维度的主题采样：对于语料库中的每篇文档中的每個单词wi，根据公式（2.4）计算p（zi=k|z-i，d，wi），即排除当前词的主题分配，根据其他所有词的主题分配来估计当前词分配各个主题的概率。然后根据这个概率分布为当前词随机抽样获取一个新的主题分配z（a）；按照顺序对语料库中的每篇文档中的每个单词重复上面的步骤；
d） 重复迭代步骤（c），直至发现每个文档下主题分布θ和每个主题下单词的分布 收敛，算法停止，输出待估计的参数θ和Φ。
建立随机游走模型系统，以基于用户聚类和相似度传播的两阶段关系推荐用于潜在好友推荐。随机游走模型是一种衡量结构上下文（Structual-Context）相似性的算法，即它利用图的结构信息来计算上下文中各个对象之间的相似度：如果两个节点所连接的节点相似，那么这两个节点也相似。换句话说，节点间的相似性依赖于其邻居节点间的相似性，用户之间的相似度沿用用户的关注链接网络进行传播，这样就充分考虑了已关注的对象对用户交友过程的影响，进而通过这种影响与关联实现对相似信息的推荐。最后通过实验进行对比，验证该模型系统的有效性。
1） 基于主题内容相似度（Content-based）的K近邻关注对象推荐算法：对用户的微博进行主题建模，根据主题相似度进行排序后推荐。
2） 基于共同邻居（Common Neighbors）的关注对象推荐算法：仅考虑两个用户间的共同邻居数来度量相似度，排序后推荐。
3） 基于随机游走算法：不考虑相邻用户间的权重信息，直接进行随机游走更新相似度，排序后推荐。
3 系统实现功能
实现一个基于聚类与传播的微博用户关系提取与推荐的软件系统，系统能够完成以下功能。
对微博用户中现有关系群的挖掘功能：本系统通过分析微博网络中用户的特性以及用户之间的交互行为来深入解析链接关系，继而基于Kernighan-Lin算法完成交互行为的用户关系类型挖掘[6]。
对潜在关系的推荐功能：系统通过实现基于传递闭包的用户聚类方法、基于LDA模型的数据处理、以及通过随机游走模型的计算，完成相似度的传播与微博用户潜在关系的推荐。
4 结束语
本文在基于数据挖掘以及聚类方法的基础上，对微博用户关系进行挖掘，并通过挖掘的关系对用户进行个性化的推荐。通过此系统，不仅能对用户进行关系化的管理，而且还可以通过用户关系对用户进行推荐，使用户获得的被推荐内容更加有效，也提高用户获取信息以及新闻的效率。
参考文献
何黎，何跃，霍叶青.微博用户特征分析和核心用户挖掘[J].情报理论与实践，2011，11：121-125.
王晓光. 微博客用户行为特征与关系特征实证分析—以“新浪微博”为例[J].竞争情报，2010，54（14）：66-70.
张晨逸，孙建伶，丁轶群.基于MB-LDA模型的微博主题挖掘[J].计算机研究与发展. 2011（10）.
贾彩燕，陆汝钤.关联规则挖掘的取样误差量化模型和快速估计算法[J].计算机学报. 2006（04）.
Han JW，Kameber M，数据挖掘概念与技术（范明，孟小峰等译）[M].北京，机械工业出版社，2001：223～261.
胡可云，陆玉昌，石纯一. 基于概念格的分类和关联规则的集成挖掘方法[J]. 软件学报. 2000（11）.