У меня есть два списка:
например. 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. Спасибо!
Вы можете использовать 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
Похоже, что редактирование (или Левенштейн) - это именно то, что нужно для работы.
Вот одна реализация 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, это расстояние редактирования.
Учитывая расстояние редактирования и длину двух массивов, вычисление метрики "процентного сходства" должно быть довольно тривиальным.
Просто используйте тот же алгоритм для вычисления расстояния редактирования на строках, если значения не имеют никакого особого значения.
Один из способов решения этой проблемы - использовать 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
Таким образом, вам нужно быть более конкретным, чтобы узнать наиболее подходящую меру подобия, подходящую для ваших целей.
Если им не хватает точки.
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,'%')
Я уже давно реализовал что-то для подобной задачи. Теперь у меня есть запись в блоге для этого. Это было просто: вам приходилось вычислять 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