继续寒冷

    今天是清明节前的一天，我仔细思路了一下前一段研究日志模式处理时的方法。发现关于层次聚类时有一个
弊端我当时忽略了，就是关于距离度量的问题，我选择的方法会出现距离为无穷大的情况，这样显然是不合理的！
因此今天我就寻找了一天关于距离度量的论文和相关方法，看能不能找到合理的代替方式。最后找到了几个不错的
方式，周末要总结一下。
    下午3点，办公室就放假了，不过此时外面下起了大雪。春寒到了，为了不让鞋子走湿，我晚上就去了所里
的食堂吃饭，然后就继续回办公室，想着呆到雪停了再走。因为最近在看微积分，因此就上网搜了一下可微可导
的概念，想复习一下，结果知乎上搜到了一个很好的答案，顺着他的答案，一路看下去，把微积分的发展史
给看了一遍……发现看完已经到了该锁门的时间了，于是我就离开了，但是外面的雪下的还是很大！我晕，回去鞋子
还是湿了！

文本相似度度量相关方法

下面内容主要出自wiki百科，从wiki百科里搜索的字符串比较例子如下：

Name	Example
Hamming distance	"karolin" and "kathrin" is 3.
Levenshtein distance and Damerau–Levenshtein distance	kitten and sitting have a distance of 3. kitten → sitten (substitution of "s" for "k") sitten → sittin (substitution of "i" for "e") sittin → sitting (insertion of "g" at the end).
Jaro–Winkler distance	JaroWinklerDist("MARTHA","MARHTA") = $d_{j}={\frac {1}{3}}\left({\frac {m}{\|s_{1}\|}}+{\frac {m}{\|s_{2}\|}}+{\frac {m-t}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944$ $m$ is the number of matching characters; $t$ is half the number of transpositions(`"MARTHA"[3]!=H, "MARHTA"[3]!=T`).
Most frequent k characters	MostFreqKeySimilarity('research', 'seeking', 2) = 2

根据这个表格，我研究尝试了一下各个例子的运行。其中，表格中的前三个距离算法，我直接调用了一个名叫jellyfish的库。该库是包含的字符匹配算法有如下几种：

Levenshtein Distance–>编辑距离
Damerau-Levenshtein Distance
Jaro Distance
Jaro-Winkler Distance
Match Rating Approach Comparison–>匹配评级方法比较
Hamming Distance–>汉明距离

使用方法非常简单：

import jellyfish
jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')

即可，当然，传入的不是字符也行，只要是列表类型的数据即可。比如对于我的分类问题，可以传入： [1,2,34,3]和[1,2,11,3]这样算的编辑距离就是1，非常方便。

对于第四个距离的算法，我们直接在这个网页里面，就可以发现各种语言的实现，直接复制粘贴即可。举个例子：

import collections
def MostFreqKHashing(inputString, K):
    occuDict = collections.defaultdict(int)
    for c in inputString:
        occuDict[c] += 1
    occuList = sorted(occuDict.items(), key = lambda x: x[1], reverse = True)
    outputDict = collections.OrderedDict(occuList[:K])
    #Return OrdredDict instead of string for faster lookup.
    return outputDict 
 
def MostFreqKSimilarity(inputStr1, inputStr2):
    similarity = 0
    for c, cnt1 in inputStr1.items():
        #Reduce the time complexity of lookup operation to about O(1).
        if c in inputStr2: 
            cnt2 = inputStr2[c]
            similarity += cnt1 + cnt2
    return similarity
 
def MostFreqKSDF(inputStr1, inputStr2, K, maxDistance):
    return maxDistance - MostFreqKSimilarity(MostFreqKHashing(inputStr1,K), MostFreqKHashing(inputStr2,K))


str1 = "67676"
str2 = "76765"
K = 3
maxDistance = 100
dict1 = MostFreqKHashing(str1, K)
print("%s:"%dict1)
print(''.join(c + str(cnt) for c, cnt in dict1.items()))
dict2 = MostFreqKHashing(str2, K)
print("%s:"%dict2)
print(''.join(c + str(cnt) for c, cnt in dict2.items()))
print(MostFreqKSDF(str1, str2, K, maxDistance))

2018/04/04 更寒冷

文本相似度度量相关方法

FEATURED TAGS

FRIENDS