© ElVisti Лекция 7 Кластерный анализ и информационный поиск Дмитрий Владимирович ЛАНДЭ МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ. - презентация

1 © ElVisti Лекция 7 Кластерный анализ и информационный поиск Дмитрий Владимирович ЛАНДЭ МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ

2 © ElVisti2 Понятие «кластерного анализа» Пример кластеров сайтов - «групп подобия по контенту» (www touchgraph.com) Кластерный анализ - метод группировки экспериментальных данных в классы. Наблюдения, попавшие в один класс, в некотором смысле ближе друг к другу, чем к наблюдениям из других классов. (Глоссарий.ru)

3 © ElVisti3 Понятие информационного портрета Портрет - модель реального объекта, выраженную его наиболее узнаваемыми чертами. Информационный портрет документа - статистически значимая совокупность информационных характеристик. В качестве информационного портрета темы можно рассматривать множество ключевых слов, наиболее точно (по статистическим и смысловым алгоритмам) отражающее информацию, соответствующую данной теме. Тематической рубрике соответствует ее информационный портрет: P i = { v ij }, (j=1,..,K), где v ij –весовой коэффициент, соответствующий j- му терм, K - количество термов в словаре системы.

4 © ElVisti4 Взвешивание потока документов в пространстве информационного портрета М = {m ij } (i = 1,..,N; j = 1,..,K) - матрица соответствия потока документов D информационному портрету l. D={d i } {i=1,K}. di – определяется как TF*IDF. Близость D и P i – sim(D, P i ) – скалярное произведение K-мерных векторов. Алгоритм взвешивания:

5 © ElVisti5 Латентное семантическое индексирование Метод кластерного анализа LSI (латентного семантического индексирования), базируется на сингулярном разложении матриц (SVD). Сингулярным разложением матрицы A называется ее разложение вида A=USV T, где U и V – ортогональные матрицы, а S – диагональная матрица, элементы которой s ij = 0, если i не равно j, а s iі >= 0. В рассматриваемом примере (таблиц взаимосвязей) матрица А = М T М – квадратная, однако метод LSI применяется и к прямоугольным матрицам, но в этих случаях размерность матрицы S соответствует рангу матрицы А. В соответствии с методом LSI в рассмотрение берутся k наибольших сингулярных значений, а каждому такому сингулярному значению матрицы А соответствует кластер взаимосвязанных документов. А аппроксимируется матрицей A k = Σ u i s ii v i T. Метод LSI применим и к ранжированию выдачи информационно-поисковых систем, основанному на цитировании. Это алгоритм HITS (Hyperlink Induced Topic Search) – один из двух самых популярных на сегодня в области информационного поиска. Ввиду своей вычислительной трудоемкости (равной O(N 2 ), N – размерность А), этот метод LSI применяется только для относительно небольших матриц.

6 © ElVisti6 Взаимосвязь тем и метод k-means Суть алгоритма k-means: случайным образом выбирается k векторов-строк, которые определяются как центроиды кластеров. Затем k кластеров наполняются – для каждого из оставшихся векторов-строк определяется близость к центроиду соответствующего кластера. После этого вектор- строка приписывается к тому кластеру, к которому он наиболее близок. После этого строки-векторы перегруппируются. Затем для каждого из новых кластеров заново определяется центроид. После этого заново выполняется процесс наполнения кластеров и т. д., пока процесс не стабилизируется или не зациклится.

7 © ElVisti7 Группировка тем метод k-means В отличие от метода LSI, k-means идеально подходит для кластеризации динамических информационных потоков. Укрупнение рубрик – актуальная задача кластерного анализа и она может быть решена путем их группировки по признакам подобия. Выделение групп взаимосвязанных рубрик методом кластерного анализа k- means:

8 © ElVisti8 Метод, основанный на применении сетевого подхода - выявление сюжетов

9 © ElVisti9 Построение адаптивных интерфейсов уточнения запросов

10 © ElVisti Спасибо за внимание! Ландэ Д.В МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ Киев, Украина