Адекватность мер близости задаче кластерного анализа документов

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

Применяя векторную модель и подразумевая, что семантика документов отражается частотой употребления в них определенных терминов, нельзя не понимать, что те или иные из них лучше или хуже представляют индивидуальность каждого документа [21]. Иными словами, некоторые термины обладают большей отличительной, различающей способностью, чем остальные.

С помощью таких методов как LSA, можно получить пространство, основанное на терминах, наиболее адекватно отражающих семантику данной коллекции документов, в котором, действительно, сходные по смыслу документы, в соответствии с мерой близости, располагаются друг от друга намного ближе несходных и, соответственно, имеют большую тенденцию к объединению в кластеры.

Это дает существенное улучшение результатов поиска и кластерного анализа в таком пространстве, однако для того, чтобы действительно в полной мере использовать различающую способность отобранных терминов, необходимы наиболее чувствительные к этому фактору меры близости [21].

Различающая способность термина определяется степенью его влияния на среднюю близость документов в коллекции. Существует мера различающей способности термина k, которая может быть задана как [21]:

, (25)

где sim – функция близости между двумя документами, d_ik – представление документа i без учета термина k и c_k – средний, центральный вектор коллекции, подсчитанный без учета термина k, d_i и c – документ и средний вектор соответственно, представленные с учетом термина k.

Сравнительные опыты [21] с использованием различных мер близости показали, что термины могут обладать положительным значением меры различающей способности – их использование делает документы менее близкими друг другу в среднем (то есть, многие документы, считавшиеся близкими без учета этого термина, оказываются менее близкими при взятии его в расчет), отрицательным – использование этих терминов уменьшает степень различия документов, и нулевым – термины, в любом случае, почти не оказывают влияния на сходство между документами.

Так на рисунке 2 изображено пространство документов до добавления термина с положительным значением меры различающей способности (слева) и после (справа) [29].

Рисунок 2 . Добавление термина с положительной различающей способностью

Идеальным же для кластеризации, с точки зрения основной гипотезы кластерного анализа документов, считается пространство, изображенное на рисунке 3.

Исходя из этого, можно, аналитически проанализировав формулу меры различающей способности, придти к следующим выводам.

Использование меры ненормализованного скалярного произведения дает всегда отрицательное значение меры различающей способности для данного термина, либо нулевое, если термин не попал в представляющую документы выборку (отсеян LSA, например).

 

Рисунок 3 . Идеальное пространство с точки зрения кластерного анализа

Использование меры евклидового расстояния (и вообще любой метрики Минковского) дает всегда положительное значение меры различающей способности. То есть всегда, при удалении любого термина, расстояния между векторами уменьшается (повышается сходство). Более того, если все векторы, при учете нового термина в качестве дополнительного измерения, получают примерно равные значения этого атрибута, общее распределение связей в коллекции остается неизменным, векторы просто переносятся на некоторое равное расстояние в пространстве.

Угловые меры, такие как мера косинуса, намного более чувствительны к взаимным корреляциям между измерениями пространства. Только мера косинуса может изменить свое значение в любую сторону, если в пространство документов добавляется новый термин. К примеру, если какой-то термин, имеющий большую различающую силу, дублируется, то есть в пространство добавляется новое измерение с такими же значениями для него у векторов, то при использовании меры косинуса, терминам, образующим оба измерения, будет соответствовать отрицательная величина меры различающей способности, то есть удаление хотя бы одного из них повлечет уменьшение общего среднего сходства. Меры же, основанные на расстояниях далеко не так точны и поэтому дают наихудшие результаты в многомерных документных пространствах [5].

Примерно равную с угловыми мерами эффективность дают корреляционные меры, такие как расширенное сходство Жаккара и коэффициент корреляции Пирсона. Однако мера косинуса все-таки чувствительнее к различающим способностям терминов и сильнее превосходит недостатки мер, основанных на расстояниях. Серьезное отличие меры косинуса от корреляционных мер заключается еще и в том, что она, в отличие от последних, инвариантна к длинам векторов документов.

Подводя итог анализу мер близости, можно заключить следующее. При подсчете сходства с помощью ненормализованного скалярного произведения, учитывается только степень употребления общих терминов, то есть берутся во внимание только их количество и веса (используется сходство в употреблении) [28].

Меры сходства, основанные на расстояниях, зависят в большей степени от количества и характеристик терминов, не употребляемых в сравниваемых документах (используется различие в употреблении) [28].

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

Надо отметить, что все вышесказанное справедливо в большей степени для представления векторов документов в полном пространстве терминов, то есть не урезанном с помощью техник, вроде SVD до некоторого k наилучшим образом аппроксимирующих исходное пространство измерений. Фактически, этим анализом выбираются термины, обладающие наибольшей различающей способностью и только они потом представляют документы.

Значения измерений уже не являются частотами терминов, в новом пространстве их величина может быть любой, даже отрицательной. Получается, что ненормализованное скалярное произведение при удалении какого-то из терминов может, как повысить значение, так и понизить.

Мера евклидова расстояния в любом случае при удалении, делает все документы более сходными, что логично и верно, поскольку все термины (измерения) обладают высокой положительной различающей способностью. Однако, количество терминов k, наилучшим образом представляющих документы, то есть k измерений, наилучшим образом аппроксимирующих начальное пространство, для каждого такого пространства свое и выбирается приблизительно, эмпирически, угадать точно его нельзя [41].

Поэтому, различающая способность этих k измерений, терминов не одинакова, хоть и положительна. Получается, что неточность в определении k может быть компенсирована выбранной мерой, адекватность которой была проверена на пространствах с терминами, обладающими большим разбросом различающей способности.

Таким образом, можно предположить, что мера косинуса будет наиболее адекватной и при использовании пространства, полученного SVD (или подобным методом), а значит и для нашей задачи, в частности.