Построение новостного агрегатора в Интернет на основе материалов сайтов СМИ (обзор технологии yandex.ru) Шевченко Алексей, 422 группа

Yandex.ru

План доклада Проблематика Проблематика Реализация новостной ленты на примере yandex.ru Реализация новостной ленты на примере yandex.ru Поиск «похожих» текстов Поиск «похожих» текстов Методы кластеризации Методы кластеризации Стандарт RSS Стандарт RSS

Проблематика Поиск и объединение в сюжетные темы документов, описывающих одни и те же события Поиск и объединение в сюжетные темы документов, описывающих одни и те же события Ранжирование сюжетов Ранжирование сюжетов

Построение сюжетов на yandex.ru Определение попарной текстуальной близости документов Определение попарной текстуальной близости документов Построение матрицы попарной близости Построение матрицы попарной близости Обработка матрицы двухуровневым алгоритмом кластеризации с эмпирически подобранным радиусом Обработка матрицы двухуровневым алгоритмом кластеризации с эмпирически подобранным радиусом

Построение сюжетов на infostream.ua Определение текстуальной близости документов на основе последовательностей ключевых слов Определение текстуальной близости документов на основе последовательностей ключевых слов Построение цепочек документов, коэффициент близости которых превышает некоторый, установленный эмпирически Построение цепочек документов, коэффициент близости которых превышает некоторый, установленный эмпирически Выбор самой актуальной информации на основании длины и оперативности цепочек Выбор самой актуальной информации на основании длины и оперативности цепочек

Метрики Полнота – описывает количество сообщений, не попавших в нужные сюжеты Полнота – описывает количество сообщений, не попавших в нужные сюжеты Точность – описывает количество «чужих» сообщений в сюжете Точность – описывает количество «чужих» сообщений в сюжете В обеих системах достигаются полнота более 80% и точность около 95%.

Алгоритмы определения текстуальной близости на yandex.ru Алгоритм поиска похожих документов (базируется на методе w-шинглов) Алгоритм поиска похожих документов (базируется на методе w-шинглов) Алгоритм нечеткого поиска, базирующийся на матрице похожести текстов Алгоритм нечеткого поиска, базирующийся на матрице похожести текстов

Метод w-шинглов Метод шинглов определяет близость двух текстов Метод шинглов определяет близость двух текстов Каждый из текстов рассматривается как набор слов Каждый из текстов рассматривается как набор слов Алгоритм разбивает каждый текст на пересекающиеся цепочки из слов фиксированной длины, затем полученные цепочки сличаются Алгоритм разбивает каждый текст на пересекающиеся цепочки из слов фиксированной длины, затем полученные цепочки сличаются Для достижения наилучших результатов можно применять алгоритм неоднократно, увеличивая длину цепочки Для достижения наилучших результатов можно применять алгоритм неоднократно, увеличивая длину цепочки

Метод w-шинглов Первый текст: а роза упала на лапу Азора Первый текст: а роза упала на лапу Азора Второй текст: а роза упала на лапу, упала на лапу Азора Второй текст: а роза упала на лапу, упала на лапу Азора Пусть длина шингла равна трем Пусть длина шингла равна трем

Метод w-шинглов Для первого текста имеем цепочки: (а, роза, упала), (роза, упала, на), (упала, на, лапу), и т.д. Аналогично строятся цепочки для второго текста Для первого текста имеем цепочки: (а, роза, упала), (роза, упала, на), (упала, на, лапу), и т.д. Аналогично строятся цепочки для второго текста Для каждого текста из получившегося набора шинглов удаляются дубликаты Для каждого текста из получившегося набора шинглов удаляются дубликаты Пусть S(A) – множество шинглов для текста A. Тогда схожесть текстов определяется по формуле: Пусть S(A) – множество шинглов для текста A. Тогда схожесть текстов определяется по формуле:

Метод w-шинглов Таким образом, используя метод шинглов с длиной 3, получаем, что исходные два текста являются полными дубликатами Таким образом, используя метод шинглов с длиной 3, получаем, что исходные два текста являются полными дубликатами

Другой метод определения похожести текстов Метод определяет похожесть двух текстов Метод определяет похожесть двух текстов Текст рассматривается как набор слов Текст рассматривается как набор слов Для пары текстов строится матрица MxN, где M – количество слов первого текста, N – второго Для пары текстов строится матрица MxN, где M – количество слов первого текста, N – второго Значение матрицы Aij равно похожести соответствующих слов Значение матрицы Aij равно похожести соответствующих слов

Другой метод определения похожести текстов Похожесть слов определяется некоторым образом (например, как расстояние редактирования) Похожесть слов определяется некоторым образом (например, как расстояние редактирования) Все слова, похожесть которых меньше некоторого порогового значения (например, 20%), считаются абсолютно непохожими (0%) Все слова, похожесть которых меньше некоторого порогового значения (например, 20%), считаются абсолютно непохожими (0%) Пусть для определенности M

Другой метод определения похожести текстов Для матрицы строится максимальное покрытие, т.е. такое покрытие, элементы которого имеют наибольший суммарный вес Для матрицы строится максимальное покрытие, т.е. такое покрытие, элементы которого имеют наибольший суммарный вес Значение функции похожести текстов определяется как частное суммарного веса элементов максимального покрытия и max(M,N) Значение функции похожести текстов определяется как частное суммарного веса элементов максимального покрытия и max(M,N)

Кластеризация Кластеризация – объединение в группы схожих объектов Кластеризация – объединение в группы схожих объектов На yandex.ru используется двухуровневая иерархическая кластеризация для объединения атомарных кластеров в более крупные (построение «сюжетов»и «событий») На yandex.ru используется двухуровневая иерархическая кластеризация для объединения атомарных кластеров в более крупные (построение «сюжетов»и «событий»)

Основные типы алгоритмов кластеризации Графовые алгоритмы (исходная выборка представляется в виде графа) Графовые алгоритмы (исходная выборка представляется в виде графа) Статистические алгоритмы (основаны на предположении, что кластеры описываются семейством вероятностных распределений) Статистические алгоритмы (основаны на предположении, что кластеры описываются семейством вероятностных распределений) Иерархические алгоритмы (построение системы вложенных разбиений) Иерархические алгоритмы (построение системы вложенных разбиений)

Графовые алгоритмы (алгоритм связных компонент) Выборка представляется в виде графа Выборка представляется в виде графа Вершины графа соответствуют элементам выборки Вершины графа соответствуют элементам выборки Ребрам графа соответствуют расстояния между соответствующими вершинами Ребрам графа соответствуют расстояния между соответствующими вершинами Из графа удаляются все ребра, для которых расстояние между вершинами больше некоторой константы Из графа удаляются все ребра, для которых расстояние между вершинами больше некоторой константы Суть алгоритма – подбор такой константы, чтобы граф распадался на несколько связных компонент Суть алгоритма – подбор такой константы, чтобы граф распадался на несколько связных компонент

Статистические алгоритмы (алгоритм k средних) Элементы выборки представляются n-мерными векторами, расстояние вычисляется как евклидово Элементы выборки представляются n-мерными векторами, расстояние вычисляется как евклидово Необходимо знать число кластеров заранее Необходимо знать число кластеров заранее Идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга Идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга Алгоритм: Алгоритм: 1) Выбор начальных k центров как наиболее удаленных друг от друга объектов выборки 1) Выбор начальных k центров как наиболее удаленных друг от друга объектов выборки 2) Построение k кластеров 2) Построение k кластеров 3) Вычисление нового центра каждого кластера как среднего значения для всех его элементов 3) Вычисление нового центра каждого кластера как среднего значения для всех его элементов 4) Переход ко второму шагу 4) Переход ко второму шагу Выполнение завершается в двух случаях: Выполнение завершается в двух случаях: Покластерное распределение следующей итерации совпало с предыдущей Покластерное распределение следующей итерации совпало с предыдущей Достигнуто некоторое максимальное количество итераций Достигнуто некоторое максимальное количество итераций

Иерархические алгоритмы (алгоритм инкрементальной кластеризации - базовый алгоритм yandex.ru) Задача алгоритма – при получении нового сообщения соотнести его с уже имеющимся кластером или принять решение о создании нового кластера Задача алгоритма – при получении нового сообщения соотнести его с уже имеющимся кластером или принять решение о создании нового кластера Выбирается мера близости нового сообщения и кластера (на этапе определения текстуальной близости) Выбирается мера близости нового сообщения и кластера (на этапе определения текстуальной близости) Для каждого нового сообщения выбирается кластер, наиболее близкий к сообщению Для каждого нового сообщения выбирается кластер, наиболее близкий к сообщению В случае, если значение меры близости превышает некоторое пороговое значение, сообщение добавляется в существующий кластер В случае, если значение меры близости превышает некоторое пороговое значение, сообщение добавляется в существующий кластер Если же значение меры близости не превысило пороговое значение, создается новый кластер Если же значение меры близости не превысило пороговое значение, создается новый кластер

Иерархические алгоритмы (алгоритм инкрементальной кластеризации) Кластеризация выполняется в два подхода, поэтому алгоритм иерархический Кластеризация выполняется в два подхода, поэтому алгоритм иерархический Такой алгоритм кластеризации позволяет строить сюжеты (кластеры высокого уровня) и выделять события внутри каждого из них (атомарные кластеры) Такой алгоритм кластеризации позволяет строить сюжеты (кластеры высокого уровня) и выделять события внутри каждого из них (атомарные кластеры) Документы в данном методе представлены n- мерными векторами Документы в данном методе представлены n- мерными векторами Для реализации такого алгоритма необходимо ввести понятие расстояния между кластером и элементом (вектором). Расстояние может вводиться различными способами Для реализации такого алгоритма необходимо ввести понятие расстояния между кластером и элементом (вектором). Расстояние может вводиться различными способами

Иерархические алгоритмы (алгоритм инкрементальной кластеризации) – td*idf мера Для определения схожести документов используется tf*idf мера (Tf = term frequency, Idf = inverse document frequency): Для определения схожести документов используется tf*idf мера (Tf = term frequency, Idf = inverse document frequency): Размерность вектора, представляющего документ, равна общему количеству термов (различных слов) во всей выборке документов Размерность вектора, представляющего документ, равна общему количеству термов (различных слов) во всей выборке документов J-й элемент вектора I, соответствующего I-му документу, равен tf*idf J-й элемент вектора I, соответствующего I-му документу, равен tf*idf Tf = ½ + ½ * TermFrequency/MaxTermFrequency, где TermFrequency – частота терма в документе, MaxTermFrequency – максимальная частота термов в документе Tf = ½ + ½ * TermFrequency/MaxTermFrequency, где TermFrequency – частота терма в документе, MaxTermFrequency – максимальная частота термов в документе Idf = log(N/df), где N – число документов в выборке, df – число документов, в которых встречается терм Idf = log(N/df), где N – число документов в выборке, df – число документов, в которых встречается терм Схожесть документов определяется как косинус угла между векторами, представляющими документы: Схожесть документов определяется как косинус угла между векторами, представляющими документы:

Ранжирование сюжетов на yandex.ru Основными факторами, влияющими на ранжирование, являются свежесть и размер сюжета Основными факторами, влияющими на ранжирование, являются свежесть и размер сюжета Свежесть отсекает старые сюжеты Свежесть отсекает старые сюжеты Размер позволяет выделить наиболее популярные Размер позволяет выделить наиболее популярные Кроме того, интересным для ранжирования фактором оказался «интерес пользователей поисковой системы» Кроме того, интересным для ранжирования фактором оказался «интерес пользователей поисковой системы»

Что такое RSS? RSS 2.0 – стандарт, определяющий формат xml-документов RSS 2.0 – стандарт, определяющий формат xml-документов RSS = Really Simple Syndication (для версии 2.0) RSS = Really Simple Syndication (для версии 2.0) RSS используется для организации трансляций RSS используется для организации трансляций

Для чего используется RSS Обычно с помощью RSS даётся краткое описание новой информации, появившейся на сайте, и ссылка на её полную версию Обычно с помощью RSS даётся краткое описание новой информации, появившейся на сайте, и ссылка на её полную версию Интернет-ресурс в формате RSS называется RSS-каналом или RSS-лентой Интернет-ресурс в формате RSS называется RSS-каналом или RSS-лентой

Кто работает с RSS Браузеры и почтовые клиенты (IE начиная с 7.0) Браузеры и почтовые клиенты (IE начиная с 7.0) RSS-агрегаторы – приложения, собирающие и обрабатывающие информацию RSS- каналов (yandex.ru – новостной агрегатор) RSS-агрегаторы – приложения, собирающие и обрабатывающие информацию RSS- каналов (yandex.ru – новостной агрегатор)

Пример RSS-документа

Краткая спецификация RSS 2.0 RSS-каналы должны удовлетворять стандарту XML 1.0 RSS-каналы должны удовлетворять стандарту XML 1.0 RSS-канал должен начинаться тегом верхнего уровня с атрибутом version, например, RSS-канал должен начинаться тегом верхнего уровня с атрибутом version, например,

Краткая спецификация RSS 2.0 Внутри элемента должен располагаться элемент. Он содержит описание канала (метаданные) и собственно содержание Внутри элемента должен располагаться элемент. Он содержит описание канала (метаданные) и собственно содержание

Краткая спецификация RSS 2.0 Обязательные подэлементы элемента : Обязательные подэлементы элемента : - имя канала. Например, BBC News. - имя канала. Например, BBC News. - ссылка на сайт, к которому относится канал. Например, - ссылка на сайт, к которому относится канал. Например, - описание канала. Например, The lastest world news from BBC.com - описание канала. Например, The lastest world news from BBC.com

Краткая спецификация RSS 2.0 Необязательные подэлементы элемента : Необязательные подэлементы элемента : Необязательными элементами могут быть теги, указывающие на язык, копирайты, адреса ответственных за работу канала, логотип и т.д. Необязательными элементами могут быть теги, указывающие на язык, копирайты, адреса ответственных за работу канала, логотип и т.д. Например, NewsPaper Например, NewsPaper Или (Betty Guernsey) Или (Betty Guernsey)

Краткая спецификация RSS 2.0 Основными (необязательными) подэлементами являются элементы Основными (необязательными) подэлементами являются элементы Элементы несут смысловую нагрузку Элементы несут смысловую нагрузку Как правило, RSS-канал содержит не более 20 элементов Как правило, RSS-канал содержит не более 20 элементов

Краткая спецификация RSS 2.0 Основные подэлементы элемента : Основные подэлементы элемента : Все подэлементы item-а необязательные, однако каждый элемент должен содержать хотя бы один подэлемент или. Все подэлементы item-а необязательные, однако каждый элемент должен содержать хотя бы один подэлемент или. Каждый элемент может быть анонсом некоторого документа (указаны, например, название, ссылка на документ и вступление) Каждый элемент может быть анонсом некоторого документа (указаны, например, название, ссылка на документ и вступление) Каждый может быть полноценной статьей, тогда весь текст размещается в. Каждый может быть полноценной статьей, тогда весь текст размещается в. Yandex требует, чтобы каждый дружественного СМИ содержал полный текст новости. Yandex требует, чтобы каждый дружественного СМИ содержал полный текст новости.

Пример RSS-документа

История RSS В 1997 году компанией Netscape была предложена первая версия RSS 0.90 В 1997 году компанией Netscape была предложена первая версия RSS 0.90 Следующая версия RSS 0.91 была более простой Следующая версия RSS 0.91 была более простой Netscape прекращает разработку RSS, отойдя от бизнеса порталов. Далее разработкой занимаются две компании – UserLand создает версии 0.92, 0.93, 0.94 и 2.0, RSS-DEV Working Group создает RSS 1.0 и 1.1 Netscape прекращает разработку RSS, отойдя от бизнеса порталов. Далее разработкой занимаются две компании – UserLand создает версии 0.92, 0.93, 0.94 и 2.0, RSS-DEV Working Group создает RSS 1.0 и 1.1 Самыми популярными являются версии 0.91, 1.0, 2.0 Самыми популярными являются версии 0.91, 1.0, 2.0

История RSS Любой файл RSS 0.91 или 0.92 будет также файлом RSS 2.0, но не наоборот Любой файл RSS 0.91 или 0.92 будет также файлом RSS 2.0, но не наоборот RSS 1.0 является продолжением RSS 0.90, более сложный, чем RSS 2.0 RSS 1.0 является продолжением RSS 0.90, более сложный, чем RSS 2.0 Официально с выходом RSS 2.0 были отменены форматы , однако некоторые из них до сих пор используются Официально с выходом RSS 2.0 были отменены форматы , однако некоторые из них до сих пор используются

История RSS Как замена формату RSS был разработан формат Atom, также основанный на XML и предназначенный для выполнения тех же задач Как замена формату RSS был разработан формат Atom, также основанный на XML и предназначенный для выполнения тех же задач Конкуренции не получилось – как правило, поддержка RSS идет вместе с поддержкой Atom Конкуренции не получилось – как правило, поддержка RSS идет вместе с поддержкой Atom В настоящее время главным сторонником RSS является Microsoft, сторонником Atom - Google В настоящее время главным сторонником RSS является Microsoft, сторонником Atom - Google