Мы продолжаем публикацию очередного патента Google: "Определение спам-документов системой получения информации, основанное на фразах." Часть 2 (ПРОДОЛЖЕНИЕ).
Идентификация соотнесенных фраз и кластеров соотнесенных фраз.
Рис 4отражает процесс идентификации соотнесенных фраз, который включает в себя следующие функциональные операции:
- Определить соотнесенные фразы, которые имеют высокую информационную ценность
- определить кластеры из соотнесенных фраз
- сохранить цифровой вектор и номер кластера
А теперь подробнее обо всех этих операциях.
Как описывалось ранее, матрица совместного появления 212 содержит хорошие фразы g
j, каждая из которых предвосхищает по меньшей мере одну хорошую фразу g
k, с информационной ценностью выше установленного порога. Чтобы определить соотнесенные фразы 400, для каждой пары хороших фраз (g
j, g
k) информационная ценность сравнивается с пороговым значением, т.е., 100. Таким образом, g
j и g
k являются соотнесенными фразами, если I (g
j, g
k) > 100.
Подобный высокий порог служит для определения уровня совместного появления хороших фраз, который намного превышает среднестатистический уровень совместного появления. Статистически это значит, что фразы g
j и g
k совместно появляются в 100 раз чаще, чем это ожидается. К примеру, если взять фразу "Monica Lewinsky», то фраза "Bill Clinton" будет упомянута в том же документе с вероятностью в 100 раз большей, чем та же фраза "Bill Clinton" будет упомянута в другом, случайным образом выбранном, документе. Другими словами, точность предвосхищения составляет 99,999%, поскольку показатели появления соотносятся как 100:1.
Соответствующим образом, любая запись (g
j, g
k), которая не превосходит порога Соотнесенных Фраз, отсеивается, указывая на то, что фразы g
j, g
k не соотносятся. Оставшиеся записи в матрице совместного появления 212 будут указывать на соотнесенные фразы.
Колонки g
k в каждом ряду g
j матрицы совместного появления 212 затем сортируются по порядку значений качества информации I (g
j, g
k), так что соотнесенные фразы g
k с наилучшими показателями качества информации идут первыми. Такая сортировка определяет, какие фразы будут наиболее соотнесенными в плане качества информации с данной фразой g
j.
Следующий шаг – определение 402 того, какие из соотнесенных фраз составляют кластер соотнесенных фраз. Кластер – это набор соотнесенных фраз, в котором каждая фраза обладает высоким качеством информации по отношению к по меньшей мере одной другой фразе. В данной реализации, кластеры определены следующим образом:
В каждом ряду g
j матрицы, будет одна или более фраз, которые соотнесены с фразой g
j. Этот набор является набором соотнесенных фраз R
j, где R = { g
k, g
l … g
m}.
Для каждой соотнесенной фразы m в R
j, система индексирования 110 определяет, является ли любая другая из соотнесенных фраз также соотнесенной к g
j. Таким образом, если I(g
k, g
l) также не равно нулю, то g
j, g
k и g
l также являются частью кластера. Этот кластерный тест повторяется для каждой пары (g
l, g
m) в R.
Например, предположим, что хорошая фраза «Bill Сlinton» соотнесена с фразами «President», «Monika Lewinsky», поскольку информационная ценность каждой из этих фраз по отношению к фразе «Bill Сlinton» превосходит установленный порог для Соотнесенных Фраз. Дальше, предположим, что фраза «Monica Lewinsky» соотнесена с фразой «purse designer». Эти фразы образуют набор R. Для определения кластеров, система индексирования 110 оценивает информационную ценность для каждой из фраз по отношению к остальным – путем определения их соответствующих значений информационной ценности. Итак, система индексирования 110 определяет информационную ценность I(«President», «Monika Lewinsky»), I («President», «purse designer») , и т.д. – для всех пар в R. В данном примере, «Bill Сlinton», «President» и «Monika Lewinsky» принадлежат одному кластеру, «Bill Сlinton» и «President» - из другого кластера, «Monika Lewinsky» и «purse designer» принадлежат третьему кластеру, а , «Monika Lewinsky», «Bill Сlinton» и «purse designer» относятся к четвертому кластеру. Это происходит потому, что хотя «Bill Clinton» не предвосхищает появление «purse designer» с достаточными качественными показателями, однако «Monika Lewinsky» предвосхищает обе эти фразы.
22.02.07
Источник:
gool.
Автор:
Google. Перевод:
.