基于不确定语义的社交网用户行为关系推演系统及方法

摘要

本发明一种基于不确定语义的社交网用户行为关系推演系统及方法，属于数据挖掘和服务信息推荐领域，本发明基于用户地理位置相似性与用户活动相似性推演出用户是否具有行为关系；通过地理位置与活动相似性推断出与用户具有行为关系的用户，从而可以对未知用户行为做出准确预测，可以极大地提升信息推荐服务的质量；实验证明，本发明在未知本发明在未知用户行为预测的准确性上优于现在已有的行为预测方法，具有很高的实际应用价值，所以如果能够得到推广，将能极大地提高用户行为预测的准确性，对企事业明确目标客户人群，做出正确决策具有显著的意义。

说明书

技术领域

本发明属于数据挖掘和服务信息推荐领域，具体涉及一种基于不确定语义的社交网用户 行为关系推演系统及方法。

背景技术

在线社交网络成为了使用户之间相互联系，分享各种信息的重要平台，如Twitter、 Facebook、Instagram等知名社交网络。其中，由于Twitter具有内容简洁性及强大的用户 实时交互性，已经成为当今国外主流社交媒体。

Tweet(推特)中的“@”字符表示“提及”，意思是“向某人说”，不难看出，“@”操 作是揭示用户间紧密关系的有效途径之一。但查阅资料后得知，目前学术界和工业界对社交 关系研究，一方面，仅局限于“关注/被关注”关系，或者是“Retweet关系”，即通过计算 用户相似度、分析网络拓扑结构、度量用户交互性等手段来分析静态的社交网用户关系及其 强度，缺乏对“@”关系的深入探讨，但事实是，在体现用户紧密程度方面，“@”关系比“关 注/被关注”关系更强，因为只有关注了某个用户，才能去“@”该用户，因此目前社交网关 系研究遗漏了对更紧密相似语义行为关系的挖掘。另一方面，尽管有些研究工作提出了与位 置有关的用户关系推断，但只研究了“关注”和“推送”这种简单的显式连接关系，对用户 间是否具有更复杂的隐式语义连接，比如通过“活动”所体现出来的餐饮、旅行、购物等语 义关系尚未作出探讨，事实上，利用位置所体现的语义信息能更准确地找到相似用户，但这 一点被忽略。综上所述，社交网用户行为关系的研究尚不够深入和完善，行为关系挖掘技术 也不全面，这些不足最终导致信息推荐服务对象不够准确。基于此，本专利系统深入探讨了 如何通过“提及”关系来更有效地挖掘用户间的相似语义行为关系，旨在进一步完善行为关 系发现技术，以有助于商业服务推荐、广告精准投放等，因此本专利具有重要理论研究价值 和实际应用意义。

发明内容

针对现有技术的缺点，本发明提出一种基于不确定语义的社交网用户行为关系推演系统 及方法，以达到提高用户行为预测的准确性的目的。

一种基于不确定语义的社交网用户行为关系推演系统，包括不确定词条活动库构建模块、 未知地理位置推演模块、推特文本词条提取模块、推特文本词条表达活动概率值推演模块、 用户对活动相似性概率矩阵计算模块、用户对物理位置相似度矩阵计算模块、用户对语义行 为关系矩阵推演模块和用户对语义行为关系聚类推演模块；其中，

不确定词条活动库构建模块：用于获取第三方应用中的活动类别及各活动类别中所包含 的不确定词条，根据每个不确定词条在不同活动类别中的词频和每个不确定词条的逆向文本 频率，获得每个不确定词条在不同活动类别中的重要性权重值，并根据设定的两个重要性权 重阈值和每个不确定词条在不同活动类别中的重要性权重值，对每个不确定词条进行分类， 再根据分类情况计算词条属于各活动类别的概率值，最终根据获得的活动类别、各活动类别 中所包含的不确定词条、各不确定词条的类型和各不确定词条所属活动类别的概率值，构建 不确定词条活动库；

未知地理位置推演模块：用于获取社交网中提及目标用户的其他用户的已知物理位置经 度和纬度，计算其他用户的已知物理位置方差，并根据上述方差，采用最大似然估计法获得 目标用户的未知物理位置，发送至用户对物理位置相似度矩阵计算模块中；

推特文本词条提取模块：用于通过分词工具将社交网中提及目标用户的其他用户所发文 本进行词条提取，并发送至推特文本词条表达活动概率值推演模块中；

推特文本词条表达活动概率值推演模块：用于在不确定词条活动库中对所提取的词条进 行匹配，并确定词条在不同活动类别中的词条类型和概率值，并获得所提取的词条所属活动 类别的所有组合情况，并计算各活动类别中每种词条组合情况的概率值；

用户对活动相似性概率矩阵计算模块：用于采用杰卡德相似系数计算获得任意用户对所 产生的各类活动的相似度和相似概率，并将大于设定阈值的相似度所对应的活动相似概率进 行求和，获得该用户对活动相似概率，进而获得所有目标用户对活动相似概率，并构建用户 对相似行为活动概率下三角矩阵；

用户对物理位置相似度矩阵计算模块：用于将目标用户的地理经度和纬度转换成平面距 离，根据平面距离计算任意用户对间物理位置的相似度，并获取用户对间物理位置的相似度 大于设定阈值的相似度值，并将上述相似度值保存至用户对物理位置相似度下三角矩阵中， 完成用户对物理位置相似度下三角矩阵的构建；

用户对语义行为关系矩阵推演模块：用于根据构建完成的用户对相似行为活动概率下三 角矩阵和用户对物理位置相似度下三角矩阵，获取目标用户对在用户对相似行为活动概率下 三角矩阵和用户对物理位置相似度下三角矩阵中对应位置的两数值，并将两数值相乘，获得 目标用户对用户对语义行为关系值，并构建用户对用户对语义行为关系矩阵；

用户对语义行为关系聚类推演模块；用于根据用户对用户对语义行为关系矩阵构建连通 图，即将用户作为连通图的节点，用户对间的用户对语义行为关系值作为连通图节点之间的 连通边，删除用户对语义行为关系值小于设定阈值的连通边，将剩余连通边构成的每个连通 子图作为一组用户对语义行为关系，完成社交网用户语义行为关系的推演。

采用基于不确定语义的社交网用户行为关系推演系统进行的推演方法，包括以下步骤：

步骤1、构建不确定词条活动库，具体步骤如下：

步骤1-1、获取第三方应用中的活动类别及各活动类别中所包含的不确定词条；

步骤1-2、根据每个不确定词条在不同活动类别中的词频和每个不确定词条的逆向文本频 率，获得每个不确定词条在不同活动类别中的重要性权重值；

步骤1-3、设置不确定词条在不同活动类别中的两个重要性权重阈值，根据两个重要性 权重阈值和每个不确定词条在不同活动类别中的重要性权重值，对每个不确定词条进行分类；

具体如下：

若不确定词条的重要性权重值同时小于两个重要性权重阈值，则该不确定词条为活动不 相关词条；

若不确定词条的重要性权重值同时大于两个重要性权重阈值，则该不确定词条为活动相 关词条；

若不确定词条的重要性权重值介于两个重要性权重阈值之间，则该不确定词条为活动半 相关词条；

步骤1-4、根据活动半相关词条在某类活动类别中的权重值和该类活动类别中全部词条 中权重值最大值，确定活动半相关词条属于该活动类别的概率值；

步骤1-5、根据获得的活动类别、各活动类别中所包含的不确定词条、各不确定词条的 类型和各不确定词条所属活动类别的概率值，构建不确定词条活动库；

步骤2、采用未知地理位置推演模块获取社交网中提及目标用户的其他用户的已知物理 位置经度和纬度，计算其他用户的已知物理位置方差，并根据上述方差，采用最大似然估计 法获得目标用户的未知物理位置；

步骤3、采用推特文本词条提取模块，通过分词工具将社交网中提及目标用户的其他用 户所发文本进行词条提取；

步骤4、采用推特文本词条表达活动概率值推演模块，推演出社交网中用户所提取的词 条所属活动类别集合，具体如下：

步骤4-1、在不确定词条活动库中对所提取的词条进行匹配，并确定词条在不同活动类别 中的词条类型和概率值；

步骤4-2、获得所提取的词条所属活动类别的所有组合情况，并计算各活动类别中每种词 条组合情况的概率值；

步骤5、采用用户对活动相似性概率矩阵计算模块，获得社交网中任意用户对产生相似 活动的概率，并构建用户对相似行为活动概率下三角矩阵，具体如下：

步骤5-1、采用杰卡德相似系数计算获得任意用户对所产生的各类活动的相似度和相似 概率，并将大于设定阈值的相似度所对应的活动相似概率进行求和，获得该用户对活动相似 概率；

步骤5-2、反复执行步骤5-1，直至获得所有目标用户对活动相似概率，并构建用户对相 似行为活动概率下三角矩阵；

步骤6、采用用户对物理位置相似度矩阵计算模块，获得社交网中任意用户对物理位置 相似度，并构建用户对物理位置相似度下三角矩阵，具体如下：

步骤6-1、将目标用户的地理经度和纬度转换成平面距离，根据平面距离计算任意用户 对间物理位置的相似度；

步骤6-2、获取用户对间物理位置的相似度大于设定阈值的相似度值，并将上述相似度 值保存至用户对物理位置相似度下三角矩阵中，完成用户对物理位置相似度下三角矩阵的构 建；

步骤7、采用UPSBR关系矩阵推演模块，根据构建完成的用户对相似行为活动概率下三 角矩阵和用户对物理位置相似度下三角矩阵，获取目标用户对在用户对相似行为活动概率下 三角矩阵和用户对物理位置相似度下三角矩阵中对应位置的两数值，并将两数值相乘，获得 目标用户对用户对语义行为关系值，并构建用户对用户对语义行为关系矩阵；

步骤8、采用用户对语义行为关系聚类推演模块构建连通图，即将用户作为连通图的节 点，用户对间的用户对语义行为关系值作为连通图节点之间的连通边，删除用户对语义行为 关系值小于设定阈值的连通边，将剩余连通边构成的每个连通子图作为一组用户对语义行为 关系，完成社交网用户语义行为关系的推演。

步骤1-3所述的设置不确定词条在不同活动类别中的两个重要性权重阈值，具体步骤如 下：

步骤1-3-1、获得活动相关词条判断阈值，计算公式如下：

θ_r＝αθ_max     (1)

其中，θ_r为活动相关词条的判断阈值，θ_max为某类活动中词条集合中权重排序第一的词 条权重，α为一个调节参数，取值范围为0.3～0.4；

步骤1-3-2、删除权重值大于活动相关词条判断阈值的不确定词条，将剩余的不确定词 条按照由大到小进行排序；

步骤1-3-3、在排序后的词条中，寻找相邻词条间权重值差值最大的位置，以该位置处排 序靠前的词条权重值作为活动半相关词条判断阈值；

步骤1-3-4、将获得的活动相关词条判断阈值和活动半相关词条判断阈值作为在该类活 动中的两个重要性权重阈值。

步骤5-1所述的设定阈值取值范围为0.4～0.6。

步骤6-2所述的设定阈值取值范围为0.5～0.6。

步骤8所述的设定阈值取值范围为0.4～0.5。

本发明优点：

本发明一种基于不确定语义的社交网用户行为关系推演系统及方法，基于用户地理位置 相似性与用户活动相似性推演出用户是否具有行为关系；通过地理位置与活动相似性推断出 与用户具有行为关系的用户，从而可以对未知用户行为做出准确预测，可以极大地提升信息 推荐服务的质量；实验证明，本发明在未知本发明在未知用户行为预测的准确性上优于现在 已有的行为预测方法，具有很高的实际应用价值，所以如果能够得到推广，将能极大地提高 用户行为预测的准确性，对企事业明确目标客户人群，做出正确决策具有显著的意义。

附图说明

图1是本发明一种实施例的基于不确定语义的社交网用户行为关系推演系统结构框图；

图2是本发明一种实施例的基于不确定语义的社交网用户行为关系推演方法流程图；

图3是本发明一种实施例的一对用户间UPSBR关系推演示意图；

图4是本发明一种实施例的推演一个用户对间具有UPSBR关系的样例示意图；

图5为本发明一种实施例的对应一个UPSBR关系矩阵的连通图，其中，图(a)为UPSBR 关系矩阵M所对应的最大树连通图，图(b)为为UPSBR关系矩阵M对应生成的连通子图；

图6为本发明一种实施例的物理位置推演测试结果图，其中，图(a)为不同ED段的物 理位置推演测试结果图，图(b)为“@-次数”对不同ED段的物理位置推演的影响结果图；

图7为本发明一种实施例的UPSBR推演测试结果图；

图8为本发明一种实施例的UGSBR关系聚类精度测试结果图，其中，图(a)为NMI测试 结果图；图(b)为F1-Measure测试结果图，

图9为本发明一种实施例的UGSBR关系聚类参数敏感性测试结果图，其中，图(a)为参 数θ_sim敏感测试结果图；图(b)为参数α敏感测试结果图，

具体实施方式

下面结合附图对本发明一种实施例做进一步说明。

针对目前信息推荐服务对象不够准确，本发明以用户Tweets(推特)内容中“@”关系 为核心研究如何有效挖掘用户间的相似行为关系，首先，提出了一种“语义行为关系”概念， 简称SBR(Semantic Behavior Relationship)，SBR体现了在相似地理位置进行相似活动的 语义行为；进一步，将SBR关系又分为“用户对语义行为关系”(User Pair Semantic Behavior  Relationship，简称UPSBR)和“用户群语义行为关系”(User Group Semantic Behavior  Relationship-UGSBR)，其中，UPSBR体现的是一对用户间的行为关系，UGSBR体现的是用 户群之间的行为关系。其次，本发明还提出了一种基于不确定活动词条的社交网用户语义行 为关系推演系统，即SBR-IS(Semantic Behavior Relationship-Inferring System)， 该系统设置于计算机中，如图1所示，包括八个模块：不确定词条活动库构建模块、未知地 理位置推演模块、推特(Tweets)文本词条提取模块、推特(Tweets)文本词条表达活动概率 值推演模块、用户对活动相似性概率矩阵计算模块、用户对物理位置相似度矩阵计算模块、 用户对语义行为(UPSBR)关系矩阵推演模块和用户对语义行为(UPSBR)关系聚类推演模块； 其中，

不确定词条活动库构建模块：用于获取第三方应用中的活动类别及各活动类别中所包含 的不确定词条，根据每个不确定词条在不同活动类别中的词频和每个不确定词条的逆向文本 频率，获得每个不确定词条在不同活动类别中的重要性权重值，并根据设定的两个重要性权 重阈值和每个不确定词条在不同活动类别中的重要性权重值，对每个不确定词条进行分类， 再根据分类情况计算词条属于各活动类别的概率值，最终根据获得的活动类别、各活动类别 中所包含的不确定词条、各不确定词条的类型和各不确定词条所属活动类别的概率值，构建 不确定词条活动库；

本发明实施例中，不确定词条活动库构建模块根据第三方应用Foursquare(四方)的活 动类别和维基百科词条分类构建社交网用户活动词条库，然后抽取出每类活动包含的词条， 并通过TF·IDF(TF：统计词条的词频，IDF：词条的逆向文本频率)方法给出词条表达活 动的重要性权值，再将词条划分为活动相关词条、活动半相关词条和活动不相关词条，并赋 予词条表达活动的概率值；

未知地理位置推演模块：用于获取社交网中提及目标用户的其他用户的已知物理位置经 度和纬度，计算其他用户的已知物理位置方差，并根据上述方差，采用最大似然估计法获得 目标用户的未知物理位置，发送至用户对物理位置相似度矩阵计算模块中；

本发明实施例中，未知地理位置推演模块用于对“@关系”进行概率产生可能性的最大化 计算，并通过“@关系”中“提及者”发布Tweets的若干已知历史位置信息计算出“提及者” 历史位置方差，然后根据“提及者”历史位置方差和当前所在已知地理位置用最大似然估计 法推演出“@”关系中“被提及者”的未知地理位置；

推特文本词条提取模块：用于通过分词工具将社交网中提及目标用户的其他用户所发文 本进行词条提取，并发送至推特文本词条表达活动概率值推演模块中；

本发明实施例中，推特文本词条提取模块用于根据Lucene分词工具对“@关系”中“提 及者”所发Tweets文本进行文本解析，经过去停用词等操作提取出文本包含的词条；

推特文本词条表达活动概率值推演模块：用于在不确定词条活动库中对所提取的词条进 行匹配，并确定词条在不同活动类别中的词条类型和概率值，并获得所提取的词条所属活动 类别的所有组合情况，并计算各活动类别中每种词条组合情况的概率值；

本发明实施例中，推特文本词条表达活动概率值推演模块用于将所提Tweets文本词条与 不确定词条活动库中的词条进行匹配，然后列出匹配上的Tweets文本词条活动表达集合的所 有可能存在形式，并根据对应的不确定词条活动库中词条被赋予的概率值推演出每种Tweets 文本词条活动表达集合形式下所具有的概率值；

用户对活动相似性概率矩阵计算模块：用于采用杰卡德相似系数计算获得任意用户对所 产生的各类活动的相似度和相似概率，并将大于设定阈值的相似度所对应的活动相似概率进 行求和，获得该用户对活动相似概率，进而获得所有目标用户对活动相似概率，并构建用户 对相似行为活动概率下三角矩阵；

本发明实施例中，用户对活动相似性概率矩阵计算模块用于根据待推演的每对用户间的 活动相似度及这对用户各自的词条表达活动概率值集合，计算出对应的用户对的活动相似性 概率，并将每对概率值作为活动相似性矩阵元素构建活动相似性概率矩阵A。

用户对物理位置相似度矩阵计算模块：用于将目标用户的地理经度和纬度转换成平面距 离，根据平面距离计算任意用户对间物理位置的相似度，并获取用户对间物理位置的相似度 大于设定阈值的相似度值，并将上述相似度值保存至用户对物理位置相似度下三角矩阵中， 完成用户对物理位置相似度下三角矩阵的构建；

本发明实施例中，用户对物理位置相似度矩阵计算模块用于根据欧氏距离计算出待推演 的每对用户间的物理位置相似度，并将每对相似度值作为矩阵元素构建物理位置相似度矩阵 L。

用户对语义行为关系矩阵推演模块：用于根据构建完成的用户对相似行为活动概率下三 角矩阵和用户对物理位置相似度下三角矩阵，获取目标用户对在用户对相似行为活动概率下 三角矩阵和用户对物理位置相似度下三角矩阵中对应位置的两数值，并将两数值相乘，获得 目标用户对用户对语义行为关系值，并构建用户对用户对语义行为关系矩阵；

本发明实施例中，UPSBR关系矩阵推演模块用于根据待推演的每对用户间的用户对活动 相似性概率矩阵值和用户对物理位置相似度矩阵值计算出每对用户是否具有UPSBR关系， 如果二者的活动相似性概率值和物理位置相似度值均大于预先设定的阈值范围，那么可以推 出二者具有UPSBR关系，并将活动相似性概率值和物理位置相似度值的乘积作为矩阵元素 以生成UPSBR关系矩阵M。

用户对语义行为关系聚类推演模块；用于根据用户对用户对语义行为关系矩阵构建连通 图，即将用户作为连通图的节点，用户对间的用户对语义行为关系值作为连通图节点之间的 连通边，删除用户对语义行为关系值小于设定阈值的连通边，将剩余连通边构成的每个连通 子图作为一组用户对语义行为关系，完成社交网用户语义行为关系的推演。

本发明实施例中，UGSBR关系聚类推演模块用于根据最大树聚类技术对生成的UPSBR 关系矩阵M进行关系聚类，如果M对应的连通图的最小生成树中一些边的权值小于预先给 定阈值，就将这些边剪掉，于是剩余连通子图便是UGSBR关系聚类结果，而每个类则表示 一组具有UGSBR关系的用户群体。

采用基于不确定语义的社交网用户行为关系推演系统进行的推演方法，本发明实施例中 (如图4所示)，以用户u₂和用户u₅为例，判断二者是否具有UPSBR关系；然后，再判断用 户u₁、用户u₂、用户u₃、用户u₄和用户u₅间是否具有UGSBR关系，方法流程图如图2所 示，包括以下步骤：

步骤1、构建不确定词条活动库，具体步骤如下：

步骤1-1、获取第三方应用中的活动类别及各活动类别中所包含的不确定词条；

本发明实施例中，借鉴第三方应用FourSquare的活动分类信息并根据实际需要，将活动 分为以下六类：

(1)Food(美食)：主要包括各种餐厅，如中国餐馆等。

(2)Shopping(购物)：主要有商店等。

(3)Travel(旅行)：主要包括著名旅游景点。

(4)Art(艺术)：主要包括一些博物馆等。

(5)Entertainment(娱乐)：主要包括游泳馆、足球场等。

(6)Business(商业)：主要包括开会地点等。

每类活动下存储表示该类活动的词条，由于活动分类词条与社交应用本身紧密相关，即 存在一定语义偏斜，因此本实施例中在构建活动分类词条集合时，根据类别语义通过维基百 科增加了部分相关词条，以改善语义倾斜问题。

步骤1-2、根据每个不确定词条在不同活动类别中的词频和每个不确定词条的逆向文本频 率，获得每个不确定词条在不同活动类别中的重要性权重值；

步骤1-2-1、统计每个不确定词条在不同活动类别中的词频

计算公式如下：

$\mathrm{TF}=\frac{f_{\mathrm{ij}}}{\mathrm{\Sigma f}}---\left(2\right)$

其中，TF表示词条t_i在第j类活动中出现的词频，f_ij表示词条t_i在第j类活动A_j中出 现的次数，∑f表示在所有活动中包含的词条总数；

步骤1-2-2、统计每个不确定词条的逆向文本频率

计算公式如下：

$\mathrm{IDF}=\log \frac{\left|A\right|}{{|A}_i|}---\left(3\right)$

其中，IDF表示词条t_i的逆向文本频率，|A|表示全部活动个数，|A_i|表示包含词条t_i的 活动个数；

步骤1-2-3、获得词条的重要性权重。

词条t_i在多少个活动中出现过，对t_i与某个活动的相关性大小有重要影响：若t_i在越多的 活动中出现，则t_i与某个活动能够的相关性越低；反之，若t_i在越少的活动中出现，则t_i与活 动的相关性越高；因此，用TF·IDF方法计算词条表达活动的重要性权重，

计算公式如下：

w＝TF·IDF     (4)

其中，w表示词条t_i在活动A_j中的重要性权重，并将公式(2)和(3)代入；

步骤1-3、设置不确定词条在不同活动类别中的两个重要性权重阈值，根据两个重要性 权重阈值和每个不确定词条在不同活动类别中的重要性权重值，对每个不确定词条进行分类；

所述的设置不确定词条在不同活动类别中的两个重要性权重阈值，具体步骤如下：

步骤1-3-1、获得活动相关词条判断阈值θ_r，计算公式如下：

θ_r＝αθ_max     (1)

其中，θ_r为活动相关词条的判断阈值，θ_max为某类活动中词条集合中权重排序第一的词条 权重，α为一个调节参数，通过实验确定取值为0.3；

步骤1-3-2、删除权重值大于活动相关词条判断阈值的不确定词条，将剩余的不确定词 条按照由大到小进行排序；

步骤1-3-3、在排序后的词条中，寻找相邻词条间权重值差值最大的位置l，以该位置处 排序靠前的词条权重值作为活动半相关词条判断阈值θ_u；

相邻词条间权重值差值最大的位置l计算公式如下：

w[l]-w[l+1]＝max_1≤v≤z-1{w[v]-w[v+1]}     (5)

其中，w[v]表示排在第v位词条的权重，w[v+1]表示排在第v+1位词条的权重，z表示 除r_t外的词条个数；

步骤1-3-4、将获得的活动相关词条判断阈值θ_r和活动半相关词条判断阈值θ_u作为在该 类活动中的两个重要性权重阈值。

分类具体如下：

若不确定词条的重要性权重值同时小于两个重要性权重阈值，则该不确定词条为活动不 相关词条u_t；

若不确定词条的重要性权重值同时大于两个重要性权重阈值，则该不确定词条为活动相 关词条r_t；

若不确定词条的重要性权重值介于两个重要性权重阈值之间，则该不确定词条为活动半 相关词条s_t；

步骤1-4、根据活动半相关词条在某类活动类别中的权重值和该类活动类别中全部词条 中权重值最大值，确定活动半相关词条属于该活动类别的概率值；

本发明实施例中，词条t_i是活动相关词条r_t时，表达活动A_j的概率为1，词条t_i是活动 不相关词条u_t时，表达活动A_j的概率为0，词条t_i是活动半相关词条s_t时，计算其表达活动 A_j的概率；计算公式如下：

$p\left(t_i^{s_t}\right)=w\left(t_i\right)/w_{\max }---\left(6\right)$

其中，表示词条t_i为r_t时表达活动A_j的概率，w(t_i)表示词条t_i的权重，w_max表示 全部词条的最大权重值，于是

步骤1-5、根据获得的活动类别、各活动类别中所包含的不确定词条、各不确定词条的 类型和各不确定词条所属活动类别的概率值，构建不确定词条活动库；

本发明实施例中，六类活动及其包含的词条如表1所示(仅列出部分词条)。表中词条后 括号中的“字母-数字”表明该词条是活动相关(用字母r表示)，还是活动半相关(用字母s 表示)。注意，此处活动不相关词条由于对活动表达无关，因此被删去；数字则表示该词条表 达所属活动的权重值。

表1

步骤2、采用未知地理位置推演模块获取社交网中提及目标用户的其他用户的已知物理 位置经度和纬度，计算其他用户的已知物理位置方差，并根据上述方差，采用最大似然估计 法获得目标用户的未知物理位置；

步骤2-1、计算“@”用户u_i的第1个用户的物理位置方差具体步骤如下：

根据图3，此处假定有m个用户在Tweets中“@”了u_i，即u_i是“被提及者”，m个用户 是“提及者”，“@”u_i的第r个“提及者”用表示，每个“提及者”到“被提及者”的“@ 关系”用表示；

步骤2-1-1、提取出用户在一周内发布的所有Tweets文本；

本发明实施例中Tweets文本需要满足以下3个条件：

1)从Tweet中能获取到“@u_i”的第1个用户的物理位置，即的和分别表示的已知物理位置经度和纬度；

2)Tweet中含有“@”其他用户的信息，即存在边；k₁表示一周内@其 他用户次数

3)从Tweet中能获取“@”其他用户时所处物理位置；

本发明实施例中，存在u₁、u₂、u₃、u₄和u₅五位用户，其中u₁和u₄分别“@”了u₂， u₃“@”了u₅；u₁、u₃和u₄的语义活动和物理位置已知，且他们在一周内“@”其他用户 的Tweets文本和发布位置也已知；u₂和u₅的语义活动和物理位置均未知；

由图4可知，本发明实施例中，“@”u₂的第一个“提及者”(即u₁)的已知物理位 置的经度纬度一周内“@”其他三个用户时已知物 理位置的经度和纬度分别为$X_1^{w_1}=41,{Y_1}^{w_1}=-73;{X_1^{w_2}=41,Y_1}^{w_2}=-74;X_1^{w_3}=40,{Y_1}^{w_3}=-73.$

步骤2-1-2、计算用户的位置方差

计算公式如下：

${\sigma }_1^{i^2}=\underset{w=1}{\overset{k_1}{\Sigma }}\frac{{(X_1^i-X_1^w)}^2+{(Y_1^i-Y_1^w)}^2}{{2k}_1}---\left(7\right)$

其中，表示“提及者”的物理位置方差，和Y₁^w分别表示一周内“@”第w (1≤w≤k₁)个用户时已知的物理位置经度和纬度；

根据公式(7)可得“提及者”的物理位置方差为：

${\sigma }_1^{i^2}=\frac{{(40-41)}^2+{(-74-(-73))}^2+{(40-41)}^2+{(-74-(-74))}^2+{(40-40)}^2+{(-74-(-73))}^2}{2\times 3}=\frac{2}{3}$

类似地，可计算出“@”u₂的其他位置已知的“提及者”的未知物理位置方差。假定的已知经度$X_2^2=41,$纬度$Y_2^2=-75,$并${\sigma }_2^{2^2}=5/6;$

步骤2-1-3：重复步骤1-2-1和1-2-2，计算出“@”u_i的剩余m-1个“提及者”的位置方 差到

步骤2-2、利用最大似然估计模型对“@”了某个用户(假定u_i)的全部“@关系”建立 概率产生的最大化计算公式，

计算公式如下：

$p\left({@}_r^i\right)=\underset{r=1}{\overset{m}{\Pi }}\frac{1}{{2\mathrm{\pi \sigma }}_r^{i^2}}{e}^{\frac{{(X_{u_i}^{*}-X_r^i)}^2+{(Y_{u_i}^{*}-Y_r^i)}^2}{-2_r^{i^2}}}---\left(8\right)$

其中，表示产生边的概率；表示所处物理位置的方差；和分别 表示u_i未知物理位置的经度和纬度；和则分别表示已知物理位置的经度和纬度。

本发明实施例中，公式(8)中包含着三个未知变量和其中可以通过对“提 及者”的已知历史位置数据计算求出，于是对未知变量和的概率计算就演变为当它 们分别取什么值时可以让值最大，此时和所取的值就是“被提及者”u_i未知位 置的推演结果，换句话说，值越大，和就越接近实际情况。

步骤2-3、推演“被提及者”u_i未知物理位置的精度和纬度；

计算公式如下：

$\left(\begin{array}{cc}{X}_{u_i}^{*}=\frac{\underset{r=1}{\overset{m}{\Sigma }}\frac{X_r^i}{{\sigma }_r^{i^2}}}{\underset{r=1}{\overset{m}{\Sigma }}\frac{1}{{\sigma }_r^{i^2}}}& Y_{u_i}^{*}=\frac{\underset{r=1}{\overset{m}{\Sigma }}\frac{Y_r^i}{{\sigma }_r^{i^2}}}{\underset{r=1}{\overset{m}{\Sigma }}\frac{1}{{\sigma }_r^{i^2}}}\end{array}\right)---\left(9\right)$

其中，和分别为u_i未知物理位置的经度和纬度，和分别为已知物理位置 的经度和纬度，为的已求得的物理位置方差。

本发明实施例中，根据公式(9)可计算出“被提及者”u_i的未知物理位置的经度和纬度 分别为

$X_{u_2}^{*}=\frac{40/(2/3)+41(5/6)}{1/(2/3)+1/(5/6)}=34.88$

$Y_{u_2}^{*}=\frac{(-74)/(2/3)+(-75)/(5/6)}{1/(2/3)+1(5/6)}=74.44$

本发明实施例中，u₅的经、纬度计算结果为(41.54，-73.82)。

步骤2-4、重复步骤2-1到步骤2-3，求出所有其他用户具有“@关系”的“被提及者” 的未知物理位置；

步骤3、采用推特文本词条提取模块，通过分词工具将社交网中提及目标用户的其他用 户所发文本进行词条提取；

本发明实施例中，采用计算机中的Tweets文本词条提取模块，利用Lucene分词工具， 通过去停用词等操作对所有@关系”中的“提及者”所发Tweets文本进行词条提取。

本发明实施例中，从“@”u₂的所有Tweets文本中提取的不确定活动词条集合如下：

$A_{u_2}=(\mathrm{mall},\mathrm{KFC},\mathrm{sales},\mathrm{clothes},\mathrm{spend})$

从“@”u₅的所有Tweets文本中提取的不确定活动词条集合如下：

$A_{u_5}=(\mathrm{mall},\mathrm{KFC},\mathrm{clothes})$

经过与词条库匹配可得mall、KFC和sales为活动相关词条，clothes和spend为活动 半相关词条，且w(mall)＝1，w(KFC)＝0.95，w(sales)＝0.9，w(clothes)＝0.8，w(spend)＝0.6， w_max＝1。根据公式(6)可算出，活动半相关词条clothes和spend的相关概率分别为：

p(clothes)＝w(clothes)/w_max＝0.8；p(spend)＝w(spend)/w_max＝0.6；

将活动相关词条和活动半相关词条加入到描述用户活动的词条集合中。

步骤4、采用推特文本词条表达活动概率值推演模块，推演出社交网中用户所提取的词 条所属活动类别集合，具体如下：

步骤4-1、在不确定词条活动库中对所提取的词条进行匹配，并确定词条在不同活动类别 中的词条类型和概率值；

本发明实施例中，“@”u₂的所有“提及者”，即u₁和u₄发布Tweets文本所包含的不确定 活动词条已被解析出来且经过词库词条匹配获得；“@”u₅的所有“提及者”，即u₃发布Tweets 文本所包含的不确定活动词条已被解析出来且经过词库词条匹配获得；

步骤4-2、获得所提取的词条所属活动类别的所有组合情况，并计算各活动类别中每种词 条组合情况的概率值；

步骤4-2-1、去掉用户的(表示“@”u_i的第一个“提及者”所发布得Tweets文本 (此处u_i即为u₂))所对应的不确定活动词条集合中不相关活动词条；

本发明实施例中，令其中表示第b个活动词条。因为活 动不相关词条概率p(u_t)＝0，对于活动表示没有任何意义，则就变为仅含相关活动词条和 半相关活动词条的即${\hat{A}}_{u_1^i}=\{r_{u_1^i}^1,r_{u_1^i}^2,...,r_{u_1^i}^{n_r},s_{u_1^i}^1,s_{u_1^i}^1,..,s_{u_1^i}^{n_s}\},$其中表示第b_r个活动相关词条；表示第b_s个活动半相关词条；

步骤4-2-2、得出提取词条表达可能产生活动的所有组合形式，并计算各活动类别中每种 词条组合情况的概率；

用多种带概率值的不确定活动词条集合表示则每种表达形式都存在一个概率值， 计算公式如下：

$p\left({\hat{A}}_{u_1^i}^{\hat{m}}\right)=\underset{\hat{i}=1}{\overset{\hat{k}}{\Pi }}{p}_{\hat{i}}---\left(10\right)$

其中，是的第种表达形式；如果某个活动半相关词条出现在中，则$p_{\hat{i}}=p\left(s_{u_1^i}^{\hat{i}}\right),$否则$p_{\hat{i}}=1-p\left(s_{u_1^i}^{\hat{i}}\right).$

步骤4-2-3、重复步骤4-2-1和4-2-2，完成对到以及剩余用户的“提及者”所发布文 本中词条表达活动工作；

本发明实施例中，推演“@”u₂的Tweets文本词条所代表的活动表达集合及其概率为以 下4种形式：

$\left(\begin{array}{cc}{A}_{u_2}^1=(\mathrm{mall},\mathrm{KFC},\mathrm{sales})& p\left(A_{u_2}^1\right)=(1-p\left(\mathrm{clothes}\right))\times (1-p\left(\mathrm{spend}\right))=0.2\times 0.4=0.08\end{array}\right)$

$A_{u_2}^2=(\mathrm{mall},\mathrm{KFC},\mathrm{sales},\mathrm{clothes})$

$p\left(A_{u_2}^2\right)=p\left(\mathrm{clothes}\right)\times (1-p\left(\mathrm{spend}\right))=0.8\times 0.4=0.32$

$A_{u_2}^3=(\mathrm{mall},\mathrm{KFC},\mathrm{sales},\mathrm{spend})$

$p\left(A_{u_2}^3\right)=p\left(\mathrm{spend}\right)\times (1-p\left(\mathrm{clothes}\right))=0.6\times 0.2=0.12$

$A_{u_2}^4=(\mathrm{mall},\mathrm{KFC},\mathrm{sales},\mathrm{clothes},\mathrm{spend})$

$p\left(A_{u_2}^4\right)=p\left(\mathrm{spend}\right)\times p\left(\mathrm{clothes}\right)=0.6\times 0.8=0.48$

“@”u₅的Tweets文本词条所代表的活动表达集合及其概率为以下2种形式：

$A_{u_5}^1=(\mathrm{mall},\mathrm{KFC})$

$p\left(A_{u_5}^1\right)=(1-p\left(\mathrm{clothes}\right))=1-0.8=0.2$

$A_{u_5}^2=(\mathrm{mall},\mathrm{KFC},\mathrm{sales})$

$p\left(A_{u_5}^2\right)=p\left(\mathrm{clothes}\right)=0.8$

步骤5、采用用户对活动相似性概率矩阵计算模块，获得社交网中任意用户对产生相似活 动的概率，并构建用户对相似行为活动概率下三角矩阵，具体如下：步骤5-1、采用杰卡德 (Jaccard)相似系数计算获得任意用户对所产生的各类活动的相似度和相似概率，并将大于 设定阈值0.6的相似度所对应的活动相似概率进行求和，获得该用户对活动相似概率；

本发明实施例中，利用Jaccard相似系数计算出一对用户间的活动相似度，计算公式如 下：

$\mathrm{Sim}({\hat{A}}_{u_i}^{\hat{r}},{\hat{A}}_{u_j}^{\hat{s}})=\frac{|{\hat{A}}_{u_i}^{\hat{r}}\cap {\hat{A}}_{u_j}^{\hat{s}}|}{|{\hat{A}}_{u_i}^{\hat{r}}\cup {\hat{A}}_{u_j}^{\hat{s}}|}---\left(11\right)$

其中，表示用户u_i与用户u_j间的活动相似度，表示用户u_i语义行为表 达的第种概率活动词条描述集合，表示用户u_j语义行为表达的第种概率活动词条描 述集合；

计算用户u_i与用户u_j间相似活动的概率值：

选出和的所有概率活动词条描述集合中相似度大于活动相似度阈值θ_sim的描述集 合，θ_sim＝0.6，则任意一对用户间相似活动的概率值是这些集合的概率值相加，

计算公式如下：

$p({\hat{A}}_{u_i},{\hat{A}}_{u_j})=\underset{{\hat{r}}_{\theta },{\hat{s}}_{\theta }}{\Sigma }p({\hat{A}}_{u_i}^{{\hat{r}}_{\theta }},{\hat{A}}_{u_j}^{{\hat{s}}_{\theta }})---\left(12\right)$

其中，表示用户u_i和用户u_j间相似活动的概率值，即大于活动相似度阈值的 这些集合中的词条能够以多大概率代表两个用户产生某类或某几类相似活动；表示所 有概率活动词条描述集合中相似度大于活动相似度阈值范围θ_sim的第个描述集合；表示 所有概率活动词条描述集合中相似度大于活动相似度阈值范围θ_sim的第个描述集合；

步骤5-2、反复执行步骤5-1，直至获得所有目标用户对活动相似概率，并构建用户对相 似行为活动概率下三角矩阵；

本发明实施例中，将所有和中词条对应的某类或某几类活动的概率值作为第j行和第i列元素存入矩阵A中；

本发明实施例中，计算出u₂和u₅活动相似度如表2中活动相似度一列所示。

表2

本发明实施例中θ_sim＝0.6，则$p(A_{u_2},A_{u_5})=0.016+0.256+0.384=0.656,$即u₂和u₅的活 动相似性概率为0.656，将0.656填入矩阵A的第5行和第2列。类似地，计算出其他用户对 间的活动相似度概率，最终计算出的用户对活动相似概率矩阵A如下：

步骤6、采用用户对物理位置相似度矩阵计算模块，获得社交网中任意用户对物理位置 相似度，并构建用户对物理位置相似度下三角矩阵，具体如下：

步骤6-1、将目标用户的地理经度和纬度转换成平面距离，根据平面距离计算任意用户 对间物理位置的相似度；

步骤6-1-1、将用户地理经、纬度转换成平面距离；

计算公式如下：

$D(u_i,u_j)=2\arcsin \sqrt{{\sin }^2\frac{\lambda }{2}+\cos \left({\mathrm{radX}}_{u_i}^{*}\right)*\cos \left({\mathrm{radX}}_{u_j}^{*}\right)*{\sin }^2\frac{\beta }{2}*\gamma }---\left(13\right)$

其中，D(u_i，u_j)表示一对用户间的平面距离，表示弧度值，λ表示经度差，β表示 纬度差，γ表示地球半径(γ＝6378.137公里)；

本发明实施例中，根据公式(13)计算出

$D(u_2,u_5)=2\arcsin \sqrt{{\sin }^2\frac{\lambda }{2}+\cos \left({\mathrm{radX}}_{u_i}^{*}\right)*\cos \left({\mathrm{radX}}_{u_j}^{*}\right)*{\sin }^2\frac{\beta }{2}*\gamma }=0.5153$

步骤6-1-2、计算一对用户间物理位置的相似度；

计算公式如下：

${\mathrm{Sim}}_L(L_{u_i}^{*},L_{u_j}^{*})=\frac{1}{1+D(u_i,u_j)}---\left(14\right)$

其中，表示一对用户间物理位置的相似度。

根据公式(14)计算出${\mathrm{Sim}}_L=(L_{u_2}^{*},L_{u_5}^{*})=\frac{1}{1+0.5153}=0.66$

步骤6-2、获取用户对间物理位置的相似度大于设定阈值0.5的相似度值，并将上述相 似度值保存至用户对物理位置相似度下三角矩阵中，完成用户对物理位置相似度下三角矩阵 的构建；

本发明实施例中，将大于阈值ε₂＝0.5的值填入矩阵L对应的第i行和第j列 中，重复步骤6-1和步骤6-2，完成对所有用户对的物理位置相似度计算并生成下三角矩阵L；

本发明实施例中，将0.66填入矩阵L的第5行和第2列。类似地，计算出其他用户间的 物理位置相似度值。同理，此处假定其他用户对间的物理位置相似度已计算完毕，并给出了 具体值。最终计算出的用户对物理位置相似度矩阵L如下：

步骤7、采用UPSBR关系矩阵推演模块，根据构建完成的用户对相似行为活动概率下三 角矩阵和用户对物理位置相似度下三角矩阵，获取目标用户对在用户对相似行为活动概率下 三角矩阵和用户对物理位置相似度下三角矩阵中对应位置的两数值，并将两数值相乘，获得 目标用户对用户对语义行为关系值，并构建用户对用户对语义行为关系矩阵；

步骤7-1、扫描A和L中第i行和第j列元素，如果其中ε₁＝0.5，ε₂＝0.5，那么推出u_i和u_j具有UPSBR关系；

本发明实施例中，扫描A和L中第5行和第2列元素，由于(预 先定义ε₁＝0.5)，(预先定义ε₂＝0.5)；

步骤7-2、生成用户对用户对语义行为关系矩阵M中的第j行和第i列元素；

计算公式如下：

M_ji＝A_ji·L_ji     (15)

本发明实施例中，计算出A₅₂·L₅₂＝0.656×0.66＝0.433，将0.433填入矩阵位置M₅₂中， 同时推出u₂和u₅具有UPSBR关系。

步骤7-3、重复步骤7-1和7-2，直至扫描完用户对相似行为活动概率下三角矩阵A和用 户对物理位置相似度下三角矩阵L的所有下三角元素，完成所有用户对的UPSBR关系推演， 并生成用户对用户对语义行为关系矩阵M。

本发明实施例中，计算出其他用户对的关系值，则最终生成的UPSBR关系矩阵M如下：

步骤8、采用用户对语义行为关系聚类推演模块构建连通图，即将用户作为连通图的节 点，用户对间的用户对语义行为关系值作为连通图节点之间的连通边，删除用户对语义行为 关系值小于设定阈值0.4的连通边，将剩余连通边构成的每个连通子图作为一组用户对语义 行为关系，完成社交网用户语义行为关系的推演。

具体步骤如下：

步骤8-1、根据M构建对应的连通图G；

步骤8-1-1、将M的用户作为连通图G的节点；

步骤8-1-2、将用户对间的矩阵值作为对应节点之间的边；

步骤8-1-3、重复步骤8-1-1和8-1-2，完成所有用户对操作；

步骤8-2、选择G中任意一个顶点v(u_i)加入到最小生成树已选顶点集合；

步骤8-3、选择一条代价最小的边e(u_i，u_j)加入到最小生成树中；

步骤8-4、重复步骤8-2和8-3，生成G的最小生成树T；

步骤8-5、根据最小生成树T进行用户群聚类；

步骤8-5-1、取定一个阈值0.4；

步骤8-5-2、去掉最小生成树T中边权重小于λ的连通边；

步骤8-5-3、剩余边构成的每个连通子图即为一组UGSBR关系；

本发明实施例中，计算推演出的UPSBR关系矩阵M所对应的最大树如图5(a)所示； 设定λ＝0.4，则对应生成的连通子图如图5(b)所示，即用户被聚成两类，分别是 C₁＝{u₁，u₂，u₃，u₅}，C₂＝{u₄}。

本发明中，通过实验验证了所提基于不确定活动词条的社交网用户语义行为关系推演系 统SBR-IS的有效性和可行性。

图6(a)给出了SBR-IS(语义行为关系推演系统中文)中未知物理位置推演测试结果。 当预测距离与实际距离的ED大约处在16km范围内时，SBR-IS推演出的用户比例略高于现有 方法UOW(Users Own Words)，且在实际应用中，大部分用户一般都被定位在误差16km范围 内，因此说明在衡量位置推断准确性时，SBR-IS比UOW的准确性要高一些。其次，图6(a) 中的两条曲线都呈现出先下降再略有上升的趋势，只不过SBR-IS在曲线尾部即大约512km处 上升，而UOW在大约16km处上升，说明有一些用户会在发布距离较远的Tweet文本中“提及” 该测试用户，但目的不是为了体现二者相近地理位置，更多的是为表达一种相关联系，比如 某种思念之情等。

图6(b)说明了@次数对不同ED段的物理位置推演的影响。在实验中，分别测试了@次 数为1、2、3及3次以上，ED分别取不同范围值的物理位置推演情况，并以用户比例的分布 来衡量预测效果。从图6(b)可以看出，随着@次数的增加，用户比例略呈上升趋势，即准确 度有所提高，说明@次数的多少在某种程度上对位置推演的准确度有一定影响。

图7给出了SBR-IS中UPSBR推演正确率的测试结果。从图7可以看出，随着ε₁的逐渐增 大，正确率呈下降趋势。因为ε₁越大，行为相似可能性就越小，满足UPSBR条件用户对越少， 进而使得正确率减少；反之，ε₁越小，行为相似可能性就越大，满足UPSBR条件用户对越多， 从而导致正确率增加。

图8(a)和(b)分别从NMI(互信息)和F1-Measure(综合了准确率和召回率的评价 指标)两个性能指标测试了本专利所用最大树聚类BRMC算法对推演UGSBR关系的聚类精度性 能。为有相对比较，本专利将逐行扫描活动相似性矩阵元素来发现UGSBR的方法命名为 A-BR(Activity-Behavior Relationship)方法。从图8可以看出，SBR-IS采用的BRMC方法 的聚类精度好于简单的A-BR算法。

图9(a)和(b)分别从F1-Measure(综合了准确率和召回率的评价指标)性能指标测 试了本专利所用最大树聚类BRMC算法对推演UGSBR关系的聚类参数敏感性。从图9中可以看 出，θ_sim＝[0.4，0.6]、α＝0.3均是性能较好的可选参数值范围。

综上所述，本发明提出的SBR-IS系统具有很好的推测物理位置准确度和SBR关系预测效 果。