Сходство элементов списка

Question

У меня есть десять списков, и я хочу получить их «сходство».Вот входные данные, которые у меня есть:

data = [
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'SeasonNumber', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'SeasonNumber', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'Genres', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', '_StudioName', 'Type', 'LanguageOfMetadata', 'ReleaseDate', 'Studio', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'TVSeriesID', 'Locales', 'EpisodeNumber', 'Name', 'Synopsis', 'Products', 'SeasonNumber', 'Platform'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'LanguageOfMetadata', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'Genres', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', '_StudioName', 'Type', 'LanguageOfMetadata', 'ReleaseDate', 'Studio', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'TVSeriesID', 'Locales', 'EpisodeNumber', 'Name', 'Synopsis', 'Products', 'SeasonNumber', 'Platform'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'ReleaseDate', 'Genres', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales'], 
    ['RuntimeInMinutes', 'EpisodeNumber', 'Genres', 'ReleaseDate', 'Name', 'Platform', 'PlatformID', 'BaseURL', 'Languages', 'ArtworkURL', 'Synopsis', 'TVSeriesID', 'Products', '_NetworkName', 'ReleaseYear', '_ContentProviderName', 'Studio', '_StudioName', 'Type', 'Locales']
]

Мой текущий метод заключается в сравнении длины набора этих значений с общей длиной.Таким образом, в приведенном выше тексте это будет:

>>> len(set(data))/len(data)
0.5

Однако это довольно грубо, так как я хотел бы получить сходство, которое не "все или ничего".Другими словами, что-то вроде концептуального сходства, где вышеупомянутое может иметь сходство на 98% (извините, если у меня возникают проблемы с объяснением именно того, что я хочу здесь - но я имею в виду оценивать сходство как не только сам список, но исходство его элементов.

Answer 1

Когда вы говорите, что хотите получить сходство между двумя списками, есть несколько способов сделать это.Нравится @Nick Pandey Jaccard Сходство.Другое соотношение, называемое танимото , тоже хорошо работает.

Это моя реализация:

def tanimoto (list1, list2):
    intersection = [common_item for common_item in list1 if common_item in list2]
    return float(len(c))/(len(a) + len(b) - len(c))

Теперь, чтобы решить вашу проблему необходимости сравнивать 10 списков одновременно.Вы можете сравнивать только два элемента одновременно, используя что-то вроде выше.Однако вы можете разработать свою собственную логику, чтобы дать вам общее представление о том, насколько все сходно друг с другом.

Например, вы можете взять по пять списков за раз и сравнить, или, что лучше, сравнить первые два списка, сохранить коэффициент танимото, сравнить следующие два и повторить.Наконец, возьмите среднее значение коэффициентов.Это лучше в коде:

def grouped(iterable, n):
    return zip(*[iter(iterable)]*n)

coeffs = []
for i, j in grouped(data, 2): # data refers to the variable in the question
    coeffs.append(tanimoto(i, j))

similarity = sum(coeffs)/len(coeffs)

Надеюсь, это поможет:)

Answer 2

Взгляните на библиотеку datasketch и ее структуру данных MinHash.Это основано на сходстве Жакара для множеств, которое является просто пересечением (что у них общего), деленным на объединение (все возможные элементы).

Вот пример:

from datasketch import MinHash

data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'datasets']
data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'documents']

m1, m2 = MinHash(), MinHash()
for d in data1:
    m1.update(d.encode('utf8'))
for d in data2:
    m2.update(d.encode('utf8'))
print("Estimated Jaccard for data1 and data2 is", m1.jaccard(m2))

Дает вам оценку сходства, если ваши наборы большие.В противном случае, просто используйте встроенные операции над множествами:

s1 = set(data1)
s2 = set(data2)
actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))
print("Actual Jaccard for data1 and data2 is", actual_jaccard)

Если вы хотите взять сходство Жакара более чем из двух множеств, просто вычислите парное сравнение и возьмите среднее (среднее) для всехзначения:

from datasketch import *
import itertools
minhash_data = list()
for element in data:
    m = MinHash()
    for d in element:
        m.update(d.encode('utf-8'))
    minhash_data.append(m)

jaccard_sims = list()
for pair in itertools.combinations(minhash_data, 2):
    jaccard_sims.append(pair[0].jaccard(pair[1]))

average = sum(jaccard_sims) / float(len(jaccard_sims))
print("Average Jaccard similarity: {}".format(average))

Среднее сходство по Джакарду: 0,9512152777777778