快捷導(dǎo)航

Python計算序列相似度的算法實例

更新時間：2023年07月28日 10:35:33 作者：Eyizoha

這篇文章主要介紹了Python計算序列相似度的算法實例,求兩個序列轉(zhuǎn)換的最少交換步驟和最小交換距離,本文提供了部分實現(xiàn)代碼與解決思路,對開發(fā)非常有幫助,需要的朋友可以參考下

Python計算序列相似度的算法

代碼

位方差(location square deviation, LSD)

def location_square_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    lst = lst_1.copy()
    if lst_2 is not None:
        if n != len(lst_2):
            return False
        for i in range(n):	# 以lst2為映射表，將lst1映射為lst可直接與[0,1,2,...]比較
            lst[lst_1.index(lst_2[i])] = i
    s = 0
    for i in range(n):
        s += (lst[i]-i) ** 2
    s /= n
    return s

位均差(location mean deviation, LMD)

def location_mean_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    lst = lst_1.copy()
    if lst_2 is not None:
        if n != len(lst_2):
            return False
        for i in range(n):
            lst[lst_1.index(lst_2[i])] = i
    s = 0
    for i in range(n):
        s += abs(lst[i]-i)
    s /= n
    return s

交換差(swap deviation, SD)

def swap_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    lst = lst_1.copy()
    if lst_2 is not None:
        if n != len(lst_2):
            return False
        for i in range(n):
            lst[lst_1.index(lst_2[i])] = i
    count = 0	# 計算序列中的循環(huán)數(shù)
    for i in range(n):
        if lst[i] == -1:
            continue
        p = i
        while lst[p] != -1:
            q = lst[p]
            lst[p] = -1
            p = q
        count += 1
    return n - count # 序列長減去循環(huán)數(shù)即為最小交換次數(shù)

交換距離差(swap distance deviation, SDD)

def swap_distance_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    lst = lst_1.copy()
    if lst_2 is not None:
        if n != len(lst_2):
            return False
        for i in range(n):
            lst[lst_1.index(lst_2[i])] = i
    swap_lst = []
    weight = 0
    while location_mean_deviation(lst) != 0:
        r_best = 0	# 最佳交換收益
        i_best = 0
        j_best = 0
        for i in range(n):
            for j in range(i+1, n):	# 遍歷所有交換，尋找最佳交換步驟
            	# 交換收益r=交換后位均差的下降值ΔLMD(A,B)/交換距離(j-i)
            	# 令交換距離恒為1可求最少交換步驟&最少交換次數(shù)
                r = ((abs(lst[i]-i)+abs(lst[j]-j)) - (abs(lst[j]-i)+abs(lst[i]-j)))/(j-i)
                if r > r_best:
                    r_best = r
                    i_best = i
                    j_best = j
        lst[i_best], lst[j_best] = lst[j_best], lst[i_best]
        weight += (j_best-i_best)
        swap_lst.append((i_best, j_best))
    # return swap_lst # 求最小交換距離的步驟（交換距離為1則是求最少交換步驟）
    return weight

值方差(value square deviation, VSD)

def value_square_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    if lst_2 is not None:
        if n != len(lst_2):
            return False
    else:
        lst_2 = [i for i in range(n)]
    s = 0
    for i in range(n):
        s += (lst_1[i] - lst_2[i]) ** 2
    s /= n
    return s

值均差(value mean deviation, VMD)

def value_mean_deviation(lst_1, lst_2=None):
    n = len(lst_1)
    if lst_2 is not None:
        if n != len(lst_2):
            return False
    else:
        lst_2 = [i for i in range(n)]
    s = 0
    for i in range(n):
        s += abs(lst_1[i] - lst_2[i])
    s /= n
    return s

點積比(dot product ratio, DPR)

def dot_product_ratio(lst_1, lst_2=None):
    n = len(lst_1)
    if lst_2 is not None:
        if n != len(lst_2):
            return False
    else:
        lst_2 = [i for i in range(n)]
    s = 0
    max_s = 0
    for i in range(n):
        s += lst_1[i] * lst_2[i]
        max_s += lst_1[i] ** 2
    s /= max_s
    return s

歸一化點積比(normalization dot product ratio, NDPR)

def normalization_dot_product_ratio(lst_1, lst_2=None):
    n = len(lst_1)
    if lst_2 is not None:
        if n != len(lst_2):
            return False
    else:
        lst_2 = [i for i in range(n)]
    s = (2*n-1)/(n+1)*dot_product_ratio(lst_1, lst_2)-(n-2)/(n+1)
    return s

到此這篇關(guān)于Python計算序列相似度的算法實例的文章就介紹到這了,更多相關(guān)Python序列相似度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: