一种社交网络热词和事件挖掘系统及方法[发明专利]

*CN102609436A*

(10)申请公布号 CN 102609436 A(43)申请公布日 2012.07.25

(12)发明专利申请

(21)申请号 201110434991.0(22)申请日 2011.12.22

(71)申请人北京大学

地址100871 北京市海淀区颐和园路5号(72)发明人闫宏飞 树柏涵 赵鑫 李晓明(74)专利代理机构北京路浩知识产权代理有限

公司 11002

代理人王莹(51)Int.Cl.

G06F 17/30(2006.01)

权利要求书 2 页 说明书 5 页 附图 2 页权利要求书2页 说明书5页 附图2页

(54)发明名称

一种社交网络热词和事件挖掘系统及方法(57)摘要

本发明公开了一种社交网络热词和事件挖掘系统及方法，涉及社交网络领域。所述方法包括步骤：对候选词进行统计，得到相应的候选词序列；根据所述候选词序列，计算所述候选词在不同时间点的状态参数；提供备选状态序列，根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价；根据所述备选状态序列，计算所述候选词的状态转移代价；根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。所述系统和方法提高了热词挖掘的准确度。

CN 102609436 ACN 102609436 A

权 利 要 求 书

1/2页

1.一种社交网络热词和事件挖掘系统，其特征在于，包括：信息统计模块、状态参数模块、生成代价模块、转移代价模块和状态序列模块；

所述信息统计模块，用于对候选词进行统计，得到相应的候选词序列；所述状态参数模块，用于根据所述候选词序列，计算所述候选词在不同时间点的状态参数；

所述生成代价模块，用于根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价；

所述转移代价模块，根据所述备选状态序列，计算所述候选词的状态转移代价；所述状态序列模块，用于提供所述备选状态序列，并根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。

2.一种社交网络热词和事件挖掘方法，其特征在于，包括步骤：A：对候选词进行统计，得到相应的候选词序列；B：根据所述候选词序列，计算所述候选词在不同时间点的状态参数；C：提供备选状态序列，根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价；

D：根据所述备选状态序列，计算所述候选词的状态转移代价；E：根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。

3.如权利要求2所述的方法，其特征在于，所述步骤A中，所述候选词序列包括：通过统计各个时间点包含所述候选词的社交网络文本数得到的词频序列，或者通过统计各个时间点包含所述候选词且是转发的社交网络文本数得到的转发序列，或者通过统计各个时间点包含所述候选词且是原创的社交网络文本数得到的原创序列，或者通过统计各个时间点发送包含所述候选词的社交网络文本的用户的数量得到的用户序列，或者通过统计各个时间点包含URL信息且包含所述候选词的社交网络文本数量得到的URL序列。

4.如权利要求2所述的方法，其特征在于，所述状态参数为泊松分布参数，并且包括：0状态参数和1状态参数。

5.如权利要求4所述的方法，其特征在于，所述0状态参数的计算公式如下：

其中，λ0，i表示每天24小时中第i个时间点的0状态参数，0≤i≤23；rt表示所述候选词序列中第t个时间点对应的数据，t为自然数；n表示所述候选词序列中时间点的总数。

6.如权利要求5所述的方法，其特征在于，所述1状态参数的计算公式如下：λ1，i＝βλ0，i；其中，λ1，β表示热度系数，并且βi表示每天24小时中第i个时间点的1状态参数；＞1。

7.如权利要求6所述的方法，其特征在于，所述步骤C具体包括步骤：

2

CN 102609436 A

权 利 要 求 书

2/2页

C1：提供备选状态序列；C2：根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成概率；

C3：根据所述状态生成概率得到所述候选词的状态生成代价。8.如权利要求7所述的方法，其特征在于，所述步骤C2中的状态生成概率的计算公式如下：

其中，P(k，rt)表示所述候选词对应k状态的状态生成概率，k等于1或者0。9.如权利要求8所述的方法，其特征在于，所述步骤C3中的状态生成代价C-G(k，rt)的计算公式如下：

C-G(k，rt)＝-ln(P(k，rt))。10.如权利要求2所述的方法，其特征在于，所述状态转移代价的计算公式如下：

其中，(Si’，Si’+1...Si’+q-1)表示由1或者0构成的备选状态序列中的相邻的q个状态，q的取值是2、3或者4，i’为自然数；将所述q个状态分为m组，要求组内状态连续并且状态值相同，相邻组的状态值不同，aj表示第j个组中的状态的个数，1≤j≤m；γ表示转移代价系数。

3

CN 102609436 A

说 明 书

一种社交网络热词和事件挖掘系统及方法

1/5页

技术领域

[0001]

本发明涉及社交网络技术领域，特别涉及一种社交网络热词和事件挖掘系统及方

法。背景技术

根据词在社交网络上的使用情况，可以挖掘该词使用较为频繁的时间段，即该词

为热词的时间段；在热词时间段对包含热词的社交网络文本进行事件挖掘，可以对事件进行摘要，同时挖掘出传播该事件的有影响力的用户，并且可能会对企业、政府的调研、决策提供有力的数据支持。[0003] J.Kleinberg在“Bursty and hierarchical structure in streams”一文中提出了一种热词挖掘方法，该方法认为候选词在一个时间区间内可能处于两种状态：(1)0状态-普通状态，(2)1状态-热词状态，并为候选词计算了一个基础概率P0和一个热词概率P1，分别作为两种状态下的词的生成概率；将词的生成概率取对数后再取负，得到词的生成代价；该方法还定义状态之间的转移代价。该方法采用序列标注的方式对一个热词在若干连续时间区间进行状态标注，求得一个使总代价最小的标注序列。[0004] 该方法的缺点是：

[0005] (1)对一个词采用静态全局概率作为基础概率。全局静态概率没有考虑到某些词在社会上使用概率的变化，例如“囧”在2008年之前很少使用，而在2008年后则成为中文地区的网络社群间成为一种流行的表情符号。

[0006] (2)不能解决社交网络上周期性热词问题。比如“晚安”在晚间使用较多，容易挖掘出一些非事件性的周期性热词。

[0007] (3)该方法主要针对新闻数据，没有考虑到社交网络数据特有的信息，比如转发信息、用户关系信息，社交网络文本中包含的URL信息等。[0008] (4)使用一个时间点上的总社交网络文本数，而总社交网络文本数在社交网络的不同时间点变化很大(比如晚上8-9点的总社交网络文本数必然多于凌晨)。因此，其不能解决总社交网络文本数波动较大的问题。

[0002]

发明内容

[0009] (一)要解决的技术问题

[0010] 本发明要解决的技术问题是：如何提供一种社交网络热词和事件挖掘系统及方法，以便提高热词挖掘的准确度。[0011] (二)技术方案

[0012] 为解决上述技术问题，本发明提供一种社交网络热词和事件挖掘系统，其包括：信息统计模块、状态参数模块、生成代价模块、转移代价模块和状态序列模块；[0013] 所述信息统计模块，用于对候选词进行统计，得到相应的候选词序列；[0014] 所述状态参数模块，用于根据所述候选词序列，计算所述候选词在不同时间点的

4

CN 102609436 A

说 明 书

2/5页

状态参数；

[0015] 所述生成代价模块，用于根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价；[0016] 所述转移代价模块，根据所述备选状态序列，计算所述候选词的状态转移代价；[0017] 所述状态序列模块，用于提供所述备选状态序列，并根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。

[0018] 本发明还提供一种社交网络热词和事件挖掘方法，其包括步骤：[0019] A：对候选词进行统计，得到相应的候选词序列；[0020] B：根据所述候选词序列，计算所述候选词在不同时间点的状态参数；[0021] C：提供备选状态序列，根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价；[0022] D：根据所述备选状态序列，计算所述候选词的状态转移代价；[0023] E：根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。[0024] 优选地，所述步骤A中，所述候选词序列包括：通过统计各个时间点包含所述候选词的社交网络文本数得到的词频序列，或者通过统计各个时间点包含所述候选词且是转发的社交网络文本数得到的转发序列，或者通过统计各个时间点包含所述候选词且是原创的社交网络文本数得到的原创序列，或者通过统计各个时间点发送包含所述候选词的社交网络文本的用户的数量得到的用户序列，或者通过统计各个时间点包含URL信息且包含所述候选词的社交网络文本数量得到的URL序列。[0025] 优选地，所述状态参数为泊松分布参数，并且包括：0状态参数和1状态参数。[0026] 优选地，所述0状态参数的计算公式如下：

[0027]

其中，λ0，i表示每天24小时中第i个时间点的0状态参数，0≤i≤23；rt表示所述候选词序列中第t个时间点对应的数据，t为自然数；n表示所述候选词序列中时间点的总数。

[0029] 优选地，所述1状态参数的计算公式如下：[0030] λ1，i＝βλ0，i；[0031] 其中，λ1，β表示热度系数，并i表示每天24小时中第i个时间点的1状态参数；且β＞1。

[0032] 优选地，所述步骤C具体包括步骤：[0033] C1：提供备选状态序列；[0034] C2：根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成概率；

[0035] C3：根据所述状态生成概率得到所述候选词的状态生成代价。

[0028]

5

CN 102609436 A[0036]

说 明 书

3/5页

优选地，所述步骤C2中的状态生成概率的计算公式如下：

[0037]

其中，P(k，rt)表示所述候选词对应k状态的状态生成概率，k等于1或者0。

[0039] 优选地，所述步骤C3中的状态生成代价C-G(k，rt)的计算公式如下：[0040] C-G(k，rt)＝-ln(P(k，rt))。[0041] 优选地，所述状态转移代价的计算公式如下：

[0038] [0042]

其中，(Si’，Si’+1...Si’+q-1)表示由1或者0构成的备选状态序列中的相邻的q个状态，q的取值是2、3或者4，i’为自然数；将所述q个状态分为m组，要求组内状态连续并且状态值相同，相邻组的状态值不同，aj表示第j个组中的状态的个数，1≤j≤m；γ表示转移代价系数。

[0044] (三)有益效果

[0045] 本发明所述社交网络热词和事件挖掘系统及方法，采用泊松分布计算状态生成概率，避免了总的社交网络文本数dt波动大的问题；对不同的时间点分别计算状态参数，克服了周期性热词问题；采用多状态转移代价，是热词挖掘结果更平滑。综上，本发明的系统和方法提高了热词挖掘的准确度。

[0043]

附图说明

图1是本发明的社交网络热词和事件挖掘系统的模块结构示意图；

[0047] 图2是本发明的社交网络热词和事件挖掘方法流程图。

[0046]

具体实施方式

[0048] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0049] 图1是本发明的社交网络热词和事件挖掘系统的模块结构示意图。如图1所示，所述系统包括：信息统计模块100、状态参数模块200、生成代价模块300、状态序列模块400和转移代价模块500。

[0050] 所述信息统计模块100，用于对候选词进行统计，得到相应的候选词序列。所述状态参数模块200，用于根据所述候选词序列，计算所述候选词在不同时间点的状态参数。所述生成代价模块300，用于根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价。所述转移代价模块500，根据所述备选状态序列，计算所述候选词的状态转移代价。所述状态序列模块400，用于提供所述备选状态序列，并根据所述候选词序列、状态参数、状态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。

[0051] 图2是本发明的社交网络热词和事件挖掘方法流程图。如图2所示，所述方法包

6

CN 102609436 A

说 明 书

4/5页

括：

步骤A：所述信息统计模块100对候选词进行统计，得到相应的候选词序列r1，...rn-1>。所述候选词序列包括：通过统计各个时间点包含所述候选词的社交网络文本数得到的一个时间段上的词频序列，或者通过统计各个时间点包含所述候选词且是转发的社交网络文本数得到的一个时间段上的转发序列，或者通过统计各个时间点包含所述候选词且是原创的社交网络文本数得到的一个时间段上的原创序列，或者通过统计各个时间点发送包含所述候选词的社交网络文本的用户的数量得到的一个时间段上的用户序列，或者通过统计各个时间点包含URL(Universal Resource Locator，统一资源定位符)信息且包含所述候选词的社交网络文本数量得到的一个时间段上的URL序列。本实施例所述方法可以对上述一种或者多种候选词序列进行热词挖掘，得到一组或多组标注序列，多组序列间可以相互补充得到最优序列，其中时间点以小时为单位，比如2011年10月1日10点。[0053] 步骤B：所述状态参数模块200根据所述候选词序列，计算所述候选词在不同时间点的状态参数。考虑到t时间点上包含所述候选词的社交网络文本数rt远小于t时间点上总的社交网络文本数dt，并且dt在不同时间点波动较大，本发明方法舍弃dt，并采用泊松分布计算所述候选词在某个时间点t的生成概率。因此，所述状态参数为泊松分布参数；并且为了克服社交网络上小时级的周期性热词问题，所述方法对一天中24个时间点，分别通过计算均值的方法计算所述候选词的0状态参数和1状态参数。[0054] 所述0状态参数的计算公式如下：

[0052] [0055]

其中，λ0，i表示每天24小时中第i个时间点的0状态参数，0≤i≤23；rt表示

所述候选词序列中第t个时间点对应的数据，t为自然数；n表示所述候选词序列中时间点的总数。

[0057] 所述1状态参数的计算公式如下：[0058] λ1，i＝βλ0，i；[0059] 其中，λ1，β表示热度系数，并i表示每天24小时中第i个时间点的1状态参数；且β＞1。β可以直观的理解为词的热度标准，即热词的出现频率应该为普通状态下的β倍。显然，β越大，对热词状态的标准越高，提取出的热词的精度就越高。并且，β的经验值为3。

[0060] 步骤C：提供备选状态序列，根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成代价。

[0061] 所述步骤C具体包括步骤：[0062] C1：所述状态序列模块通过韦特比算法过程提供备选状态序列。由于传统韦特比算法只考虑相邻两个状态的转移，而本发明实施例则考虑相邻q个状态，因此要将传统韦特比算法的状态转移扩展的相邻q个状态。对于只考虑之前1个状态的传统韦特比算法，每个时间点可能的状态数实际为2^1；以此类推，本发明实施例需要考虑之前q-1个状态，每个时间点可能的状态数为2^(q-1)，为这些状态编号0，1，...(2^(q-1))-1；这样，当一个

[0056]

7

CN 102609436 A

说 明 书

5/5页

时间点的状态取值为S(0＜＝S＜2^(q-1))时，S只依赖于前一个时间点的两个状态，分别为(S&(2^(q-2)-1))＜＜1和((S&(2^(q-2)-1))＜＜1)+1。[0063] C2：所述生成代价模块根据所述候选词序列、状态参数和备选状态序列，计算所述候选词的状态生成概率。所述步骤C2中的状态生成概率的计算公式如下：

[0064]

其中，P(k，rt)表示所述候选词对应k状态的状态生成概率，k等于1或者0。

[0066] C3：所述生成代价模块根据所述状态生成概率得到所述候选词的状态生成代价。所述步骤C3中的状态生成代价C-G(k，rt)的计算公式如下：[0067] C-G(k，rt)＝-ln(P(k，rt))。[0068] 步骤D：根据所述备选状态序列，计算所述候选词的状态转移代价。所述状态转移代价的计算公式如下：

[0065] [0069]

其中，(Si’，Si’+1...Si’+q-1)表示由1或者0构成的备选状态序列

中的相邻的q个状态，q的一般的取值是2、3或者4，q的值越大，热词挖掘的结果越平滑，i’为自然数；将所述q个状态分为m组，要求组内状态连续并且状态值相同，相邻组的状态值不同，aj表示第j个组中的状态的个数，1≤j≤m；γ表示转移代价系数，用于调整状态转移代价的影响，显然γ越大，状态转移代价越大，热词挖掘的精度则越高，反之，热词挖掘的精度会越低。并且，γ的经验值为10。[0071] 步骤E：所述状态序列模块根据所述候选词序列、状态参数λk，状i、态生成代价和状态转移代价对所述备选状态序列进行筛选，得到总代价最小的状态序列。所述总代价依赖于相邻q个状态，其目标函数如下：

[0070] [0072]

本发明实施例所述社交网络热词和事件挖掘系统及方法，采用泊松分布计算状态生成概率，避免了总的社交网络文本数dt波动大的问题；对不同的时间点分别计算状态参数，克服了周期性热词问题；采用多状态转移代价，使热词挖掘结果更平滑。综上，本发明实施例所述系统和方法提高了热词挖掘的准确度。[0074] 以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。

[0073]

8

CN 102609436 A

说 明 书 附 图

1/2页

图1

9

CN 102609436 A

说 明 书 附 图

2/2页

图2

10