Основные способы определения центроидов.

1. Логический профиль (обозначается Р₁).

Заданы вектора документов в следующем виде:

V^Di = (d₁ , d₂ , d₃ , … , d_t), где t – число индексационных терминов, выделенных во всех документах нашего массива. Тогда логический профиль определяется как результат с логической “или”:

Р₁ = V^D1 v V^D2 v V^D3 v …

1, если термин t^k входит в вектор документа D_i;

d_k (k = 1,t) = 0, в противном случае.

2.Профиль частотного документа (Р2).

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

3.Профиль частотности термина (Р3).

Здесь используются веса терминов в документах:

V^Di = (w₁ , w₂ , w₃ , … , w_t), где w_i – веса терминов входящих в вектор документа V^Di.

В вычислении Р3 участвуют веса.

Р3 (k = 1,t) = сумм(j = 1,N) wⁱ_k , где j – порядковый номер документа;    N – число документов кластера; t – число индексационных терминов в массиве; k – порядковый номер термина.

Логический способ определения центроидов.

Логический профиль (обозначается Р₁).

Заданы вектора документов в следующем виде:

V^Di = (d₁ , d₂ , d₃ , … , d_t), где t – число индексационных терминов, выделенных во всех документах нашего массива. Тогда логический профиль определяется как результат с логической “или”:

Р₁ = V^D1 v V^D2 v V^D3 v …

1, если термин t^k входит в вектор документа D_i;

d_k (k = 1,t) = 0, в противном случае.

Профиль частотности документа.

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

Профиль частотности термина.

Здесь используются веса терминов в документах:

V^Di = (w₁ , w₂ , w₃ , … , w_t), где w_i – веса терминов входящих в вектор документа V^Di.

В вычислении Р3 участвуют веса.

Р3 (k = 1,t) = сумм(j = 1,N) wⁱ_k , где j – порядковый номер документа;      N – число документов кластера; t – число индексационных терминов в массиве; k – порядковый номер термина.

Вопрос 28(окончание).

D_p+1), если существуют пары: (D_i , D_p+1) , (D_j , D_p+1) , … , (D_p , D_p+1).

Алгоритм заканчивается, когда дальнейшее слияние невозможно.

Недостаток метода: образуется большое число кластеров.

Метод одной связи.

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

S(D_i , D_k) , S(D_k , D_j);

S(D_i , D_k) , S(D_k , D_m) , S(D_m , D_j);

Самое сильное требование: S(D_i , D_k) – если в матрице подобия уже существует подобие.

Если одно из условий выполняется, то документы в одном классе.

Кластеризация вокруг выборочных документов.

Вместо построения матрицы подобия используют плотность пространства некоторых документов. В качестве возможных центров кластера выступают те документы, которые по результатам расчётов оказались расположенными в плотных зонах пространства. Все документы в данном методе делятся на 3 класса:

Документы, уже включённые в кластеры;

Документы, ещё не подвергшиеся исследованию(не включенные в кластеры);

Свободные документы. Те документы, относительно которых делалась попытка включения в кластер, но она закончилась неудачей.

Берём документ, пробуем включить его в кластер. Если не получается, то заносим его в множество свободных документов. Далее из свободного множества пытаемся подключить документы к кластеру.

Алгоритм:

Выбирается очередной, не включённый в кластеры документ и считается возможным центром кластера;

Рассчитываются коэффициенты подобия между этим документом, документами свободного типа и документами, не включёнными в классы;

Плотность считается достаточной, если:

существует по меньшей мере n1 документов, коэффициенты подобия которых по отношению к выбранному документу превышает некоторое пороговое значение T1;

Существует по крайней мере n2 документов, коэффициенты подобия (КП) которых, по отношению к исследуемому документу превышают пороговое значение T2;

Если между n2 и T2 существует некоторое соотношение: n2>=n1; T2<=T1, тогда считается, что выбранный документ - “центр массы”, вокруг которого собраны другие документы. Если плотность недостаточна (если одно из условий не выполняется), то документ относят к свободным и аналогичным образом исследуют следующий документ из множества не включенных в кластеры. Если плотность достаточна, то формируют кластер, включающий все свободные документы и не включённые ранее в кластеры документы, для которых КП с исследуемым документом не меньше порогового значения T3. Для нового кластера строится вектор центроида, и все документы, включённые в этот кластер и те, которые включены в остальные кластеры сопоставляются с данным центроидом. Это сопоставление служит для отнесения каждого документа к одной из следующих категорий:

Вопрос 33(окончание).

Фиксированная адаптация. При этом пользователь сам явно выбирает свой уровень подготовки;

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

Косметическая. Занимает промежуточное место между фиксированной полной и достигается использованием специальных приёмов:

Приём использования сокращений (md – mkdir , cd – chdir , *.bak);

Синонимы – пользователь выбирает то, что ему ближе;

Использование объектов по умолчанию и макросы.