一种基于KNN的动态事件聚类和提取的方法

1.一种动态事件聚类方法，其特征在于，该方法包括如下步骤：
(1)抽取新文档D关键词；
(2)计算选出新文档D的邻居文档；
(3)判断新文档D的事件归属；
所述步骤(1)包括如下步骤：
A.用切词工具去除新文档D中的停用词以及标注词性和人名；
B.按下式计算每个词在新文档D中的权重：
tft,d为特征词在文档d中的词频；tfmax为新闻中最大的词频值，D为新闻库文档总数，dft为关键词t出现的文档频率；
C.选出20个权重高的词作为新文档D的关键词；
所述步骤(2)包括如下步骤：
A.将邻居节点中的每篇文档的20个关键词建立倒排链表，每个链表按文档id排序，在
20个倒排链表中寻找和新文档D有5个以上的相同关键词的文档作为备选文档；
B.根据关键词计算备选文档和新文档D的相似度，将相似度超过初设阈值N的文档作为邻居文档。
2.根据权利要求1所述动态事件聚类方法，其特征在于，所述邻居节点为近4天的有效数据文档。
3.根据权利要求1所述动态事件聚类方法，其特征在于，所述步骤(3)的步骤如下：
A.从邻居文档中选出一篇与新文档D距离最近的文档；
B.判断距离是否小于初设阈值M；
B-1.若小于则新文档D和距离最近的文档为同一事件，更新该事件；
B-2若不小于则判断新文档D与邻居事件的归属。
4.根据权利要求3所述动态事件聚类方法，其特征在于，判断新文档D与邻居事件归属的步骤如下：
a、通过邻居文档的事件分布计算新文档D邻居事件的归属度，选取归属度最高和第二高的事件E1、E2；
b、判断E1的归属度是否高于初设阈值W；
b-1、若不高于阈值W则新文档D为独立的新事件，建立事件E3，建立指纹事件映射，操作结束；
b-2、若高于阈值W则新文档D属于事件E1；
c、从新文档D中抽取前10个关键词作为核心词，更新事件E1的核心词，同时将这10个核心词添加到核心词表中；
d、重新计算事件E1和E2之间的距离；
e、判断两个事件之间的距离是否高于初设阈值G；
e-1、若不高于则合并事件E1和E2为E1，更新事件E1，建立指纹事件映射，并将事件E2指纹映射指向E1；
e-2、若高于则操作结束。
5.根据权利要求1所述动态事件聚类方法，其特征在于，所述事件属性包括地域和新闻类型。
6.一种事件提取的方法，其特征在于，所述方法的步骤如下：
A、采用如权利要求1至4任一所述的方法进行事件聚类；
B、选择事件搜索范围，包括事件脉络和单一事件；
C、使用切词工具切分查询词；
D、通过核心词表过滤查询词；
E、判断查询词在核心词表的比例是否高于初设阈值P；
E-1、若不高于则无结果直接返回；
E-2、若高于则根据初设范围进行事件脉络搜索或单一事件搜索。
7.根据权利要求6所述事件提取的方法，其特征在于，所述事件脉络搜索的步骤如下：
a、核心词倒排查找满足条件的事件集合；
b、断符合条件事件脉络事件是否大于初设阈值Q；
b-1、若大于则形成脉络，输出事件集合；
b-2、若不大于则不构成脉络，无结果返回。
8.根据权利要求6所述事件提取的方法，其特征在于，所述单一事件搜索的步骤如下：
a、核心词倒排查询最近的大堆事件；
b、事件是否存在；
b-1、若存在则返回该事件；
b-2、若不存在则无结果返回。

一种基于KNN的动态事件聚类和提取的方法\n技术领域\n[0001] 本发明涉及一种动态事件的处理方法，具体涉及一种基于KNN的动态事件聚类及事件提取的方法。\n背景技术\n[0002] 如今是网络迅速发展的年代，新闻阅读已成为大多数网民每天必不可少的一种行为，每天也同时有海量的新闻被无数的媒体发布出来，如何能从这些媒体中选取重要的新闻和感兴趣的新闻来阅读，已经成为了大众的需求，所以就有了新闻事件的概念，百度公司已经推出了一种提取事件脉络的方法，用来向用户展示事件随时间变化的主要节点。\n[0003] KNN是一种聚类算法，全称是K最邻近结点算法(k-Nearest Neighbor algorithm)。\n[0004] 百度公司的事件脉络生成方式是以离线数据为基础，将一段时间内的数据通过关键词的方式提取媒体报道，根据媒体报道的热度聚集点来提取事件的脉络节点，由于不是实时的，所以必然会有滞后，对于新闻来说，时效性不高。\n发明内容\n[0005] 为了克服上述现有技术的不足，本发明提供一种基于KNN的动态事件聚类和提取的方法，本方法基于KNN聚类算法，实现对动态事件的聚类和提取，可随时获得最新的新闻事件，并对事件进行归类。\n[0006] 为了实现上述发明目的，本发明采取如下技术方案：\n[0007] 一种动态事件聚类方法，该方法步骤如下：\n[0008] (1)抽取新文档D关键词；\n[0009] (2)计算选出新文档D的邻居文档；\n[0010] (3)判断新文档D的事件归属。\n[0011] 本发明提供的优选技术方案中，所述步骤(1)抽取关键词的步骤如下：\n[0012] A.使用切词工具去除新文档D中的停用词以及标注词性和人名；\n[0013] B.计算每个词在新文档D中的权重，计算公式如下：\n[0014]\n[0015] tft,d为特征词在文档d中的词频；tfmax为新闻中最大的词频值，D为新闻库文档总数，dft为关键词t出现的文档频率；\n[0016] C.选出20个权重高的词作为新文档D的关键词。\n[0017] 本发明提供的第二优选技术方案中，所述步骤(2)选出邻居文档的步骤如下：\n[0018] A.将邻居节点中的每篇文档的20个关键词建立倒排链表，每个链表按文档id排序，在20个倒排链表中寻找和新文档D有5个以上的相同关键词的文档作为备选文档；\n[0019] B.根据关键词计算备选文档和新文档D的相似度，将相似度超过初设阈值N的文档作为邻居文档。\n[0020] 本发明提供的第三优选技术方案中，所述邻居节点为近4天的有效数据文档。\n[0021] 本发明提供的第四优选技术方案中，所述步骤(3)判断事件归属的步骤如下：\n[0022] A.从邻居文档中选出一篇与新文档D距离最近的文档；\n[0023] B.判断距离是否小于初设阈值M；\n[0024] B-1.若小于则新文档D和距离最近的文档为同一事件，更新该事件；\n[0025] B-2若不小于则判断新文档D与邻居事件的归属。\n[0026] 本发明提供的第五优选技术方案中，判断新文档D与邻居事件归属的步骤如下：\n[0027] a、通过邻居文档的事件分布计算新文档D邻居事件的归属度，选取归属度最高和第二高的事件E1、E2；\n[0028] b、判断E1的归属度是否高于初设阈值W；\n[0029] b-1、若不高于阈值W则新文档D为独立的新事件，建立事件E3，建立指纹事件映射，操作结束；\n[0030] b-2、若高于阈值W则新文档D属于事件E1；\n[0031] c、从新文档D中抽取前10个关键词作为核心词，更新事件E1的核心词，同时将这10个核心词添加到核心词表中；\n[0032] d、重新计算事件E1和E2之间的距离；\n[0033] e、判断两个事件之间的距离是否高于初设阈值G；\n[0034] e-1、若不高于则合并事件E1和E2为E1，更新事件E1，建立指纹事件映射，并将事件E2指纹映射指向E1；\n[0035] e-2、若高于则操作结束。\n[0036] 本发明提供的第六优选技术方案中，一种事件提取的方法，所述方法的步骤如下：\n[0037] A、采用如权利要求1至6任一所述的方法进行事件聚类；\n[0038] B、选择事件搜索范围，包括事件脉络和单一事件；\n[0039] C、使用切词工具切分查询词；\n[0040] D、通过核心词表过滤查询词；\n[0041] E、判断查询词在核心词表的比例是否高于初设阈值P；\n[0042] E-1、若不高于则无结果直接返回；\n[0043] E-2、若高于则根据初设范围进行事件脉络搜索或单一事件搜索。\n[0044] 本发明提供的第七优选技术方案中，所述事件脉络搜索的步骤如下：\n[0045] a、通过核心词倒排查找满足条件的事件集合；\n[0046] b、判断符合条件事件脉络事件是否大于初设阈值Q；\n[0047] b-1、若大于则形成脉络，输出事件集合；\n[0048] b-2、若不大于则不构成脉络，无结果返回。\n[0049] 本发明提供的第八优选技术方案中，所述单一事件搜索的步骤如下：\n[0050] a、通过核心词倒排查询最近的大堆事件；\n[0051] b、判断事件是否存在；\n[0052] b-1、若存在则返回该事件；\n[0053] b-2、若不存在则无结果返回。\n[0054] 与现有技术相比，本发明的有益效果在于：\n[0055] 本方法随时获得最新的新闻事件，无需进行人工干预，全自动进行整理和准备文档库的操作，在事件的属性中添加了分类信息，将事件进行归类，事件的输出多样化，可根据所需来提取。\n附图说明\n[0056] 图1是添加文档事件过程流程图\n[0057] 图2是根据核心词查询事件流程图\n具体实施方式\n[0058] 下面结合附图对本发明作进一步详细说明。\n[0059] 如图1所示，添加文档事件的具体步骤如下：\n[0060] A.使用切词工具去除新文档D中的停用词以及标注词性和人名；\n[0061] B.计算每个词在新文档D中的权重，计算公式如下：\n[0062]\n[0063] tft,d为特征词在文档d中的词频；tfmax为新闻中最大的词频值，D为新闻库文档总数，dft为关键词t出现的文档频率；\n[0064] C.选出20个权重高的词作为新文档D的关键词；\n[0065] D将邻居节点中的每篇文档的20个关键词建立倒排链表，每个链表按文档id排序，在20个倒排链表中寻找和新文档D有5个以上的相同关键词的文档作为备选文档；\n[0066] E根据关键词计算备选文档和新文档D的相似度，将相似度超过初设阈值N的文档作为邻居文档；\n[0067] F从邻居文档中选出一篇与新文档D距离最近的文档；\n[0068] G判断距离是否小于初设阈值M；\n[0069] G-1若小于则新文档D和距离最近的文档为同一事件，更新该事件；\n[0070] G-2若不小于则判断新文档D与邻居事件的归属；\n[0071] 判断新文档D与另据事件的归属的具体步骤如下：\n[0072] a、通过邻居文档的事件分布计算新文档D邻居事件的归属度，选取归属度最高的事件E1和第二高的事件E2；\n[0073] b、判断E1的归属度是否高于初设阈值W；\n[0074] b-1、若不高于阈值W则新文档D为独立的新事件，建立事件E3，建立指纹事件映射，操作结束；\n[0075] b-2、若高于阈值W则新文档D属于事件E1；\n[0076] c、从新文档D中抽取前10个关键词作为核心词，更新事件E1的核心词，同时将这10个核心词添加到核心词表中；\n[0077] d、重新计算事件E1和E2之间的距离；\n[0078] e、判断两个事件之间的距离是否高于初设阈值G；\n[0079] e-1、若不高于则合并事件E1和E2为E1，更新事件E1，建立指纹事件映射，并将事件E2指纹映射指向E1；\n[0080] e-2、若高于则操作结束。\n[0081] 事件搜索分三种，一是热门事件搜索，此搜索无需关键词，只需给定时间范围即可，二是事件脉络或热门人物事件搜索，需要给定关键词和时间范围，三是焦点事件搜索，搜索单一事件。\n[0082] 热门事件搜索，会选取时间范围内的报道量最多的事件集合，焦点事件和事件脉络都需要查询词来进行搜索，具体查询运用核心词查询事件的方法进行搜索。\n[0083] 如图2所示，通过核心词查询事件的方法，具体步骤如下：\n[0084] A、采用如图1所示的方法进行事件聚类；\n[0085] B、选择事件搜索范围，包括事件脉络和单一事件；\n[0086] C、使用切词工具切分查询词；\n[0087] D、通过核心词表过滤查询词；\n[0088] E、判断查询词在核心词表的比例是否高于初设阈值P；\n[0089] E-1、若不高于则无结果直接返回；\n[0090] E-2、若高于则根据初设范围进行事件脉络搜索或单一事件搜索。\n[0091] 所述事件脉络搜索的步骤如下：\n[0092] a、通过核心词倒排查找满足条件的事件集合；\n[0093] b、判断符合条件事件脉络事件是否大于初设阈值Q；\n[0094] b-1、若大于则形成脉络，输出事件集合；\n[0095] b-2、若不大于则不构成脉络，无结果返回。\n[0096] 所述单一事件搜索的步骤如下：\n[0097] a、通过核心词倒排查询最近的大堆事件；\n[0098] b、判断事件是否存在；\n[0099] b-1、若存在则返回该事件；\n[0100] b-2、若不存在则无结果返回。\n[0101] 事件的属性主要包括地域和分类，地域指事件发生的地点，大到国内、国外，小到省市，都可以由事件内文档的具体地域投票选出；分类指财经新闻，军事新闻，体育新闻等多种新闻类别，之所以提供地域和分类属性，是为了查询的时候可以通过这些属性来过滤，从而产生频道事件数据。\n[0102] 最后应当说明的是：以上实施例仅用以说明本发明的技术方案而非对其限制，尽管参照上述实施例对本发明进行了详细的说明，所属领域的普通技术人员应当理解：依然可以对本发明的具体实施方式进行修改或者等同替换，而未脱离本发明精神和范围的任何修改或者等同替换，其均应涵盖在本发明的权利要求范围当中。