一种基于知识学习对等社交网络文档检索方法

摘要

本发明公开了一种基于知识学习对等社交网络文档检索方法，它属于社交网络技术领域，主要解决对等社交网络中文档检索召回率低、转发开销大和性能不太理想的问题。其步骤为：A)节点建立兴趣索引和知识索引；B)节点通过兴趣索引和知识索引获取推荐节点转发查询消息。节点根据与它兴趣相同节点的兴趣向量关键词获得的文档数量建立兴趣索引，并且根据查询关键词获得的文档数量建立知识索引。在转发查询消息时，从兴趣索引和知识索引中获取推荐节点，消息转发给推荐节点。该方法在查询过程中学习知识，建立索引，并依据索引获得较好的查询，与现有的一些典型方法比较，取得了较高的召回率、较低的网络开销和较好的性能。

说明书

技术领域

本发明涉及到社交网络技术领域，将本发明提出的知识学习对等社交网络文档检 索方法(IESLP)用于对等社交网络服务的文档检索。

背景技术

社交网络应用越来越广泛，人们通过社交网络可以实现虚拟社区的社交活动，如 交友、聊天、互助、发布商业广告、进行资源分享和检索等。社交网络有多种类型，有基于客 户机/服务器模式的在线社交网络如FaceBook、人人网等；有基于蜂窝覆盖技术的移动社交 网络，如微信；也有基于P2P技术的对等社交网络。

P2P技术也称对等互联网技术，对等社交网络中的节点既是服务器也是客户端。在 使用非结构化P2P技术构建的社交网络中，检索文档是一个具有挑战性的课题。目前已有一 些方法可以用于对等社交网络的文档检索，如(1)随机宽度优先搜索技术(RBFS) [V.Kalogeraki,D.Gunopulos,D.Zeinalipour-yazti.ALocalSearchMechanismfor Peer-to-PeerNetworks[C].Proc.Ofthe11thACMConferenceonInformationand KnowledgeManagement(CIKM’02).NewYork:ACM,2002:300-307.]。(2)NeuroGrid技术 [JosephS.NeuroGrid:Semanticallyroutingqueriesinpeer-to-peer networks.ProceedingsoftheInternationalWorkshoponPeer-to-PeerComputing, Pisa,Italy,2002.]。(3)ESLP技术[L.Liu,N.Antonopoulos,S.Mackin,J.Xu,D.Russell, EfficientResourceDiscoveryinSelf-organizedUnstructuredPeer-to-Peer Networks,ConcurrencyandComputation:PracticeandExperience,Wiley,Vol23(2), February2009,pp.159-183.]等。RBFS方法在进行查询消息处理时，随机选择k个邻居节点 进行查询消息转发，收到消息的邻居节点再随机选择k个邻居转发查询消息，直到TTL耗尽， 这种检索文档的方法效率低、延时长。NeuroGrid技术在网络节点建立知识库，将在查询过 程中学习到的知识存储到知识库中，依知识库中的知识选择推荐节点进行消息转发，转发 节点数介于最小转发度和最大转发度之间。该方法比RBFS有了改进，召回率和网络性能都 有了提高。ESLP是一种新颖的对等社交网络搜索技术，它把人们交往过程中的人际关系理 论运用到文档检索中，模拟人的社交行为快速学习知识，自发形成社交圈，提高文档检索的 成功率，该方法在性能方面比NeuroGrid有了较大的改进。

现有的这些方法虽然可以实现对等社交网络的文档检索，但还存在一些缺陷。 RBFS的转发度是一个固定的常数；NeuroGrid的转发度介于最小转发度和最大转发度之间， 但不能自适应变化；ESLP的转发度虽然考虑目标节点与查询关键词的相关性自适应变化， 但没有考虑到目标节点文档数量与查询关键词的关系，并且也没有考虑到最小转发度和最 大转发度的自适应变化。社交网络中用户按兴趣形成社区，这些算法也没有显式的挖掘用 户的兴趣属性，从而通过兴趣向量相似性的比较自我学习，快速聚类成社区。现有的这些对 等社交网络文档检索技术方法在召回率、转发开销、网络性能等方面还有提升的空间。

发明内容

为了解决上述对等社交网络环境下文档检索召回率较低、网络开销大、性能不高 的缺陷，本发明提出了一种基于知识学习对等社交网络文档检索方法(简称IESLP)，网络节 点依据兴趣向量和查询关键词自我学习，自动形成社区聚类，以提高对等社交网络环境下 的文档检索召回率和综合性能。采用IESLP文档检索方法的对等社交网络中的每个节点的 作用是相等的，节点执行文档检索路由算法分两种情形：当该节点查询文档时产生并发送 初始查询消息，并根据网络中其它节点的反馈消息建立或更新兴趣索引和知识索引；当该 节点接收来自其它节点的查询消息时将统计本地与关键词匹配的文档数量，向查询节点发 送反馈消息，并选择自己的邻居节点转发查询消息。实现本发明的技术方案包括如下：

一种基于知识学习对等社交网络文档检索方法，包括如下步骤：

步骤A，节点建立兴趣索引和知识索引，包括：在文档检索过程中，节点从兴趣相同 的目标节点获得兴趣相似的知识存储在本地兴趣索引表中，同时依据查询关键词获得与查 询关键词匹配的知识存储在本地知识索引表中；

步骤B，节点通过本地兴趣索引和知识索引获取邻居节点作为推荐节点，并向推荐 节点转发查询消息，包括：节点需要转发其他节点发送过来的查询消息时，查询本地兴趣索 引表和知识索引表获取包含匹配查询关键词文档的邻居节点列表，依据匹配文档数量计算 列表中邻居节点的相关度系数，并结合最小转发度和最大转发度计算自适应转发度，然后 依据列表中邻居节点的自适应转发度选择推荐节点进行查询消息转发。

作为优选技术方案，所述步骤A建立兴趣索引和知识索引的过程如下：

步骤1)，当查询节点和目标节点兴趣相同时，查询节点依据目标节点反馈的兴趣 向量关键词及目标节点包含兴趣向量关键词的文档数量建立或更新本地兴趣索引表；

步骤2)，当查询节点和目标节点兴趣不同时，或者查询节点和目标节点兴趣相同 且目标节点兴趣向量关键词列表不包含查询关键词时，查询节点依据目标节点反馈的查询 关键词及目标节点包含查询关键词的文档数量建立或更新本地知识索引表；

步骤3)，目标节点依据查询关键词统计匹配文档数量。

作为优选技术方案，所述步骤B中将邻居节点作为推荐节点的判定方法为：若列表 中邻居节点的自适应转发度数值大于已选推荐节点的数量，则该邻居节点被选为推荐节 点。

作为优选技术方案，所述步骤B选择推荐节点进行查询消息转发的过程如下：

步骤1)当查询关键词包含在节点的兴趣向量中，则依据查询关键词从兴趣索引表 中选择节点添加到推荐节点列表中，当推荐列表中节点数量不足最大转发度数值，则依据 查询关键词从知识索引表中选择节点添加到推荐节点列表中，当推荐列表中节点数量不足 最小转发度数值，则从邻居列表中随机选择剩余节添加到推荐节点列表中；

步骤2)当查询主题关键词不在当前节点的兴趣向量中，则依据查询关键词从知识 索引表中选择节点添加到推荐节点列表中，当推荐列表中节点数量不足最小转发度数值， 则从邻居列表中随机选择剩余节添加到推荐节点列表中；

步骤3)当兴趣索引表和知识索引表中均没有符合查询要求的推荐节点时，扩大搜 索范围，增加最小转发度的数值；从当前节点的连接邻居节点中随机选择满足最新最小转 发度要求的节点作为推荐节点，添加到推荐节点列表中；

4)依次从推荐节点列表中选择节点转发查询消息，直到推荐节点列表为空。

作为优选技术方案，所述步骤B中计算相关度系数，具体为：

依据查询关键词从兴趣索引表或知识索引表中获取的第i个节点的相关度系数为 其中i＝1,2,…,n，n为依据查询关键词从兴趣索引表或知识索引表获取 的邻居节点的个数，等式右边项的分子m_i为第i个节点与查询关键词匹配的文档数量，分母 为依据查询关键词从兴趣索引表或知识索引表获取的节点的匹配文档数量和。

作为优选技术方案，所述步骤B中计算自适应转发度的值为：

第i个节点的自适应转发度k_i＝Round(r_i^λ(d_max-d_min))+d_min，其中i＝1,2,…,n，r_i为第i个节点的相关度系数，d_min为最小转发度，即最少被选择转发查询消息的邻居节点个 数，d_max为最大转发度，即最大被选择转发查询消息的节点个数，λ为指数调节因子，范围在0 ～1之间，Round函数为取整函数。

作为优选技术方案，所述最小转发度d_min＝2，最大转发度d_max＝3，指数调节因子λ ＝0.7。

作为优选技术方案，所述兴趣索引表和所述知识索引表均为结构相同的哈希表结 构，关键词构成哈希表的键，包含匹配查询关键词文档的邻居节点列表构成键的哈希值。

作为优选技术方案，所述列表中的元素包括两个域，一个域存储邻居节点信息，另 一个域存储该邻居节点包含对应的关键词匹配的文档数量；所述列表中包含邻居节点信息 的元素按文档数量值从大到小倒序排序，随机选择的节点默认匹配文档数量值为0，排在列 表末尾。与现有技术相比，本发明的有益效果：

本发明在对等社交网络节点构造兴趣索引和知识索引，在文档检索过程中，节点 将相同兴趣邻居节点信息按文档数量值从大到小存储到自己兴趣索引表中，并将按查询关 键词检索到的节点信息按文档数量从大到小存储到知识索引表中，转发查询消息时，节点 根据学习到知识获取文档数量较多邻居节点作为转发推荐节点。如此，提高了对等社交网 络文档检索的召回率和检索性能。

附图说明

图1是兴趣索引表和知识索引表结构图；

图2是建立兴趣索引和知识索引的实施例图；

图3是节点通过兴趣索引和知识索引获取推荐节点转发查询消息的实施例图；

图4是本发明技术方案IESLP与ESLP、NeuroGrid方法召回率的比较；

图5是本发明技术方案IESLP与ESLP、NeuroGrid方法转发开销的比较；

图6是本发明技术方案IESLP与ESLP、NeuroGrid方法每转发一个查询消息获得召 回率的比较。

具体实施方式

下面通过附图和具体实施例对本发明技术方案做更进一步的说明。

本发明的实现包括两个步骤A和B：

步骤A：节点建立兴趣索引和知识索引的步骤；

当节点(查询节点)查询文档时，生成查询消息并向邻居节点发送查询消息，查询 节点从兴趣相同的目标节点获得兴趣相似的知识存储在本地兴趣索引表中，同时依据查询 关键词获得所需知识存储在本地知识索引表中。建立兴趣索引和知识索引的过程如下：

1)当查询节点和目标节点兴趣相同时，查询节点依据目标节点反馈的兴趣向量关 键词及目标节点包含兴趣向量关键词的文档数量建立或更新本地兴趣索引表；

2)当查询节点和目标节点兴趣不同，或者查询节点和目标节点兴趣相同且目标节 点兴趣向量关键词列表不包含查询关键词时，查询节点依据目标节点反馈的查询关键词及 目标节点包含查询关键词的文档数量建立或更新本地知识索引表；

3)目标节点依据查询关键词统计匹配文档数量。

图1为本发明兴趣索引表和知识索引表的结构图。兴趣索引表和知识索引表均为 结构相同的哈希表结构，关键词构成哈希表的键，匹配查询关键词文档的邻居节点列表构 成键的哈希值；列表中的元素包括两个域，一个域存储邻居节点地址信息，另一个域存储该 邻居节点包含对应的关键词(键)匹配的文档数量。列表中包含邻居节点信息的元素按文档 数量值从大到小倒序排序，随机选择的节点默认匹配文档数量值为0，排在列表末尾。

图1中，索引表中左侧列Topic_n_i(其中i＝1,2,…,y，y为键的数量)为哈希表的 键，由兴趣关键词或查询关键词构成；右侧为键对应的哈希链表，链表节点中的Node_n_i(i ＝1,2,…,x)为查询节点的邻居节点，m_i(i＝1,2,…,x)为邻居节点包含关键词(键)的文档 数量，且m_i>m_i+1，x为哈希链表节点的数量。

图2是建立兴趣索引和知识索引的一个实施例。在图2中，节点A、B、D有相同兴趣， 兴趣向量(InterestVector)为节点C、E兴趣相同，它们的 兴趣向量为节点A对主题“iPhone”感兴趣，产生查询消 息，消息中封装主题“iPhone”，查询消息被A分别广播给邻居节点B、C、D。节点B、D和A的兴趣 相同，它们分别读取兴趣向量中的关键词C#、Java和Python，查找包含这三个关键词的本地 文档，并依据关键词统计文档数量。B和D将统计信息反馈给A，节点A将收到的信息写入兴趣 索引表(InterestIndex)中。包含C#主题的文档B有9篇，D有6篇，因此，在兴趣索引表中，对 应C#关键词的节点向量中B应排在D的前面。而包含Java关键词的文档B有3篇，D有8篇，故在 兴趣索引表中对应Java关键词的节点向量中D应排在B的前面。包含Python关键词的文档B 和D各6篇，A根据收到反馈消息的先后顺序存储信息。假设图2中，A先收到B的反馈，后收到D 的反馈，则B排在D的前面。

节点C和A的兴趣不同，但节点C本地文档中有A感兴趣的主题“iPhone”。节点C在本 地查找包含主题“iPhone”的文档，每找到一个满足要求的文档匹配次数增一。共找到8篇文 档，节点C成功查找次数为8。C将信息反馈给A，节点A将收到的信息以“iPhone”为关键词存 储到知识索引表(KnowledgeIndex)中。C将消息转发给邻居节点E。节点E在本地文档中查 找到包含主题“iPhone”的文档2篇，则节点E成功查找次数为2。此时，网络中成功查找次数 将增加10篇(8+2＝10)。E将信息反馈给A，在A的知识索引表中，以“iPhone”为关键词的节点 向量中C有8篇文档，节点A收E的反馈信息后，将插在C的后面，并建立到E节点的连接。

值得关注的是，与查询节点兴趣相同的目标节点的兴趣向量中尽管不包含查询主 题关键词，但是目标节点有可能存在查询节点感兴趣的文档，因此，目标节点除按兴趣查找 外，还应按查询关键词查找。图2中，节点B中有一篇文档包含“iPhone”，因此B节点的成功查 找次数为1，B节点反馈信息给A，A将收到的信息存储到知识索引中，插入到节点E的后面。

步骤B：节点通过本地兴趣索引和知识索引获取邻居节点作为推荐节点，并向推荐 节点转发查询消息的步骤。

当节点接收到其它节点发送过来的查询消息时，如果需要转发查询消息，则查询 本地兴趣索引表和知识索引表获取包含匹配查询关键词文档的邻居节点列表，依据匹配文 档数量计算列表中邻居节点的相关度系数，并结合最小转发度和最大转发度计算自适应转 发度，然后依据列表中邻居节点的自适应转发度选择推荐节点进行查询消息转发。若列表 中邻居节点的自适应转发度数值大于已选推荐节点的数量，则该邻居节点被选为推荐节 点。

依据匹配文档数量计算列表中邻居节点的相关度系数，具体为：

依据查询关键词从兴趣索引表或知识索引表中获取的第i个节点的相关度系数为 其中i＝1,2,…,n，等式右边项的分子m_i为第i个节点与查询关键词匹配 的文档数量，分母为依据查询关键词从兴趣索引表或知识索引表获取的节点的匹配 文档数量和，n为依据查询关键词从兴趣索引表或知识索引表获取的邻居节点的个数。

计算自适应转发度具体为：

第i个节点的自适应转发度k_i＝Round(r_i^λ(d_max-d_min))+d_min，其中i＝1,2,…,n，r_i为第i个节点的相关度系数，d_min为最小转发度，即最少被选择转发查询消息的邻居节点个 数，d_max为最大转发度，即最大被选择转发查询消息的节点个数，λ为指数调节因子，范围在0 ～1之间，Round函数为取整函数，n为依据查询关键词从兴趣索引表或知识索引表获取的邻 居节点的个数。。

所述选择推荐节点进行查询消息转发的过程如下：

1)当查询关键词包含在节点的兴趣向量中，则依据查询关键词从节点的本地兴趣 索引表中选择包含匹配查询关键词文档的邻居节点添加到推荐节点列表中；当推荐节点列 表中邻居节点数量不足最大转发度数值，则依据查询关键词从节点的本地知识索引表中选 择包含匹配查询关键词文档的邻居节点添加到推荐节点列表中，如果此时推荐节点列表中 邻居节点数量不足最小转发度数值，则从节点的邻居节点列表中随机选择剩余邻居节点添 加到推荐节点列表中，直到推荐节点列表中邻居节点数量达到最小转发度数值；

2)当查询主题关键词不在节点的兴趣向量中，则依据查询关键词直接从节点的本 地知识索引表中选择包含匹配查询关键词文档的邻居节点添加到推荐节点列表中，当推荐 节点列表中邻居节点数量不足最小转发度数值，则从节点的邻居节点列表中随机选择剩余 邻居节点添加到推荐节点列表中，直到推荐节点列表中邻居节点数量达到最小转发度数 值；

3)当节点的本地兴趣索引表和知识索引表中均没有符合查询要求的推荐节点时， 扩大搜索范围，增加最小转发度的数值。从节点的邻居节点中随机选择满足最新最小转发 度要求的邻居节点作为推荐节点，添加到推荐节点列表中；

4)依次从推荐节点列表中选择邻居节点转发查询消息，直到推荐节点列表为空。

图3是通过兴趣索引和知识索引获取推荐节点转发查询消息的实施例。目标节点A 有7连接节点B、C、D、E、F、G，H，其中A与B、C、D有共同的兴趣向量 E和F有共同的兴趣向量假设最小转发度为2，最大转发度为3，指数调节因子λ＝0.7。若查询主题关键词为 “Google”，则A从兴趣索引表中获得相关节点B、C、D，并按匹配文档数量倒排序，计算三个节 点实际转发度k_B＝3,k_C＝3,k_D＝2。开始时推荐节点数量为0小于k_B＝3，因此选择B，此时推 荐节点数量为1不大于k_C＝3，C被选择。选择C后推荐节点数量为2与k_D＝2相等，停止选择。因 为推荐节点数量没有达到最大转发度3，接着查询知识索引表，知识索引表中没有匹配查询 关键词“Google”的节点，并且推荐节点数量达到了最小转发度2，停止选择过程，最终B、C被 选为推荐节点。若查询主题关键词为“Baidu”，则A从兴趣索引表中获得推荐节点C，因为推 荐节点数量没有超过最大转发度，接着从知识索引表中获得推荐节点E，此时推荐节点数量 为2，达到最小转发度要求，停止选择过程，最终C、E被选为推荐节点。若查询主题关键词为 “Bing”，兴趣索引表和知识索引表都没有满足要求的节点，则随机选择G、H节点作为推荐节 点。若查询主题关键词为“iPhone”，它不在A的兴趣向量中，则从知识索引表中获得相关节 点F和E，实际转发度k_F＝3,k_E＝2，F和E均作为推荐节点被选择，转发节点数量达到最小转发 度，选择结束。查询消息被转发给推荐节点。

下面通过实验对本发明提出的检索方法的技术效果进行说明。

实验评价指标：平均召回率(AverageRecall)、转发开销(Numberof TransferringQueryMessage)、每个查询消息的召回率(RecallPerTransferring QueryMessage)。

平均召回率(AverageRecall)：查找成功的文档数量和网络中在线节点所有符合 查询要求文档数量的比，求平均值，该值为加权平均值，权值系数定义为每次查询获得召回 率占所有召回率数值总和的比率，范围在0和1之间。

转发开销(NumberofTransferringQueryMessage)：网络中查询消息的转发数 量的平均值，该值为加权平均值。

每个查询消息的召回率(RecallPerTransferringQueryMessage)：召回率与 转发开销的比率，该指标可以评价技术方案的性能。

仿真场景设置：

生成1000个网络节点，每个节点随机和另外4个节点保持双向连接，每个节点有八 条边连接到其它节点，初始网络是联通的。生成包含1024个主题关键词的向量。生成32个兴 趣向量，每个兴趣包含32个关键词，兴趣向量中的关键词从1024个主题关键词中随机选取。 从32个兴趣向量中随机选取一个指派给网络中的一个节点，重复该过程，直到网络中每个 节点都拥有一个兴趣向量。生成3000个文档，每个文档包含8个关键词，文档关键词从1024 个主题关键词中随机选取。将所有文档存储到网络节点。仿真天数为30天，每天仿真2000 次，仿真总次数60000次。每天(2000次)针对实验评价指标计算平均值。每次仿真随机选择 一个网络节点产生查询消息，查询消息转发次数TTL为3。

图4、图5、图6为仿真结果。由图4可以看出，本发明提出的技术方案IESLP平均召回 率要高于ESLP和NeuroGrid。由图5可以看出，本发明的IESLP的转发开销比ESLP低，比 NeuroGrid高。由图6可以看出，本发明的IESLP每个查询消息获得的召回率要高于ESLP和 NeuroGrid。

综上所述，本发明提出的IESLP技术方案性能要好于ESLP和NeuroGrid。

以上所述仅仅用于描述本发明的技术方案和具体实施例，并不用于限定本发明的 保护范围，应当理解，在不违背本发明实质内容和精神的前提下，本领域人员所作任何修 改、改进或等同替换等都将落入本发明的保护范围内。