著录项信息
专利名称 | 一种基于KNN的动态事件聚类和提取的方法 |
申请号 | CN201510063453.3 | 申请日期 | 2015-02-06 |
法律状态 | 授权 | 申报国家 | 中国 |
公开/公告日 | 2015-05-20 | 公开/公告号 | CN104636461A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F17/30 | IPC分类号 | G;0;6;F;1;7;/;3;0查看分类表>
|
申请人 | 北京中搜网络技术股份有限公司 | 申请人地址 | 北京市海淀区北三环西路43号院2号楼5层08-09号
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 北京中搜云商网络技术有限公司 | 当前权利人 | 北京中搜云商网络技术有限公司 |
发明人 | 张鹏飞;赵晓亮 |
代理机构 | 北京安博达知识产权代理有限公司 | 代理人 | 徐国文 |
摘要
本发明提供一种基于KNN的动态事件聚类和提取的方法,本方法基于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] 最后应当说明的是:以上实施例仅用以说明本发明的技术方案而非对其限制,尽管参照上述实施例对本发明进行了详细的说明,所属领域的普通技术人员应当理解:依然可以对本发明的具体实施方式进行修改或者等同替换,而未脱离本发明精神和范围的任何修改或者等同替换,其均应涵盖在本发明的权利要求范围当中。
法律信息
- 2023-01-17
未缴年费专利权终止
IPC(主分类): G06F 17/30
专利号: ZL 201510063453.3
申请日: 2015.02.06
授权公告日: 2018.10.23
- 2018-10-23
- 2017-05-17
专利申请权的转移
登记生效日: 2017.04.27
申请人由北京中搜网络技术股份有限公司变更为北京中搜云商网络技术有限公司
地址由100191 北京市海淀区学院路51号首亨科技大厦0902室变更为100086 北京市海淀区北三环西路43号院2号楼5层08-09号
- 2015-06-17
实质审查的生效
IPC(主分类): G06F 17/30
专利申请号: 201510063453.3
申请日: 2015.02.06
- 2015-05-20
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有引用任何外部专利数据! |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |