“智能问诊”项目——数据匹配（1）

小鱼儿 2022-06-05 04:16 520阅读 0赞

之前在这个项目中症状与药品的匹配是另外一个队友做的，我一直没有仔细研究，今天有时间就大概看了一下，在这里总结一下。

首先，这个检索过程用到了levenshtein算法，也就是求编辑距离，先来解释一下这个算法的原理：

**编辑距离定义：**

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

许可的编辑操作包括：将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将eeba转变成abac：

1.  eba（删除第一个e）
2.  aba（将剩下的e替换成a）
3.  abac（在末尾插入c）

所以eeba和abac的编辑距离就是3

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

算法：

算法就是简单的线性动态规划（最长上升子序列就属于线性动态规划）。

设我们要将s1变成s2

定义状态矩阵edit\[len1\]\[len2\]，len1和len2分别是要比较的字符串s1和字符串s2的长度+1（+1是考虑到动归中，一个串为空的情况）

然后，定义edit\[i\]\[j\]是s1中前i个字符组成的串，和s2中前j个字符组成的串的编辑距离

具体思想是，对于每个i，j从0开始依次递增，对于每一次j++，由于前j-1个字符跟i的编辑距离已经求出，所以只用考虑新加进来的第j个字符即可

插入操作：在s1的前i个字符后插入一个字符ch，使得ch等于新加入的s2\[j\]。于是插入字符ch的编辑距离就是edit\[i\]\[j-1\]+1

删除操作：删除s1\[i\]，以期望s1\[i-1\]能与s2\[j\]匹配（如果s1\[i-1\]前边的几个字符能与s2\[j\]前边的几个字符有较好的匹配，那么这么做就能得到更好的结果）。另外，对于s1\[i-1\]之前的字符跟s2\[j\]匹配的情况，edit\[i-1\]\[j\]中已经考虑过。于是删除字符ch的编辑距离就是edit\[i-1\]\[j\]+1

替换操作：期望s1\[i\]与s2\[j\]匹配，或者将s1\[i\]替换成s2\[j\]后匹配。于是替换操作的编辑距离就是edit\[i-1\]\[j-1\]+f(i,j)。其中，当s1\[i\]==s2\[j\]时，f(i,j)为0；反之为1

于是动态规划公式如下：

*  if i == 0 且 j == 0，edit(i, j) = 0
 *  if i == 0 且 j > 0，edit(i, j) = j
 *  if i > 0 且j == 0，edit(i, j) = i
 *  if 0 < i ≤ 1 且 0 < j ≤ 1 ，edit(i, j) == min\{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) \}，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

Python实现：

官方扩展包：

python有一个官方扩展包（在pypi里面，即python package index），叫做python-Levenshtein，这个包不仅可以计算编辑距离，还能计算hamming（汉明）距离，Jaro-Winkler距离等，链接如下：

[https://pypi.python.org/pypi/python-Levenshtein][https_pypi.python.org_pypi_python-Levenshtein]

下载python-Levenshtein-0.10.2.tar.gz，解压后，cd到解压后的文件夹，执行：

python setup.py build

python setup.py install

即可。

注意：如果没有安装setuptools的话要先安装setuptools，链接如下：

[https://pypi.python.org/pypi/setuptools/][https_pypi.python.org_pypi_setuptools]

下载setuptools 0.6c11即可，解压后，cd到对应目录，执行：

python setup.py build

python setup.py install

即可。

检查是否安装成功：进入python，执行from Levenshtein import \*，如果没有报错则安装成功

具体使用方法见如下博文（这边博文下方还有完整的使用文档的连接）：

[http://www.cnblogs.com/kaituorensheng/archive/2013/05/18/3085653.html][http_www.cnblogs.com_kaituorensheng_archive_2013_05_18_3085653.html]

注意：如果采用from Levenshtein import \*导入，则调用函数的时候不用加Levenshtein.

例如：直接调用distance(str1, str2)即可计算编辑距离

简单的实现代码：

如果你想要更加轻量级的实现的话，就用下面的代码吧：

（选自边苏涛的博客，[http://biansutao.iteye.com/blog/326008][http_biansutao.iteye.com_blog_326008]）

# \[python\] [view plain][] [copy][view plain]  \#!/user/bin/env python  \# -\*- coding: utf-8 -\*-  **class** arithmetic():   **def** \_\_init\_\_(self):   **pass**  ''''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''  **def** levenshtein(self,first,second):   **if** len(first) > len(second):    first,second = second,first   **if** len(first) == 0:   **return** len(second)   **if** len(second) == 0:   **return** len(first)    first\_length = len(first) + 1   second\_length = len(second) + 1   distance\_matrix = \[range(second\_length) **for** x **in** range(first\_length)\]   \#print distance\_matrix  **for** i **in** range(1,first\_length):   **for** j **in** range(1,second\_length):    deletion = distance\_matrix\[i-1\]\[j\] + 1   insertion = distance\_matrix\[i\]\[j-1\] + 1   substitution = distance\_matrix\[i-1\]\[j-1\]   **if** first\[i-1\] != second\[j-1\]:    substitution += 1   distance\_matrix\[i\]\[j\] = min(insertion,deletion,substitution)   **print** distance\_matrix   **return** distance\_matrix\[first\_length-1\]\[second\_length-1\]   **if** \_\_name\_\_ == "\_\_main\_\_":    arith = arithmetic()   **print** arith.levenshtein('GUMBOsdafsadfdsafsafsadfasfadsfasdfasdfs','GAMBOL00000000000dfasfasfdafsafasfasdfdsa' #

而在我们的项目中的实现方法是这样的

#key[1] = u"肾性高血压"
                #key[2] = u"心功能不全"
                #key[3] = u"充血性心力衰竭"
                #key[4] = u"高血压病"
                #key[5] = u"高血脂"
                keys = [key[0], key[1], key[2], key[3], key[4]] #五个关键词
    
                weight1 = 2.0 
                weight2 = 1.75
                weight3 = 1.5
                weight4 = 1.25
                weight5 = 1.0
                keysWeight = [weight1, weight2, weight3, weight4, weight5] #关键词对应权重
    
                diseaseWeight = 1.0
                symptomWeight = 0.8
                drugWeight = 0.6
                colsWeight = [diseaseWeight, symptomWeight, drugWeight]
    
                ansNum = 10
    
                self.matchKeyWords(path, keys, keysWeight, colsWeight, ansNum) #计算levenshtein距离

总而言之，还是将两个字符串进行比较，求出将一个字符串变为另一个所需要的最小操作次数，但是这种做法还是比较基本的字符串匹配，也就是“文本相似度”，对于近义词，尤其是药品与症状的对应关系可能并不能很好的解决，这可能也是导致模型效果不理想的原因，接下来在这方面可以做一些优化，比如研究一下TF-IDF之类的算法

参考资料：http://blog.csdn.net/luo123n/article/details/9999481

[https_pypi.python.org_pypi_python-Levenshtein]: https://pypi.python.org/pypi/python-Levenshtein
[https_pypi.python.org_pypi_setuptools]: https://pypi.python.org/pypi/setuptools/
[http_www.cnblogs.com_kaituorensheng_archive_2013_05_18_3085653.html]: http://www.cnblogs.com/kaituorensheng/archive/2013/05/18/3085653.html
[http_biansutao.iteye.com_blog_326008]: http://biansutao.iteye.com/blog/326008
[view plain]: http://blog.csdn.net/luo123n/article/details/9999481#