Содержание к диссертации
Введение
1. Аналитический обзор методов оптимизации запросов СУБД 16
1.1. Локальная оптимизация запросов СУБД 16
1-2. Эффективные алгоритмы выполнения запросов 26
1.3. Глобальная оптимизация потока запросов 31
1.4. Выводы 35
2. Методы группирования данных в задаче анализа потоков запросов 36
2.1. Методы визуализации данных 37
2.2. Методы автоматического группирования данных ., 48
2.3. Алгоритмы поиска if-then правил в данных 56
2.4. Анализ ассоциативных правил , 64
2.5. Предлагаемые новации 69
2.6- Выводы 71
3. Инструменты исследования текстов в задаче анализа потоков запросов 73
3.1. Возможности Text Mining на примере системы Oracle ConText Option 74
3.2. Системы семантического анализа текстов 82
3.3. Система для семантического анализа текстов TextAnaiyst 90
Выводы 101
4. Новые теоретические решения и практические алгоритмы и программы анализа потока запросов. 102
4.1. Программные средства для получения и преобразования исходной информации
4.2. Поиск ассоциативных связей элементов "сырых" запросов в контексте времени их выполнения 112
4.3. Бесконтекстный поиск ассоциативных связей в характеристиках запросов 115
4.4. Результаты кластерного анализа потока запросов 118
4.5. Результаты применения программы TextAnalyst в задаче локализации семантически сходных запросов 123
4.6. Выводы 132
Заключение 134
Литература 135
- Локальная оптимизация запросов СУБД
- Методы визуализации данных
- Возможности Text Mining на примере системы Oracle ConText Option
- Программные средства для получения и преобразования исходной информации
Введение к работе
Типичная сложная информационная система содержит ряд взаимосвязанных компонент: операционную систему, множество бизнес- и аналитических приложений и одну или более базу данных для постоянного накопления транзакций и представления различных отчетов. Все указанные элементы и система в целом нуждаются в исследовании, оптимизации и постоянном мониторинге.
Анализ запросов в сложной информационной системе, как правило, рассматривают в контексте задачи оптимизации запросов. Обычно, говоря про оптимизацию сложных информационных систем, имеют в виду аспект оптимизации запросов и взаимодействий между компонентами систем, то есть такой способ выполнения запросов, когда по начальному представлению запроса путем его синтаксических и семантических преобразований вырабатывается процедурный план выполнения запроса, наиболее оптимальный при существующих в сложных информационных системах управляющих структурах.
Общий подход к оптимизации может быть проиллюстрирован на реляционных базах данных, и мы будем периодически использовать пример реляционных СУБД для. иллюстрации ключевых моментов нашего исследования.
В связи с оптимизацией запросов существует достаточное количество проблем: проблемы преобразований запроса к более эффективному непроцедурному представлению (логическая оптимизация), проблемы выбора набора альтернативных процедурных планов выполнения запроса, проблемы оценок стоимости выполнения запроса по выбранному плану и др. Для решения каждого класса проблем существует более одного подхода. Например, проблемы, связанные с логической оптимизацией запросов, породили направление, называемое семантической оптимизацией [1-6]. Очень многие исследователи заняты проблемами оценок стоимости процедурных планов
выполнения запросов [7—23], хотя до сих пор вопрос о достоверности этих оценок до конца не ясен.
Можно рассматривать оптимизацию и в более широком смысле. Оптимизатор запросов выбирает наиболее оптимальный способ выполнения запроса на основе известных в оптимизаторе стратегий выполнения элементарных составляющих запроса и способов композиции более сложных стратегий на основе элементарных. Тем самым, пространство поиска оптимального плана выполнения запроса ограничено заранее фиксированными элементарными стратегиями. Поэтому существенным направлением исследований, непосредственно примыкающим к вопросам оптимизации, является поиск новых, более'эффективных элементарных стратегий [24-46]. В контексте реляционных СУБД это более всего относится к разработке эффективных алгоритмов выполнения реляционной операции соединения наиболее накладной реляционной операции. При этом исследуются и возможности выбора более адекватных для эффективного выполнения этой операции управляющих структур базы данных, и возможности повышения эффективности за счет распараллеливания выполнения операции на специализированной аппаратуре (здесь направления исследований примыкают к тематике машин баз данных).
Особенно много работ в последние годы посвящается оптимизации запросов и выбору эффективных способов выполнения реляционных операций в распределенных реляционных системах управления базами данных [47-53], Здесь, конечно, существует очень много вариантов и физической организации распределенных баз данных (с поддержкой копий отношений в нескольких узлах сети, с горизонтальным или вертикальным разделением отношений в нескольких узлах, с поддержкой мгновенных снимков базы данных и т.д.), и алгоритмов выполнения реляционных операций при каждой такой организации. Несмотря на то, что реально существуют и функционируют несколько
распределенных реляционных СУБД (например, System R и распределенная INGRES), нельзя считать, что уже найдены адекватные решения этих проблем.
Наконец, сравнительно новой, еще недостаточно исследованной, но безусловно очень важной темой является глобальная оптимизация запросов в системах баз данных [54-72]. Под глобальной оптимизацией понимается совместная оптимизация заранее известного набора запросов- Это наиболее актуально в системах логического программирования (и подобных системах, связанных с обработкой правил), реализуемых на основе реляционных баз данных. При таком подходе выполнение логической программы в конечном счете сводится к выполнению большого количества запросов к базе данных, причем, как правило, запросы содержат соединения. Совместная оптимизация этих запросов способна резко уменьшить общее время выполнения.
Из приведенного краткого описания направлений исследований и разработок в области оптимизации выполнения запросов в реляционных СУБД как и для сложных информационных систем в целом следует практическая актуальность этой тематики. В данной работе мы не будем стремиться привести подробное описание каждого направления с характеристиками всех наиболее важных и интересных решений. Мы ограничимся тем, что более точно сформулируем проблемы и акцентируем основное внимание на проблеме группирования похожих запросов. Это группирование является нетривиальной задачей, обусловленной специфическими конструкциями запросов в сложной информационной системе и связанной с многообразием возможных мер близости (различия) SQL подобных выражений и алгоритмов группирования. Разработка методов и программных средств для группирования запросов в сложной информационной системе является актуальной теоретической задачей, имеющей важные практические приложения.
Целью настоящей работы является повышение производительности сложных информационных систем в целом и приложений, функционирующих в информационных системах.
Для достижения поставленной цели решаются следующие задачи:
1. Исследование и разработка многомерных статистических методов для
решения задачи группирования потока запросов в сложной информационной системе.
2. Исследование и адаптация инструментов анализа текстов для решения задачи
определения подобия запросов.
3. Разработка программных средств для получения и преобразования запросов в
информационной системе для обработки программами группирования многомерной числовой и текстовой информации. Методы исследования основаны на использовании аппарата прикладной статистики, теории баз данных, имитационного моделирования. Результаты исследований получены путем теоретических и компьютерных расчетов, ориентированы на создание конкретных алгоритмических и программных средств, их апробацию и внедрение.
Достоверность результатов определяется корректностью применяемого математического аппарата и подтверждена испытаниями разработанных методов и программных средств на реальных данных.
Положения, выносимые на защиту, L Методика преобразования потока запросов в матрицу количественных
данных.
Подход к интерпретации результатов кластерного анализа потока запросов с помощью логических функций.
Метод генерации "шумящей" выборки запросов, в которой распределение каждого отдельного показателя идентично распределению значений этого показателя в реальной выборке,
Словарь терминов-предгїочтений для системы обработки потока запросов информационной системы.
Научная новизна работы. Получены следующие новые результаты;
Разработана методика определения количественных показателей запросов.
Предложен подход к интерпретации кластеров в потоке запросов посредством логических правил.
Разработан метод генерации многомерной случайной выборки с распределениями значений отдельных признаков, идентичными распределениям значений в реальной выборке.
Разработан словарь терминов предпочтений для выявления сходных запросов.
Практическая ценность. Разработанные методы и инструменты представляют собой ценность для специалистов, деятельность которых связана с задачами сопровождения и оптимизации сложных информационных систем. Программные средства, созданные в результате выполнения диссертационной работы, могут быть востребованы в качестве инструментов для анализа функционирования сложных информационных систем в различных предметных областях. Кроме того, теоретические результаты представляют собой самостоятельную ценность в задачах группирования информации, представленной набором записей на профессионально ограниченных языках.
Реализация. Исследования, отраженные в диссертации, реализованы в виде программные средств "Log-Analyzer", "Cross-Campaign Analyzer", и "Log Transformer", которые предназначены для получения, и преобразования данных для обработки запросов с помощью инструментов статистического анализа. Они внедрены на предприятиях США "Reader's Digest" и "American Express".
Апробация. Результаты работы докладывались и обсуждались на 3 международных и российских конференциях: "CRM for Business-to-Business and Business-to-Concumer" (Boston Prudancial Center, March 2000); "CRM for financial institutions" (June 2003, Toronto, Canada), Юбилейная конференция "20 лет медицинской информатике в СПбМАПО" (март 2006, СПб).
Публнкацни. Основные результаты диссертации изложены самостоятельно и в соавторстве в 5 публикациях.
Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы, включающего 152 наименования. Работа изложена на 151 странице, содержит 15 рисунков и 5 таблиц.
Первая глава имеет следующую структуру. В начале главы рассматриваются проблемы и решения в области локальной оптимизации запросов в реляционных СУБД (далее мы будем называть эту область просто оптимизацией запросов). Анализируются проблемы преобразования запросов в их непроцедурном представлении и, в частности, проблемы семантической оптимизации; проблемы выбора и оценки стоимости альтернативных планов выполнения запросов и проблемы увеличения гибкости оптимизатора по отношению к внедрению новых стратегий выполнения элементарных запросов.
Далее в первой главе приводится обзор работ, связанных с выработкой более эффективных алгоритмов выполнения реляционных операций. Акцент в обзоре приходится на эффективные алгоритмы выполнения соединений и алгоритмы вычисления агрегатных функций.
В завершение главы рассматриваются предпосылки, анализируются имеющиеся подходы и формулируются основные проблемы глобальной оптимизации систем запросов, как одного из наиболее перспективных направлений оптимизации запросов в СУБД.
Практически мало исследованным является применение для анализа потока запросов статистических процедур, в том числе современных продвинутых методов Data и Text Mining, позволяющих выявлять в экспериментальном числовом и текстовом материалы как сравнительно простые, так и неочевидные закономерности. Этому слабо изученному направлению посвящены следующие главы.
Вторая глава посвящена исследованию статистических методов многомерного группирования данных в контексте задачи анализа потока
запросов. Исследуются методы визуализации данных, методы автоматического группирования данных, алгоритмы поиска if-then правил в данных и ассоциативных правил.
Проведенный аналитический обзор методов группирования данных дал основание сделать следующие рекомендации по возможностям их применения в задаче глобальной оптимизации потока запросов в информационной системе.
Методы визуализации могут служить вспомогательным эффективным инструментом для предварительного выделения подгрупп "похожих1' запросов. Среди этих методов наиболее испытанным средством является метод главных компонент. Однако его использование требует специальных преобразований запросов в таблицу "объект-признак". Привлекательным среди методов визуализации данных является использование тех или иных процедур многомерного * шкалирования. Эти процедуры не требуют отмеченного выше преобразования исходной информации к табличной форме, так как для них первичной информацией является матрица сходства-различия запросов информационной системы. Однако сами меры сходства-различия задаются эвристически, и для их вычисления требуется разработка специальной компьютерной программы. Общим недостатком методов визуализации является то, что они "хорошо работают" только при сравнительно небольшом количестве объектов^запросов, когда удобно рассматривать "облака" - сгущения точек (объектов) в различных ракурсах. При большом количестве объектов (а анализируемые потоки запросов сложной информационной системы могут содержать тысячи и десятки тысяч запросов) их проецирование на плоскость или в трехмерное пространство не позволяет "разглядеть" много важных для группирования запросов деталей.
Среди методов автоматического группирования объектов-запросов представляется наиболее эффективным использование алгоритмов иерархического группирования. Эти алгоритмы имеют достаточно высокое быстродействие и способны отражать существенную для решения задачи
оптимизации потока запросов информацию с регулируемой степенью
детализации. Вместе с тем, применение этих алгоритмов для решения задачи
анализа потока запросов также нуждается в дополнительной предобработке
запросов с помощью специальных программ,
Минимальные средства предобработки запросов информационной системы
нужны при использовании алгоритмов поиска ассоциативных правил. Эти
средства фактически могут быть сведены к некоторой "подчистке1' запросов,
которая заключается в удалении лишних, несущественных элементов.
Вместе с тем» применение алгоритмов поиска ассоциативных правил при
анализе потока запросов сталкивается с проблемой выбора целевого или,
иными словами, "осевого" элемента, с которым будут искаться ассоциации
других элементов в запросе.
В ходе исследования проблемы задания целевого атрибута продуктивным
оказался подход, суть которого сводится к поиску ассоциаций в полном наборе
запросов, которые отсутствуют в выборке случайно сгенерированных запросов.
То есть, подход, где целевым атрибутом выступает классифицирующая
переменная, отражающая принадлежность запросов к реальной или случайно
сгенерированной выборке запросов - "шуму".
Генерации случайной выборки посвящено много литературы. В задаче анализа данных эта проблема особенно остро стоит при решении проблемы "множественных сравнений". Основная проблема здесь заключается в том, чтобы у случайно сгенерированной многомерной выборки распределения значений отдельно взятых показателей были бы идентичны распределениям значений в реальной выборке. Решение этой задачи было бы достаточно несложным, если бы указанные распределения подчинялись тем или иным известным законам распределения. Но в реальной жизни мы имеем дело с принципиально неоднородными выборками данных (такими как, например, в нашей задаче анализа потока запросов информационной системы). Поэтому для
генерации случайной выборки, альтернативной реальной выборке нами предложен специальный метод.
Этот метод заключается в том, что случайная выборка образуется из реальной путем случайной перестановки элементов каждого столбца по отдельности- Тем самым, обеспечивается полная идентичность распределений значений столбцов реальной и случайно организованной матрицы данных, В то же время, в "шуме" разрушены взаимосвязи между элементами, присутствующие в реальном потоке запросов.
С целью улучшения интерпретации результатов кластерного анализа предложен подход, основанный на применении технологий поиска if-then правил, в которым классифицирующим фактором служит номер кластера.
Использование логических правил для описания кластеров является более информативным, чем традиционный способ описания через характеристики центроидов. Обращает на себя внимание также тот факт, что в случае центроидов в описании кластеров участвуют все переменные таблицы данных, а в логические правила входят элементарные условия только на существенных переменных. Это заостряет внимание специалиста, занимающегося задачей повышения производительности информационной системы, только на наиболее важных чертах тех или иных группировок запросов.
В третьей главе исследуются методы и инструментальные средства анализа текстовой информации, относящиеся к области Text Mining- Сделан вывод, что большинство коммерческих систем, заявленных в рубрике Text Mining, представляют собой мощные и дорогостоящие программные комплексы, обладающие изощренными и развитыми средствами манипулирования большими массивами текстовой информации. Вместе с тем, в указанных системах сильно завышены притязания на обладание свойствами семантического анализа и поиска в текстах, В большинстве случаев так называемый "семантический анализ" в данных системах сводится к автоматической иерархической рубрификации текстов.
Проведенное в третьей главе исследование позволило выявить две технологии анализа текстов, способные оказаться полезными для группирования потока запросов в информационной системе. Это технология "ключи от текста" () и технология, используемая в системе TextAnalyst ()- Характерной чертой данных технологий является то, что они фактически пренебрегают обширными теоретическими изысканиями в области лингвистики, н опираются на результаты формального статистического анализа словоформ и их сочетаний в текстах. Несмотря на кажущуюся внешнюю ущербность подобного анализа, отмеченные технологии демонстрируют достаточно эффективные и не тривиальные результаты, которые способны в определенной мере претендовать на заявляемую функцию "семантический анализ и поиск1'. Технология "ключи от текстамеще не доведена до стадии коммерческого продукта. Поэтому в для исследования потоков запросов нами выбрана в качестве основы система TextAnalyst.
В оригинальной версии программы TextAnalyst важную роль играет словарь, в который входят слова-предпочтения, слова-исключения, общеупотребимые слова и удаляемые слова. Это естественно, так как программа исходно предназначается для анализа обычных текстов.
В случае анализа потока запросов информационной системы мы имеем дело с профессионально ограниченным языком. Поэтому одной из главных задач использования программы TextAnalyst с целью группирования запросов являлась ее адаптация к этому профессионально ограниченному языку, И эта адаптация, в первую очередь, касается создания нового словаря,
В диссертации с учетом особенностей языка запросов был разработан такой словарь и разработана демонстрация в форме разбора конкретного случая (Case study) использования адаптированной системы TextAnalyst в задаче группирования запросов.
Четвертая глава посвящена новым теоретическим решениям,
* практическим методам, алгоритмам и программам анализа потока запросов,
В этой главе сначала описываются специально разработанные программные
средства, "заточенные" для работы в альянсе с известной системой "The
Affinium Suite" () компании UNICA
(США), предназначенной для проведения полнофункциональных
маркетинговых исследований. Это "Log-Analyzer for Affinium Campaign",
который предоставляет возможность вычленения деталей работы отдельно
взятой маркетинговой кампании в информационной системе, и "Cross-Campaign
Analyzer for Affinium Campaign", который позволяет оценивать эффективность
использования тех или иных источников данных, группировать по заданным
критериям запросы в потоке запросов для определенных периодов времени.
Одна из функций модуля Cross-Campaign Analyzer, полезная для нашего
исследования, заключается в создании логов запросов с привязанными к ним
характеристиками производительности (например, время выполнения запроса и
др.) и экспорте заказанной информации в требуемый формат. Кроме того, нами
разработана программа "Log Transformer", предназначенная для
предварительной подготовки данных перед их дальнейшим анализом с помощью инструментов статистического анализа.
Затем в четвертой главе на реальном материале рассматриваются два варианта поиска ассоциативных связей в наборе запросов. Первый вариант поиска производился с разбиением всех запросов на группы с различным временем выполнения, а второй вариант - вне контекста данного времени.
Для бесконтекстного варианта в потоке запросов выявлено 10 ассоциаций, покрывающих в совокупности 73 % всех запросов информационной системы в рамках анализируемой маркетинговой кампании. Более детальный анализ найденных ассоциаций позволил выделить в них наиболее информативные элементы, которые дают возможность более четко интерпретировать подгруппы запросов, описываемых той или иной ассоциацией. Например, одна
подгруппа запросов характеризуется наличием большой вложенности логических операторов, другой подгруппе свойственно использование арифметических операций и т.д. Такая интерпретация оказалась серьезным подспорьем для специалиста, проводящего работу по глобальной оптимизации информационной системы, давая ему возможность более нацелено исследовать выделяемые подгруппы запросов-
Преобразование потока запросов в форму таблиц "объект-признак" с помощью разработанной программы Log Transformer дало возможность использовать для группирования запросов известные техники кластерного анализа, В нашем случае с этой целью был использован модель кластерного анализа известно статистического пакета SPSS.
Испытания адаптированной программы TextAnalyst на реальном множестве запросов показали, что программа представляет удобный и полезный инструмент для специалиста, занимающегося оптимизацией информационной системы и тесно связанной с этим задачей поиска подмножеств запросов с похожими конструкциями. Скорость ранжирования запросов по степени «похожести» составила доли секунды на ПК Pentium IV 3 ГГц, что является весьма важным при проведении практических исследований потока запросов.
В заключение четвертой главы приводится практический пример анализа потока запросов NET SEG из Readers Digest После проведения комплекса работ с использованием разработанных инструментов статистического анализа потока запросов удалось уменьшить среднее время исполнения запросов за период проведения отдельной маркетинговой кампании более чем в 2 раза.
Локальная оптимизация запросов СУБД
Локальная оптимизация запросов СУБД Оптимизации запросов в реляционных СУБД посвящены несколько объемных обзорных работ. На русском языке в настоящее время доступны книги Дейта [73], Ульмана [74] и Мейера [75], в которых проблемам оптимизации посвящены отдельные главы. Более современные работы рассматриваготся в последнем издании книги Дейта [76]- Наконец, наиболее полный, на наш взгляд, обзор подходов и методов оптимизации запросов содержится в статье [77].
Историю оптимизации запросов отсчитывают с середины 70-х годов, хотя, конечно, исследования проводились и раньше. Фундаментальные работы, относящиеся к оптимизации запросов, были выполнены в рамках проектов System R корпорации IBM [78] и Ingres университета Беркли [79]. В System R были заложены основы техники оптимизации запросов на основе оценок стоимости плана выполнения запроса [80]. В университетском проекте Ingres, фактически использовались методы, которые позже стали называть семантической оптимизацией запросов.
Достаточно полный и актуальный в настоящее время обзор подходов к оптимизации запросов в SQL-ориентированных СУБД приведен в [81]. Более современный обзор дан Чаудхари в [82]. Этапы обработки запроса в SQL-ориентированной СУБД Обработка запроса состоит из этапов (фаз), представленных на рисЛ [83]. На первой фазе запрос подвергается лексическому и синтаксическому анализу. При этом вырабатывается его внутреннее представление, отражающее структуру запроса и содержащее информацию, которая характеризует объекты базы данных, упомянутые в запросе (отношения, поля и константы). Информация о хранимых в базе данных объектах выбирается из каталогов базы данных. Внутреннее представление запроса используется и преобразуется на следующих стадиях обработки запроса. Выбор внутреннего представления должно быть достаточно удобным для последующих оптимизационных преобразований.
На второй фазе запрос в своем внутреннем представлении подвергается логической оптимизации- При этом могут применяться различные преобразования, "улучшающие1 начальное представление запроса. Среди этих преобразований могут быть эквивалентные преобразования, после проведения которых получается внутренне представление, семантически эквивалентное начальному (например, приведение запроса к некоторой канонической форме). Преобразования могут быть и семантическими, когда получаемое представление не является эквивалентным начальному, но гарантирует, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в базе данных. В любом случае после выполнения второй фазы
обработки запроса его внутреннее представление остается непроцедурным, хотя и является в некотором смысле более эффективным, чем начальное.
Третий этап обработки запроса состоит в выборе на основе априорной информации набора альтернативных процедурных планов выполнения данного запроса. Кроме того, для каждого плана оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется статистическая информация о состоянии базы данных, доступная оптимизатору- Из полученных альтернативных планов выбирается наиболее дешевый, и именно его внутреннее представление теперь соответствует обрабатываемому запросу.
На четвертом этапе по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое представление плана. Выполняемое представление плана может быть программой в машинных кодах или быть машинно-независимым, но более удобным для интерпретации, если система ориентирована на интерпретацию запросов. В контексте нашего исследования случае это непринципиально, поскольку четвертая фаза обработки запроса уже не связана с оптимизацией.
Наконец, на последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с выполняемым планом запроса. Это либо выполнение соответствующей подпрограммы, либо вызов интерпретатора с передачей ему для интерпретации выполняемого плана.
Заметим, что для нашего рассмотрения несущественно разделение процесса обработки запроса на подготовительную (включающую фазы 1-4) и исполнительную (фазу 5) части. В представленную схему укладывается и реальное отделение по времени первых четырех фаз от пятой (подход с предварительной компиляцией запроса до реального выполнения), и последовательное выполнение всех пяти фаз при каждом выполнении запроса. Для строгости заметим, что некоторые методы оптимизации (и даже подходы к оптимизации) довольно сильно зависят от общей организации обработки запроса. При отрыве во времени процесса компиляции от реального выполнения запроса оптимизатор располагает меньшей и менее достоверной информацией, чем в том случае, когда этап компиляции тесно привязан к этапу выполнения (выполняется в рамках транзакции пользователя).
Методы визуализации данных
Как следует из аналитического обзора, представленного в предыдущей главе, важная роль при решении задачи глобальной оптимизации отводится методам группирования «похожих» запросов в общем потоке запросов информационной системы. Эти методы можно разделить на три большие группы.
Первая группа методов использует аппарат многомерной прикладной статистики и включает в себя методы визуализации многомерной информации и алгоритмы автоматического группирования данных- Использование указанной группы методов предполагает предварительную обработку запросов с целью приведения их к форме таблиц «объект-признак».
Вторая группа методов занимает относительно самостоятельное место среди аппарата прикладной статистики. Эта группа методов в современном понимании относится к инструментарию Data Mining и предназначена для поиска в данных ifhen правил, выражающих характерные черты подгрупп многомерных объектов (запросов, в нашем случае). Одна часть рассматриваемой группы также требует предварительной предобработки и приведения исходной информации к форме таблиц «объект-признак». Другая часть имеет дело с поиском ассоциативных связей в запросах—транзакциях, не приведенных к форме плоской таблицы.
Третья группа методов относится к области анализа текстовой информации базируется на своем специфическом инструментарии.
В настоящей главе рассматривается первые две группы методов и алгоритмов. Методы визуализации данных Основное назначение рассматриваемой группы методов — дать визуальное представление о структуре изучаемых данных. Визуализация данных предполагает получение тем или иным способом графического отображения совокупности объектов на числовую ось? на плоскость или в трехмерный объем, максимально отражающего особенности распределения этих объектов в многомерном пространстве.
Метод главных компонент (МГК) был предложен Пирсоном в 1901 году и затем вновь открыт и детально разработан Хоггелннгом в 1933 году. Ему посвящено большое количество исследований, и он широко представлен в литературных источниках. Обратим внимание на основные феномены МГК.
Линейные комбинации выбираются таким образом, что среди всех возможных линейных нормированных комбинаций исходных признаков первая главная компонента у\(х) обладает наибольшей дисперсией. Геометрически это выглядит как ориентация новой координатной оси i вдоль направления наибольшей вытянутости эллипсоида рассеивания объектов исследуемой выборки в пространстве признаков х\, -- л - Вторая главная компонента имеет наибольшую дисперсию среди всех оставшихся линейных преобразований, некоррелированных с первой главной компонентой. Она интерпретируется как направление наибольшей вытянутости эллипсоида рассеивания, перпендикулярное первой главной компоненте- Следующие главные компоненты определяются по аналогичной схеме.
То есть полагается, что значения каждого признака х могут быть выражены взвешенной суммой латентных переменных (простых факторов) , количество которых меньше числа исходных признаков, и остаточным членом t с дисперсией Т(є) действующей только на xif который называют специфическим фактором.
Коэффициенты Ц называются нагрузкой j-й переменной на -й фактор или нагрузкой у-го фактора на /-ю переменную. В самой простой модели факторного анализа считается, что факторы J] взаимно независимы и их дисперсии равны единице, а случайные величины ; тоже независимы друг от друга и от какого-либо фактора fj. Максимально возможное количество факторов т при заданном числе признаков/? определяется неравенством которое должно выполняться, чтобы задача не вырождалась в тривиальную. Данное неравенство получается на основании подсчета степеней свободы, имеющихся в задаче [ПО]. Сумму квадратов нагрузок называют общностью соответствующего признака х,- и чем больше это значение, тем лучше описывается признак дг( выделенными факторами fJt Общность есть часть дисперсии признака» которую объясняют факторы. В свою очередь, sf показывает, какая часть дисперсии исходного признака остается необъясненной при используемом наборе факторов, и данную величину называют специфичностью признака. Задачу факторного анаїшза нельзя решить однозначно. Равенства в факторной модели не поддаются непосредственной проверке, так как р исходных признаков задается через (р + т) других переменных - простых и специфических факторов. Поэтому представление корреляционной матрицы факторами, как говорят ее факторизацию можно произвести бесконечно большим числом способов. Если удалось произвести факторизацию корреляционной матрицы с помощью некоторой матрицы факторных нагрузок F, то любое линейное ортогональное преобразование F (ортогональное вращение) приведен к такой же факторизации [109]. Поэтому нередко в одном и том же пакете программ анализа данных реализовано сразу несколько версий методов факторизации, и у исследователей возникает закономерный вопрос, какой из них лучше. Здесь сошлемся на слова одного из основоположников современного факторного анализа Г. Хартмана: "Ни в одной из работ не было показано, что какой-либо один метод приближается к "истинным7 значениям общностей лучше, чем другие методы... Выбор среди группы методов наилучшего производится в основном с точки зрения вычислительных удобств, а также склонностей и привязанностей исследователя, которому тот или иной метод казался более адекватным его представлениям об общности" /цит. по [111]/.
Возможности Text Mining на примере системы Oracle ConText Option
Oracle ConText Option — это решение для управления текстом, которое дает возможность организациям использовать текстовые источники информации так же быстро и легко, как и структурированные данные, Oracle ConText Option — ключевой компонент сервера Oracle Universal Server, полного решения для управления реляционными, текстовыми, пространственными, графическими, видео и звуковыми данными в любом приложении, в любом масштабе.
Разработчики Oracle ConText Option отмечают, что задача выявления информационного неструктурированного текстового ресурса оставалась до сих пор практически нерешенной. В то время как для структурированных данных использовались мощные, основанные на SQL реляционные базы данных, для текста применялись специфические и трудно масштабируемые процессоры поиска» Современные решения нуждаются в унифицированной, основанной на стандартах, масштабируемой системе для управления каждым видом информации.
Oracle удовлетворяет эту потребность с помощью ConText Option для Oracle7. Теперь предоставляются возможности интегрировать большие объемы текстовых данных со стратегическими приложениями клиент/сервер, которые позволяют сохранять, управлять, отыскивать, редуцировать и классифицировать текст с помощью новых эффективных методов, ConText Option объединяет мощность Огас1е7 и SQL с современной технологией текстового поиска. Преимущества интеграции ConText option с Oracle Universal Server возможность работы как с текстами, так и со структурированной информацией из одного и того же приложения, используя SQL. возможность написания приложений с использованием любого инструментария (Developer/2000, PowerBuilder, Delphi, SQL Windows,»)» поддерживающего SQL и вызов хранимых процедур Oracle. возможность хранения текстов как в базе данных, так и в файлах операционной системы, а также в Internet. использование всех мощностей Oracle Server (распараллеливание, распределенная обработка, репликации) для работы с текстами. Возможности технологии ConText Option text retrieval — полнотекстовый поиск по документам при помощи стандартного SQL, включающий в себя следующие средства: V exact searching — поиск документов по точному совпадению слова или фразы; V wildcard searching — поиск с использованием шаблонов; V proximity searches — поиск документов, где слова из поискового критерия располагаются близко друг от друга; V boolean logic — поддержка булевой логики; J multilingual stemming — обработка по словообразующим; V thesaurus support — поддержка тезаурусов, поиск с использованием синонимов и иерархии терминов; S soundex searching — поиск по созвучию, т.е поиск слов, для которых известно произношение, но неизвестно правильное написание, {для документов на английском и некоторых других европейских языках, кроме русского); S fuzzy searching — поиск слов заданных в критерий правильно, а в документе с ошибками, например, при вводе документов через OCR; text classification — классификации документов по автоматически сгенерированным темам (для англоязычных документов); text reduction — автоматическая подготовка краткого содержания по тексту документа (для англоязычных документов). Языковая поддержка В настоящее время Oracle ConText Option поддерживает основные европейские языки (английский, французский, немецкий, голландские итальянский, испанский), японский, корейский, китайский, а также русский. Области применения ConText Option большие архивы текстов и multimedia доступ к текстам через WWW хранение статей (газеты, конференции) техническая поддержка коммерческие и правительственные приложения библиотеки законодательство и многое другое Способы хранения документов
Независимо от выбранного способа хранения идентификатор документа и его текст или указатель на файл должны храниться в таблице базы данных. Эта таблица может содержать заголовок документа, дату публикации и любые другие атрибуты документа. Сам текст документа может храниться двумя способами: direct (в базе данных) в LONG или LONG RAW столбце таблицы. Каждый документ занимает одну строку таблицы. Преимущества этого метода хранения заключаются в экономии пространства в базе данных и простоте структуры таблицы документов. С другой стороны, использование типа LONG резко ограничивает возможности обработки текста документа. в VARCHAR2 столбцах — конфигурация Master-Detail.
В этом случае документ хранится в двух таблицах, связанных отношением Master-Detail- Master-таблица содержит идентификатор документа в качестве первичного ключа и другие атрибуты документа. Detail-таблица содержит идентификатор документа как внешний ключ, номер строки в документе и текст строки.
Программные средства для получения и преобразования исходной информации
Получение исходного материала для дальнейшего анализа с целью оптимизации информационной системы связано с необходимостью разработки специальных программных средств, встраиваемых в данную информационную систему и учитывающих специфику решаемых системой информационных задач- В данном разделе будут охарактеризованы специально разработанные программные средства, "заточенные" для работы в альянсе с известной системой "The Affmium Suite" (http://www.unicacorpxom/products/index-html) компании UN1CA (США), предназначенной для проведения полнофункциональных маркетинговых исследований- Это весьма сложная и дорогостоящая система, включающая в себя модули моделирования, планирования, управления и генерации отчетов для обеспечения всей технологической маркетинговой цепочки- Эффективность системы "The Affmium Suite" подтверждена ее использованием в ряде крупнейших американских корпораций (табл- 4-1) Как видно из таблицы, в число пользователей "The Affinium Suite" входят крупнейшие предприятия США (например, "Reader s Digest"), маркетинговые компании которых достигают весьма впечатляющих масштабов- В этих компаниях одновременно принимают участие десятки и сотни менеджеров и аналитиков, чем определяется высокая нагрузка на используемую информационную систему и соответствующие высокие требования ко всем ее компонентам. При этом, конечно, далеко не последнее место занимают требования к быстродействию системы, чем определяется значимость задачи ее оптимизации.
-103-Среда, в которой работает программное обеспечение UNICA, сложна и состоит из сетей, баз данных, серверов и различных платформ- Проблема оптимизации "The Affinium Suite11 трудна из-за этой сложности и взаимосвязанности различных систем IT, Для решения этой проблемы мы, прежде всего, разработали два программных модуля, позволяющих, в частности, регистрировать транзакции и некоторые важные показатели производительности системы.
" Log- Analyzer for Affinium Campaign" предоставляет возможность "объемного11 видения деталей работы отдельно взятой маркетинговой кампании в информационной системе. Обычно, наибольший интерес здесь представляют статистические сведения о наихудших с точки зрения производительности запросов, время, затрачиваемое системой на те или иные процессы, время передачи информации по сети, время записи результатов и др. "Cross-Campaign Analyzer for Affinium Campaign" позволяет идентифицировать "плохие 1 в том или ином контексте запросы в повторяющихся маркетинговых кампаниях и обеспечивает детализацию элементов таких запросов для дальнейшего анализа. Этот модуль позволяет оценивать эффективность использования тех или иных источников данных, группировать по заданным критериям запросы в потоке запросов для определенных периодов времени. Одна из функций модуля Cross-Campaign Analyzer, полезная для нашего исследования, заключается в создании логов запросов с привязанными к ним характеристиками производительности (например, время выполнения запроса и др.) и экспорте заказанной информации в требуемый формат. Пример такой информации, экспортированной в HTML документ приведен на рис. 4.2.
Здесь в левой колонке содержатся выражения запросов, затем во второй колонке записан идентификатор запроса, и в следующих колонках отображены время начала и окончания выполнения каждого запроса. Указанная информация служит первичным материалом для дальнейшей обработки различными методами, описанными в главах 2 и 3.
Еще одна специально разработанная программа LogTransformer предназначена для предварительной подготовки данных перед их дальнейшим анализом с помощью инструментов статистического анализа. На входе LogTransformer мы имеем текстовый файл со строками вида: expression timeelapsed time_download tot#_ofjecords, (4.1) где expression — строка запроса, которая будет анализироваться; time_elapsed, time_download - времена выполнения тех или иных операций; tot#_of records - число записей в потоке запросов. На выходе LogTransformer выдает таблицу (как в виде текстового файла с разделителями, так и в экранном виде), где столбцами являются различные параметры запроса, а строками - запросы из входного файла (строка из входного файла соответствует строке выходного). Пользователь может выбирать, какие параметры запроса отобразить в таблице.
Опишем более подробно функционирование LogTransformer.
Программа анализирует запросы из текстового файла, каждая строка которого имеет вид (4.1). Разделители — знак табуляции. Первая строка - имена полей (первая строка не анализируется).
Изначально в Summary Table стоят пороговые значения, принятые по умолчанию. Их можно изменить вручную и пересчитать значения процентов нажатием кнопки Refresh Summary Table, Следует учесть, что Summary Table составляется на основании главной таблицы (Table of Queries1 Parameters), поэтому если из главной таблицы были удалены какие-то записи, то и в Summary Table они учитываться не будут. Также важно заметить, что значения в Summary Table пересчитываются только по нажатию кнопки Refresh Summary Table или кнопки Go.
Далее полученные результаты (таблицу Table of Queries Parameters) можно вывести в текстовый файл с разделителями - знаками табуляции. Это делается по нажатию кнопки То File. Таблица выводится в файл в том же виде, что и на экране (то есть с теми же столбцами, и если в ней были удалены строки, то они в файл выведены не будут). Путь к выходному файлу, как уже было сказано ранее, можно изменить с помощью кнопки Change Output или введя вручную-Также можно в отдельный файл вывести сами запросы, которые анализировались в программе- Это можно сделать по нажатию кнопки Expressions to file. Для вывода создается файл с тем же путем и названием, что и у выходного файла, но к названию добавляется __ехрг (то есть, если в качестве выходного указан файл table.txt, то запросы будут выведены в файл table_expr.txt).
