Hiroki Arimura, Atsushi Wataki, Ryoichi Fujino, and Setsuo Arikawa
A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases
Быстрый алгоритм для обнаружения оптимальных образцов в больших базах данных
Перевод: Погорский Н.В.
2004
2.2 Задача получения данных (data mining problem) 4
3.1 Перечисление образцов в канонической форме с использованием суффиксного дерева 6
3.2 Вычисление значений поддержки с использованием региональных запросов 7
5 Agnostic PAC-learning и минимизация эмпирической ошибки 10
7 Экспериментальные результаты. 12
Мы рассмотрим проблему выборки данных (data mining problem) в больших наборах неструктурированных текстов, основанную на правилах зависимости между подсловами текста. Образец зависимых слов есть выражение такое как
(TATA,30,AGGAGGT) - C
- выражает правило, по которому если текст содержит подстроку TATA, и следующую за ней подстроку AGGAGGT с расстоянием между ними не более 30 символов, то свойство C с высокой вероятностью будет выполняться. Решение проблемы оптимизации доверия образца представляет собой часто встречающиеся образцы (a, k, b), которые оптимизируют доверие по отношению к данному набору текстов. Хотя существует прямой алгоритм, решающий эту задачу за полиномиальное время, который перечисляет все возможные образцы за время O(n5), мы сосредоточимся на рассмотрении более эффективных алгоритмов, которые могут быть применены к большим базам данных. Мы представим алгоритм, который решает задачу оптимизации доверия образца за время O(max{k,m}n2) с использованием памяти O(kn), где m и n – количество и общая длина классифицируемых исходных данных соответственно, k – небольшая константа в диапазоне около 30-50. Этот алгоритм сочетает в себе структуру данных суффиксные деревья и алгоритм регионального поиска (региональные запросы, orthogonal range query), которые ускоряют вычисления. Кроме того, для большинства случайных текстов, таких как последовательности ДНК, мы увидим, что модифицированный алгоритм работает за время O(kn*log(n)3), используя память O(kn). Мы также обсудим некоторые эвристики, такие как осуществление выборки (sampling) и обрезание (pruning) как практические усовершенствования. Затем мы оценим эффективность и работу алгоритмов для эксперимента с генетическими последовательностями. Также обсуждается связь с эффективным Agnostic PAC-learning.
Недавний прогресс связи и сетевых технологий, таких как электронная почта, всемирная паутина, и др. сделали простым накопление больших массивов неструктурированных и полуструктурированных текстовых данных [1]. Такие текстовые базы данных могут быть наборами web-страниц или SGML документов (OPENTEXT Index [26]), баз данных белков (GenBank [11]), online – словарей (OED [13]) и другими очевидными текстовыми данными в файлах. Имеется потенциальный спрос на эффективные методы поиска полезной информации в текстовых базах данных, отличные от существующих методов доступа к информации [1, 19, 28].
Получение данных (data mining) – область исследования, цель которой – разработка полуавтоматических инструментов для поиска полезной информации в больших базах данных. Эта область появилась в начале 90-х годов прошлого века и обширно разработана и в теории и в практике [2, 10, 15]. Однако существующие технологии получения данных имеют дело с хорошо структурированным данными, такими как реляционными базами с булевыми или числовыми атрибутами [2, 10, 15], и, таким образом, напрямую не применимы к неструктурированным массивам данных. Это происходит потому, что текстовые базы данных представляют собой просто набор неструктурированных строк и количество данных огромно, в пределах от мега до терабайт. Мы сосредоточимся на эффективных и адекватных методах поиска, которые работают для больших наборов неструктурированных данных [9, 19, 23, 28].
В этой работе мы рассмотрим поиск очень простого образца, называемого образец зависимых k-близких слов. Возьмем набор текстов S и целевое условие С на S. Образец зависимых k-близких слов – это выражение вида
(TATA, 30, AGGAGGT) - C,
которое выражает правило, по которому если текст содержит подстроку TATA, и следующую за ней подстроку AGGAGGT с расстоянием между ними не более 30 символов, то свойство C для этого текста с высокой вероятностью будет выполняться. Хотя этот класс правил кажется очень ограниченным, они более гибкие для описания локального подобия в текстах с контекстной информацией, чем неупорядоченные наборы ключевых слов или единичных подслов. Следовательно, этот тип правил часто используется в приложениях биоинформатики [12], библиографического поиска [13], и поиска в интернете [26]. Далее, как мы увидим в этой работе, простота класса позволяет адекватно и эффективно работать с зашумленными средами.
Как структуру получения данных мы принимаем так называемый оптимальный образец поиска, недавно предложенный Фукудой (Fukuda) и др. [10]. В их структуре алгоритм поиска получает типовой набор S с целевым свойством C: S –> {0,1} и ищет все/некоторые образцы P, которые максимизируют некоторый критерий. На основании этой структуры мы рассмотрим эффективную разрешимость задачи оптимизации доверия образца и задачи минимизации эмпирической ошибки (Kearns, Shapire, Sellie [17]; Maass [20]).
Задача оптимизации доверия образца может быть решена прямым алгоритмом за время O(n5), который перебирает O(n4) возможных образцов зависимых слов, т.к. самое большое имеется O(n2) возможных подслов. Однако этот полином слишком велик, чтобы применять алгоритм в реальных приложениях. В разделе 3 и 4 мы представим модификации алгоритма, которые находят все образцы зависимых слов, используя структуру данных для обработки тек стов – суффиксные деревья и алгоритм вычислительной геометрии – региональный поиск. Идея состоит в сведении поиска такого образца к рассмотрению прямоугольника со сторонами, параллельными осям, на двумерной плоскости рангов суффиксов.
В 3-ем разделе мы представим алгоритм, выполняющийся за время O(mn2 log2(n)), использующий память O(kmn log(n)), где m и n – количество и общая длина текстов соответственно, k – близость слов. Далее, в 4-ом разделе, осуществляя региональный поиск прямо на суффиксном дереве, мы получим модифицированную версию алгоритма, оценка времени которого O(max{k,m}n2) и памяти O(kn) в самом плохом случае. Для большинства почти случайных текстов, таких как последовательности ДНК, известно, что глубина суффиксного дерева ограничена O(log n). Тогда мы видим, что наш алгоритм может быть преобразован так, что время работы станет O(kn log(n)3) для таких случайных текстов.
В 5-ом разделе, мы описываем приложение [to computational learning theory]. Мы увидим, что наш алгоритм из 4-го раздела может быть преобразован для эффективного решения задачи минимизации эмпирической ошибки. В заключении мы получим эффективный Agnostic PAC-learner для класса образцов зависимых k-близких слов. Nakanishi и др. [25] изучают проблему последовательности (consistency problem), которая является частным случаем задачи минимизации эмпирической ошибки для класса одиночных подстрок. Т.к. одиночная подстрока является частным случаем образца зависимых k-близких слов, мы обобщаем их результат.
В 6-ом разделе, мы вводим некоторые эвристики и анализируем их. В 7-ом разделе мы оцениваем эффективность и работу нашего алгоритма с эмпирической точки зрения, проводя эксперименты с генетическими последовательностями. В заключение, в 8-ой секции мы обобщаем результаты.
Пусть S – конечный алфавит. Мы всегда принимаем фиксированным порядок букв в алфавите S. Если s – строка, S – множество строк, тогда |s| обозначим длину строки, а size(S) – общую длину строк во множестве S. Если существуют некоторые u, v, w Î S*, такие что t = uvw, тогда говорят что u, v и w – префикс, подслово и суффикс t соответственно. Текстом называется любая строка над алфавитом S. За t[i] обозначим i-ую букву в слове t. Местонахождение строки s в t есть целое положительное число i, такое что t[i]…t[i+|t|-1] = s.
Пусть k – целое неотрицательное число. Образец зависимых k-близких слов (k-proximity two words association pattern), или кратко - образец, есть тройка P = (a,k, b) где a,b Î S* - строки над алфавитом S, k³0 – параметр близости слов. Образец удовлетворяет строке s, если существует пара p,q – целые, такая что p и q есть местонахождения строк a и b соответственно, удовлетворяющая неравенствам 0£q-p£k. Пара (p,q) называется местонахождением образца P в строке t. Обозначим число элементов множества S за card(S). Пусть i, j – целые неотрицательные, тогда [i..j] обозначает интервал {i, i+1, …, j} если i£ j или Æ (пустое множество) в противном случае.
2.2 Задача получения данных (data mining problem)
Выборкой называется конечное множество S = {s1,…,sm} строк над алфавитом S и целевое условие на S – двоичная функция С: S®{0,1}. Каждая строка si Î S называется документом, C(si) – его метка. Документ siположительный(позитивный) если C(si) = 1 и отрицательный (негативный) в противном случае. Пусть a - некоторая метка. Обозначим за Sa множество {sÎS | C(s) = a}. Для подмножеств T множества S, мы определим count(P,T) как число документов s Î T удовлетворяющих образцу P.