Приводит к поиску таблиц корреляции - PullRequest
Новая
       17

Приводит к поиску таблиц корреляции

0 голосов
/ 04 ноября 2011

Имеют эти две таблицы: 

TableA
ID  Opt1    Opt2    Type
1   A       Z       10
2   B       Y       20
3   C       Z       30
4   C       K       40

и 

TableB
ID  Opt1    Type
1   Z       57
2   Z       99
3   X       3000
4   Z       3000

Какой будет хороший алгоритм для нахождения произвольных отношений между этими двумя таблицами?В этом примере я хотел бы найти очевидную связь между записями, содержащими Op1 = C в Таблице A и Type = 3000 в Таблице B.

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

спасибо.

Ответы [ 2 ]

1 голос
/ 04 ноября 2011

В псевдокоде наивная реализация может выглядеть так: 

  1. for each column c1 in table1
  2.    for each column c2 in table2
  3.      if approximately_isomorphic(c1, c2) then
  4.         emit (c1, c2)

  approximately_isomorphic(c1, c2)
  1. hmap = hash()
  2. for i = 1 to min(|c1|, |c2|) do
  3.    hmap[c1[i]] = c2[i]
  4. if |hmap| - unique_count(c1) < error_margin then return true
  5. else then return false

Идея такова: сделать попарное сравнение элементов каждого столбца с каждым другим столбцом. Для каждой пары столбцов создайте хэш-карту, связывающую соответствующие элементы двух столбцов. Если хеш-карта содержит то же количество ссылок, что и уникальные элементы первого столбца, то у вас есть идеальный изоморфизм; если у вас есть еще несколько, у вас есть почти изоморфизм; если у вас их намного больше, вплоть до количества элементов в первом столбце, у вас есть то, что, вероятно, не представляет никакой корреляции.

Пример вашего ввода: 

  ID & anything  : perfect isomorphism since all of ID are unique

  Opt1 & ID      : 4 mappings and 3 unique values; not a perfect
                  isomorphism, but not too far away.
  Opt1 & Opt1    : ditto above
  Opt1 & Type    : 3 mappings & 3 unique values, perfect isomorphism

  Opt2 & ID      : 4 mappings & 3 unique values, not a perfect
                  isomorphism, but not too far away
  Opt2 & Opt2    : ditto above
  Opt2 & Type    : ditto above

  Type & anything: perfect isomorphism since all of ID are unique

Для достижения наилучших результатов вы можете выполнить эту процедуру в обоих направлениях, то есть сравнить таблицу1 с таблицей2 и затем сравнить таблицу2 с таблицей1 - чтобы найти биективные отображения. В противном случае вас могут отбросить тривиальные случаи ... все значения в первом различны (совершенный изоморфизм) или все значения во втором одинаковы (совершенный изоморфизм). Также обратите внимание, что этот метод обеспечивает способ ранжирования или измерения того, насколько похожи или различаются столбцы.

Это идет в правильном направлении? Кстати, это O (ijk), где в table1 есть столбцы i, в таблице 2 столбцы j, а в каждом столбце k элементов. Теоретически, лучшее, что вы могли бы сделать для метода, это O (ik + jk), если вы можете найти корреляции без проведения парных сравнений.

1 голос
/ 04 ноября 2011

Звучит как проблема интеллектуального анализа данных.Я бы предложил попробовать FOIL Росса Куинлана: http://www.rulequest.com/Personal/

...