Статьи

Neo4j: Cypher — обнаружение дубликатов с использованием отношений

Ноябрь 29, 2018

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

Они не являются дубликатами в том смысле, что есть несколько записей с одним и тем же идентификатором, но скорее имеют разные идентификаторы, но кажутся одним и тем же документом!

например, есть пара статей под названием «Аутентификация в операционной системе Taos»:

http://dl.acm.org/citation.cfm?id=174614

2016-07-20_11-43-00

http://dl.acm.org/citation.cfm?id=168640

2016-07-20_11-43-38

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

Теперь в этом случае довольно легко просто сравнить строки названий этих статей и понять, что они идентичны. Ранее я использовал превосходную библиотеку дедупликации, чтобы сделать это, и есть также отличный доклад от Berlin Buzzwords 2014, где автор использует хеширование с учетом локальных особенностей для достижения аналогичного результата.

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

Вот как выглядит график:

граф-8

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

01
02
03
04
05
06
07
08
09
10
11
MATCH (r:Resource {id: "168640"})-[:REFERENCES]->(other)
WITH r, COLLECT(other) as myReferences
  
UNWIND myReferences AS reference
OPTIONAL MATCH path = (other)-[:REFERENCES]->(reference)
WITH other, COUNT(path) AS otherReferences, SIZE(myReferences) AS myReferences
WITH other, 1.0 * otherReferences / myReferences AS similarity WHERE similarity > 0.5
  
RETURN other.id, other.title, similarity
ORDER BY similarity DESC
LIMIT 10
1
2
3
4
5
6
7
╒════════╤═══════════════════════════════════════════╤══════════╕
│other.id│other.title                                │similarity│
╞════════╪═══════════════════════════════════════════╪══════════╡
│168640  │Authentication in the Taos operating system│1         │
├────────┼───────────────────────────────────────────┼──────────┤
│174614  │Authentication in the Taos operating system│1         │
└────────┴───────────────────────────────────────────┴──────────┘

Этот запрос:

  • выбирает одну из газет Таос и находит ее ссылки
  • находит другие документы, которые ссылаются на эти же документы
  • вычисляет оценку сходства на основе того, сколько у них общих ссылок
  • возвращает документы, которые имеют более 50% одинаковых ссылок с самыми похожими в верхней части

Я попробовал это с другими бумагами, чтобы видеть, как это случилось:

Производительность Firefly RPC

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
╒════════╤════════════════════════════════════════════════════════════════╤══════════════════╕
│other.id│other.title                                                     │similarity        │
╞════════╪════════════════════════════════════════════════════════════════╪══════════════════╡
│74859   │Performance of Firefly RPC                                      │1                 │
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│77653   │Performance of the Firefly RPC                                  │0.8333333333333334│
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│110815  │The X-Kernel: An Architecture for Implementing Network Protocols│0.6666666666666666│
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│96281   │Experiences with the Amoeba distributed operating system        │0.6666666666666666│
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│74861   │Lightweight remote procedure call                               │0.6666666666666666│
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│106985  │The interaction of architecture and operating system design     │0.6666666666666666│
├────────┼────────────────────────────────────────────────────────────────┼──────────────────┤
│77650   │Lightweight remote procedure call                               │0.6666666666666666│
└────────┴────────────────────────────────────────────────────────────────┴──────────────────┘

Аутентификация в распределенных системах: теория и практика

1
2
3
4
5
6
7
╒════════╤══════════════════════════════════════════════════════════╤══════════════════╕
│other.id│other.title                                               │similarity        │
╞════════╪══════════════════════════════════════════════════════════╪══════════════════╡
│121160  │Authentication in distributed systems: theory and practice│1                 │
├────────┼──────────────────────────────────────────────────────────┼──────────────────┤
│138874  │Authentication in distributed systems: theory and practice│0.9090909090909091│
└────────┴──────────────────────────────────────────────────────────┴──────────────────┘

К сожалению, это не так просто, как найти 100% совпадений по ссылкам! Я ожидаю, что более поздние редакции статьи добавят больше контента и, следовательно, дополнительных ссылок

Что если мы посмотрим на сходство авторов?

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MATCH (r:Resource {id: "121160"})-[:REFERENCES]->(other)
WITH r, COLLECT(other) as myReferences
  
UNWIND myReferences AS reference
OPTIONAL MATCH path = (other)-[:REFERENCES]->(reference)
WITH r, other, authorSimilarity,  COUNT(path) AS otherReferences, SIZE(myReferences) AS myReferences
WITH r, other, authorSimilarity,  1.0 * otherReferences / myReferences AS referenceSimilarity
WHERE referenceSimilarity > 0.5
  
MATCH (r)<-[:AUTHORED]-(author)
WITH r, myReferences, COLLECT(author) AS myAuthors
  
UNWIND myAuthors AS author
OPTIONAL MATCH path = (other)<-[:AUTHORED]-(author)
WITH other, myReferences, COUNT(path) AS otherAuthors, SIZE(myAuthors) AS myAuthors
WITH other, myReferences, 1.0 * otherAuthors / myAuthors AS authorSimilarity
WHERE authorSimilarity > 0.5
  
  
  
RETURN other.id, other.title, referenceSimilarity, authorSimilarity
ORDER BY (referenceSimilarity + authorSimilarity) DESC
LIMIT 10
1
2
3
4
5
6
7
╒════════╤══════════════════════════════════════════════════════════╤═══════════════════╤════════════════╕
│other.id│other.title                                               │referenceSimilarity│authorSimilarity│
╞════════╪══════════════════════════════════════════════════════════╪═══════════════════╪════════════════╡
│121160  │Authentication in distributed systems: theory and practice│1                  │1               │
├────────┼──────────────────────────────────────────────────────────┼───────────────────┼────────────────┤
│138874  │Authentication in distributed systems: theory and practice│0.9090909090909091 │1               │
└────────┴──────────────────────────────────────────────────────────┴───────────────────┴────────────────┘
1
2
3
4
5
6
7
╒════════╤══════════════════════════════╤═══════════════════╤════════════════╕
│other.id│other.title                   │referenceSimilarity│authorSimilarity│
╞════════╪══════════════════════════════╪═══════════════════╪════════════════╡
│74859   │Performance of Firefly RPC    │1                  │1               │
├────────┼──────────────────────────────┼───────────────────┼────────────────┤
│77653   │Performance of the Firefly RPC│0.8333333333333334 │1               │
└────────┴──────────────────────────────┴───────────────────┴────────────────┘

Я уверен, что мог бы найти некоторые другие документы, где ни одно из этих сходств не работало хорошо, но это интересное начало.

Я думаю, что следующим шагом будет создание обучающего набора пар документов, которые не похожи друг на друга. Затем мы могли бы обучить классификатор, чтобы определить, являются ли два документа идентичными.

Но это на другой день!

Ссылка: Neo4j: Cypher — Обнаружение дубликатов с использованием отношений от нашего партнера JCG Марка Нидхэма в блоге Марка Нидхэма .
41
Share: