Технология разработки программного обеспечения(вторая часть)Поведенческие шаблоны проектирования ПО презентация

извлечения информации из Web-документов и сервисов 1.1. Проблемы анализа информации из Web

Поиск значимой информации;
Создание новых знаний вне информации, доступной на Web;
Персонализация информации;
Изучение потребителя или индивидуального пользователя.

и сервисов в Web.
Извлечение информации — автоматическое извлечение определенной информации из найденных Web-ресурсов.
Обобщение — обнаружение общих шаблонов в отдельных и пересекающихся множествах сайтов.
Анализ — интерпретация найденных шаблонов.

Web-контента (Web Content Mining);.
Извлечение Web-структур (Web Structure Mining);
Исследование использования Web-ресурсов (Web Usage Mining).

не имеющие определенной структуры;
К почти структурированным относятся документы, имеющие структуру в целом, но позволяющую вхождение в структурный элемент неструктурированного текста. К таким документам относятся HTML, XML и другие.

соответствие некоторое свойство. Данное свойство может иметь или логический тип, отражающий наличие или отсутствие слова в тексте, или числовое значение, отражающее частоту появления слова в тексте. Последующая обработка может быть связана с удалением пунктуации, нечастых слов, стоп-слов и др. Уменьшение числа свойств возможно за счет применения различных методов выбора свойств, основанных на расчете следующих метрик:
информационного прироста (information gain);.
полного количества информации (mutual information);
перекрестной энтропии (cross entropy);
вероятности успешного исхода (odds-ration).

отметить что векторное представление документов имеет существенный недостаток: оно не обрабатывает синонимы — документы считаются семантически далекими друг от друга, если в них нет одинаковых слов. Данный недостаток устраняется методом скрытой семантической индексации (Latent Semantic Indexing — LSI).

информацию о позиции слова в документе;
использующие n-граммное представление (последовательности слов длины вплоть до n) (например, "морфологический корень" — 3-грамма);
использующие целые фразы (например, "быстрая лиса исчезла из вида");
использующие понятие документа категорий;
использующие термины (например, "норма годового процента" или "Уолл-стрит");
использующие гипернимы (hypernym — слово, являющееся более общим, абстрактным по отношению к данному) (лингвистический термин отношения "это есть" — "собака есть животное", поэтому "животное" — это hypernym "собаки");
использующие адресные объекты (например, имена людей, даты, почтовые адреса, расположения, организации или URL).

для ее решения используются такие же методы. Отдельно стоит остановиться на задаче определения событий и трекинге. Данная задача является частной задачей более широкого направления автоматизированной обработки новостных данных — Topic Detection and Tracking.

В TDT выделяют следующие направления исследований:
разбиение потока на сюжеты;
идентификация новых событий;
определение связей между новостными историями;
отслеживание интересующей пользователя информации.

применяются общие методы Data Mining.

Область применения методов довольно широка:

гипертекстовая классификация;
классификации и кластеризации;
изучение отношений между Web-документами;
извлечение шаблонов или правила;
поиск шаблонов и слабоструктурированных данных.

информационного поиска

методы извлечения Web-контента для целей базы данных используют представления, которые отличаются от представлений, используемых для целей информационного поиска. Данные методы в основном используют представления в виде модели объектного обмена (Object Exchange Model — OEM).
В большинстве своем рассмотренные методы применяются в задачах, связанных с выявлением, исследованием или формированием схем DataGuides.

базе данных

из-за сложности вычислений DataGuide часто аппроксимируется. Некоторые приложения не решают задачу поиска глобальной схемы, они концентрируются на задачах поиска подсхем в слабоструктурированных данных. Другое применение методов данной категории Web Mining — это формирование многослойной базы данных (MLDB), в которой каждый уровень создается обобщением низших уровней и использует специальный язык запросов для Web Mining, чтобы извлекать некоторые знания из MLDB.

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

Гиперссылки моделируются с разным уровнем детализации в зависимости от применения модели. В простейших моделях гиперссылки могут быть представлены как направленный граф:
G = (D, L),
где D — это набор узлов, документов или страниц,
L — набор ссылок.

анализа Web-структуры:

Оценка важности структуры Web (документа или узла), воздействие и влияние их друг на друга;
Поиск Web-документов с учетом гиперссылок, содержащихся в них;
Кластеризация структур для их возможного явного объединения.

значимости Web-структур использовать пути, основанные на входящих ссылках. В соответствии с этой идеей количество путей длиной r от узла i к j обозначается rij. Общее количество путей разной длины вычисляется по формуле: Qij = , величина < 0 должна выбираться таким образом, чтобы обеспечить сходимость формулы для каждой пары. Значимость узла j вычисляется как сумма количеств путей от всех узлов: s j =

в виде: S = (I - bA)-1 - I , где I — единичная матрица; A — матрица, содержащая веса связей между узлами.

для ранжирования найденных документов в поисковых системах. Так, широкое применение в данной категории задачи Web Mining нашла метрика, используемая поисковой системой Google—PageRank. PageRank — статическая величина, предназначенная для оценки качества страниц на основании информации о количестве ссылок на нее.

R i+1 (p) = d + (1 - d) Rj (pi) / Сj(pi), где R( p) — PageRank страницы; C( p) — число исходящих ссылок на странице; k — число ссылающихся на p страниц; d — коэффициент затухания (damping factor), обычно 0,1< d < 0,15 . Если масштабировать PageRank таким образом, что R (pi) = 1, где N — число всех страниц, для которых производится расчет PageRank, то R( p) можно рассматривать как распределение вероятности по всем страницам.

где каждому элементу mij матрицы присваивается значение R0( p) =1/ C( p) в том случае, если с i -й страницы имеется ссылка на j -ю, все оставшиеся элементы матрицы заполняются нулями. Таким образом, вычисление PageRank сводится к отысканию собственного вектора матрицы M , что достигается умножением матрицы M на вектор Rj на каждом шаге итерации. Введение коэффициента затухания гарантирует, что процесс сходится. Другой популярной метрикой определения важности Web-страницы является HITS (Hyperlink-Induced Topic Search). HITS вычисляется локально для каждого запроса.

(Marchiori's) HyperSearch. В нем значение релевантности для страницы p вычисляется методом, который включает релевантность страниц, достижимых из p . При этом зависимость от релевантности достижимой страницы уменьшается за счет коэффициента затухания, уменьшенного экспоненциально с увеличением расстояния от страницы p .

поискового формализма, который будет способен обрабатывать запросы, включающие предикаты текста и ссылок. Ароцена (Arocena), Менделзон (Mendelzon) и Михаила (Mihaila) разработали структуру, поддерживающую Web-запросы, которые комбинируют стандартные ключевые слова с условиями структуры окружающей ссылки.

подобия из библиометрики, вычисляемых для каждой пары документов p и q :
библиографическая связанность (bibliographic coupling) — количество документов, цитируемых обоими документами p и q ;
взаимное цитирование (co-citation) — количество документов, которые цитируют оба документа p и q.

только три фазы:
Препроцессинг;
Извлечение шаблонов;
Анализ шаблонов.

данные, которые описывают использование страниц, такие как IP-адреса, ссылки на страницы, а также дату и время доступа к ним;
пользовательские профили — данные, которые обеспечивают демографическую информацию (пол, возраст, социальное положение и др.) о пользователе, а также регистрационную информацию.

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

удобства), на котором можно увидеть проблемы. IP-адрес 123.456.78.9 относится к трем серверным сессиям. Адреса 209.456.78.2 и 209.45.78.3 относятся к одной — четвертой сессии. Выделение 3-х сессий для одного адреса (с 1-й по 11-ю строку таблицы) возможно на основании совместно используемой информации о ссылке, по которой произошел переход с предыдущей страницы, и агенте.
В данном примере без использования информации о куки-файлах, встроенной в запрос ID сессии, или информации со стороны клиента не удастся определить, что строки 12 и 13 принадлежат одной сессии, т. к. они различаются IP-адресами

Web-ресурсов применяются различные методы как классической статистики, так и относящиеся к области Data Mining.
Многие инструменты анализа трафика позволяют получить такие характеристики, как наиболее часто посещаемые страницы, среднее время посещения страниц или средняя длина пути перемещения по страницам.
Так, например, может быть построена модель зависимости между этапами, которые проходит посетитель, и фактом совершения покупки в интернет-магазине (т. е. модель, отличающая случайного посетителя от потенциального покупателя). Существует несколько вероятностных методов обучения модели, которые могут быть использованы для построения модели поведения пользователя при просмотре Web, включая скрытые модели Маркова (Hidden Markov Models) и Байесовские сети доверия (Bayesian BeliefNetworks).

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

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

Improvement);
Модификация сайтов (Site Modification);
Бизнес-интеллект (Business Intelligence);

и анализ;
Различают следующие категории задач Web Mining: извлечение Web-контента, извлечение Web-структур и исследование использования Web-ресурсов;
В решении задачи извлечения структуры Web используются подходы из области социальных сетей, библиометрики, ранжирования документов и т. п.
Существуют два основных подхода анализа использования Web-ресурсов: преобразование данных использования Web-сервера в реляционные таблицы до выполнения адаптированных методов Data Mining и использование информации из файла протокола непосредственно, применяя специальные методы предварительной обработки.

Вопрос 1. Расположите по порядку следующие этапы Web Mining: извлечение информации, поиск ресурсов, обобщение и анализ

1. Поиск ресурсов;
2. Извлечение информации;
3. Обобщение и анализ.

Вопрос 2. Представлены следующие категории Web Mining. Выберите лишнее.

извлечение Web-контента;
извлечение Web-структур;
исследование использования Web-ресурсов;
создание запросов для БД.

Вопрос 3. Какого типа данные рассматриваются в категории «Извлечение Web-контента»?

неструктурированные и слабоструктурированные Web-документы;
Структуры ссылок;
IP-адреса, URL и а также дату и время доступа к ним.

Вопрос 4. Для построения модели поведения пользователя, при просмотре Web, используются вероятностные методы. Какой из этих методов не может быть использован?

Скрытые модели Маркова (Hidden Markov Models);
Байесовские сети доверия (Bayesian Belief Networks);
Деревья решений.