Вычисление подобия двух списков

У меня есть два списка:

например. a = [1,8,3,9,4,9,3,8,1,2,3] а также b = [1,8,1,3,9,4,9,3,8,1,2,3]

Оба содержат int. Для ints нет смысла (например, 1 не "ближе" к 3, чем к 8).

Я пытаюсь разработать алгоритм для вычисления сходства между двумя списками ORDERED. Упорядочено - это ключевое слово прямо здесь (поэтому я не могу просто взять набор обоих списков и рассчитать их процент заданного значения_разницы). Иногда числа повторяются (например, 3, 8 и 9 выше, и я не могу игнорировать повторы).

В приведенном выше примере функция, которую я бы назвал, скажет мне, что a и b примерно равны 90%, например. Как я могу это сделать? Расстояние редактирования было чем-то, что приходило в голову. Я знаю, как использовать его со строками, но я не уверен, как использовать его со списком int. Спасибо!

Ответ 1

Вы можете использовать difflib модуль

отношение()
Возвратите меру сходства последовательностей как float в диапазоне [0, 1].

Что дает:

 >>> s1=[1,8,3,9,4,9,3,8,1,2,3]
 >>> s2=[1,8,1,3,9,4,9,3,8,1,2,3]
 >>> sm=difflib.SequenceMatcher(None,s1,s2)
 >>> sm.ratio()
 0.9565217391304348

Ответ 2

Похоже, что редактирование (или Левенштейн) - это именно то, что нужно для работы.

Вот одна реализация Python, которая может быть использована в списках целых чисел: http://hetland.org/coding/python/levenshtein.py

Используя этот код, levenshtein([1,8,3,9,4,9,3,8,1,2,3], [1,8,1,3,9,4,9,3,8,1,2,3]) возвращает 1, это расстояние редактирования.

Учитывая расстояние редактирования и длину двух массивов, вычисление метрики "процентного сходства" должно быть довольно тривиальным.

Ответ 3

Просто используйте тот же алгоритм для вычисления расстояния редактирования на строках, если значения не имеют никакого особого значения.

Ответ 4

Один из способов решения этой проблемы - использовать histogram. В качестве примера (демонстрация с numpy):

In []: a= array([1,8,3,9,4,9,3,8,1,2,3])
In []: b= array([1,8,1,3,9,4,9,3,8,1,2,3])

In []: a_c, _= histogram(a, arange(9)+ 1)
In []: a_c
Out[]: array([2, 1, 3, 1, 0, 0, 0, 4])

In []: b_c, _= histogram(b, arange(9)+ 1)
In []: b_c
Out[]: array([3, 1, 3, 1, 0, 0, 0, 4])

In []: (a_c- b_c).sum()
Out[]: -1

В настоящее время существует множество способов использования a_c и b_c.

Где (по-видимому) простейшая мера подобия:

In []: 1- abs(-1/ 9.)
Out[]: 0.8888888888888888

Далее следуют:

In []: norm(a_c)/ norm(b_c)
Out[]: 0.92796072713833688

In []: a_n= (a_c/ norm(a_c))[:, None]
In []: 1- norm(b_c- dot(dot(a_n, a_n.T), b_c))/ norm(b_c)
Out[]: 0.84445724579043624

Таким образом, вам нужно быть более конкретным, чтобы узнать наиболее подходящую меру подобия, подходящую для ваших целей.

Ответ 5

Если им не хватает точки.

from __future__ import division

def similar(x,y):
    si = 0
    for a,b in zip(x, y):
        if a == b:
            si += 1
    return (si/len(x)) * 100


if __name__ in '__main__':
    a = [1,8,3,9,4,9,3,8,1,2,3] 
    b = [1,8,1,3,9,4,9,3,8,1,2,3]
    result = similar(a,b)
    if result is not None:
        print "%s%s Similar!" % (result,'%')

Ответ 6

Я уже давно реализовал что-то для подобной задачи. Теперь у меня есть запись в блоге для этого. Это было просто: вам приходилось вычислять PDF обеих последовательностей, тогда он обнаружил бы общую область, покрытую графическим представлением pdf.

Извините за сломанные изображения по ссылке, внешний сервер, который я использовал тогда, теперь мертв.

Прямо сейчас, для вашей проблемы код переводится на

def overlap(pdf1, pdf2):
    s = 0
    for k in pdf1:
        if pdf2.has_key(k):
            s += min(pdf1[k], pdf2[k])
    return s

def pdf(l):
    d = {}
    s = 0.0
    for i in l:
        s += i
        if d.has_key(i):
            d[i] += 1
        else:
            d[i] = 1
    for k in d:
        d[k] /= s
    return d

def solve():
    a = [1, 8, 3, 9, 4, 9, 3, 8, 1, 2, 3]
    b = [1, 8, 1, 3, 9, 4, 9, 3, 8, 1, 2, 3]
    pdf_a = pdf(a)
    pdf_b = pdf(b)
    print pdf_a
    print pdf_b
    print overlap(pdf_a, pdf_b)
    print overlap(pdf_b, pdf_a)

if __name__ == '__main__':
    solve()

К сожалению, он дает неожиданный ответ, только 0.212292609351