Советы по проектированию структуры данных

Question

У меня есть файл, из которого я читаю данные.Мне нужен совет о том, как спроектировать структуру данных, которая делает следующее: Итак, данные имеют форму

id_1::id_2::similiarity_score

Теперь, хотя данные в этой форме, но это также означает, что

id_2::id_1::same_similiarity_Score

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

object.maxSimiliarity(object_id_1)
returns object_id_2 # has max score

, но тогда этот object_id_1 также может быть в столбце product_id_2 в базе данных ...

такв базе данных может иметь любую форму:

 object_id_1:: object_id_2::score
 or object_id2::object_id_1::score

, поэтому я хотел бы спроектировать эту структуру данных таким образом, чтобы

k_1, k_2:: value <--> k_2,k_1::value

Answer 1

Общий прием для такого рода вещей - найти канонизацию - функцию, которая отображает всех членов определенного класса на один и тот же объект.В этом случае вы можете достичь этого, отсортировав первые два компонента, которые преобразуют B :: A :: Score в A :: B :: Score, оставив A :: B :: Score без изменений.

Answer 2

Мне кажется, что вы можете использовать баллы для составления списков лучших и худших матчей:

d = {
     'id1':  [id_best_match_to_id1, id_next_best_match_to_id1, ..., id_worst_match_to_id1],
     'id2':  [id_best_match_to_id2, id_next_best_match_to_id2, ..., id_worst_match_to_id2],
     ...
}

Если необходимо сохранить оценки сходства, используйте список кортежей в форме (id_best_match_to_id1, similarity_score_to_id1).

Я не вижу способа использовать это сходство как симметричное соотношение, где sim(x,y)==sim(y,x).

Answer 3

Данные очень похожи на узлы и ребра взвешенного графа. Если a похоже на b со счетом 5.0 и аналогично c со счетом 1.0, вы можете визуализировать это следующим образом:

                                    a
                                   / \
                                  /   \
                                5.0   1.0
                                /       \
                               b         c

Networkx - это библиотека Python, предоставляющая готовые графовые объекты и алгоритмы. Загрузка ваших данных во взвешенный мультиграф (то есть он поддерживает множественные соединения между узлами A--B и B--A - это тривиально. После этого получение наиболее похожего объекта с помощью идентификатора объекта - это случай поиска узла, нахождение его наиболее взвешенный край и возвращающий узел в конце.

import networkx as nx

## Test data
data = """\
a::b::2
b::a::3
a::c::5
b::e::1
"""
rows = (row.split('::') for row in data.split())


class Similarity(object):
    def __init__(self, data):
        self.g = nx.MultiGraph()
        self.load(data)

    def load(self, data):
        ## Turn the row into data suitable for networkx graph
        rows = ((row[0], row[1], float(row[2])) for row in data)
        self.g.add_weighted_edges_from(rows)

    def most_similar(self, obj_id):
        ## Get edges from obj_id node
        edges = self.g.edges_iter(obj_id, data=True)
        ## Sort by weight, get first, get joined node
        return sorted([(i[0], i[1], i[2].get('weight', 0)) for i in edges])[-1][1]


sc = Similarity(rows)
sc.most_similar('a') ## 'c'
## Add some more data linking a --> f with a high score
sc.load([('a', 'f', 10)])
sc.most_similar('a') ## 'f'