多尺度空间下不确定行为语义的社交群体发现系统及方法

摘要

本发明涉及一种多尺度空间下不确定行为语义的社交群体发现系统及方法，属于数据挖掘和知识发现领域，本发明基于用户社交网Twitter行为轨迹，根据其发布推文地理位置的相似性以及推文词条所表达的不确定活动语义的相似性，来发现用户是否具相似有行为关系，从而找到对应的相似行为用户群体；实验证明，本发明在发现用户相似行为群体的准确性上优于现在已有的判断方法，具有很高的实际应用价值，如果能够得到极大推广，势必会有助于产业创新、促进跨界融合、惠及社会民生，推动我国经济和社会的创新发展。

说明书

技术领域

本发明属于数据挖掘和知识发现领域，具体涉及一种多尺度空间下不确定行为语义的社交群体发现系统及方法。

背景技术

随着社交网应用的快速普及，越来越多的用户融入到社交网中，比较典型的应用有国内的新浪微博、国外的推特(Twitter)等，这些社交应用允许用户将其最新动态和想法以短信形式发布到手机或是网站，如果用户愿意，还可发布微博-推文所处物理位置信息。微博-推文内容虽然简短，但却蕴涵一定语义，在某种程度上可以用于推演用户行为；而允许公开物理位置信息则可以方便追踪用户最新动态，如果能将上述两个方面加以有效利用，就能更好地为诸如商业销售、旅游路线推荐、广告精准投放以及城市功能规划等领域进行服务。

令人遗憾的是，迄今为止，在行为语义研究方面，几乎所有研究成果都认为行为语义是确定性的，但事实上，行为语义本身往往具有一定的不确定性，这主要源于当用推文对应的“词条集合(asetofterms)”表达行为所蕴涵的“活动(activity)”语义时，“词条”与“活动”之间存在着不确定的语义映射关系，比如一个“词条”可隶属于多个“活动”，而一个“活动”又可包含多个词条，正是这种语义映射的不确定性在一定程度上影响了相似行为用户群体发现的精度，但目前该问题却一直未能引起相关人员的高度重视。而另一方面，在利用微博和推特等社交数据服务于各种应用时没有充分考虑不同地理空间尺度对社交群体聚类的影响。实际上，根据地理学第一定律，有理由认为位置相近用户所产生的行为要比距离较远用户产生的行为更相似；其次，在细粒度地理空间上共享相似位置的用户具有更大的行为相似可能性，比如，两个用户在同一大学发推文可能比在同一城市发推文更具行为相似性，因此以分裂方式对位置轨迹进行不同空间度量尺度下的递归聚类，可以更有效地区分相似行为用户。

发明内容

针对现有技术的不足，本发明提出一种多尺度空间下不确定行为语义的社交群体发现系统及方法，基于用户社交网Twitter行为轨迹，根据其发布推文地理位置的相似性以及推文词条所表达的不确定活动语义的相似性，来发现用户是否具有相似行为关系。

一种多尺度空间下不确定行为语义的社交群体发现系统，包括社交网推文采集模块、多尺度空间下推文物理位置聚类模块、推文物理位置相似度矩阵计算模块、不确定行为语义词条库构建模块、推文词条提取模块、推文词条表达活动概率值及相似性概率获取模块和行为相似社交群体发现模块，其中：

社交网推文采集模块：用于采集社交网站的推文数据集，包括发布内容、发布位置、用户ID、用户名和文本发布时间，并经过数据清洗操作后进行存储；

多尺度空间下推文物理位置聚类模块：用于将每个用户推文形成的时空轨迹，按照基于密度的聚类方式在不同地理空间尺度下进行浓密区聚类，以生成用户多层次推文物理位置聚类簇序列；

推文物理位置相似度矩阵计算模块：用于对聚类所得的任意一对用户间的各层推文轨迹簇序列进行物理位置的综合性相似度获取，即获得推文轨迹物理位置相似度；

不确定行为语义词条库构建模块：用于构建社交网用户行为活动词条库，并抽取出每类活动包含的词条，通过重要性权重分布曲线，确定活动相关词条的判断阈值和活动半相关词条的判断阈值；将词条权重概率值大小与阈值进行比较，将词条分为活动相关词条、活动半相关词条和活动不相关词条三类，并赋予词条表达活动的概率值，获得不确定词条活动库；

推文词条提取模块：用于对所有用户发布的推文文本进行词条提取；

推文词条表达活动概率值及相似性概率获取模块：用于针对同层每一个最大位置轨迹匹配，合并同一用户不同物理位置簇的推文，生成推文语义词条集合，获得一对用户间推文语义活动的所有组合情况及各组合的概率值，进而获得一对用户间推文语义活动的同层概率值，即获得一对用户间同层推文语义行为相似度的概率值，再根据不同粒度划分层对语义相似度的权重，获得一对用户间推文语义活动的多层概率值，即获得一对用户间多层推文语义行为相似度的概率值；

行为相似社交群体发现模块：用于根据推文轨迹物理位置相似度和活动相似性概率获得轨迹行为相似度，通过构建连通图的方式获得推文相似行为群体。

采用所述的多尺度空间下不确定行为语义的社交群体发现系统进行的发现方法，包括以下步骤：

步骤1、在样本采集范围内采用社交网推文采集模块获取社交网站的推文数据集；

所述的推文数据集包括按照推文时间排序的推文物理位置和推文文本词条；

步骤2、采用计算机中的多尺度空间下推文物理位置聚类模块，将每个用户推文形成的时空轨迹，按照基于密度的聚类方式在不同地理空间尺度下进行浓密区聚类，以生成用户多层次推文物理位置聚类簇序列；

步骤3、采用多层次推文物理位置相似度矩阵计算模块，对聚类所得的任意一对用户间的各层推文轨迹簇序列进行物理位置的综合性相似度获取；

步骤4、采用计算机中的不确定行为语义词条库构建模块，构建不确定词条行为活动库，具体步骤如下：

步骤4-1、划分活动类别，并提取各类活动包含词条；

步骤4-2、赋予各种不确定词条表达活动的概率值，具体步骤如下：

步骤4-2-1、统计词条的词频和词条的逆向文本频率，根据词条的词频和词条的逆向文本频率获得词条的重要性权重；

步骤4-2-2、通过重要性权重分布曲线，确定活动相关词条的判断阈值和活动半相关词条的判断阈值；

步骤4-2-3、将词条权重概率值大小与阈值进行比较，将词条分为活动相关词条、活动半相关词条和活动不相关词条三类，并赋予词条表达活动的概率值，获得不确定词条行为活动库；

步骤5、采用推文词条提取模块对所有用户发布的推文文本进行词条提取；

步骤6、采用推文词条表达活动概率值及相似性概率获取模块，获得一对用户间推文语义行为相似度的概率值，具体步骤如下：

步骤6-1、针对同层每一个最大位置轨迹匹配，合并同一用户不同物理位置簇的推文，生成推文语义词条集合；

步骤6-2、获得一对用户间推文语义活动的所有组合情况及各组合的概率值，进而获得一对用户间推文语义活动的同层概率值，即获得一对用户间同层推文语义行为相似度的概率值；

步骤6-3、根据不同粒度划分层对语义相似度的权重，获得一对用户间推文语义活动的多层概率值，即获得一对用户间多层推文语义行为相似度的概率值；

步骤7、采用行为相似社交群体发现模块，根据推文轨迹物理位置相似度和活动相似性概率获得轨迹行为相似度，通过构建连通图的方式获得推文相似行为群体。

步骤1所述的在样本采集范围内采用社交网推文采集模块获取社交网站的推文数据集，需要对所采集的数据经过数据清洗操作后进行存储。

步骤2所述的生成用户多层次推文物理位置聚类簇序列，具体包括如下步骤：

步骤2-1、确定多种聚类空间度量粒度，即确定多尺度空间的距离尺度；

步骤2-2、采用聚类算法对处于每种粒度下的推文物理位置进行聚类；

步骤2-3、按推文发送时间先后顺序生成对应每个用户的推文位置聚类簇序列。

步骤3所述的对聚类所得的任意一对用户间的各层推文轨迹簇序列进行物理位置的综合性相似度获取，具体步骤如下：

步骤3-1、获得同层节点下一对用户相似推文物理位置的相似度；

同层节点下一对用户相似推文物理位置的相似度计算公式如下：

$>Sim(S_{il}^r,S_{jl}^r)=\frac{{\Sigma }_{q=1}^{\left|q\right|}(\frac{n_C\left({\mathrm{TLCS}}_q\right)}{M}\times {\Sigma }_{f=1}^{n_c\left({\mathrm{TLCS}}_q\right)}log\frac{N_u}{n_u\left(C_f\right)})}{\left|S_{il}^r\right|\times \left|S_{jl}^r\right|}---\left(1\right)$>

其中，表示用户u_i在第l层的物理位置轨迹簇序列；表示用户u_j在第l层的物理位置轨迹簇序列；r表示物理位置轨迹；l表示第l层物理位置轨迹簇聚类；|q|表示最大匹配的个数；n_C(TLCS_q)表示第l层第q个最大推文轨迹簇公共子序列所包含的聚类簇个数，1≤q≤|q|；M表示同一聚类尺度下用户轨迹聚类簇总数；N_u表示推文数据集中的总用户数，u表示用户；n_u(C_f)表示访问第l层第q个最大推文轨迹簇公共子序列第f个公共位置簇C_f的用户数，1≤f≤n_C(TLCS_q)；表示u_i在l层上的推文轨迹簇序列所包含的位置聚类簇个数；表示u_j在l层上的推文轨迹簇序列所包含的位置聚类簇个数；

步骤3-2、综合获得各层节点下一对用户推文物理位置的相似度；

计算公式如下：

$>Sim(T_i^r,T_j^r)={\Sigma }_{l=1}^{\left|l\right|}{w}_l\times Sim(S_{il}^r,S_{jl}^r)---\left(2\right)$>

其中，表示用户u_i和u_j位置轨迹相似度；T_i^r表示用户u_i的位置轨迹；表示用户u_j的位置轨迹；r表示物理位置轨迹；w_l表示不同粒度划分层对物理位置相似度的影响权重，w_l＝2^l-1，1≤l≤|l|，|l|表示不同粒度划分层的个数；

步骤3-3、重复步骤3-1至步骤3-2，获得所有用户对的多层次相似推文物理位置的相似度，并生成用户对多层次推文物理位置相似度下三角矩阵。

步骤6-2所述的进而获得一对用户间推文语义活动的同层概率值，即获得一对用户间同层推文语义行为相似度的概率值，具体公式如下：

$>Sim({\hat{D}}_l^i,{\hat{D}}_l^j)=\frac{{\Sigma }_q{p}_q({\hat{D}}_l^i,{\hat{D}}_l^j)}{\left|q\right|}---\left(3\right)$>

其中，表示用户u_i和u_j在第l层物理位置轨迹聚类簇序列上的推文行为语义相似度，表示u_i和u_j间满足第q个最大匹配的相似活动的概率值，|q|表示最大匹配的个数。

步骤6-3所述的根据不同粒度划分层对语义相似度的权重，获得一对用户间推文语义活动的多层概率值，即获得一对用户间多层推文语义行为相似度的概率值，具体公式如下：

$>Sim(T_i^d,T_j^d)={\Sigma }_{l=1}^{\left|l\right|}{w}_l^d\times Sim({\hat{D}}_l^i,{\hat{D}}_l^j)---\left(4\right)$>

其中，表示用户u_i和u_j的推文行为语义相似度；T_i^d表示用户u_i的位置轨迹所对应的推文轨迹；表示用户u_j的位置轨迹所对应的推文轨迹；表示第l层语义相似度权重；d表示推文轨迹；|l|表示不同粒度划分层的个数。

本发明优点：

本发明提出一种多尺度空间下不确定行为语义的社交群体发现系统及方法，本发明基于用户社交网Twitter行为轨迹，根据其发布推文地理位置的相似性以及推文词条所表达的不确定活动语义的相似性，来发现用户是否具相似有行为关系，从而找到对应的相似行为用户群体；

首先，本发明优点之一在于成功借鉴了地理学第一定律定量分析地理空间的理念，即“任何事物都相关，只是相近的事物关联更紧密”，认为用户在社交网应用Twitter上发布的推文其位置相近用户所产生的行为要比距离较远用户产生的行为更相似，即行为轨迹相似隐含着地理位置的相似，因此位置轨迹是否相似是进一步判断行为轨迹相似的必要前提；

其次，本发明首次针对Twitter行为轨迹提出在细粒度地理空间上共享相似位置的用户具有更大的行为相似可能性，比如，两个用户在同一大学发推文可能比在同一城市发推文更具行为相似性，因此以分裂方式对位置轨迹进行不同空间度量尺度下的递归聚类，可以更有效地区分相似行为用户；

此外，以往基于内容的行为轨迹研发工作大都认为行为轨迹的活动语义是确定的，但事实上，语义与活动之间的映射关系往往是不唯一的，因为推文词条集合对行为语义表达可有多种不同形式，这导致行为轨迹的活动语义表达具有不确定性，但该问题却被忽略。基于上述，本发明提出了多尺度空间下不确定行为语义的社交群体发现系统。

在当今如火如茶的互联网+时代，该系统的成功开发，无疑可以促进传统行业与互联网的深度融合，比如，有推荐需求的旅游业、广告业、销售业、餐饮业等，基于该系统能对目标客户人群做出更为准确的判断，从而提升信息推荐服务质量。实验也证明，本发明在发现用户相似行为群体的准确性上优于现在已有的判断方法，具有很高的实际应用价值，如果能够得到极大推广，势必会有助于产业创新、促进跨界融合、惠及社会民生，推动我国经济和社会的创新发展。

附图说明

图1为本发明一种实施例的多尺度空间下不确定行为语义的社交群体发现系统结构框图；

图2为本发明一种实施例的多尺度空间下不确定行为语义的社交群体发现方法流程图；

图3本发明一种实施例的原始推文轨迹在3个层上的不同聚类结果示意图，其中，图(a)为第1层上的不同聚类结果示意图，图(b)为第2层上的不同聚类结果示意图，图(c)为第3层上的不同聚类结果示意图；

图4本发明一种实施例的在第2层上的聚类转换簇图，其中，图(a)为用户u₁的原始轨迹图在第2层上的聚类转换簇图，图(b)用户u₂的原始轨迹图在第2层上的聚类转换簇图；

图5本发明一种实施例的在第3层上的聚类转换簇图，其中，图(a)为用户u₁的原始轨迹图在第3层上的聚类转换簇图，图(b)为用户u₂的原始轨迹图在第3层上的聚类转换簇图；

图6为本发明一种实施例的群体发现示意图，其中，图(a)为关系矩阵对应的连通图；图(b)为利用最大树聚类算法发现的推文行为相似群体图；

图7为本发明一种实施例的聚类效果之调和值比较图；

图8为本发明一种实施例的聚类效果之熵值比较图；

图9为本发明一种实施例的运行时间比较图；

图10为本发明一种实施例的不同推文数目下ε_r对聚类效果的敏感性测试图，其中，图(a)为推文数200情况下ε_r的测试结果示意图，图(b)为推文数300情况下ε_r的测试结果示意图，图(c)为推文数400情况下ε_r的测试结果示意图，(d)为推文数500情况下ε_r的测试结果示意图；

图11为本发明一种实施例的不同Tweets数目下ε_d对聚类效果的敏感性测试图，其中，图(a)为推文数200情况下ε_d的测试结果示意图，图(b)为推文数300情况下ε_d的测试结果示意图，图(c)为推文数400情况下ε_d的测试结果示意图，(d)为推文数500情况下ε_d的测试结果示意图；

图12为本发明一种实施例的不同Tweets数目下ζ对聚类效果的敏感性测试图，其中，图(a)为推文数200情况下ζ的测试结果示意图，图(b)为推文数300情况下ζ的测试结果示意图，图(c)为推文数400情况下ζ的测试结果示意图，(d)为推文数500情况下ζ的测试结果示意图。

具体实施方式

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

本发明实施例例中，如图1所示，多尺度空间下不确定行为语义的社交群体发现系统，包括社交网推文采集模块、多尺度空间下推文物理位置聚类模块、推文物理位置相似度矩阵计算模块、不确定行为语义词条库构建模块、推文词条提取模块、推文词条表达活动概率值及相似性概率获取模块和行为相似社交群体发现模块；

本发明实施例例中，所述的社交网推文采集模块利用推特应用所提供的API函数提取具有公开属性的发布内容(即文本)、发布位置(即经、纬度)，同时提取出的内容还包括用户ID、用户名、文本发布时间，然后经过数据清洗操作以记录形式存入MongoDB数据库中；

本发明实施例中，所述的多尺度空间下推文物理位置聚类模块用于将每个用户推文形成的时空轨迹，按照基于密度的聚类方式在不同地理空间尺度下进行浓密区聚类，以生成用户多层次推文物理位置聚类簇序列；

本发明实施例中，所述的推文物理位置相似度矩阵计算模块用于对聚类所得的任意一对用户间的各层推文轨迹簇序列进行物理位置的综合性相似度获取，即获得推文轨迹物理位置相似度，并将该相似度值作为矩阵元素构建推文轨迹物理位置相似度矩阵L；

本发明实施例中，所述的不确定行为语义词条库构建模块用于构建社交网用户行为活动词条库，并抽取出每类活动包含的词条，通过重要性权重分布曲线，确定活动相关词条的判断阈值和活动半相关词条的判断阈值；将词条权重概率值大小与阈值进行比较，将词条分为活动相关词条、活动半相关词条和活动不相关词条三类，并赋予词条表达活动的概率值，获得不确定词条活动库；

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

本发明实施例中，推文词条表达活动概率值及相似性概率获取模块用于针对同层每一个最大位置轨迹匹配，合并同一用户不同物理位置簇的推文，生成推文语义词条集合，获得一对用户间推文语义活动的所有组合情况及各组合的概率值，进而获得一对用户间推文语义活动的同层概率值，即获得一对用户间同层推文语义行为相似度的概率值，再根据不同粒度划分层对语义相似度的权重，获得一对用户间推文语义活动的多层概率值，即获得一对用户间多层推文语义行为相似度的概率值，并将每对概率值作为活动相似性矩阵元素构建活动相似性概率矩阵A；

本发明实施例中，所述的行为相似社交群体发现模块用于根据给定的物理位置相似度阈值范围和语义相似度阈值范围，计算出L和A对应相同行与列上的两个值的乘积并构成轨迹行为相似矩阵M；然后利用给定的行为相似度阈值范围将M进行最大树聚类，如果M对应的连通图的最小生成树中一些边的权值小于预先给定行为相似度阈值，就将这些边剪掉，于是剩余连通子图便是最大树聚类结果，而每个类则表示一组行为相似的社交群体；

本发明实施例中，采用所述的多尺度空间下不确定行为语义的社交群体发现系统进行的发现方法，方法流程图如图2所示，包括以下步骤：

步骤1、在样本采集范围内采用计算机中的社交网推文采集模块，获取Twitter可用推文数据集；所述的推文数据集包括按照推文时间排序的推文物理位置和推文文本词条；

本发明实施例中，具体步骤如下：

步骤1-1、选取城市；

本发明实施例中，选取美国城市人口数排名前20的城市；

步骤1-2、选取样本采集点；

本发明实施例中，对从步骤1-1中获得的每一个城市，以均匀分布选取1,000个点；

步骤1-3、确定样本最大采集区域；

本发明实施例中，以步骤1-2中获得的1,000个点为中心，以1公里为半径画出1,000个相互之间不重叠的圆形区域；

步骤1-4、确定样本采集范围；

本发明实施例中，从步骤1-3的结果中选取20,000个圆形区域；

步骤1-5、提取样本原始推特数据；

本发明实施例中，利用步骤1-4确定的区域，通过Twitter提供的API函数接口获取170,955条推特数据；

步骤1-6、预处理样本原始推特数据；

本发明实施例中，对步骤1-5获得的原始推特数据，进行数据清洗，去掉不完整的数据；

步骤1-7、存储可用推特数据；

本发明实施例中，对步骤1-6获得的可用推特数据按照统一格式，存入MongoDB数据库中；

本发明实施例中，如图3中图(a)、图(b)和图(c)所示，假定给出了两个Twitter用户u₁和u₂的推文语义行为轨迹T₁^b和如下：

T₁^b＝(p₁₁，D₁₁)→(p₁₂，D₁₂)→(p₁₃，D₁₃)→(p₁₄，D₁₄)→(p₁₅，D₁₅)

$>T_2^b=(p_{21},D_{21})\to (p_{22},D_{22})\to (p_{23},D_{23})\to (p_{24},D_{24})\to (p_{25},D_{25})$>

其中，D₁₁表示u₁在其第一个发布点发布推文的文本词条集合，同理，D₂₁表示u₂在其第一个发布点发布推文的文本词条集合，其他各地点发布的推文集合以此类推；p₁₁表示u₁在其第一个发布点的物理位置，即经度和纬度；同理，p₁₂表示u₂在其第一个发布点的物理位置，即经度和纬度；其他各发布地点以此类推；

首先，需要说明的是，u_i的一条原始位置轨迹T_i^r是一个由(p_ik，τ_ik)构成的按时间τ_ik排序的位置点序列，其中p_ik＝(x_ik，y_ik)，x_ik和y_ik是第k个位置的经、纬度，于是其中是T_i^r上的位置点数目，则u₁和u₂的原始位置轨迹如下：

T₁^r＝p₁₁→p₁₂→p₁₃→p₁₄→p₁₅

其次，u_i的一条语义行为轨迹T_i^b是一个由p′_ik＝(x_ik，y_ik，τ_ik，D_ik)构成的时间序列，其中D_ik＝{t_i1，t_i2，...，t_ih}，其中，h为D_ik所包含的词条数目。

步骤2、采用计算机中的多尺度空间下推文物理位置聚类模块，将每个用户推文形成的时空轨迹，按照基于密度的聚类方式在不同地理空间尺度下进行浓密区聚类，以生成用户多层次推文物理位置聚类簇序列；具体包括如下步骤：

步骤2-1、确定多种聚类空间度量粒度，即确定多尺度空间的距离尺度；

根据不同应用需求可设置不同的聚类空间度量尺度，本发明实施例中，如图3中图(a)、图(b)和图(c)所示中的l₁至l₃，分为三种，即10公里范围、5公里范围和1公里范围，即划分层次设为三层；

步骤2-2、采用聚类算法对处于每种粒度下的推文物理位置进行聚类；

本发明实施例中，根据步骤2-1所确定的每种聚类空间度量粒度，利用DBSCAN聚类算法对处于每种粒度下的推文物理位置进行聚类；

步骤2-3、按推文发送时间先后顺序生成对应每个用户的推文位置聚类簇序列；

本发明实施例中，根据步骤2-2所得的聚类簇，针对每个用户，按推文发送时间先后顺序生成对应每个用户的推文位置聚类簇序列；

本发明实施例中，如图3中的l₁层，u₁和u₂均被聚类在同一簇C₁₁中，u₁和u₂的第2层和第3层聚类转换簇图分别如图4中图(a)、图(b)和图5中图(a)、图(b)所示。

表1给出了聚类结果及对应参数；结合图3中例子，以l₃为例，说明各参数。其中假定，N_u＝100，n_u(C₃₃)＝10，n_u(C₃₄)＝20，则n_C(TLCS_q)＝2，因为有2个公共簇，即C₃₃和C₃₄；而Q＝1，即从和中找到1个最大公共匹配C₃₃→C₃₄；此外，M＝5，

表1实施例聚类结果及对应参数

步骤3、采用多层次推文物理位置相似度矩阵计算模块，对聚类所得的任意一对用户间的各层推文轨迹簇序列进行物理位置的综合性相似度获取；具体步骤如下：

步骤3-1、获得同层节点下一对用户相似推文物理位置的相似度；

同层节点下一对用户相似推文物理位置的相似度计算公式如下：

$>Sim(S_{il}^r,S_{jl}^r)=\frac{{\Sigma }_{q=1}^{\left|q\right|}(\frac{n_C\left({\mathrm{TLCS}}_q\right)}{M}\times {\Sigma }_{f=1}^{n_c\left({\mathrm{TLCS}}_q\right)}log\frac{N_u}{n_u\left(C_f\right)})}{\left|S_{il}^r\right|\times \left|S_{jl}^r\right|}---\left(1\right)$>

其中，表示用户u_i在第l层的物理位置轨迹簇序列；表示用户u_j在第l层的物理位置轨迹簇序列；r表示物理位置轨迹；l表示第l层物理位置轨迹簇聚类；|q|表示最大匹配的个数；n_C(TLCS_q)表示第l层第q个最大推文轨迹簇公共子序列所包含的聚类簇个数，1≤q≤|q|；M表示同一聚类尺度下用户轨迹聚类簇总数；N_u表示推文数据集中的总用户数，u表示用户；n_u(C_f)表示访问第l层第q个最大推文轨迹簇公共子序列第f个公共位置簇C_f的用户数，1≤f≤n_C(TLCS_q)；表示u_i在l层上的推文轨迹簇序列所包含的位置聚类簇个数；表示u_j在l层上的推文轨迹簇序列所包含的位置聚类簇个数；

本发明实施例中，利用TF-IDF思想计算同一聚类尺度(即同层节点)下一对用户相似推文物理位置的相似度。根据公式(1)可计算出u_i和u_j在第3层的位置簇序列相似度如下：

$>Sim(S_{13}^r,S_{23}^r)=\frac{\frac{2}{5}\times (log\frac{100}{10}+log\frac{100}{10})}{4\times 4}=\frac{\frac{2}{5}\times (1+1)}{4\times 4}=\frac{1}{20}=0.05$>

类似求得各层相似度结果如下：

$>Sim(S_{12}^r,S_{22}^r)=\frac{\frac{2}{2}\times (log\frac{100}{20}+log\frac{100}{33})}{3\times 2}=\frac{(log5+log3)}{3\times 2}=\frac{0.6990+0.4771}{6}=0.196$>

$>Sim(S_{11}^r,S_{21}^r)=\frac{\frac{1}{1}\times (log\frac{100}{90}+log\frac{100}{50})}{1\times 1}=log1+log2=0.301$>

步骤3-2、综合获得各层节点下一对用户推文物理位置的相似度；

计算公式如下：

$>Sim(T_i^r,T_j^r)={\Sigma }_{l=1}^{\left|l\right|}{w}_l\times Sim(S_{il}^r,S_{jl}^r)---\left(2\right)$>

其中，表示用户u_i和u_j位置轨迹相似度；T_i^r表示用户u_i的位置轨迹；表示用户u_j的位置轨迹；r表示物理位置轨迹；w_l表示不同粒度划分层对物理位置相似度的影响权重，w_l＝2^l-1，1≤l≤|l|，|l|表示不同粒度划分层的个数；

本发明实施例中，综合计算多种聚类尺度(即各层节点)下一对用户推文物理位置的相似度。令w_l＝2^l-1，根据公式(2)计算出最终位置相似度如下：

$>Sim(T_1^r,T_2^r)=0.05*4+0.196*2+0.301=0.2+0.392+0.301=0.893$>

步骤3-3、重复步骤3-1至步骤3-2，获得所有用户对的多层次相似推文物理位置的相似度，并生成用户对多层次推文物理位置相似度下三角矩阵；

本发明实施例中，将步骤3-2生成的每一对作为第j行和第i列元素存入多层次推文物理位置相似度下三角矩阵L中，重复步骤3-1至步骤3-2，完成所有用户对的多层次相似推文物理位置的相似度计算，并生成用户对多层次推文物理位置相似度下三角矩阵L；

本发明实施例中，生成用户对多层次推文物理位置相似度下三角矩阵L如下(为表示简单起见，仅给出其中的5个用户对)。

步骤4、采用计算机中的不确定行为语义词条库构建模块，构建不确定词条行为活动库，具体步骤如下：

步骤4-1、划分活动类别，并提取各类活动包含词条；

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

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

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

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

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

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

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

每类活动下存储表示该类活动的词条，由于活动分类词条与社交应用本身紧密相关，即在某种程度上或多或少存在一定语义偏斜，因此本文在构建活动分类词条集合时，根据类别语义通过维基百科适当增加了部分相关词条，旨在改善语义倾斜问题；

步骤4-2、赋予各种不确定词条表达活动的概率值，具体步骤如下：

步骤4-2-1、统计词条的词频和词条的逆向文本频率，根据词条的词频和词条的逆向文本频率获得词条的重要性权重；

步骤4-2-1-1、统计词条的词频；

计算公式如下：

$>TF=\frac{g_{ij}}{\Sigma g}---\left(5\right)$>

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

步骤4-2-1-2、统计词条的逆向文本频率；

计算公式如下：

$>IDF=log\frac{\left|A\right|}{\left|A_i\right|}---\left(6\right)$>

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

步骤4-2-1-3、计算词条的重要性概率值；

本发明实施例中，词条t_i在多少个活动中出现过，对t_i与某个活动的相关性大小有重要影响：若t_i在越多的活动中出现，则t_i与某个活动能够的相关性越低；反之，若t_i在越少的活动中出现，则t_i与活动的相关性越高。因此，用TF·IDF方法计算词条表达活动的重要性权重，然后除以最大权重值w_max；

计算公式如下：

p_w(t_i)＝TF·IDF/w_max(7)

其中，TF·IDF表示词条t_i在活动A_j中的重要性权重，并将公式(5)和(6)代入；w_max表示权重值中的最大值；p_w(t_i)表示词条t_i在活动A_j中的重要性权重概率值，即权重概率值；

步骤4-2-2、通过重要性权重分布曲线，确定活动相关词条r_t的判断阈值θ_r和活动半相关词条s_t的判断阈值θ_u；

本发明实施例中，将词条分为活动相关词条r_t、活动半相关词条s_t和活动不相关词条u_t三类，由于权重分布曲线符合Zipf分布，因此根据数理统计概率分布中的1/3和2/3分位点所对应的权重概率值，作为主题相关词条阈值θ_r和主题不相关词条阈值θ_u；

步骤4-2-3、将词条权重概率值大小与阈值进行比较，将词条分为活动相关词条、活动半相关词条和活动不相关词条三类，并赋予词条表达活动的概率值，获得不确定词条行为活动库；

本发明实施例中，取某一词条t_x的权重概率值p_w(t_x)作为相关词条与半相关词条的分界线，当且仅当公式(8)成立；同理，取某一词条t_y的权重概率值p_w(t_y)作为半相关词条与不相关词条的分界线，当且仅当公式(9)成立，其中|k|代表全部推文集合中的词条总数(1≤x，y≤|k|)；

$>{\Sigma }_{i=0}^{x-1}{p}_w\left(t_i\right)<\frac{{\Sigma }_{i=1}^{\left|k\right|}{p}_w\left(t_i\right)}{3}<{\Sigma }_{i=1}^x{p}_w\left(t_i\right)---\left(8\right)$>

$>{\Sigma }_{i=0}^{y-1}{p}_w\left(t_i\right)<\frac{2·{\Sigma }_{i=1}^{\left|k\right|}{p}_w\left(t_i\right)}{3}<{\Sigma }_{i=1}^y{p}_w\left(t_i\right)---\left(9\right)$>

权重概率值大于θ_r的词条是活动相关词条；权重概率值小于θ_u的词条是活动不相关词条；权重概率值介于θ_r和θ_u之间的词条是活动半相关词条；

本发明实施例中，假定整个推文词条活动库包含t₁、t₂、t₃、t₄、t₅和t₆六个词条，即|k|＝6，且这些词条属于同一类活动，则它们基于TF-IDF的重要性概率值分别为p_w(t₁)＝1，p_w(t₂)＝0.5，p_w(t₃)＝0.33，p_w(t₄)＝0.25，p_w(t₅)＝0.2，p_w(t₆)＝0.17，经计算当取x＝1时，有$>{\Sigma }_{i=0}^{x-1}{p}_w\left(t_i\right)={\Sigma }_0^0{p}_w\left(t_i\right)=p_w\left(t_0\right),$>本发明实施例中，设定p_w(t₀)＝0，即$>{\Sigma }_0^0{p}_w\left(t_i\right)=0,$>而因此t₁满足公式(8)，于是将t₁作为t_r与t_s的分界线，同理，经类似计算并根据公式(8)将t₃作为t_s与t_u的分界线。最后的词条分类结果为t_r={t₁}，t_s＝{t₂，t₃}，t_u={t₄，t₅，t₆}，这时p_w(t₁)＝1，p_w(t₂)＝0.5，p_w(t₃)＝0.33，p_w(t₄)＝p_w(t₅)＝p_w(t₆)＝0。

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

表2

步骤5、采用计算机中的推文词条提取模块，利用Lucene分词工具，通过去停用词等操作对所有用户发布的推文文本进行词条提取；

步骤6、采用推文词条表达活动概率值及相似性概率获取模块，获得一对用户间推文语义行为相似度的概率值，具体步骤如下：

步骤6-1、针对同层每一个最大位置轨迹匹配TLCS_q(1≤q≤|q|)，合并同一用户不同物理位置簇的推文，生成推文语义词条集合D_l(TLCS_q)，所述的D_l(TLCS_q)表示第l物理位置聚类层、第q个最大位置轨迹匹配对应的推文词条集合；

本发明实施例中，以附图5为例，假定在第三层，用户u₁和u₂各自合并后的D₃(TLCS_q)分别如表3中的l₃列所示。

表3

步骤6-2、获得一对用户间推文语义活动的所有组合情况及各组合的概率值，进而获得一对用户间推文语义活动的同层概率值，即获得一对用户间同层推文语义行为相似度的概率值；

本发明实施例中，将推文语义词条集合D_l(TLCS_q)与词条库中的词条进行匹配，判断是活动相关词条还是活动半相关词条；枚举出不确定词条表达D_l(TLCS_q)推文语义活动的所有组合形式及每种形式的存在概率；去掉和中各自所对应的不相关活动词条，使得和中只包含相关活动词条和半相关活动词条，并计算出它们各自所包含的半相关词条个数和

本发明实施例中，仍以D₃(TLCS_q)为例，将其包含的词条与词条库进行匹配后，得出其所属类别为：t_r＝{t₁}，t_s＝{t₂，t₃}；其中，t_r和t_s分别代表相关词条集合和半相关词条集合。因此，有$>t_r^i=t_r^j=\left\{t_1\right\},$>而$>t_s^i=\left\{t_2\right\},t_s^i=\{t_2,t_3\},$>且p_w(t₁)＝1，p_w(t₂)＝0.5，p_w(t₃)＝0.33；

本发明实施例中，根据得出的和枚举出和中相应的所有词条活动表达集合形式，枚举个数分别为和其计算如下：

$>m_l^i=1+\frac{{\alpha }_i^r({\alpha }_i^r+1)}{2}---\left(10\right)$>

$>m_l^j=1+\frac{{\alpha }_j^r({\alpha }_j^r+1)}{2}---\left(11\right)$>

其中，表示中所有的词条表达活动的集合形式个数；表示中所有的词条表达活动的集合形式个数；公式中的第一部分，即数字“1”代表由全部相关词条集合构成的一种确定活动表达形式，称为“相关基”；公式的第二部分，则代表以“相关基”作为初始部分，向其逐条追加半相关词条时构成的不确定词条表达活动形式的集合数。

本发明实施例中，根据得出的枚举结果，计算出每个词条集合表达推文语义活动的存在概率，计算公式如下：

其中，是的第λ个活动词条描述集合表达形式；是该集合中第φ个词条的存在概率(如果相关词条存在于该集合中，则其存在概率为1；如果半相关词条存在与该集合中，则其存在概率值为否则概率值为是该集合所包含词条的个数；同理，是的第λ′个活动词条描述集合表达形式，其对应概率计算与前者相同，此处不再赘述。

本发明实施例中，根据得出的对应和所有词条表达活动集合形式，枚举出所有推文对组合，组合数为

本发明实施例中，仍以D₃(TLCS_q)为例，则和的所有可能组合形式及每种形式的存在概率如表4所示。其中，和分别表示用户u₁和u₂在第3物理位置轨迹聚类层上、去掉不相关词条后、对应第q个最大匹配TLCS_q的推文文本词条集合。和分别表示用户u₁在中的第一种、第二种词条表达活动形式，即上标表示用户，下标表示在第几层的第几种表达形式，以此类推，用户u₂在中的四种表达形式分别为和具体如表4第3列所示。

表4例子的可能表达形式及其存在概率

本发明实施例中，针对得出的所有推文对组合及其所含推文表达活动形式的存在概率值，利用Jaccard相似系数计算出一对用户间每个可能的推文对的活动语义的相似度，即的计算如表5所示；

表5例子的相似性计算及其存在概率

本发明实施例中，令则根据公式(11)得出如下：

$>\left(\begin{array}{c}{p}_1({\hat{D}}_3^i,{\hat{D}}_3^j)=p_1({\hat{D}}_{31}^i,{\hat{D}}_{31}^j)+p({\hat{D}}_{31}^1,{\hat{D}}_{31}^2)+p({\hat{D}}_{31}^1,{\hat{D}}_{31}^2)\\ +p({\hat{D}}_{32}^1,{\hat{D}}_{31}^2)+p_1({\hat{D}}_{32}^i,{\hat{D}}_{32}^j)+p_1({\hat{D}}_{32}^i,{\hat{D}}_{34}^j)\\ =0.125+0.1675+0.0825+0.125+0.1675+0.0825\\ =0.75\end{array}\right)$>

本发明实施例中，针对得出的所有推文对组合及其所含推文表达活动形式的存在概率值，利用Jaccard相似系数计算出一对用户间每个可能的推文对的活动语义的相似度，计算公式如下：

$>Sim({\hat{D}}_{l\lambda }^i,{\hat{D}}_{{\mathrm{l\lambda }}^{\prime }}^j)=\frac{\left|{\hat{D}}_{l\lambda }^i\cap {\hat{D}}_{{\mathrm{l\lambda }}^{\prime }}^j\right|}{\left|{\hat{D}}_{l\lambda }^i\cap {\hat{D}}_{{\mathrm{l\lambda }}^{\prime }}^j\right|}---\left(14\right)$>

其中，是的第λ个活动词条描述集合表达形式，是的第λ′个活动词条描述集合表达形式；

本发明实施例中，计算出一对用户间每个可能的推文对的活动语义相似度的存在概率值即一对用户间同层相似活动的概率值；

本发明实施例中，选出和的所有概率活动词条描述集合中相似度大于同层活动相似度阈值(通过实验测得)的描述集合，则任意一对用户间相似活动的概率值是这些集合存在的概率值相加，计算公式如下：

$>p_q({\hat{D}}_l^i,{\hat{D}}_l^j)=\underset{\hat{\lambda },\hat{\lambda }}{\Sigma }p({\hat{D}}_{l\hat{\lambda }}^i,{\hat{D}}_{l{\hat{\lambda }}^{\prime }}^j)---\left(15\right)$>

其中，和分别表示和所有概率活动词条描述集合中相似度大于活动相似度阈值范围的第个和第个描述集合，表示u_i和u_j间满足第q个最大匹配的相似活动的概率值，换句话说，第q个最大匹配中大于活动相似度阈值的这些集合中的词条能够以多大概率代表两个用户产生某类或某几类相似活动；

本发明实施例中，计算满足全部最大匹配的一对用户间同层推文相似活动的相似度，计算公式如下：

$>Sim({\hat{D}}_l^i,{\hat{D}}_l^j)=\frac{{\Sigma }_q{p}_q({\hat{D}}_l^i,{\hat{D}}_l^j)}{\left|q\right|}---\left(3\right)$>

其中，表示用户u_i和u_j在第l层物理位置轨迹聚类簇序列上的推文行为语义相似度，表示u_i和u_j间满足第q个最大匹配的相似活动的概率值，|q|表示最大匹配的个数。

本发明实施例中，由于而|q|＝1，因此根据公式(3)得出如下：

$>Sim({\hat{D}}_3^1,{\hat{D}}_3^2)=\frac{0.75}{1}=0.75$>

步骤6-3、根据不同粒度划分层对语义相似度的权重，获得一对用户间推文语义活动的多层概率值，即获得一对用户间多层推文语义行为相似度的概率值；具体公式如下：

$>Sim(T_i^d,T_j^d)={\Sigma }_{l=1}^{\left|l\right|}{w}_l^d\times Sim({\hat{D}}_l^i,{\hat{D}}_l^j)---\left(4\right)$>

其中，表示第l层语义相似度权重，d表示推文轨迹，表示用户u_i和u_j的推文行为语义相似度，|l|表示不同粒度划分层的个数。

本发明实施例中，假定l₂和l₁的参数如表3中的第2列和第3列所示，并假定已计算出$>Sim({\hat{D}}_2^1,{\hat{D}}_2^2)=0.3,Sim({\hat{D}}_1^1,{\hat{D}}_1^2)=0.2,$>通过预定义的各层语义相似度权重$>w_3^d=0.7,w_2^d=0.2,$>则根据公式(13)，最终得出如下：

$>Sim(T_1^d,T_2^d)=0.7*0.75+0.2*0.3+0.1*0.2=0.605$>

本发明实施例中，将语义相似度作为第j行和第i列元素存入矩阵A中，完成所有用户对的推文语义相似行为概率计算，并生成用户对相似行为活动概率下三角矩阵A如下：

步骤7、采用行为相似社父群体发现模块，根据推文轨迹物理位置相似度和活动相似性概率获得轨迹行为相似度，通过构建连通图的方式获得推文相似行为群体；具体步骤如下：

步骤7-1、构建推文轨迹行为相似矩阵M；

步骤7-1-1、扫描L和A中第i行和第j列元素，如果其中设置ε_d＝0.5，ε_r＝0.5，那么生成M中的第j行和第i列元素，计算公式如下：

M_ji＝A_ji·L_ji(16)

本发明实施例中，扫描L和A中第2行和第1列元素，且那么根据公式(16)则可计算出A₂₁·L₂₁＝0.893·0.605＝0.54，然后将该值填入矩阵位置M₂₁中，即生成推文轨迹行为相似矩阵M中的第j行和第i列元素。以此类推，最终获得所有用户的推文相似行为下三角矩阵M(假定其他用户间的数值按上述方法都被计算出来)：

步骤7-1-2、重复步骤7-1-1，直至扫描完矩阵A和L的所有下三角元素，完成矩阵M的生成；

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

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

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

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

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

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

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

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

步骤7-6-1、取定一个阈值ζ＝[0.4，0.6]；

步骤7-6-2、去掉最小生成树T中边权重小于ζ的连通边；

步骤7-6-3、剩余边构成的每个连通子图即为一组推文轨迹相似用户群体。

本发明实施例中，计算关系矩阵M所对应的最大树如图6中图(a)所示。假定ζ＝0.5，则对应生成的连通子图如图6中图(b)所示，即用户被聚成两类，即在给出的5个用户中发现了2个推文相似群体，它们分别是C₁＝{u₁，u₂，u₄}和C₂＝{u₃，u₅}；

本发明实施例中，通过实验验证了所提的多尺度空间下基于不确定行为语义的社交群体发现系统的有效性和可行性。

本发明实施例中，根据不同地理空间聚类尺度将所提系统划分成UUGD-1、UUGD-2和UUGD-3三种，其中，UUGD-1用一种度量尺度(聚类范围1公里)，UUGD-2综合两种度量尺度(聚类范围分别为1公里和5公里)，UUGD-3综合三种度量尺度(聚类范围分别为1、5、10公里)；尽管地理位置空间度量尺度不同，但这三种方法对不确定语义的相似性计算则采用相同概率方法求解，而后将它们分别与LDA-TFIDF算法在影响聚类效果的F-measure和熵指标上进行了有效性测试与比较，测试结果如图7和图8所示。

本发明实施例中，如图4所示，在同样一种地理空间聚类尺度下，UUGD-1的聚类效果优于LDA-TFIDF，因为前者考虑了Tweet轨迹活动语义表达的不确定性，即为最有可能表达活动语义的推文词条赋以较高概率，相比于LDA-TFIDF算法的确定性语义计算，UUGD处理不确定性的概率手段能使活动语义被更充分地表达出来，因此聚类效果更优。其次，在不同地理空间聚类尺度下，UUGD-2和UUGD-3的聚类效果不仅优于LDA-TFIDF，而且优于UUGD-1，这一方面源于上述提及的UUGD对不确定语义的考虑，一方面则体现出了不同地理空间聚类尺度对聚类效果有着重要影响。由于UUGD-3的地理空间划分涵盖了UUGD-2和UUGD-1，即UUGD-3能更合理地反映Twitter行为轨迹在地理位置上的相似性聚类，因此聚类效果相比其他两种方法更准确。接下来，从熵指标来看，由于熵越小聚类效果越好，因此图8中的UUGD-3也同样好于UUGD-2、UUGD-1方法和LDA-TFIDF方法，原因与对F-measure的分析是相同的。

图9给出了四种方法运行时间的测试结果。如图9所示，由于UUGD-1要综合处理地理位置空间聚类和不确定语义概率计算两种操作，因此时间略多于LDA-TFIDF；而UUGD-2和UUGD-3的运行时间均多于UUGD-1，这是因为它们要综合多个度量空间尺度计算聚类，因此耗费时间相比UUGD-1要更多一些。

为验证UUGD参数对该模型本身执行聚类效果的影响，本文对涉及到的相关参数进行了详细测试，由于UUGD-3考虑了更细的地理空间划分，聚类效果更优，因此本发明实施例中给出了UUGD-3达到最优性能时各参数的合理取值范围，其他方法类似，此处不再赘述。

图10～图12给出了Tweet数据集合分别取200、300、400和500大小情况下，参数ε_r、ε_d和ζ分别对聚类评价指标F-measure和熵的影响。

首先，从图10中图(a)～图(d)可以看出，随着ε_r值的增加，F-measure呈现出先上升后下降趋势，而熵则呈现出先下降后上升趋势，这是因为如果阈值ε_r取值过低，UUGD认为大量地理位置不相近的数据有较大相似度，将它们聚为一个簇；相反，如果ε_r取值过高，UUGD会将大量地理相近度较高的数据分开，因此聚类效果下降。众所周知，F-measure越大聚类效果越好，反之，熵越小则聚类效果越好，因此，二者越接近的地方就是ε_r最为敏感的取值之处，尽管ε_r的最佳取值还要依赖于不同的数据集合，但根据本文所选测试集，有理由认为当ε_r在0.5左右取值时，聚类效果较好。

其次，文本语义相似度阈值ε_d对聚类效果的影响如图11中图(a)～图(d)所示。从图8可以看出，当ε_d∈[0.4，0.6]时，UUGD的聚类效果较好。类似于ε_r敏感度对聚类的影响，ε_d对聚类影响也具有同样变化趋势，原因是阈值ε_d取值过低，UUGD认为大量Tweets文本语义不相近的数据有较大相似度，将它们聚为一个簇；相反，如果ε_d取值过高，UUGD会将大量Tweets文本语义相似度较高的数据分开，因此聚类效果下降。同样，ε_d的最佳取值一方面还要依赖于不同数据集合。最后，最大树聚类参数阈值ζ对聚类效果的影响如图12中图(a)～图(d)所示。从图12中可以看出，当ζ∈[0.4，0.6]时，聚类效果较好，原因类似于ε_d，此处不再赘述。