基于关系的文本数据的可扩展社区发现

bcdfg

基于关系的文本数据的可扩展社区发现
论文标题：Scalable Community Discovery on Textual Data with Relations
作者：微软研究院网络搜索和挖掘小组
本文主要贡献：1.对关于大规模文本数据集的社区发现就可拓展性以及其对初始参数的敏感性做出了分析。2.定义了一个同时利用文本属性以及关系的可拓展社区发现方法。3.为了减少初始参数设定的影响，介绍了一个新的社区合并方法。4.对此方法进行评估比较，比其他方法提高了15%的精确度。（这是一篇08年的比较老的文章了，就介绍一下它的主要思想）

一.对LDA在处理大型文本数据时的分析
1.可拓展性2.对初始参数设定的敏感性
LDA（Latent Dirichlet Allocation 潜在狄利克雷分配）是一种文档主题生成模型，也称为一个三层贝叶斯概率模型，包含词、主题和文档三层结构。LDA是一种非监督机器学习技术，可以用来识别大规模文档集（document collection）或语料库（corpus）中潜藏的主题信息。
它采用了词袋的方法，这种方法将每一篇文档视为一个词频向量，从而将文本信息转化为了易于建模的数字信息。
当LDA应用于整个数据集，由于文档集合的规模巨大，LDA不能返回任何结果，并在初始化时就将内存耗尽。这种可扩展性限制使LDA无法应用在真实系统的主题挖掘中。
总之，为了更好地利用LDA主题聚类，因为LDA对主题的数目十分敏感所以在基础数据集上确定一个合适的主题数目是十分必要的。


二.本文提出的模型及思路：

社区模型：一个社区 Ci 是一个documents集合{di|i = 1, 2, ..., n, di =< Ai, Ri >}，Ai代表di 的属性，Ri是和di相连的关系。与Ci相关联的主题表示为Zi,每个Ci可能包括几个主要成员Ki。而Ci的附属成员则根据与Zi的联系紧密度排序，这样就使得社区Ci有了一个分层。
而整个模型包括核心发现，核心合并，附属成员拓展，分类这几个过程。

核心发现：在这一步中，解决方案开始从关系分析，找到核心，其特征是经常被引用的文档。每一个核心，记为基，将作为一个社区种子。这一步是有效地限制了分析范围，从而提高了解决方案可扩展性。
1.每个核心可能包括不止一个核心成员。2.每个核心成员可以与许多社区的附属关系成员相连。3.并不要求核心成员各自都紧密相连。

这个核心发现算法是基于先验算法（apriori algorithm）来生成的，但和先验算法有所不一样。(这个先验算法文章没有做具体介绍，我简单介绍一下，具体见http://baike.baidu.com/link?url= ... dkprjNHITY-xleD_uKK)。
Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
   1.依据支持度找出所有频繁项集（频度）支持度3%：意味着3%顾客同时购买牛奶和面包
   2.依据置信度产生关联规则（强度）   置信度40%：意味着购买牛奶的顾客40%也购买面包
如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。
首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次扫描。
核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。
核心发现算法与先验算法的区别：
1.先验算法是基于固定阈值的，而在这里是根据项目集的长度来确定。因为长的项目集倾向于有更小的支持率。
2.发现长项目集，Apriori算法生成的往往是其他项集的超集。在这种情况下，如果两个频繁项集的S1⊂S2，我们不保持S1。

核心合并：这一步骤中，核心根据他们的局部相似性被合并，以减少核心探测中使用参数的敏感性。在第一幅图第一步中中，K3和K4相连且相关。他们在这一步中合并成新的核心，新的核心包括 Df,Dh,Di。

两个核心的合并首先要求必须含有相同元素||Ki ∩ Kj ||> 0,接下来再对两个核心进行局部相似性计算。vij min 和 vij max分别代表属于核心Ki的所有文件在特征维度j上的最大值和最小值

对于一对核心Ki和Kj，我们先计算他们的交叉Rij，如果在每个维度上，Pi min都大鱼pj max，就没有算Rij的必要了。如果两个核心在特征空间上有重叠，即Rij = ∅，如果∃p ¯ ∈ p ¯ i ∪ p ¯ j,p ¯ ∈ Ki ∩ Kj，就将其合并。

而核心合并与其核心合并顺序是没有关系的。保持了很高的一致性。

附属成员拓展：内核构建后，关系被用来扩展核心形成初始社区。在这一步的子图的实心圆表示社区的边界。
在进行完核心合并之后剩下的都属于附属成员{di|di ∈ C − K} 。然后对在语料库中的di进行迭代判断，看其是否于核心相关联，相关联则加入社区。但在这个步骤中为避免环的出现而造成无限循环会限制迭代步数。

分类：分类的过程是在一个基于文本社区对每个成员进行从属关系的敲定。错误的关系则会被去掉。因为发现基于关系传播的社区可能会因为局部模糊的弱关系而产生错误的链接。所以在这个步骤中会利用属性分析来过滤掉社区的一些候选成员。
这个剪枝的过程可以看作是一种特殊的分类问题。给出一个社区 Ci = {di1, di2, ..., din}以及它的核心 Ki, 我们希望可以将 Ci两个部分 Ci  and Ci‘ so that Ci = Ci  ∪ Ci ’and Ki ⊂ Ci .

先使用LDA算法，LDA是用于数据降维（N）。Ci的中各个文件以及所有采样的文件将有一个特征向量来表示其在特征空间中的局部位置，表示式子=＜v1，v2，…，Vn >。每一个文档向量在分类过程中作为特征使用，以揭示文档之间的局部相似性。在降维之后，ki以及其他社区中的元素等数据将被用来进行SVM训练。然后用SVM来判断附属成员是否属于这个社区。

三.实验结果：
首先，测试算法的可扩展性，使用不同大小的数据集和过滤阈值。

质量测试 与其他算法的对比

参数敏感性测试

n‘是生成向量的维度

总结：提出了一个新的分级社区模型，解决方案克服了可扩展性问题，使用关系分析限制分析范围到一个小的子集。这篇文章是08年的文章，现在的社区发现方法也得到了进一步的发展，针对图中节点类型以及节点间关系的类型也有了更多进一步的研究。这篇论文的启发是可以在解决问题的过程中尝试多一些的方法，完善更多的细节将带来更多性能上的提高。