Для записи 404 кластерной информации, каждому кластеру присваивается уникальный кластерный номер (cluster ID). Эта информация, далее, записывается в связи с каждой хорошей фразой g
j.
В данной реализации, номер кластера определяется бит-вектором кластера, который также указывает на ортогональные связи между фразами. Бит-вектор кластера – это последовательность битов длиной n, количество хороших фраз в списке хороших фраз 208. Для данной хорошей фразы g
j, позиции битов соответствуют отсортированным соотнесенным фразам R для g
j. Значение бита устанавливается, если соотнесенная фраза g
k в R находится в том же кластере, что и фраза g
j. В более общем виде, это значит, что соответствующий бит в бит-векторе кластера установлен, если существует информационная ценность в любом направлении между g
j и g
k.
Номер кластера – это значение битовой строки, получаемой в результате. В данной реализации предусмотрено, что соотнесенные фразы, имеющие множественную или одностороннюю информационную ценность, появляются в одном кластере.
Пример бит-векторов кластера, с использованием рассмотренных выше фраз:
TABLE-US-00001 Monica purse Cluster Bill Clinton President Lewinsky designer ID Bill Clinton 1 1 1 0 14 President 1 1 0 0 12 Monica 1 0 1 1 1 11 Lewinsky purse 0 0 1 1 3 designer
В результате, после этого процесса, для каждой хорошей фразы g
j , будет определен набор соотнесенных фраз R, отсортированных по мере убывания качества информации I (g
j, g
k). Кроме того, для каждой хорошей фразы g
j, будет определен битовый вектор кластера, значением которого станет номер кластера, идентифицирующий первичный кластер, членом которого является фраза g
j, а также ортогональные значения (1 или 0 для каждой битовой позиции), показывающие, какие из соотнесенных фраз находятся в одном кластере с g
j.В приведенном выше примере, “Bill Clinton», «President» и «Monika Lewinsky» находятся в кластере 14, исходя из битовых значений в ряду для фразы «Bill Clinton».
Для хранения этой информации, доступны два основных решения. Первое, как было показано выше, использует для хранения информации матрицу совместного появления 212, где:
Запись G[row j col. k] = (I(j,k), clusterNumber, clusterBitVector)
В качестве альтернативного варианта, можно избежать использования матрицы, и хранить всю информацию в списке хороших фраз 208, где каждый ряд представляет хорошую фразу g
j:
Фраза row
j = list [phrase g
k,(I(j,k), clusterNumber, clusterBitVector)]
Этот подход предоставляет удобный способ для организации кластеров. Во-первых, вместо жесткой – и зачастую стихийной – иерархии тем и концепций, данное решение учитывает, что темы, определяемые соотнесенными фразами, составляют сложный граф взаимоотношений. Некоторые фразы соотносятся со многими другими фразами, а некоторые фразы обладают более ограниченным диапазоном влияния. Взаимоотношения могут быть многосторонними (каждая фраза предвосхищает другую) или однонаправленными (одна фраза предвосхищает другую, но не наоборот). В результате кластеры могут быть охарактеризованы как «локальные» по отношению к каждой хорошей фразе, а некоторые кластеры будут перекрываться, включая в себя одну или более общих соотнесенных фраз.
Для данной хорошей фразы g
j, порядок следования соотнесенных фраз, отсортированных по показателю качества информации, предоставляет таксономию для наименования кластеров фразы: имя кластера – это имя соотнесенной фразы в кластере, которая имеет наибольшее значение качества информации.
Описанный выше процесс предоставляет довольно эффективный способ определения значимых фраз, которые появляются в коллекции документов, а также показывает способ совместного употребления этих соотнесенных фраз в естественных “кластерах” и в реальных условиях. В результате, эта основанная на данных кластеризация соотнесенных фраз избегает перекосов, присущих любому ручному “редакторскому” способу отбора соотнесенных терминов и концепций, практикуемых многими действующими системами.
22.02.07
Источник:
gool.
Автор:
Google. Перевод:
.