网络舆情研究：融合上下文信息的热点话题字典生成

构造有判别力的字典对于准确表示话题有着非常重要的意义，不同于文本分类，话题的数量（即类别）是随着时间的变化而变化的，有判别力的词随着时间的变化也在不断变化。结合话题的动态变化特点，本章提出了一种动态的话题字典生成方式。任意话题ti在j时刻的有判别力字典用Wij来表示，其中1≤i≤Lj，Lj为j时刻的话题数量。每类话题选择有判别力的词用于构建本话题的话题字典。

互信息通常被用来计算变量之间的依赖关系，变量之间的互信息值越高，变量之间的依赖性越强。为了选择出不同话题的有判别力词，我们首先用话题与词之间的互信息来衡量不同词在话题中的重要性，计算方法采用式（4-10）计算，此时的类别C表示不同的话题。计算出每个话题与属于该话题的所有词的互信息后，我们将按照互信息值从大到小的顺序对这些词进行排序，排序越靠前，互信息值越大，算法认为每个话题中最靠前的一些词为有判别力的词。据此，可将话题初始字典的构建转变为如下问题：应该从每个话题中选择前多少个词构成有判别力词字典？

为了获得每个话题中有判别力词的数量，算法主要考虑了如下三个方面：①不同话题的有判别力的词不相似。由于有判别力的词能够代表本话题的内容，其本质是希望不同话题的内容不相同。②同一话题中，用有判别力词字典构造的话题表示与用全局字典构造的话题表示相似。这样能够保证构造的话题表示尽可能地保持话题原意。③同一话题有判别力词之间的词序关系相似。同一话题的有判别力词在属于当前话题的不同新闻报道中出现顺序相对固定，不同话题间有判别力词的上下文不固定。

对于某话题ti，在j时刻有判别力词字典可表示为，如果某个词语wi∈tdij，则在tdij中词语wi的出现次数为该词语在话题ti全局字典中的出现次数ki，即=ki，否则=0。基于有判别力词上下文关系的话题内容用to表示，其主要考虑的是报道表示的上下文特征关系。在一个话题的报道中，每次出现一个有判别力的词wl，则td中kl增加1，与此不同的是，在to中，我们不仅考虑wl的出现次数，还考虑了报道中与wl最近的有判别力的上下文信息。假设报道中有判别力词wl的上下文中，与其最近邻的N个有判别力词为wp，wq，…，wr，则在to中，这些有判别力词的出现次数也相应增加1。

图4-3展示了有判别力词的话题表示与基于有判别力词上下文的话题表示的区别。在图4-3（a）中，当话题的报道中出现了词wj，则wj出现的次数加1，在图4-3（b）中，当N=2时，wj的最近的两个有判别力的词为wi和wk，如果这两个词也出现，则这三个词的出现次数都加1。

图4-3　是否考虑上下文信息的话题表示比较

算法认为话题ti中最有判别力的词即为与话题的互信息最大的前ni个词。为了获取不同话题的有判别力词，我们构造了如下目标函数：

Sim（·，·）代表话题表示之间的相似度，L代表话题数量。目标函数的第一项用于衡量不同话题之间有判别力词字典的表示，目标函数希望不同话题表示的相似度尽可能小。第二项用于衡量相同话题的全局表示和有判别力词字典表示的相似度，目标函数希望有判别力的话题表示能够尽可能保持与原话题相似，用以减少特征损失。第三项用于衡量不同话题的有判别力词上下文关系的相似度，目标函数希望不同话题用有判别力词上下文关系生成的话题表示内容不相似。上式实际上是求解多变量ni（1≤ni≤m）使得式（4-18）所示目标函数值最小，该函数可通过坐标下降法对其求解。

自2010年，Nesterov［106］成功地把坐标下降法应用于大规模数据最优化问题，坐标下降法得到了广泛的关注和应用，主要用于解决多变量最优化问题，本书将其应用于求解多个话题变量的初始最优特征子集（初始话题字典）。

假定多变量ni（1≤ni≤m）组成向量X=（n1，n2，…，nm），多变量向量X的求解为多目标求解，过程为：在第一轮循环中，先令分变量n1作为变量，其他m-1个变量（n2，…，nm）作为常量，求解min（f（X（1））），进而得到变量n1的取值1；然后采用相同的方法，依次分别对后面的分量n2，…，nm进行求解。在求解过程中，前面得到的估计值i；当作其所在坐标的变量取值，直到此轮循环结束。举例说明坐标下降法的实现过程，假设有五个变量n1，n2，n3，n4，n5，其最优化求解过程如表4-4所示。

表4-4　坐标下降法求解过程（第一次循环）

首先采用随机函数，生成一个随机值20作为每个变量的初始值，然后将n1视为变量，其他四个变量的取值均为20，求解单变量取多少时，目标函数的值最小（即转化为单变量求解问题），假设获得此时变量n1的取值为10（1）；然后将n2视为变量，其他四个视为取值为20的常量，取得此时目标函数取值最小时变量n2的取值，假设求得的值为25；重复上述操作，直至获得每个变量的单变量最优值，分别为10、25、16、11、18。至此，第一轮循环结束，第二轮循环的执行过程如表4-5所示。

表4-5　坐标下降法求解过程（第二次循环）

观察表4-5可以发现，与表4-4不同，第一行的数字不是随机生成的常量值，而是第一轮循环结束后每个变量对应的i。第二轮循环重复第一轮循环的操作，获得此轮循环中每个变量的最优值（省略号所示）。

重复上述类似循环，直至满足阈值设置要求，实际实验中，很多时候，当循环执行到一定程度后每个变量的最优值不再变化，程序就可以结束。分析上述流程可以发现，坐标下降法的实现过程是一个双层循环，实现算法如下［106］：(www.xing528.com)

输入：初始给定多变量组成的向量X=（n1，n2，…，nm），算法迭代停止参数θ，预设迭代停止轮次参数k；

输出：目标函数f（X）的最优点X*及值f（X*）；

Step1.求解f（X），得到X（1）=（1，n2，…，nm）；

Step2.外循环for i=1 to k；

Step3.内循环for j=1 to m；

Step4.令X（s）=（1（s），1（s），…，nt（s），nt（s-1），…，nm（s-1）），直到第k次迭代满足|f（X（s））-f（X（s-1））|＜θ时，迭代停止；

Step5.得到X*及值f（X*），即变量n1，n2，…，nm的最优解1，2，…，m及阈值对应的目标函数的最优值f（1，2，…，m）。

对于一个新报道s，存在两种情况，即报道属于原有话题或者报道属于某个未知的新话题。为了解决这个问题，算法首先通过如下方式衡量报道s与话题ti的相似性stdi：

将式（4-19）归一化后的相似度度量为：

式（4-19）中的相似度计算采用式（3-20）所示的基于信念的话题相似度计算方法完成。如果新报道s与最相似的话题的相似度大于预设阈值λ，则报道属于与它相似度最大的话题，否则该报道属于一个新的话题。

此外，时序性是新闻话题的典型特征［37］，随着时间的推移话题将不断地更新，如果始终保持话题字典不变，显然不合理。为了动态选取出每个话题所对应的有判别力词，我们在上述研究的基础上，提出了增量式报道字典（incremental story dictionary，ISD）选择算法，步骤如下：

（1）对于当前所有话题，通过求解式（4-18）得到每个话题的初始有判别力词的规模。（2）对于一个新的报道s，通过式（4-20）判断报道所属的话题，如果报道属于旧话题，则把报道加入话题，返回上一步，如果报道属于新的话题，则增加新话题数量，返回上一步。

ISD算法随着报道的不断增加，动态地改变了有判别力的词，因为有判别力词是随着每个新报道的出现而更新的。报道的大量出现必然导致更新频率过高，致使算法效率下降。为了提高算法效率，我们在ISD算法的基础上，提出了批量式报道字典（batch story dictionary，BSD）选择算法，步骤如下：

（1）对于当前时刻c的Lc个话题，通过求解式（4-18）得到每个话题的有判别力词。

（2）对于一组新报道S=｛s1，s2，…，sR｝中的每个报道si（1≤i≤R），通过式（4-20）判断报道所属的话题，如果报道属于旧话题，则把报道加入话题中；否则，将报道si放入集合G中。

（3）如果G为空，转步骤（1）；否则，计算G中每个报道sj与所有话题的相似度，将其组成相似度向量Simsj=（sj1，sj2，…，sjLC），然后采用层次聚类算法将G中的报道聚为r类，LC+1=LC+r。