Количественная оценка попарного, трехстороннего и т. Д. Перекрывается в двудольном графе - PullRequest
Новая
       27

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

3 голосов
/ 28 февраля 2012

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

  X Y Z
A 0 1 0
B 0 0 1
C 1 1 1

и т. Д.

Я хочуколичественно определить распределение перекрытий в строках для 1 ... S выбранных строк.Так, например, в приведенной выше матрице среднее попарное перекрытие будет (0 + 1/3 + 1/3) / 3 = 2/9, тройное перекрытие (для этого должно быть более подходящее слово)быть 0.

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

Я могу сделать что-то вроде взгляда на вероятность перекрытия для каждого столбца - так, что-то вроде числа возможныхкомбинации в каждом столбце длины S, которые будут включать не менее 1 элемента, деленного на общее количество комбинаций строк.Но я не нашел способа использовать эту информацию для получения правильного ответа.

Я думал, что должен быть какой-то алгоритм сканирования или иным образом, который решит эту проблему для произвольных значенийS, но не хватает обучения алгоритмам, чтобы знать это из головы.Есть мысли или рекомендации?

Спасибо!

Ответы [ 2 ]

3 голосов
/ 28 февраля 2012

Я думаю, что вы можете довольно эффективно вычислить это, построив гистограмму, которая отслеживает, сколько всего 1 в каждом столбце. Возьмите свой пример: 

  X Y Z
A 0 1 0
B 0 0 1
C 1 1 1

Если вы сложите столбцы, вы получите 1, 2 и 2 соответственно. Чтобы найти среднее попарное сходство, вы можете подумать о том, чтобы найти среднее сходство по каждому столбцу, а затем взять его среднее. В этом случае, чтобы найти попарное сходство, вы спросите, для каждого столбца, сколько существует пар элементов. Для столбца X это 0. Для столбца Y это 1, а для столбца Z это также 1. Если мы вычислим (0/3 + 1/3 + 1/3) / 3, вы получите 2/9, как требуется. Чтобы найти трехстороннее сходство, вы спрашиваете, сколько триплетов в каждом столбце. В каждом есть 0, поэтому среднее значение равно 0.

Причина, по которой это работает, в том, что вы хотите сумму

(Сумма (все возможные k-кортежей строк) (# столбец соответствует по строкам / num столбцам)) / num k-кортежей

Вы можете выделить это, чтобы получить

(Сумма (все возможные k-кортежей строк) (# столбец соответствует столбцам в строках)) / (num k-кортежей * num столбцов)

Эту первую сумму можно затем обменять, чтобы получить

(Sum (все столбцы) (# k-кортежей строк, соответствующих этому столбцу)) / (num k-кортежей * num столбцов)

Вычислить эту сумму намного проще, потому что вы можете просто сделать это:

  1. Рассчитать суммы столбцов.
  2. Для каждого столбца найдите, сколько способов выбрать из него k элементов (это равно n, выберите k), затем разделите его на количество столбцов.
  3. Разделите это общее количество на количество наборов строк из k элементов, которые есть (это количество строк, выбранное k).

Вы можете достаточно эффективно вычислить n select k, используя определение функции выбора (за время O (n + k)). Если у вас R строк и C столбцов, общая работа составит:

  1. Суммирование столбцов в каждой строке: O (RC)
  2. Для столбца вычисляется количество комбинаций k-элементов: O (R + k), поскольку сумма не более R.
  3. По всем столбцам, вычисляя это общее значение: O (CR + Ck)
  4. Усреднение их вместе: O (C)

Это дает общее время выполнения O (CR + Ck). Я думаю, что если вы связываете k числом строк, это выполняется за время O (CR).

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

1 голос
/ 28 февраля 2012

Пусть n будет количеством строк, а m будет количеством столбцов.Общее количество комбинаций = m * комбинаций строк = m*n*(n-1)/2

Пусть si - сумма i-го столбца.Общее количество совпадений = si*(si-1)/2.

Итак, решение: ( s1*(s1-1)/2 + s2*(s2-1)/2 +...+sm*(sm-1)/2 ) / (m*n*(n-1)/2)

Например, в вашем случае знаменатель = 3 * 3 * 2/2 = 9 

s1 = 0, s2=2, s3=2

Числитель: (0 + 1 + 1) = 2

Ответ = 2/9

Для общего p-way пересечения измените формулу.

( choose(s1,p), choose(s2,p)+...+choose(sm,p) ) / (m*choose(n,p))

, где choose(k,p) = k!/((k-p)!p!)

...