MMR算法学习

　

mmr

MMR

MMR的全称为Maximal Marginal Relevance ，中文名字为最大边界相关法或者最大边缘相关。

在MMR的公式是这样的，截图来自http://www.cnblogs.com/little-horse/p/7191287.html

由于我们算的是自动摘要，所以主要看下面的公式。

左边的score计算的是句子的重要性分值，右边的计算的是句子与所有已经被选择成为摘要的句子之间的相似度最大值，注意这里的是负号，说明成为摘要的句子间的相似度越小越好。此处体现了MMR的算法原理，即均衡考虑了文章摘要的重要性和多样性。这种摘要提取方式与textrank不同，textrank只取全文的重要句子进行排序形成摘要，忽略了其多样性。

对于一篇文档，计算当前句子Q在全文中的相似度，MMR认为，对于相似度全文排名越高的表示为重要性越高。这里的相似度一般为余弦相似度，原来的论文就是cos。推荐介绍的两篇论文都有写到一些计算相似度的算法，可以研究研究。

代码来自：https://github.com/fajri91/Text-Summarization-MMR/blob/master/mmr.py 改写成中文摘要：

[python] view plain copy

1. # -*- coding: utf-8 -*-  
2. """ 
3. Created on Thu Sep  7 17:10:57 2017 
4.  
5. @author: Mee 
6. """  
7.   
8. import os  
9. import re  
10. import jieba  
11. from sklearn.feature_extraction.text import CountVectorizer  
12. from sklearn.metrics.pairwise import cosine_similarity  
13. import operator  
14.   
15. f=open(r'C:\Users\user\Documents\Python Scripts/stopword.dic')#停止词    
16. stopwords = f.readlines()    
17. stopwords=[i.replace("\n","") for i in stopwords]     
18.   
19. def cleanData(name):  
20.     setlast = jieba.cut(name, cut_all=False)  
21.     seg_list = [i.lower() for i in setlast if i not in stopwords]  
22.     return " ".join(seg_list)  
23.   
24. def calculateSimilarity(sentence, doc):#根据句子和句子，句子和文档的余弦相似度   
25.     if doc == []:  
26.         return 0  
27.     vocab = {}  
28.     for word in sentence.split():  
29.         vocab[word] = 0#生成所在句子的单词字典，值为0  
30.       
31.     docInOneSentence = '';  
32.     for t in doc:  
33.         docInOneSentence += (t + ' ')#所有剩余句子合并  
34.         for word in t.split():  
35.             vocab[word]=0    #所有剩余句子的单词字典，值为0  
36.       
37.     cv = CountVectorizer(vocabulary=vocab.keys())  
38.   
39.     docVector = cv.fit_transform([docInOneSentence])  
40.     sentenceVector = cv.fit_transform([sentence])  
41.     return cosine_similarity(docVector, sentenceVector)[0][0]  
42.       
43. data=open(r"C:\Users\user\Documents\Python Scripts\test.txt")#测试文件  
44. texts = data.readlines()#读行  
45. texts=[i[:-1] if i[-1]=='\n' else i for i in texts]    
46.   
47. sentences = []  
48. clean = []  
49. originalSentenceOf = {}  
50.       
51. import time  
52. start = time.time()  
53.   
54. #Data cleansing  
55. for line in texts:  
56.     parts = line.split('。')[:-1]#句子拆分  
57. #   print (parts)   
58.     for part in parts:  
59.         cl = cleanData(part)#句子切分以及去掉停止词  
60. #       print (cl)  
61.         sentences.append(part) #原本的句子  
62.         clean.append(cl) #干净有重复的句子  
63.         originalSentenceOf[cl] = part #字典格式  
64. setClean = set(clean) #干净无重复的句子  
65.           
66. #calculate Similarity score each sentence with whole documents        
67. scores = {}  
68. for data in clean:  
69.     temp_doc = setClean - set([data])#在除了当前句子的剩余所有句子  
70.     score = calculateSimilarity(data, list(temp_doc)) #计算当前句子与剩余所有句子的相似度  
71.     scores[data] = score#得到相似度的列表  
72.     #print score  
73.   
74.   
75. #calculate MMR  
76. n = 25 * len(sentences) / 100 #摘要的比例大小  
77. alpha = 0.7  
78. summarySet = []  
79. while n > 0:  
80.     mmr = {}  
81.     #kurangkan dengan set summary  
82.     for sentence in scores.keys():  
83.         if not sentence in summarySet:  
84.             mmr[sentence] = alpha * scores[sentence] - (1-alpha) * calculateSimilarity(sentence, summarySet) #公式      
85.     selected = max(mmr.items(), key=operator.itemgetter(1))[0]    
86.     summarySet.append(selected)  
87. #   print (summarySet)  
88.     n -= 1  
89.   
90. #rint str(time.time() - start)  
91.       
92. print ('\nSummary:\n')  
93. for sentence in summarySet:  
94.     print (originalSentenceOf [sentence].lstrip(' '))  
95. print ('=============================================================')  
96. print ('\nOriginal Passages:\n')  

test.txt文本如下：

[plain] view plain copy

1. 米家行车记录仪正式发布，告别驾驶孤单。继上周70迈智能后视镜在小米众筹上线，数小时便完成了目标众筹之后，今日小米生态链布局中的另一个车载智能新产品，米家行车记录仪正式上线小米商城，售价349元。米家行车记录仪搭载了SONY IMX323图像传感器，感光度高的CMOS可以全面提升暗光环境下的成像表现，感光元件大至1/2.9英寸，阴天或者夜景等弱光条件下，影像画面品质优势尽显。  
2. 同时搭载了Mstar的全高清影像处理芯片，具备1080P的图像处理技术。采用的耐高温胶和静电贴组合简单又安全，单指就可以进行触摸按键，160°超广角，覆盖三车道安全全方位。米家行车记录仪是由小米生态链企业板牙科技所生产，也是唯一一家致力于车载智能产品的小米生态链公司。  
3. 为何小米生态链持续发力车载智能产品?随着中国汽车市场快速蓬勃发展，目前车辆存量已达1.2亿辆，还在以每年2000万以上的速度扩充，但是连载互联网的车辆占比低于5%。  
4. 互联快速发展的时代，未来车辆将成为重要的终端入口之一。2015年，行车记录仪全国各品牌销量在3500万台每年，大量厂商试图挤入这个火热的市场。  
5. 2016下半年，在行业经过大洗牌后，剩下的厂商对自家品牌进行积累，汽车后视镜的2.0时代正式拉开序幕。  
6. 2017年,一家叫做70迈的智能后视镜产品出现在了浪潮之中，其背后同时站着顺为和小米等多家知名VC，这样的产品为何会受到多方投资的关注?  
7. 作为小米生态链企业产品，70迈智能后视镜不惜使用8.88英寸极限高清大屏，“1920*480”高清分辨率，1670万色，搭配高品质银镜7层光学镀膜，完美兼顾界面与镜面。  
8. 屏保界面进入沉浸模式，将导航HUD、ADAS预警与整车自然融为一体。  
9. 70迈创造性的将“小米生态链企业Mai OS/手机App汽车后市场服务”的模式相结合，在智能后视镜完美融合进小米产品体系的同时，用精品模式和数据驱动深挖驾驶场景的价值。  
10. 业内人士表示，未来靠硬件赚大钱已经不再是市场发展主趋势，小米就是一个最好的例子，只有互联网服务才是突破。70迈的产品用户黏性是否足够高，产品更新换代是否足够快，都是70迈一直在专注并打磨持续打磨的环节。  
11. 只有持续保持庞大的用户量，才能保证互联网增值服务的空间与价值。  

生成摘要如下：

Summary:

[plain] view plain copy

1. 米家行车记录仪是由小米生态链企业板牙科技所生产，也是唯一一家致力于车载智能产品的小米生态链公司  
2. 70迈创造性的将“小米生态链企业Mai OS/手机App汽车后市场服务”的模式相结合，在智能后视镜完美融合进小米产品体系的同时，用精品模式和数据驱动深挖驾驶场景的价值  
3. 继上周70迈智能后视镜在小米众筹上线，数小时便完成了目标众筹之后，今日小米生态链布局中的另一个车载智能新产品，米家行车记录仪正式上线小米商城，售价349元  
4. 为何小米生态链持续发力车载智能产品?随着中国汽车市场快速蓬勃发展，目前车辆存量已达1.2亿辆，还在以每年2000万以上的速度扩充，但是连载互联网的车辆占比低于5%  

按照文中的顺序应该是这样的：

[plain] view plain copy

1. 继上周70迈智能后视镜在小米众筹上线，数小时便完成了目标众筹之后，今日小米生态链布局中的另一个车载智能新产品，米家行车记录仪正式上线小米商城，售价349元  
2. 米家行车记录仪是由小米生态链企业板牙科技所生产，也是唯一一家致力于车载智能产品的小米生态链公司  
3. 为何小米生态链持续发力车载智能产品?随着中国汽车市场快速蓬勃发展，目前车辆存量已达1.2亿辆，还在以每年2000万以上的速度扩充，但是连载互联网的车辆占比低于5%  
4. 70迈创造性的将“小米生态链企业Mai OS/手机App汽车后市场服务”的模式相结合，在智能后视镜完美融合进小米产品体系的同时，用精品模式和数据驱动深挖驾驶场景的价值  

另外我觉得需要改进的是：分词算法和停止词库，开头和结尾的重要度需要提升，还有文章中的转折语句重要性也需要提升。

相关阅读

判断素数最有效的算法

目录 定义 1 常规方法判断 2 最有效方法判断 3 测试 定义 约数只有1和本身的整数称为质数，或称素数。 1 常规方法判断 根据定义

遗传算法原理及算法实例

遗传算法原理解析 遗传算法（GA）是一种元启发式自然选择的过程，属于进化算法（EA）大类。遗传算法通常是利用生物启发算子，如变异、交叉和

实时系统动态内存算法分析dsa（二）——TLSF代码分析

上一篇我们看了dsa的分类和简单的内存管理算法实现，这篇文档我们来看TLSF的实现，一种更加高级的内存管理算法；一、实现原理 基本的Se

AI产品经理必懂算法：支持向量机SVM

作为AI产品经理必懂算法的第二篇，来了解一下支持向量机SVM算法，英文全称是“Support Vector Machine”。在机器学习中，SVM是监督学习

非常简单易懂的DOM Diff算法简析

文章整理自阿里云栖视频 DIFF算法在执行时有三个维度，分别是Tree DIFF、Component DIFF和Element DIFF，执行时按顺序依次执行，它们