составление таблицы подобия

Я не могу придумать лучшего способа решить следующую проблему...? Представьте, что у меня есть большая таблица, в которой строки и столбцы являются своего рода идентификаторами. Скажем, идентификатором книги.

book_id-->1    2     3     .....
  1       1   0.92    0.33
  2
  3

Запись в этой таблице говорит вам, насколько похожа каждая книга... так что из приведенной выше таблицы... книга 1 и книга 2 имеют индекс сходства 0,92.

Итак, я уже вычислил это в банке... для допустим "n" записей.

Из n+1 данные поступают в режиме реального времени.

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

 i = 0; i < total_books ; i++
    sim(book(n+1),book(i))

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

и если есть «m» новых книг, то это операция n ^ 2 (я думаю). Есть ли лучший алгоритм/структура данных, который может сделать это вычисление приемлемым.

Кроме того, просто заполнить фон. Это сходство есть не что иное, как скалярное произведение двух векторов. (похожесть косинуса в Google даст представление). Но в этом нет ничего необычного... просто взять точечные произведения между двумя векторами... и он вернет значение от 0 до 1.


machine-learning algorithm data-structures information-retrieval
person frazman    schedule 15.04.2012    source источник
comment
Если вам нужен декартовский квадрат мер подобия, то я не понимаю, как вы можете уменьшить его за пределы O (n ^ 2). Однако, если у вас есть какая-то другая цель, например, определить, имеет ли новый документ сходство › X, то в литературе начали появляться некоторые интересные подходы. Что ты пытаешься сделать?   -  person JRideout    schedule 15.04.2012

Ответы (1)


arrow_upward
0
arrow_downward

Когда вы добавляете 1 книгу в коллекцию из n книг, она выполняет n операций Когда вы добавляете m книг в коллекцию из n книг, она выполняет (n) + (n+1) + ... (n+m-1) операций, которые (необходимо проверить): n*m + (1+2 +... (m-1)) поэтому должно быть O(n*m + m*m).

Если вы реализовали свое решение наивным способом, вы можете сократить время вычисления вдвое, вычисляя и сохраняя sim(book_i,book_j) только тогда, когда id(book_i) ‹ id(book_j) (это не меняет сложности). Затем, когда вы хотите получить sim(i,j), вам просто нужно убедиться, что вы используете аргументы в правильном порядке.

person SylvainD    schedule 15.04.2012
comment
Эмм.. можно поподробнее. Зачем мне выполнять расчет sim, когда book_i id ‹ book_j id.. Я имею в виду, когда я вычисляю sim_score для книги номер 100, скажем, из 200 000 книг... тогда я все равно сравниваю sim_score между книгами номер 1 и 100. , 2 и 100.. и 200000 и 100? или это я вас неправильно понял? Спасибо - person frazman; 15.04.2012
comment
Учтите, что функция sim() симметрична, т. е. sim(a,b)==sim(b,a). Таким образом, вам нужно только вычислить sim(a,b), если a ‹ b, в противном случае вы просто ищете sim(b,a). - person DaveFar; 15.04.2012