«ПРЕДСТАВЛЕНИЯ И ПОИСКА СХОДНЫХ СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ЗАДАЧАХ КЛАССИФИКАЦИИ НА ОСНОВЕ РАССУЖДЕНИЙ ПО ПРИМЕРАМ ...»

В предлагаемом детерминированном методе вложения расстояния редактирования, входная строка x n преобразовывается в вектор v(x) конкатенацией всех q-граммных векторов vi,w,q = vw,q (x[i, i + w 1]), для q = q1,..., q и i = 1,..., n w + 1. В качестве расстояния между векторами принимается манхетенново (1 ) расстояние.

Для строк x, y n определим, с использованием введенного в (2.1) расстояния d 1,q2 (x, y), расстояние и с использованием доказанных в предыдущем подразделе утверждений покажем, насколько хорошо аппроксимирует расстояние редактирования предлагаемый метод вложения.

2.4.1. Нижняя оценка стоимости редактирования Будем находить ограничение снизу на количество плохих интервалов при ed(x, y) > k2, где k2 – параметр метода. Пусть количество плохих интервалов фиксировано, обозначим его N. Найдем сначала ограничение сверху на стоимость редактирования по всем возможным расположениям N интервалов, используя следующий алгоритм редактирования (восстановления) строк.

Будем последовательно переходить от интервала к интервалу, смещаясь на один символ. Допустим, строка восстановлена до позиции j 1. Если последовательно все интервалы, начиная с j-й позиции и до интервала в (j + r)-й позиции, хорошие, то они восстанавливаются за не более, чем 2(q + 1) операций, используя результат леммы 2.6 для t = 1. Все интервалы в позициях, затронутых этим восстановлением (т.е. начинающиеся между позициями j и j + r), назовем накрытыми. Если следующий, интервал, начинающийся в jй позиции, плохой, используем одну операцию редактирования, замещая x[j] на y[j] и восстанавливая таким образом один символ, и далее переходим к следующему интервалу, начинающемуся в (j + 1)-й позиции.

Псевдокод изображен на рис. 2.10. Функция Good(x, y) возвращает true, если выполняются условия леммы 2.5 и d 1,q2 (x, y) < Q и false в других случаях. Функция EditShift(x, y) выравнивает строки x, y, являющиеся сдвигом друг друга, затрачивая на это не более 2(q + 1) операций редактирования (лемма 2.5). Функция Replace(a, b) заменяет символ a на символ b, используя одну операцию замены. Отметим, что нам не нужно в действительности использовать этот алгоритм, нас интересует только оценка числа операций редактирования.

Лемма 2.7. Обозначим S =. Восстановление строки y из x с помоw щью описанного алгоритма потребует не более операций, чем Доказательство. Найдем расположение плохих интервалов, которое максимизирует стоимость редактирования по описанному алгоритму на рис. 2.10.

По определению расстояния редактирования, это верхняя оценка ed(x, y).

Максимальная стоимость редактирования будет достигаться при максимальном количестве возникновений ситуации, описанной в лемме 2.6. Поэтому расположение плохих интервалов, на котором достигается максимум стоимости редактирования, будет иметь вид повторяющихся серий вида +-===, output: edit distance upper estimate return edit_dist ;

где плюсом (+) обозначен хороший интервал, минусом (-) – плохой, а знаком равенства (=) – накрытый хороший (достаточно только одного минуса, следующего за плюсом, для добавления 2(q + 1) операций в общую стоимоcть).

Кроме того, в искомой конфигурации последний интервал будет хорошим, т.к.

это дает дополнительные 2(q + 1) операций редактирования к суммарной стоимости.

Таким образом, общая стоимость редактирования всех конфигураций вида +-=== есть 2(q + 1) min(S, N ) (стоимость восстановления таких конфигурации, умноженная на максимальное их число). Остается или nw·min(S, N ) плохих интервалов (минус единица здесь из-за последнего, всегда хорошего, интервала), или N min(S, N ) – в зависимости от того, какое из этих выражений имеет меньшую величину.

Проанализируем, какие значения может принимать выражение (2.10). Если S N, тогда 2. N > n 1 (w 1)N быть не может, т.к. тогда N > n 1/w = S, что Таким образом, из 1)–3), получаем, что если S N, то 1. если N < n 1 (w 1)S, то, подставляя S < N, ed (2(q+1)1)S+N +2(q+1) < 2N Q+2(q+1) = 2(q+1)(N +1);

3. если N = n 1 (w 1)S, подставляя S < N, то как и в 2) получаем ed k2, q1 > 2w/3, а также выполняются Доказательство. Допустим от противного, что число плохих интервалов Получаем противоречие с предположением ed(x, y) > k2.

Учитывая следствие 2.1, которое говорит о группировке плохих интервалов в кластеры по не менее t = w q2 q подряд идущих интервалов, можно доказать следующую лемму, которая аналогична лемме 2.7.

Лемма 2.8. Пусть число плохих интервалов для строк x, y длиной n фиксировано и равно N. Тогда Экспериментальная иллюстрация лемм 2.7 и 2.8 приведена в п. 2.5.1.

Аналогично следствию 2.2, с учетом леммы 2.8 получаем следующее следствие.

Следствие 2.3. Пусть ed(x, y) > k2, тогда N > t( 2(q+1) 2).

2.4.2. Верхняя оценка на расстояние редактирования Для x, y w назовем q-грамму x[i, i + q 1] k-хорошей, если найдется такая q-грамма y[i, i + q 1], что |j i| k, т.е. q-грамма в строке y, сдвинутая не более, чем на k символов. Если такой q-граммы в y нет, то назовем x[i, i + q 1] k-плохой.

Интервал [i, i+q1] назовем k-хорошим, если B[x[i, i+q1], y[i, i+q1]; q] является сдвигом и число k-хороших q-грамм в обеих строках больше или противном случае.

Пусть N [R] – количество интервалов [i, i + w 1], где выполняется некоторое условие R, налагаемое на эти интервалы.

Доказательство. Подсчитаем минимальное количество k1 -хороших интервалов при ed(x, y) k1 согласно лемме Укконена (п. 1.3.3, стр. 29). Всего имеется n w + 1 интервалов. Поскольку каждая операция редактирования может изменить максимум w интервалов, то общее количество k1 -плохих интервалов не превышает k1 w. Оставшиеся n w + 1 k1 w интервалов будут k1 -хорошими, поскольку могут сдвинуться максимум на k1 символов. Для k1 -хорошего интервала [i, i + w 1] d 1,q2 (x[i, i + w 1], y[i, i + w 1]) = q=q 2.4.3. Объединение оценок С использованием следствия 2.3 и леммы 2.9 можно определить верхнюю Обозначим множество позиций, где начинаются плохие интервалы, как и множество позиций, где начинаются хорошие интервалы, как IG = {i = 1,..., n w + 1 | d 1,q2 (x[i, i + w 1], y[i, i + w 1]) < Q}. Тогда, учитывая следствие 2.2, получаем Учитывая группировку плохих интервалов (следствие 2.3), получаем Обозначим множество позиций, где начинаются k1 -плохие интервалы, как IB1 = {i = 1,..., nw+1 | j [ik1,..., k1 +i], y[j, j+q1] = x[i, i+q1]}, а где начинаются k1 -хорошие – как IG1 = {i = 1,..., n w + 1 | j [i (n w + 1)(q + 1)D(x, y) = Таким образом, доказана следующая теорема Построение векторов v(·) с помощью префиксного дерева потребует порядка O(n(q2 + w)) операций. Соответственно, общая оценки времени построения равна O(n1+ ).

Размерность вектора v(·) при условии фиксированого алфавита определяется количеством уровней префиксного дерева q = O(n/2 ) и количеством узлов на каждом уровне – O(n), поэтому итоговая размерность имеет порядок всего O(n1+/2 ). Такой же порядок имеет и время вычисления расстояния между векторами.

Из (2.12) и (2.13) следует, что для обеспечения d2 > d1 необходимо, чтобы k2 = (k1 (n + n1 )). Отсюда, оптимальным значением будет = 1/2, при этом k2 = (k1 n1/2 ) и время построения векторов v(·) – O(n3/2 ), а их размерность – O(n5/4 ).

2.5. Численное исследование детеминированного метода вложения В данном подразделе проводится проверка некоторых из доказанных лемм с помощью численных экпериментов.

2.5.1. Экспериментальное исследование результатов лемм 2.7 и 2. Для экспериментальной проверки и иллюстрации доказательства лемм 2. и 2.8 сведем задачу к задаче нахождения разметки в (max, +)-задаче на цепочечной структуре (см., например, [150]) с 2(w + 1) состояниями.

Пусть K, |K| = 2(w + 1) – это следующее множество состояний:

1. + – хороший интервал, 2. – плохой интервал, 3. +c – накрытый хорошой интервал, i = 1,..., w, 4. c – накрытый плохой интервал, i = 1,..., w.

Построим граф соседства [150] следующим образом. Каждому интервалу в строке подставим в соответствие вершину, состояние или метка которой может принимать значения из описанного множества. Индексами i = 1,..., w указывается порядковый номер накрытого состояния внутри участка, восстанавливаемого за 2(q + 1) операций по лемме 2.6.

Вершины, соответствующие соседним интервалам, соединим дугами, вес которых определяется функциями переходов g(t, t ) между состояниями t, t K, которые определяют разрешенные переходы и их стоимость. Функции переходов g(t, t ) определяются из алгоритма восстановления 2.10 и задаются следующим образом:

• g(+, ) = – запрещен, т.к. после хорошего интервала начинаются накрытые состояния, • g(, +) = 1 – одна простая замена при нахождении в плохом интервале, • g(+, +) = 0 – переход без стоимости, • g(, ) = 1 одна замена, аналогично случаю g(, +), • g(, c ) = – входа в накрытое состояние из плохого интервала нет, ние (всегда плохое) платим полную стоимость, • g(+, +c ) = – хороший интервал не накрывает другой хороший, т.к.

они могут быть восстановлены вместе, • g(, +c ) = – плохой интервал не накрывает ничего.

Участок получаемого графа приведен на рис. 2.11. Дуги нулевой стоимости обозначены пунктиром, запрещенные дуги, стоимость которых равна, не показаны.

Разметкой графа назовем присвоение каждой вершине метки из множества K. Будем искать разметку k = arg maxk,|k| =N i=2,...,n g(ki1, ki ) (тут |k| – количество плохих интервалов, как накрытых, так и нет).

Поскольку структура полученного графа – цепочка, задача (max, +) без ограничения |k| = N решается с помощью динамического программирования за время O(nw2 ) [150]. За время O(n(wN )2 ) находится максимальный путь, содержащий фиксированное число N плохих интервалов (условие |k| = N ).

Это достигается введением дополнительных копий состояний на каждом шаге i, для каждого из возможных 0,..., N текущих значений количества плохих интервалов |k1... ki |, которые к этому шагу содержатся в k1... ki (на рис. 2. не показаны).

Экспериментально полученные разметки для разных значений w приведены в таблице 2.12 при N = k = 10, 20 и длине последовательности k = 68. Для данного примера 2(q + 1) = 10. Значение 4(q + 1)(N + 1) при N = 10, 20 соответственно равно 220 и 420. Приведенная последовательность k хороших (+) и плохих () интервалов каждой строке максимизирует расстояние редактирования по алгоритму 2.10 для изменяющейся ширины интервала w = 2,..., 68 (первый столбец). Накрытые состояния (+) и () обозначены, соответственно, (=) и (_). Реальное количество операций редактирования, возвращаемое алгоритмом на рис. 2.10, и значение по формуле (2.10) приведены, соответственно, в предпоследнем и последнем столбцах.

Аналогичные разметки, с учетом группировки плохих интервалов (лемма 2.8), приведены в таблице 2.13 для тех же значений N, w. Минимальная длина последовательсности из плохих интервалов t = 3 и t = 5. Значение 4(q + 1)( t количество операций редактирования, возвращаемое алгоритмом на рис. 2.10, приведено в последнем столбце.

Рис. 2.11. Пример участка графа соседства и разрешенные переходы между состояниями j-й и j + 1-й вершин 2 +_+_+_+_+_+_+_+_+_+_++++++++++++++++++++++++++++++++++++++++++++++++ 220 220 2 +_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_++++++++++++++++++++++++++++ 420 3 +_=+_=+_=+_=+_=+_=+_=+_=+_=+_=++++++++++++++++++++++++++++++++++++++ 220 220 3 +_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=+_=++++++++ 420 4 +_==+_==+_==+_==+_==+_==+_==+_==+_==+_==++++++++++++++++++++++++++++ 220 220 4 ---+=+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+_==+ 343 5 +_===+_===+_===+_===+_===+_===+_===+_===+_===+_===++++++++++++++++++ 220 220 5 +--+_=+_===+_===+_===+_===+_===+_===+_===+_===+_===+_===+_===+ 282 6 +_====+_====+_====+_====+_====+_====+_====+_====+_====+_====++++++++ 220 220 6 +_+_-+_====+_====+_====+_====+_====+_====+_====+_====+_====+ 241 7 -+_=====+_=====+_=====+_=====+_=====+_=====+_=====+_=====+_=====++++ 201 201 7 +----+_===+_=====+_=====+_=====+_=====+_=====+_=====+_=====+ 204 8 --+_======+_======+_======+_======+_======+_======+_======+_======++ 182 182 8 +_---+===+_======+_======+_======+_======+_======+_======+ 183 9 ---+_=======+_=======+_=======+_=======+_=======+_=======+_=======++ 163 163 9 +----+_=====+_=======+_=======+_=======+_=======+_=======+ 164 10 ----+_========+_========+_========+_========+_========+_========++++ 144 144 10 -------+=+_========+_========+_========+_========+_========+ 147 11 -+======+_=========+_=========+_=========+_=========+_=========+ 141 141 11 +-+_=====+_=========+_=========+_=========+_=========+ 141 12 -----+_==========+_==========+_==========+_==========+_==========+++ 125 125 12 -------+_==+_==========+_==========+_==========+_==========+ 127 13 --+========+_===========+_===========+_===========+_===========+ 122 122 13 +--+_=========+_===========+_===========+_===========+ 122 14 ------+_============+_============+_============+_============++++++ 106 106 14 -----------+=======+_============+_============+_============+ 111 15 ------+_=============+_=============+_=============+_=============++ 106 106 15 -------+====+_=============+_=============+_=============+ 107 16 ---+===========+_==============+_==============+_==============+ 103 103 16 ---+=+_==============+_==============+_==============+ 103 17 -------+_===============+_===============+_===============++++++++++ 87 87 17 ----------------+==============+_===============+_===============+ 96 18 -------+_================+_================+_================+++++++ 87 87 18 -------------+_============+_================+_================+ 93 19 -------+_=================+_=================+_=================++++ 87 87 19 ----------+==========+_=================+_=================+ 90 20 -------+_==================+_==================+_==================+ 87 87 20 -------+_========+_==================+_==================+ 87 21 ----+================+_===================+_===================+ 84 84 21 ----+======+_===================+_===================+ 84 22 -+_==============+_====================+_====================+ 81 81 22 -+_====+_====================+_====================+ 81 23 --------+_=====================+_=====================++++++++++++++ 68 68 23 ------------------+_=====================+_=====================++++ 78 24 --------+_======================+_======================++++++++++++ 68 68 24 ------------------+_======================+_======================++ 78 25 --------+_=======================+_=======================++++++++++ 68 68 25 -----------------+======================+_=======================+ 77 26 --------+_========================+_========================++++++++ 68 68 26 ---------------+=====================+_========================+ 75 27 --------+_=========================+_=========================++++++ 68 68 27 -------------+====================+_=========================+ 73 28 --------+_==========================+_==========================++++ 68 68 28 -----------+===================+_==========================+ 71 29 --------+_===========================+_===========================++ 68 68 29 ---------+==================+_===========================+ 69 30 -------+===========================+_============================+ 67 67 30 -------+=================+_============================+ 67 31 -----+==========================+_=============================+ 65 65 31 -----+================+_=============================+ 65 32 ---+=========================+_==============================+ 63 63 32 ---+===============+_==============================+ 63 33 -+========================+_===============================+ 61 61 33 -+==============+_===============================+ 61 34 ---------+_================================+++++++++++++++++++++++++ 49 49 34 -------------------+_================================+++++++++++++++ 59 35 ---------+_=================================++++++++++++++++++++++++ 49 49 35 -------------------+_=================================++++++++++++++ 59 36 ---------+_==================================+++++++++++++++++++++++ 49 49 36 -------------------+_==================================+++++++++++++ 59 37 ---------+_===================================++++++++++++++++++++++ 49 49 37 -------------------+_===================================++++++++++++ 59 38 ---------+_====================================+++++++++++++++++++++ 49 49 38 -------------------+_====================================+++++++++++ 59 39 ---------+_=====================================++++++++++++++++++++ 49 49 39 -------------------+_=====================================++++++++++ 59 40 ---------+_======================================+++++++++++++++++++ 49 49 40 -------------------+_======================================+++++++++ 59 41 ---------+_=======================================++++++++++++++++++ 49 49 41 -------------------+_=======================================++++++++ 59 42 ---------+_========================================+++++++++++++++++ 49 49 42 -------------------+_========================================+++++++ 59 43 ---------+_=========================================++++++++++++++++ 49 49 43 -------------------+_=========================================++++++ 59 44 ---------+_==========================================+++++++++++++++ 49 49 44 -------------------+_==========================================+++++ 59 45 ---------+_===========================================++++++++++++++ 49 49 45 -------------------+_===========================================++++ 59 46 ---------+_============================================+++++++++++++ 49 49 46 -------------------+_============================================+++ 59 47 ---------+_=============================================++++++++++++ 49 49 47 -------------------+_=============================================++ 59 48 ---------+_==============================================+++++++++++ 49 49 48 -------------------+_==============================================+ 59 49 ---------+_===============================================++++++++++ 49 49 49 ------------------+==============================================+ 58 50 ---------+_================================================+++++++++ 49 49 50 -----------------+_==============================================+ 57 51 ---------+_=================================================++++++++ 49 49 51 ----------------+==============================================+ 56 52 ---------+_==================================================+++++++ 49 49 52 ---------------+_==============================================+ 55 53 ---------+_===================================================++++++ 49 49 53 --------------+==============================================+ 54 54 ---------+_====================================================+++++ 49 49 54 -------------+_==============================================+ 53 55 ---------+_=====================================================++++ 49 49 55 ------------+==============================================+ 52 56 ---------+_======================================================+++ 49 49 56 -----------+_==============================================+ 51 57 ---------+_=======================================================++ 49 49 57 ----------+==============================================+ 50 58 ---------+_========================================================+ 49 49 58 ---------+_==============================================+ 49 59 --------+========================================================+ 48 48 59 --------+==============================================+ 48 60 -------+_========================================================+ 47 47 60 -------+_==============================================+ 47 61 ------+========================================================+ 46 46 61 ------+==============================================+ 46 62 -----+_========================================================+ 45 45 62 -----+_==============================================+ 45 63 ----+========================================================+ 44 44 63 ----+==============================================+ 44 64 ---+_========================================================+ 43 43 64 ---+_==============================================+ 43 65 --+========================================================+ 42 42 65 --+==============================================+ 42 66 -+_========================================================+ 41 41 66 -+_==============================================+ 41 67 +========================================================+ 40 40 67 --------------------++++++++++++++++++++++++++++++++++++++++++++++++ 40 68 ----------++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 30 30 68 --------------------++++++++++++++++++++++++++++++++++++++++++++++++ 40 2.5.2. Экспериментальная база RandomStrings Для некоторого набора значений длин n некоторая (случайная) строка «центр» q случайно редактировалась с использованием операций вставки, удаления и замены. Полученные при таком редактировании строки составляли коллекцию строк P. Поскольку общее число операций принято намного меньшим длины строки, а посчитать точно расстояние редактирование не представляется возможным из-за вычислительной сложности, положим, что расстояние редактирования от центра q до y P примерно равно сумме количеств исРис. 2.13. Результат решения (max, +) задачи с учетом группировки плохих интервалов кажений, проведенных над q для получения y. Аналогичное допущение было принято в [7]. В дальнейшем мы будет ссылаться на этот набор строк как на RandomStrings.

2.5.3. Проверка теоретических ограничений детерминированного Экспериментальное исследование того, попадает ли величина расстояния D(x, y) (2.9) в ограничения (2.12) и (2.13), выполнялось для строк из базы RanD(x,y) D(x,y) Рис. 2.14. Типичная зависимость расстояния D(x, y) (2.9) от ed(x, y) domStrings. Переписка с авторами работ [10, 11] говорит, что они не проводили подобную экспериментальную проверку своих алгоритмов. Единственной нам известной проверкой на практике алгоритма вложения (блочного) расстояния редактирования ([31, 30, 27], п. 1.3.3) в векторное пространство является [7].

На рис. 2.5.2 приведены минимальные (крестики) и максимальные (нолики) экспериментальные значения D(x, y) для каждого из значений расстояния редактирования ed(x, y) для двух значений n = 5000 и n = 10000. Теоретические значения верхней (2.13) и нижней границ (2.12) на значения расстояния изображены, соответственно, сплошной и пунктирной тонкими линиями. Из рис. 2.5.2 видно, что экспериментальные данные с большим запасом соответствуют теоретическим оценкам (2.12) и (2.13).

Выполаживание графика происходит вблизи максимально возможного значения расстояния D(x, y) = 2(w + 1) q2 q1 (что равно 19, 42, 60, для соответственно n = 1000, 5000, 10000, 50000), когда в каждом окне имеется 2(w q + 1) различных q-грамм для q = q1,..., q2.

2.6. Выводы по разделу 1. Разработанный q-граммный детерминированный метод аппроксимации расстояния редактирования путем вложения пространства строк длины n с метрикой редактирования в пространство 1, за счет использования q-грамм переменной длины и восстановления в смежных интервалах улучшает качество аппроксимации по сравнению с известными методам вложения расстояния редактирования в пространство 1.

2. Разработанный метод анализа разработанного вложения на основе математического аппарата графов де Брейна позволил оценить точность аппроксимации расстояния редактирования, вычислительную сложность и затраты памяти. Показано, что разработанный метод вложения дает верхнюю границу интервала k2 аппроксимации k2 = O(k1 n), размер используемой памяти O(n5/4 ) и время построения векторов O(n3/2 ) по сравнению с известными методам вложения расстояния редактирования 3. Численные экспериментов показали соответствие диапазона значений манхетеннова расстояния между векторными представлениями итогового пространства D(x, y) теоретически полученным ограничениям на этот

РАЗРАБОТКА РАСПРЕДЕЛЕННЫХ МЕТОДОВ ВЛОЖЕНИЯ

РАССТОЯНИЯ РЕДАКТИРОВАНИЯ И ЭФФЕКТИВНОГО ПОИСКА

ПРИБЛИЖЕННЫХ БЛИЖАЙШИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

На основе разработанного в разделе 2 метода детерминированного вложения пространства последовательностей с классической метрикой редактирования в пространство 1 в данном разделе разработана локально-чувствительная функция для расстояния редактирования (п. 3.1.2), а также разработаны два рандомизированных варианта вложения (п. 3.3 и п. 3.2). Они продуцируют распределенные представления, которые позволяют сократить время поиска близких последовательностей и требуемую память. На основе полученных распределенных представлений разработаны методы поиска приближенных ближайших последовательностей. Получены аналитические оценки эффективности предложенных методов представления (п. 3.1.2) и поиска (п. 3.3.1). Показана связь полученного в пункте 3.3 распределенного представления с предложенным распределенным прореживающим представлением последовательностей (п. 3.4.3).

3.1. Рандомизированные методы формирования векторных представлений для поиска ближайших строк Применение детерминированной версии (раздел 2) вложения пространства (n, ed) в 1 затруднено по причине больших размерностей получаемых векторов. Кроме того, потенциально большие размеры баз последовательностей затрудняют поиск в них ближайших соседей. Разработаем рандомизированные версии детерминированного метода, которые могут использоваться для практических приложений в задаче поиска ближайшего соседа.

3.1.1. Вероятностные варианты лемм раздела Доказательство следующих следствий – вероятностных вариантов леммы 2.9 и следствия 2.3 – тривиально, и получается при случайном выборе значения i из диапазона 1,..., n w + 1.

Доказательство. Общее число интервалов в последовательности n w + 1. Утверждение следствия получается, поделив правую часть выражения из леммы 2.9 на общее число интервалов.

Следствие 3.2. Если ed(x, y) > k2, то Доказательство. Утверждение следствия также получается, поделив правую часть выражения из следствия 2.3 на общее число интервалов.

3.1.2. Локально-чувствительная функция для расстояния Предложим новую локально-чувствительную хеш-функцию для расстояния редактирования на основе разработанного метода детерминированного вложения из раздела 2 и схемы хеширования для 1 на основе 1-стабильного распределения (п. 1.5.2, стр. 36 ) и определения (1.18).

Возьмем случайный вектор vw,q1,q2 (x), получаемый случайным и независимым выбором окна шириной w в строке x (см. следствия 3.2 и 3.1). Сгенерируем свой вектор i, элементы которого взяты из распределения Коши.

Хеш-функции hi (x), – элементы вектора h (x) = (h1 (x), h2 (x),..., h1 (x)), – определим как где bi, r – параметры из определения (1.18).

Получается трехступенчатая процедура хеширования последовательностей: получаем прореженный q-граммный вектор путем семплирования случайным окном шириной w, умножаем скалярно на случайный вектор, распределенный по Коши, и наконец применяем к полученому произведению отображение (1.18).

Докажем, что данная функция является локально-чувствительной и может использоваться в схеме LSH (п. 1.5.1 и 3.3.1).

Для определения значений pI, pII (см. (1.13)) необходимо выяснить распределение величин hi (x) и hi (y). Пусть p(d|k) – вероятность того, что расстояние d 1,q2 (x, y) = d при условии ed(x, y) = k, а P rob[h (x) = h (y)|c] = p(c), где c – целочисленное значение d 1,q2 (x, y).

Обозначим Тогда для семейства новых хеш-функций (3.1) получаем Для доказательства используем идею леммы 2 из [71]. Пусть матожидание как сумму независимых и равновероятно распределенных величин Для любых строк p, p n значения нормы разницы векторов viu (p) и viu (p ) ограничены:

Применяя неравенство Хеффдинга [55] для ограниченных случайных величин, получаем:

Аналогично доказывается, что P [DU (p0, pa ) < d2 ] < e w.

Создадим структуру S, состоящую из n структур Sk, k = 1,..., n, по одной на каждое из возможных значений расстояний редактирования между строками длины n. Каждая из Sk состоит из M структур F1,..., FM. Каждая структура Fm, m = 1,..., M содержит U значений позиций im1,..., imU (указывающих на начало соответствующих интервалов Iimu = [imu, imu + w 1]), выбранных случайно и равновероятно, с возвращением, из диапазона [1,..., n w + 1], и таблицу m, содержащую ||n ячеек (по числу возможных строк длиной n). Содержимое интервала Iimu в структуре Fm для строки x обозначим как x[Iimu ]. Конкатенацию всех vw,q1,q2 (x[Iimu ]), u = 1,..., U обозначим vm (x). Ячейка таблицы m, соответствующая z ||wU, содержит строку p P, если D(p, z) d1, если такая p существует, иначе ячейка пуста. Структура S при простейшей реализации будет занимать объем памяти порядка O(nM (U + log P ||wU ) + nP ) и может быть построена за время O(nM P (wU + ||wU )).

Объем таблиц m можно уменьшить до ||wU, индексируя ее строками, получающимися конкатенацией U интервалов. Далее, для принятия решения о внесении строки в ячейку нам необходимы q-спектры подстрок z[1 + (u 1)w, uw] при q = q1,..., q2. Поэтому можно сэкономить место под хранение таблиц m, объединив ячейки с совпадающими q-спектрами интервалов z[1 + (u 1)w, uw] для всех q = q1,..., q2. В этом случае можно обозначить И ячейка таблицы m, соответствующая z ||wU, будет содержать строку p P, если Dm (p; z) d1.

Для строки-запроса p0 n будем говорить, что структура Fm ошибается на P, если существует p1 P, такая, что ed(p0, p1 ) k1 (или строка p2 с ed(p0, p2 ) k2 ) и Dm (p0, p1 ) > d1 (Dm (p0, p2 ) < d2 ). Если существует k такое, что более, чем µM/ log n структур Fm в Sk ошибаются на P, то будем говорить, что структура S ошибается на p0. Будем говорить, что структура S ошибается, если существует p0 n, такое, что S ошибается на p0.

Для любого > 0, если положить M = (n log2 () + log n log ) ln n/µ и F = 0.52 ln(2eP ln n/µ), то для любого запроса p0 вероятность, что структура S ошибается на p0, есть максимум 2n. Для доказательства воспользуемся схемой доказательства из [71] (теорема 4). Для любого i, Fj Sk и pa P вероятность, что D(p0, pa ) будет вне нужного интервала, есть максиT 2 µ Суммируя по P строкам в базе, получаем, что вероятность, что Fj не работает, есть максимум 2e ln n. Тогда среднее число структур Fj, которые не работают, есть 2e ln n. Пусть j = 1, если Fj не работает, и j = 0 иначе.

работает более чем структур. По одной из форм неравенства Чернова Просуммировав по всем структурам 1,..., n, завершаем доказательство. Таким образом, S на всей P ошибается с вероятностью.

Процедура поиска. Допустим, S не ошибается (это происходит с вероятностью 1 ). Используем бинарный поиск для нахождения ближайшего соседа. Выберем произвольно начальное k и выберем случайно и равновероятно одну из Fm в Sk. Подсчитаем значение p0 (IFm ) и проверим соответствующую ячейку. Если ячейка не пуста, переходим и проверяем аналогично Sk1, иначе переходим к Sk+1. По лемме 6 из [71] вероятность, что выбранное Fi ошибается на p0, меньше или равна µ.

Если все Sk не ошибаются на p0, тогда расстояние от p, возвращенной алгоритмом поиска, отличается не более, чем в 1 + раз от расстояния от p0 до настоящего ближашего соседа. Для доказательства воспользуемся идеей доказательства леммы 7 из [71]. Пусть kmin = minpP ed(p, p0 ). Если k < kmin /(1 + ), то все Sk не сработают на p0. С другой стороны, все Sk, k kmin работают на p0. Следовательно, процедура бинарного поиска завершится на таком k, что kmin /(1 + ) k kmin. При этом возвращенная строка p такая, что D(p0, p ) d1. Так как для любой p P, ed(p, p0 ) > k(1 + ), D(p0, p) d2 (k). Поскольку d2 > d1, то D(p0, p) > d1, и ed(p, p0 ) (1 + )k < (1 + )kmin.

Согласно теореме 8 [71], получаем, что приведенная процедура поиска находит с высокой вероятностью (1 + )-ближайшего соседа, для любого > 0: если S не ошибается, то для любого запроса p0 алгоритм бинарного поиска находит (1 + )-приближенного соседа с вероятностью 1 µ за время O(2 n(log |P | + log log n log µ) log n).

3.3. Решение задачи поиска приближенных ближайших последовательностей с помощью разработанной локально-чувствительной функции Для решения задачи -БС была применена общая схема решения задачи (, k)-PLEB (п. 1.5.1) и разработанная локально-чувствительная функция (п. 3.1.2) для расстояния редактирования.

Предварительно найдем асимптотические значения (1.19) при r c и при r c:

Для семейства новых хеш-функций (3.1) получено в (3.3) и (3.2), что Чтобы такое семейство было локально-чувствительным (см. (1.14)), должно выполняться В свою очередь, для его выполнения необходимо, чтобы Из этого выражения найдем асимптотическое поведение k2 и, следовательно, точность аппроксимации расстояния редактирования в зависимости от n. Для этого положим w = n, 0 < < 1, и r = nµ, µ > 0. Из условия 2.3 леммы 2. q = ( w) поэтому При n, используя (1.19), (3.7), (3.8), найдем оценки 1 p(d1 ) и 1 p(d2 ) в зависимости от соотношения параметров µ, :

4. Если µ = /2, то r = (d1 ) и r = o(d2 ), то Для удовлетворения (3.11), подставим полученные выражения в (3.12) и найдем выражение для k2 для каждого случая 1. Если = µ, то k2 = (k1 (n1 ln n + n/2 ). При > 2/3, n/2 доминирует Отсюда, оптимальным значением будет = 2/3, и k2 = (k1 n1/3 ln n).

2. Если µ >, то k2 = (n/2 + k1 [n1 + nµ / ln n])). Поскольку µ >, то 3. Если /2 < µ <, то k2 = (k1 (n1µ (µ /2) ln n + n/2 ). Поскольку µ <, то n1µ ln n = (n1 ln n), что является более плохой оценкой, чем оценка в варианте с µ =.

4. Если µ = /2, то k2 = (n), что также хуже, чем вариант µ =.

Итак, оптимальным значением будет = 2/3, при котором 3.3.1. Анализ поиска приближенных ближайших последовательностей на основе предложенной локально-чувствительной функции Положим k2 из (3.12) равным для R z > 1. Это повлияет на значение и асимптотику p2, поскольку его знаln(p1 p(d1 )) ln(1A) ln(1zA), где A = 1 p1 p(d1 ), аналогично оценке для случая хэммингова расстояния [60, 46] получаем = O( 1+z ) при условии ln |P | > p1 p(d1 ).

Таким образом, согласно теореме Индыка-Мотвани (п. 1.5.2, стр. 36), метод приближенного поиска ближайшей строки, построенный на предложенном в подразделе 3.1 варианте LSH на 1-стабильном распределении, возвратит с вероятностью, большей 1/2, строку из P, которая принадлежит шару S(q, O(zk1 n1/3 ln n)), затратив на это порядка O(|P |1/(1+z) ) операций.

Поскольку схема имеет константную вероятность ошибки, повторив описанную процедуру LSH паралельно и независимо порядка O(ln ) раз, мы можем добиться вероятности успеха хотя бы в одном запуске процедуры не менее 1 для любого заданого уровня ошибки < 1.

3.4. Распределенные представления последовательностей Покажем связь методов распределенного представления символьных последовательностей на основе рандомизированных вложений, разработанных в п. 3.1 и п. 3.3, и разработанных на основе нейросетевых подходов (п. 1.2 и п. 3.4.1-3.4.3).

3.4.1. Метод распределенного представления последовательностей без Поскольку символы алфавита различны, будет представлять их (и/или q-граммы) случайно и независимо сгенерированными и затем фиксированными векторами (п. 1.2). Каждой q-грамме t (q 1) поставим в соответствие случайный независимый вектор v(t). Вектор всей последовательности создается путем суммирования или дизъюнкции векторов q-грамм. Таким образом, векторы последовательностей, состоящих из большого количества одинаковых элементов, получат близкие представления.

То есть, вектор v(x) для строки x = x1,..., xn определяется как v(x) = где r(x) есть случайный вектор, соответствующий элементу x.

i=1,...,n r(xi ), Выражение для v(x) можно переписать как где nx () – количество вхождений символа в s.

Выражение (3.13) эквивалетно проекции вектора-представления типа «bagof-items» (п. 1.3.2), с элементами векторов – q-граммами или символами, – nT () = (n1 (),..., n|| ()) путем умножения его на случайную матрицу (d ||) со столбцами r(). Таким образом, данное представление может рассматриваться как отображение из (например, VSM, п. 1.3.2) пространства размерности || в Rd, где d может быть сделано существенно меньше, чем число всех возможных элементов ||.

Если оба пространства евклидовы, то, применяя лемму Джонсона-Линденштрауса (п. 1.4.1, стр. 27) и выбирая r(x) из нормального распределения (или из определенного бинарного или тернарного распределения [1]), Таким образом, используя лемму Укконена (п. 1.3.3, стр. 29), для двух строк с расстоянием редактирования меньше k эвклидово расстояния между соответствующими векторами не превышает (1 + )qk. Это дает верхнюю границу на расстояние между векторами и может использоваться с целью фильтрации строк или документов по расстоянию редактирования. При этом распределенные представления в виде векторов малой размерности используются вместо разреженных q-граммных векторов большой размерности.

3.4.2. Методы распределенного представления последовательностей с В следующих двух предложенных методах информация о позиции элемента в последовательности объединяется с представлением самого элемента путем модификации представления элемента позиционно-зависимым способом. Векторы могут быть бинарными, при этом суммирование заменяется на дизъюнкцию.

3.4.2.1. Позиционное связывание с помощью перестановок Для сдвигового представления [109] распределенные представления элементов последовательности модифицируются путем циклического сдвига (или, в общем случае, путем случайной перестановки) на число элементов вектора, зависящее от позиции элемента последовательности, а представление всей последовательности x формируется дизъюнкцией распределенных представлений ее элементов – q-грамм:

где – побитовая дизъюнкция, а X >> y обозначает вектор X, сдвинутый циклически на y элементов. В общем случае перестановок где i – случайные и независимо выбранные перестановки.

Рассмотрим, например, строки ’abc’, ’abd’, ’cba’. Каждый символ представим случайным вектором: v(a), v(b), v(c) и т.д. Тогда вектор последовательностей формируются следующим образом:

Пересечение полученных векторов для строк, не содержащих одинаковых элементов в одинаковых позициях, будет в среднем пренебрежимо мало, при условии, что случайные векторы достаточно разрежены, а строки не слишком длинные. Недостатком приведенной процедуры является то, что она не учитывает информацию об идентичных символах в различным позициях.

3.4.2.2. Позиционное связывание с помощью представлений позиций В данном методе дополнительно к векторам подстрок генерируются векторы для позиций. Для того, чтобы представить подстроку в конкретной позиции, вектор подстроки и вектор позиции связываются:

где Z – некоторый оператор связывания.

В бинарном случае связывание осуществляется с помощью побитовой поэлементной конъюнкцией (п. 1.2).

Таким образом, в вектор символа – элемента последовательности (например, символа или q-граммы) привносится («впечатывается») информация о его позиции в последовательности. То есть в распределенном представлении теперь есть информация и о символе, и о его позиции и оно имеет значительное перекрытие с вектором и символа, и позиции.

В отличии от сдвигового метода (п. 3.4.2.1), данный вид связывания учитывает сходство идентичных элементов в разных позициях. Распределенное представление позиций может быть коррелированным для близких порядковых номеров. Чтобы сформировать распределенное представление всей последовательности, векторы связывания v(x) символ-позиция объединяются побитовой дизъюнкцией или суммированием.

3.4.3. Прореживающее связывание и его связь с разработанной локально-чувствительной функцией Установим аналогию между прореживающим распределенным представлением и подходами к аппроксимации расстояния редактирования.

Формирование i-го элемента выходного вектора v(x) размерности d при прореживающем представлении (п. 3.4.2.2) можно записать таким образом:

Рассмотрим часть произведения X = L(x) · C (рис. 3.1). Если бы матрица C содержала в своих элементах только единицы, то это произведение давало бы столбцы векторных представлений строки x (таких, как, например, q-граммные). Но, поскольку C содержит и нули, в X учитываются подстроки не во всех позициях. Таким образом, столбцы результирующей матрицы X можно считать «неполными» векторными представлениями (q-граммными представлениями, если есть множество всех q-грамм) входной строки x.

Столбцы матрицы C играют роль бинарных масок, отмечающих позиции в s, откуда символы суммируются для формирования конкретного q-граммного вектора. Например, j-ый столбец C маскирует s для получения вектора с i-м элементом, равным k=1,...,n lk cki.

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

Выше было отмечено, что векторы позиций (строки матрицы C) могут формироваться так, чтобы векторы соседних позиций отличались на малое расстояние Хэмминга и чтобы это расстояние увеличивалось с увеличением расстояния между позициями. Некоторые методы построения таких векторов для порядковых чисел предложены в [139].

Разные столбцы играют роль независимых сэмплеров, как и в методе сублинейной аппроксимации расстояния редактирования в работе [11] (п. 1.4.2, стр. 30).

Рассмотрим умножение X на матрицу R. Каждый i-й элемент выходного вектора v(x) является скалярным поризведением вектора ri на соответствующий «прореженный» q-граммный вектор. Такая операция (проекция на случайное направление) уже присутствовала в описании аналогии между неупорядоченным распределенным представлением строк с помощью присваивания случайных векторов их подстрокам (q-граммам) (п. 3.4.1). Разница в том, что там каждый из q-граммных векторов проецировался на все случайные направления, тогда как тут различные q-граммные векторы проецируются на собK K = Рис. 3.1. Пример произведения матриц (3.14) с указанием размерностей и способов получения матриц ственные случайные направления. Однако, заметим, что из-за наличия общих единиц между столбцами матрицы C части маскированного (прореженного) q-граммного вектора будут проецироваться на различные направления.

Из выражения (3.14) следует:

где R(C(k)) – матрица R с только теми строками, которые соответствуют тем векторам позиций, которые имеют единицы в позициии k. Таким образом, каждый вектор lk проецируется на соответствующее случайное подпространство, определяемое теми Cj, которые накрывают позицию k. Чем дальше находятся идентичные символы (или q-граммы) друг от друга, тем меньше общих случайных направлений они имеют, и, таким образом, тем дальше друг от друга будут находиться их проекции.

Исходя из анализа в п. 3.1, векторы ri должны выбираться градуальными и распределенными по Коши, векторы позиций – бинарными (строки матрицы, составленной из столбцов, где единицы указывают положения, накрытые случайно выбранными окнами ширины w).

Таким образом, мы получили согласующуюся с нейросетевыми концепциями (п. 3.4.2.2) схему формирования распределенных представлений последовательностей, а также возможность сублинейного поиска приближенно ближайших последовательнотсей путем применения схемы локально-чувствительного хеширования (п. 1.5.1) за счет использования в ней разработанной функции (1.18).

3.4.4. Тернаризация и бинаризация рандомизированных представлений на основе локально-чувствительной функции Помимо выбора параметра r (3.1), исходя из минимизации отношения pI /pII (cf. [35]) и значения = ln(pI /pII ), и следовательно, ускорения приближенного поиска ближайшей строки (см. выражение для L (1.16)), можно выбирать его, исходя из удобства представления и работы с получаемыми векторами. Так, работать с тернарными (или даже бинарными) векторами предпочтительнее, чем с целочисленными, из-за меньших требований к памяти и более быстрых реализаций алгоритмов. Также (разреженные) бинарные и тернарные вектора используются в моделях распределенной обработки информации, таких как АПНС [91], или для поиска текстов [132, 131]. Поэтому представляет интерес получение на выходе тернарных или бинарных векторов.

Рассмотрим, как выбор значений параметров влияет на множество значений, принимаемых хеш-функцией (1.18). Хеш-функция (1.18) будет приv,)+b r < (v, ) < r. Интегрируя выражение ((1 + x2 ))1 в пределах от r/ v l до r/ v l1, получаем, что вероятность получения тернарных значений в (1.18) Плотность нулевых элементов в векторах определяется величиной и увеличивается с увеличением параметра r.

Полученные тернарные векторы могут быть бинаризованы пороговой операцией [132]. Также, для бинаризации значений векторов разработанной локально-чувствительной функции может использоваться метод бинаризации из [23]. Эффективность отражения сходства строк с помощью таких тернарных или бинарных распределенных представлений следует исследовать на практике.

Материалы данного раздела изложены в следующих публикациях: [107, 109, 105, 106, 145, 146].

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

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

3. На основе нейросетевого распределенного представления информации предложены два метода (сдвиговый и прореживающий) распределенного представления последовательностей, учитывающие порядок компонентов последовательностей за счет связывания векторов позиций и элементов. Показано, что прореживающее распределенное представление может рассматриваться как рандомизированное вложение расстояния редактирования на основе локально-чувствительных функций.

4. Показана возможность получения тернарных и бинарных векторов путем выбора параметров локально-чувствительного хеширования, что может быть полезно для систем, использующих распределенное представление информации.

АЛГОРИТМИЧЕСКАЯ РЕАЛИЗАЦИЯ И ЧИСЛЕННОЕ

ИССЛЕДОВАНИЕ РАСПРЕДЕЛЕННОГО ПРЕДСТАВЛЕНИЯ И

ПОИСКА ПРИБЛИЖЕННЫХ БЛИЖАЙШИХ СИМВОЛЬНЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Раздел посвящен экспериментальному численному исследованию метода распределенного представления символьных последовательностей на основе рандомизированного вложения классического расстояния редактирования, разработанного в разделе 3. Приведена алгоритмическая реализация (п. 4.2) метода поиска приближенных ближайших последовательностей с помощью локально-чувствительного хеширования LSH. Предложены методы работы с базами последовательностей разной длины (п. 4.3). Проведены эксперименты со схемой на основе 1-стабильного распределения на искусственно сгенерированных данных для проверки соответствия эмпирической вероятности совпадения значений хеш-функции теоретически полученным ограничениям (п. 4.1). Проведены экспериментальные исследования влияния выбора параметров поиска приближенных ближайших последовательностей на эффективность и точность поиска, а также упорядоченность получаемых кандидатов на приближенных соседей (п. 4.4).

4.1. Экспериментальное исследование вероятности коллизии разработанной локально-чувствительной функции Экспериментальное исследование соответствия вероятности совпадения (коллизии) pcol = P rob[h(x) = h(y) | ed(x, y)] значений хеш-функции (3.1)и теоретических оценок (3.3) и (3.2) проводились на базе RandomStrings (п. 2.5.2).

На рис. 4.1 приведены экспериментально полученные вероятности совпадения (коллизии) для строк длиной n = 1000 и n = 3000 вместе с теоретическими точками верхней (нолики) и нижней (крестики) границ. Результаты показывают, что экспериментальные данные соответствуют полученным теоретически ограничениям (3.3) и (3.2).

Рис. 4.1. Экспериментальные значения вероятностей коллизии хеш-функций hi (x) (3.1) 4.2. Поиск приближенных ближайших последовательностей с Для реализации разработанной процедуры LSH (п. 3.3) при поиске приближенных ближайших соседей использована ее модификация, называемая LSH-лес (п. 1.5.1) и позволяющая пополнять базу примеров последовательностей P и изменять параметры k1, k2 без обновления хеш-векторов [13].

Для каждого j = 1,..., L все -мерные хеш-векторы hj (x) всех строк x P хранятся в виде отдельного префиксного дерева Tj (рис. 4.2) глубиной до K уровней (корень имеет глубину 0, листья – K). Узлы дерева соответствуют значениям элементов хеш-вектора и содержат ссылки на строки, хеш-векторы которых соответствуют пути от корня дерева к данному узлу. Листья деревьев соответствуют ячейкам в схеме LSH (п. 1.5.2).

Если в хеш-векторах двух строк совпадают первые k элементов хешвекторов, то и первые k узлов на пути от корня дерева Tj до листьев, соответствующих этим строкам, также совпадают.

При поступлении запроса y:

1. формируются L его K-мерных хеш-векторов hj (y);

2. для каждого хеш-вектора hj (y) в Tj находится узел, соответствующий hj (x) с наибольшим числом совпадающих первых элементов этих векторов;

3. для найденных на шаге 2 узлов самого глубокого уровня, для всех L деревьев соответствующие узлам этого уровня строки x добавляются в результирующее мультимножество S;

4. после того, как все строки, хеш-векторы которых совпадают на данном уровне, добавлены в S, все L деревьев синхронно просматриваются на следующем (более «высоком») уровне. Процедура повторяется, пока не достигнем корня или |S| не превысит 2L.

В результате получаем мультимножество S строк (кандидатов на приближенного ближайшего соседа к y), упорядоченное в порядке убывания глубины узлов дерева, до которых совпадали первые элементы хеш-векторов соответствующей строки и запроса. Будем далее под уровнем строки из S понимать глубину последнего узла дерева, на котором еще совпадали первые элементы хеш-векторов запроса и этой строки.

Исследование влияния размера мультимножества S на результаты поиска рассмотрено в п. 4.4.

Согласно результатам [13], мультимножество S будет содержать с ненулевой константной вероятностью приближенных ближайших соседей к запросу.

Параметры леса при этом выбираются, исходя из теоремы Индыка-Мотвани (п. 1.5.2, стр. 36). Выбор параметров на практике исследован в п. 4.4.

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

4.3.1. Дополнение последовательностей спецсимволами Для приложений, где отличие длин строк в P не слишком большое, простейшим способом сведения к одинаковой длины является дополнение строк одинаковым специальным символом $ до максимальной длины n, представленной в P : n = maxpP |p|. Каждая строка p P преобразуется в p = p$n|p|. Поскольку для любой пары строк p1, p2 P выполняется ed(p1, p2 ) = ed(p1, p2 ), то поиск приближенно ближайших соседей выполняется в базе дополненных строк P = p = p$n|p| |p P и, если p является приближенным соседом к q, то соответствующая строка p является приближенным соседом к q.

4.3.2. Разбиение последовательностей окнами Для приложений с длинными последовательностями предлагается применить разбиение строк из P, а также запроса q, скользящим окном фиксированной ширины n. После этого поиск выполняется для каждого окна запроса 4.3.3. Кластеризация последовательностей по длине Поскольку минимальное значение расстояния редактирования между строками длины n и m составляет |m n|, а похожие строки, как правило, мало отличаются по длине, то поиск соседей имеет смысл выполнять только для ближайшей окрестности (кластера). Поэтому для поиска приближенно ближайших соседей в базах строк с большим разнообразием значений длин предлагается использовать следующую схему кластеризации базы по длине.

Зададимся параметром, определяющим ширину кластеров следующим образом: для фиксированной длины n (центр кластера) окружающим кластером считаются все строки, длины которых содержатся в интервале In = [(1 )n, (1 + )n].

Значения центров n можно выбирать по следующему алгоритму:

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

Запрос p, |p| = n выполнялся для двух LSH-лесов, базы P1 и P2 которых состоят из строк, длины которых попадали в оба интервала, которые «накрывают» значение длины запроса. Длины строк и запроса в каждом интервале выравнивались добавлением специальных символов в конце строки до значения максимальной длины в каждом интервале, как в методе п. 4.3.1.

Разработанные методы и процедуры использованы в приложениях раздела 5.

4.4. Выбор параметров для обеспечения вычислительной эффективности и точности поиска На практике, так как необходимые для поиска ресурсы растут линейно от L (1.16), рекомендуемые теорией значения L часто оказываются слишком велики. Однако, при использовании меньших значений L теория (п. 1.5.1) не гарантирует, что в возвращенное мультимножество строк S попадет как минимум одна строка y из S(q, k2 ). Следующие эксперименты выполнялись для проверки того, как на «качество» мультимножества S влияет 1. выбор меньших, чем теоретические, значений L и 2. дополнительная фильтрация S, которой предположительно можно отсечь строки y S(q, k2 ) (false positives).

Качество S оценивалось 1. по значению точности (п. 4.4.1);

2. по упорядоченности S относительно известного эталона (п. 4.4.2).

4.4.1. Экспериментальное исследование качества кандидатов на Традиционно в системах поиска текстовой информации для оценки качества множества документов, возвращаемого в ответ на запрос, анализируется компромисс зависимости между количеством найденных релевантных текстов (true positives) и количеством найденных нерелевантных текстов (false positives). Для этого определяются величины точности (отношение количества релевантных запросу возвращенных документов к общему числу возвращенных документов) и полноты (отношение количества релевантных запросу возвращенных документов к общему числу релевантных документов) и изображают их на графиках зависимости точности от полноты [9].

При решении задачи поиска приближенного ближайшего соседа подразумевается нахождение одного соседа, а не множества соседей. Поэтому отношение |S(q, k2 ) P S|/|S(q, k2 ) P | (полнота) не информативно. Зачастую полнота не информативна и при оценке качества поисковых систем. Для пользователя все множество возвращенных результатов не интересно, он обычно ограничивается просмотром только первых страниц результатов [110]. В таких случаях вместо точности и полноты обычно используют характеристику «точность на уровне n» («precision at n /P@n») [53], вычисляемую как точность на ограниченном первыми n результатами множестве. В нашем случае этот уровень естественно ограничен размером множества S и точность на уровне |S| определяется как |S(q, k2 ) P S|/|S|.

Чтобы не вносить смещение в оценку точности на уровне |S| из-за неодинакового количества строк внутри и вне шара S(q, k2 ) и разного количества строк на определенном расстоянии от q, было сделано следующее. Мы отобрали из набора RandomStrings (п. 2.5.2) 2200 строк длиной 1000 символов (при этом k2 = 126) таким образом, что число строк, принадлежащих S(q, k2 ), составляло половину от общего числа строк, и количество строк на каждом расстоянии от центра q не превышало 10. Полученное множество P содержало строки, находящиеся от q на расстоянии редактирования от 10 до 248.

Множество P было запомнено в LSH-лесе с помощью процедуры из п. 4.2.

На вход процедуры поиска приближенно ближайшего соседа подавался запрос q. По полученному на выходе при каждом запросе множеству S (|S| > 4L) вычислялась точность на уровнях 0.5L, L, 2L, 3L, 4L. Значения точностей усреднялись по 100 случайным независимым реализациям LSH-леса. Их значения и дисперсия приведены в таблице 4.4.1.

При малых значениях L наблюдается максимальная точность, что является особенностью процедуры LSH-лес, возвращающей множество строк S, упорядоченное по глубине уровня. При увеличении значения L вначале точность падает, что объясняется б льшими шансами у строк из P S(q, k2 ) попасть в S, но в дальнейшем точность перестает существенно изменятся, и Точность на уровне |S| в зависимости от значения L и |S| одновременно уменьшается дисперсия ее значений, что позволяет говорить о стабилизации значений точности. Аналогичный эффект наблюдается при увеличении |S|. Таким образом, на практике достаточно ограничиться значением L, равным нескольким десяткам (например, 30 или 40). Это позволяет получить приемлемый уровень точности и сэкономить ресурсы. Значение |S| можно зафиксировать на значении 2L (п. 1.5.2).

4.4.2. Экспериментальное исследование порядка ближайших соседей Исследуем, насколько порядок строк в S соответствует «реальному» упорядочению этих же строк по расстоянию редактирования до q. Обозначим S мультимножество значений расстояния редактирования строк из S до q:

S = {ed(x, q) | x S}.

Для сравнения упорядоченных мультимножеств за основу было принято обобщенное расстояние Кендалла [40], которое позволяет сравнивать упорядоченные множества, рассматривая различные штрафы за нахождение элементов в разном относительном порядке в двух множествах M1, M2. Так, если два элемента i, j M1 M2 входят в сравниваемые множества под индексами i1, i2, j1, j2, то штраф u вычисляется по следующим правилам:

3. если i2 (i1 ) не определено, т.е. соответствующий элемент не входит во второе (первое) множество, а j1 < j2 (j1 > j2 ), то u = 0;

4. если j2 (j1 ) не определено, т.е. соответствующий элемент не входит во второе (первое) множество, а i1 < i2 (i1 > i2 ), то u = 0;

5. если i1, j2 (i2, j1 ) не определено, т.е. соответствующие элементы входит каждый в свое множество, то u = p.

Параметр p есть регулируемая характеристика «степени пессимистичности»

ситуации, когда один из элементов отсутствует в одном множестве, но присутствует в другом, и наоборот. Для наших экспериментов использовалось p = 1.

Расстояние DK (M1, M2 ) между множествами является суммой штрафов всех пар элементов M1 M2 :

Мы изменили описанный алгоритм подсчета обобщенного расстояния Кендалла для применения к упорядоченным мультимножествам (значений расстояний редактирования от q до ближайших строк) следующим образом. Для каждого из значений расстояния редактирования из S1 S2, входящего хотя бы в одно из мультимножеств, каждое его j-ое вхождение в оба мультимножества последовательно преобразуются в уникальный абстрактный элемент нового множества, условно обозначаемый символом sj, где индекс соответствует порядковому номеру, под которым он входит в данное множество. В частности, если элемент входит в одно их множеств только один раз, то его индекс в нем 1.

Например, из множеств S1 = {1, 2, 3, 4, 4, 3, 5}, S2 = {1, 3, 3, 4, 4, 3, 4}, получаем следующие множества элементов: S1 M1 = {11, 21, 31, 41, 42, 32, 51 }, S2 M2 = {11, 31, 32, 41, 42, 33, 43 }. Полученное описанным способом из S множество элементов будем обозначать M (S ). Таким образом, мы свели задачу сравнения упорядоченных мультимножеств S1 и S2 к задаче сравнения упорядоченных множеств M1, M2.

Как и в эксперименте в пункте 4.4.1, количество строк в S, возвращаемых процедурой LSH-лес, было переменным. То есть алгоритм возвращал множество из 2L строк, полученных в результате этапа подъема по LSH-деревьям (п. 4.2), при изменяющемся L.

Исследование проведено на наборе строк RandomStrings (п. 2.5.2). Мы использовали те же 2200 строк длиной 1000 символов, что и в предыдущем эксперименте п. 4.4.1. Множество P было запомнено в LSH-лесе с помощью процедуры LSH-лес (п. 4.2). На вход процедуры поиска приближенно ближайшего соседа подавался запрос q.

Обозначим как X упорядоченное по возрастанию мультимножество значений реальных расстояний редактирования от центра q до его ближайших соседей. Обозначим как Y упорядоченное в ходе процедуры LSH-лес мультимножество значений расстояний редактирования от центра q до возвращенных строк в ходе процедуры LSH-лес. Расстояние DK (M (X), M (Y )) (4.1) вычислялось при |S| = 10, 50, 100, 200, 300, 500, где размер множества M (X) ограничивался по значению |M (Y )| = |S|. Результаты усреднялись по 100 случайным независимым реализациям LSH-леса. Зависимость DK (M (X), M (Y )) от количества деревьев L в лесе изображена на рис. 4.3 для различных ограничений на максимальный размер возвращенного множества S и для следующих способов его дополнительной фильтрации:

Kendall coefficient Kendall coefficient Kendall coefficient Рис. 4.3. Зависимость DK (M (X), M (Y )) от L для |S| = 10, 50, 100, 200, 300, 1. «all» (без фильтрации);

2. «==max» (только строки, совпавшие с запросом q на самом глубоком для данного S уровня);

3. «==half» (строки, совпавшие на уровне от Kavg до Kavg ;

4. «>=half» (строки, совпавшие на уровне большем или равном Kavg );

где Kavg – среднее значение уровня среди возвращенных строк.

Из рис. 4.3 видно, что DK (M (X), M (Y )) незначительно уменьшается при увеличении L, что можно объяснить увеличением |S|. Поэтому, как и в эксперименте (п. 4.4.1), можно сделать вывод о возможности фиксирования L на небольшом значении.

Способы фильтрации «==max» и «==half» «выигрывают» у остальных способов (по значению DK ), подтверждая то, что совпадение строк на более глубоких уровнях свидетельствует об их большем сходстве.

Результаты данного раздела отражены в публикациях [146, 147].

4.5. Выводы по разделу 1. Разработанная алгоритмическая реализация запоминания векторных представлений базы примеров за счет использования LSH-леса позволяет осуществлять поиск приближенных ближайших последовательностей, обеспечивая эффективность счет использования структуры деревьев, и позволяющая не хешировать заново все последовательности базы при изменении параметров поиска и размера базы.

2. Разработанные методы поиска приближенных ближайших символьных последовательностей для последовательностей разной длины (дополнением спецсимволами, разбиением на окна, кластеризацией по длине) позволяют осуществлять поиск последовательностей в реальных базах.

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

4. Экспериментальное исследование на модельных данных показало возможность применения на практике небольшого (несколько десятков) количества деревьев в процедуре LSH-лес и размера мультимножества кандидатов на приближенных соседей, при сохранении точности поиска.

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

РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ

РАСПРЕДЕЛЕННОГО ПРЕДСТАВЛЕНИЯ И ПОИСКА

ПОСЛЕДОВАТЕЛЬНОСТЕЙ

В данном разделе рассматриваются разработанные программные средства, в которые реализованы методы и алгоритмы распределенного представления символьных последовательностей, их сравнения и поиска сходных (разд. 3, п. 3.3). Также рассмотрено их применение в следующих актуальных практических задачах классификации: обнаружение дубликатов (п. 5.2.1), обнаружения спама (п. 5.2.2), классификация участков ДНК (п. 5.2.3), а также в задаче классификации сессий пользователей с целью обнаружения аномалий в компьютерных системах (п. 5.2.4).

5.1. Разработка программных средств Разработаны программные средства, которые использовались для решения прикладных задач (п. 5.2), а также переданы в другие организации (см.

акты внедрения в Приложении А).

5.1.1. Программные библиотеки Были разработаны следующие программные объектно-ориентированные библиотеки.

1. Библиотека форматированного ввода TextInputTools – содержит модули форматированного ввода для баз генетических последовательностей, электронных писем, ряда популярных текстовых корпусов, аудит-последовательностей UNIX-систем.

2. Библиотечный модуль VectorComparer – унифицированное средство сравнения векторов по стандартным метрикам и мерам на основе шаблонных классов, что позволяет его использование и адаптацию под разные типы данных – векторы с элементами разных типов, квазивекторные данные (например, деревья) и др.

3. Библиотека LSHLibrary – реализует методы представления и поиска приближенных ближайших символьных последовательной (разд. 3).

Спроектирована для работы с последовательностями произвольной символьной природы (текстовые последовательности, генетические последовательности, последовательности команд и т.д.).

Основные классы библиотеки LSHLibrary:

• tree_encoder – класс, отвечающий за формирование хеш-функций по входным строкам. В реализации псевдослучайной генерации векторов по q-грамме используется кодирование q-граммы по алгоритму хеширования Карпа-Рабина [65], результат которого инициализирует генератор псевдослучайных чисел;

• lsh_tree – класс, реализующий заполнение, хранение, и запросы • lsh_tree_node – класс узла LSH-дерева, обеспечивающий хранение значения хеш-функции (3.1) (п. 3.1.2);

• lsh_forest – класс, обеспечивающий создание, управление и логику обработки запросов к лесу – набору LSH-деревьев;

• lsh_forest_collector – класс, обеспечивающий создание и управление несколькими LSH-лесам, а также обработку запросов к Все библиотеки реализованы в виде шаблонных классов для С++ без использования системно-зависимых функций, что обеспечивает их мультиплатформенность. Основой программных средств является объектно-ориентированная библиотека классов С++ CommonLib, содержащая классы векторов различных видов, методы генерации случайных величин и векторов из различных распределений, другие часто используемых компоненты. Библиотеки могут быть использованы для решения широкого круга как исследовательских, так и практических задач.

5.1.2. Программный нейрокомпьютер SNC Модульный программный нейрокомпьютер SNC разработан в отделе нейросетевых информационных технологий Международного научно-учебного центра информационных технологий и систем НАН и МОН Украины. SNC принадлежит к нейрокомпьютерам общего назначения [73, 125, 133, 137], предназначенным для решения широкого круга задач. Система имеет модульную архитектуру и позволяет визуально конструировать конфигурации обработки данных, используя расширяемый набор обрабатывающих блоков.

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

Функциональность нейропакета наращивается путем реализации новых обрабатывающих блоков: форматов и обрабатывающих блоков. Универсальный механизм сохранения результатов в БД позволяет сохранять в удобном виде все необходимые данные выполняемого проекта: параметры конфигурации, результаты работы, и т.д. Информация может использоваться для дальнейшей обработки и формирования отчетов.

В основу архитектуры SNC положена технология COM [121], которая позволила стандартизировать программные модули и облегчить включение в систему новых модулей. Ядром системы (рис. 5.1) является модуль Conguration Manager, который управляет процессом выполнения конфигурации и координирует совместную работу дополнительных модулей.

Существует два типа дополнительных модулей: форматы и обрабатывающие блоки. Модули форматы реализуют чтение и запись внешних данных, например генетических последовательностей из формата FASTA, аудит-логов из формата BSM или ACCT и т.п. Модули обрабатывающих блоков реализуют различные алгоритмы обработки данных – например, обучение и классификацию на основе персептрона, алгоритм ближайшего соседа, метод опорных векторов и др. Поддержка новых форматов и реализация новых алгоритмов осуществляется сравнительно несложно благодаря стандартизированным COM интерфейсам и шаблонным классам, реализующим необходимую минимальную функциональность.

Сохранение параметров и результатов выполнения проектов в базе данных обеспечивается модулем Storage. При запуске конфигурации в базе данных создается иерархическая схема данных проекта. В неё помещаются схема данных конфигурации проекта и схемы данных, поддерживаемых обрабатывающими блоками проекта.

Для создания конфигураций разработана графическая оболочка Graph Shell (рис. 5.2), которая позволяет визуально в режиме САПР настраивать обрабатывающие блоки, а также потоки данных и управления.

Рис. 5.1. Архитектура программного нейрокомпьютера SNC В рамках программного нейрокомпьютера реализовано большое количество реализованных блоков форматов и обрабатывающих блоков, что позволяет легко строить различные алгоритмы обучения и классификации. На рис. 5. приведен пример реализации одного из проектов.

Результаты работы сохраняются в файле и базе данных с помощью механизмов модуля Storage, а также могут быть визуализированы при выполнении проекта в графической оболочке (см. рис. 5.3).

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

Рис. 5.2. Графическая оболочка программного нейрокомпьютера Рис. 5.3. Графическая оболочка SNC в режиме выполнения конфигурации 5.1.3. Специализированные программные системы На основе разработанных библиотек для поиска текстовых дубликатов, спама, кодирующих участков генетических последовательностей и классификации сессий пользователей UNIX-системы были разработаны программные макеты DuplClassier (поиск приближенных тектовых дубликатов и дубликатов веб-документов), EmailClassier (классификация электронной почты), NuclClassier (классификация нуклеотидов генетических последовательностей), SessionClassier (классификация пользовательских сессий в компьютерной системе).

Программные средства реализованы с использованием языка C++ и с интерфейсом командной строки, что обеспечивает мультиплатформенность.

5.2. Применение в задачах классификации 5.2.1. Исследование поиска дубликатов в текстовых и веб-коллекциях Метод п. 3.3 был исследован в задаче поиска дубликатов в текстовых базах. Поиск (приближенных) дубликатов текстовых документов является операцией, которую необходимо эффективно выполнять в системах документооборота. Особенно критичной эта операция становится в поисковых машинах Интернет [17]. Документы, являющиеся приближенными дубликатами друг друга, чрезвычайно распространены в Интернет. Яркими примерами являются различные сборники FAQ, справочники по языкам программирования, командам операционных систем. Кроме того, некоторые технологии привлечения посетителей на сайты предусматривают наполнение «поддельных» страниц частями текстов легальных страниц с целью привлечения случайных посетителей для показа платной рекламы или перенаправления на другие сайты [48].

5.2.1.1. Базы данных для экспериментального исследования Поиск дубликатов осуществлялся в следующих базах новостных текстов Reuters-21578 [74], учебных текстов British National Corpus [15], характеристики которых приведены в табл. 5.1, а также на базе РОМИП [148].

Reuters-21578 является стандартной базой для исследований в области обработки текстовой информации. Содержит тексты новостей агентства Reuters, среди которых много как приближенных (укороченные версии развернутых новостей, данные о котировках на биржах, отличающиеся датами и числами в Характеристики использованных текстовых баз (при применении C-функции Коллекция Максимальная Минимальная Медиана Всего текстов Reuters- РОМИП тексте, и т.п.), так и полных дубликатов.

British National Corpus (BNC) – большая база текстов современного письменного и разговорного английского языка. Представляет собой «золотой стандарт» и источник сведений о «правильном» английском языке (например, по ней вычисляются вероятности префиксов, окончаний, слов, для использования в разных задачах). «Теоретически» дубликатов в BNC быть не должно, поскольку дубликаты портят статистику «правильного» языка.

Использовалась предварительная фильтрация текстов баз Reuters-21578 и BNC, оставляющая только символы и цифры (C-функция isalnum()) или дополнительно еще знаки пунктации ((C-функция ispunct())). Заголовки новостных текстов включались в текст, а прописные буквы заменялись на строчные. Короткие тексты, длина которых меньше длины обрезки n, дополнялись до указанной длины одинаковым специальным символом в конце.

Качество поиска дубликатов для веб-документов исследовалось на стандартной базе «Дубли Web-страниц коллекции РОМИП»1 [134], содержащей список более 10 млн. пар веб-страниц, входящих в базу РОМИП [148], сходство между которыми по значению функции String::Similarity не менее 0.85. База РОМИП является случайной выборкой 3% сайтов из домена narod.ru, что составляет 0.12%-0.30% от размера Рунета. Общий размер базы составляет 1.5Гб в архиве и включает около 800 тысяч веб-документов с более чем 23000 сайтов. База содержит множество типов сайтов, однако в ней больше мусора, чем в среднем по русской части Интернет, популярны типовые шаблоны оформления страниц, нет ряда категорий сайтов (например, корпоративных), а граф ссылок отличается от Веб [135].

Предварительная обработка базы включала удаление html-разметки, символов пунктуации, лишних пробелов, заглавные буквы заменялись маленькими, документы, состоящие из менее, чем 20 слов удалялись – в итоге документы набора содержали лишь символы латинского и кириллического алфавитов, а также цифры.

Коллекция предоставлена компанией «Яндекс» [136].

5.2.1.2. Методика поиска дубликатов Использовался метод поиска приближенно ближайших строк, описанный в п. 4.3.3. При поиске дубликатов последовательно проходятся все тексты коллекции, которые и служат запросами к LSH-лесу, где запомнены их распределенные представления. Запрос выполнялся для двух лесов, базы P1 и P2 которых состояли из текстов, длины которых попадали в оба интервала, «накрывающие» значение длины запроса (п. 4.3.3). Длины текстов (и запроса) в каждом интервале выравнивались добавлением специальных символов в конце текста до значения максимальной длины в каждом интервале (п. 4.3.1).

Был проведен ряд экспериментов для значений L = 1, 2, 5, 10, Kmax = 1, 5, 10, 25. Дубликатами считались строки, совпавшие на максимальном уровне дерева. Если рекомендуемое теорией значение K (см. выражение (1.15)) для данного кластера было меньше, чем Kmax, то для сигнализации дубликата было достаточно совпадения на уровне K.

Для поиска дубликатов в Reuters-21578 и BNC было принято, что дубликатами будут считаться тексты, у которых имеется хотя бы одно совпадение хеш-векторов длиной K. Находилось количество дубликатов в зависимости от длины обрезки текста до n = 100, 150, 250, 500, 1000, 2000 символов и без обрезки (выравнивание по максимальной длине, условно обозначаемое n = 0). Использовались следующие параметры схемы LSH: количество деревьев L = 1, 5; размерности хеш-векторов K = 1, 2, 5, 10, 25, 50, 100, 150, 200.

5.2.1.3. Результаты Найденное количество приближенных дубликатов в зависимости от значений K и n, для L = 1, 5 приведено для Reuters-21578 в табл. 5.2 (использовалась C-функция isalpha()) и в табл. 5.3 (для предварительной фильтрации использовалась C-функция isalpha()+ispunct(), а для BNC – соответственно в табл. 5.4 и 5. Число приближенных дубликатов ожидаемо уменьшается при увеличении K, стабилизируясь при больших K на значениях, примерно соответствующих количеству дубликатов, найденных в работе [99] другим методом (320 дубТаблица 5. Количество найденных приближенных дубликатов в коллекции Reuters- в зависимости от значений n и K, при L = 1 и L = 5 и использовании Количество найденных приближенных дубликатов в коллекции Reuters- в зависимости от значений n и K, при L = 1 и L = 5 и использовании ликатов). Большое число приближенных дубликатов в случае без использования обрезки по фиксированной длине (и их увеличение для эксперимента с isalnum() для n = 2000) объясняется большим сходством большинства строк, так как к ним добавлялись одинаковые символы для выравнивания длины. При увеличении L количество дубликатов также увеличивается, поскольку увеличивается вероятность совпадения K элементов хотя бы у одного дерева.

При «визуальной» проверке, однако, некоторые дубликаты оказались точными. Уменьшение количества дубликатов при увеличении длины обрезки для 10 при визуальной проверке показало, что оно вызвано мелкими опечатK ками в текстах. При меньших значениях K эти опечатки могли не вызывать несовпадений хеш-векторов.

Количество найденных приближенных дубликатов в коллекции BNC в зависимости от значений n и K, при L = 1 и L = 5 и использовании Количество найденных приближенных дубликатов в коллекции BNC в зависимости от значений n и K, при L = 1 и L = 5 и использовании с 1.5Гб памяти.

Результаты поиска сравнивались с результатами метода детерминированного вложения из [10]. За «золотой стандарт» было выбрано определение пары дубликатов, как такой, на которой значение функции языка PERL String::Similarity (основанной на алгоритме Майерса [81] вычисления расстояния редактирования) не меньше 0.85 (такой же подход применялся для создания коллекции дубликатов в [134]).

Обозначим как Tsim множество пар текстов со значением функции String ::Similarity, большим или равным sim. Принимая поочередно за «настоящие дубликаты» множества T0.85, T0.95, T0.97, T0.99, качество работы нашего метода оценивалось с помощью графиков точность-полнота путем изменения значения K (использовались K = 5, 10, 25, 50, 100, 150, 200). Результаты приведены на рис. 5.4.

Как видно, при увеличении порога sim на значение функции String::

Similarity полнота увеличивается, т.е. все большая доля «правильных»

дубликатов попадает в мультимножество |S|, достигая единицы при sim = (т.е. когда дубликатами считаются только полные дубликаты). Уменьшение точности при увеличении длины обрезки n объясняется более частым «срабатыванием» метода на большем количестве специальных символов, с помощью которых выравнивалась длина текстов.

Precision Precision Рис. 5.4. Зависимость точности от полноты поиска, полученная разработанными методами для значений sim = 0.85, 0.95, 0.97, 0.99 при L = Аналогичные графики (рис. 5.5) были построены для метода детерминированного вложения, описанного в работе [10] (BY), для длины обрезок n = 100, 150, 250, 500, 750 (для б льших значений n не удалось получить реo зультатов за приемлемое время). Для построения графиков изменялся порог на расстояние Хемминга между полученными векторами, указывающий, что считать дубликатом. Проверялись только тексты, где расстояние Хемминга не превышало 15% от максимально возможного для данной длины n.

Для сравнения пар значений точность-полнота использовалась интегральная оценка – F -мера с = 1, определяемая как F = (1 + )rp/(p + r) [116], где r – полнота, p – точность. Для каждой из кривых, изображенных на рис. 5. Precision Precision Рис. 5.5. Зависимость точности от полноты поиска, полученная методом БарЙозефа для значений sim = 0.85, 0.95, 0.97, 0.99 при L = и 5.5, было подсчитано максимальное значение F1max, достигаемое на точках этих кривых, которое для n = 100, 250, 500, 750 изображено на рис. 5.6.

Результаты показывают отсутствие существенных отличий в качестве между двумя сравниваемыми методами относительно «золотого стандарта», однако время решения задачи существенно отличается. Порядок времени поиска дубликатов на всей коллекции с учетом построения деревьев в методе, основанном на применении LSH-леса, составляет минуты, тогда как применении детерминированного метода Бар-Йозефа (BY) из [10] – от часов до дней.

LSH LSH

LSH LSH

Рис. 5.6. Значения F1max для n = 100, 250, 500, 750. Точки (кресты), обозначенные в легенде как BY, соответствуют методу Бар-Йозефа, плюсы – разработанному поиска с помощью LSH-леса Результаты поиска дубликатов в базе РОМИП для K = Результаты поиска дубликатов в базе РОМИП представлены в таблицах 5.6 и 5.7, где приведены значения точности, полноты и F -меры для значений порога на значение sim = 0.85, 0.90, 0.95, 1.00; значений = 0.005, 0.01, 0.05, 0.1, 0.2, 0.3 и L = 1, 2, 5, 10, K = 5, 10, 25, 50, 100, 150.

В работе [128] максимальное значение F -меры, полученное с помощью Результаты поиска дубликатов в базе РОМИП для K = подхода на основе поиска замкнутых множеств признаков, на части коллекции РОМИП достигало 0.49. В работе [124] на основании методов, использующих статистическую информацию (спецсимволы, длины элементов, наборы популярных слов) для порогов 0.85, 0.90, 0.95, 1.00 были получены значения F меры, соответственно, 0.66, 0.75, 0.82, 0.89. Как видно из табл. 5.6, 5.7, метод поиска дубликатов на основании поиска приближенно ближайших строк показывает результаты, превышающие полученные в [128, 124]. Также отметим, что, в отличие от экспоненциального по |P | метода [128], исследовавшего лишь до 50% всей базы, вычислительная сложность предложенного метода позволила исследовать его на полной коллекции РОМИП.

5.2.2. Обнаружение спама в электронных сообщениях Обнаружение почтового спама (сообщений, как правило, рекламного характера, массово рассылаемых людям, не выразившим желание их получать) также является актуальной задачей, поскольку количество спама среди всей почты у среднего пользователя в 2005 году уже достигало 80-85% [39] и увеличивается. Спам обнаруживают различными способами – в основном, это проверки на специфические особенности спам-писем, такие как нахождение адреса адресанта в черном списке, экстенсивное применение разметки HTML в письме, подозрительные (графические) вложения, а также использование байесовской классификации [87] на основе вероятностей специфических слов.

Одной из распространенных спам-технологий, позволяющих спамерам избежать простейших частотных фильтров, является внесение изменений в текст письма, таких как специфическое написание слов в письмах, которые перестают быть точными копиями друг друга, а также искажают картину вероятностей слов или препятствуют предварительной обработке писем фильтрами [48]. Для борьбы с подобными технологиями некоторые исследователи [142, 68, 141] предлагают использовать сравнение писем с ранее сохраненными, поскольку спам по своей природе имеет массовый характер, а рассылаемая реклама одинакова для тысяч получателей.

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

5.2.2.1. Базы данных для экспериментального исследования Были использованы тестовые базы, широко применяющиеся разработчиками систем обнаружения спама для тестирования своих продуктов: TREC 2005 Spam Track [26] и TREC 2006 Spam Track [25]. Обе базы содержат почтовые сообщения, размеченные экспертами на два класса: «спам» и «не спам».

TREC 2005 Spam Track содержит |P | = 92189 реальных почтовых сообщений объемом 0.8 Гб, из которых 52790 (57%) спамовые. Англоязычная часть TREC 2006 Spam Track содержит |P | = 37822 реальных почтовых сообщений, объемом в 189 Мб, из которых 24912 (66%) – спам.

5.2.2.2. Схема экспериментов и оценки эффективности Коллекции TREC и принятый способ оценки эффективности фильтров на них построены с учетом способа реального использования спам-фильтров у конечных пользователей. Задача тестируемых фильтров – классифицировать подаваемые в хронологическом порядке сообщения и, затем, дообучиться после получения правильной метки для этого сообщения от эксперта. Этот процесс соответствует обычному порядку действий пользователя, когда он каждый раз помечает во входящих сообщениях спам, что позволяет более точно настроить фильтр.

По условиям TREC, каждому письму должен быть присвоен параметр – степень «спамности» письма (score), по которому оно классифицируется: сообщения, получившие score больше определенного порога, считаются спамом, остальные – обычными письмами. Оценка качества работы фильтра проводится по двум основным параметрам – проценту неправильно классифицированных спам-сообщений sm%, т.е. false positives, и проценту неправильно классифицированных неспам-сообщений hm%, т.е. false negatives. Изменением порога на значение score можно построить ROC-кривые (зависимость sm% от hm%), по которым в TREC сравниваются различные алгоритмы.

Предварительный фильтр оставлял в письмах одни лишь символы алфавита (С-функция isalpha()) и обрезал сообщение по размеру n = 1000.

Подаваемые в хронологическом порядке сообщения служили запросами для процедуры поиска приближенного ближайшего соседа с помощью LSH-леса.

Значение L изменялось от 1 до 200. Значение K фиксировалось по формуле (1.15).

На основании экспериментов в пункте 4.4.2 было выбрано два способа присвоения score письмам по уровню в LSH-лесе, к которому принадлежат приближенные ближайшие соседи ко входным письмам. А именно 1. по максимальному уровню kmax = K;

2. по среднему уровню kavg.

Если сообщение на самом деле имело в коллекции экспертную метку «спам», то оно добавлялось в множество P и на классификацию подавалось следующее сообщение.

5.2.2.3. Результаты Полученные ROC-кривые изображены на рис. 5.7 и 5.8, откуда видно, что • для Spam Track 2005 при уровне hm%=10% успешно обнаруживается только 50% спама для n = 1000, а при уровне n = 5000 спам почти не обнаруживается (практические случайная классификация);

• для Spam Track 2006 результаты значительно выше: при уровне hm%=5успешно обнаруживается примерно 80% спама. Возможно, это связано с большим объемом базы.

Из ROC-кривых на рис. 5.8 видно, что при L = 1 значения hm% зачастую меньше, чем при L > 1. Это можно объяснить высокой степенью сходства части легальных писем с спамом, например, из-за использования html-формата, который оставлялся в теле письма, а не убирался и/или не анализировался его код, как это принято в реальных системах обнаружения спама. Для L = ROC-кривые для разных значений K приведены на рис. 5.9, откуда видно, что увеличение K приводит к более точной классификации легальных писем.

sm% sm% Рис. 5.7. Зависимость sm% от hm% для коллекции Spam Track 2005 для двух способов присваивания score – по среднему и по максимальному уровню, для n = 1000 и n = Возможно, при этом «улавливаются» их более тонкие отличия от спама.

Из проведенных экспериментов видно, что, реализовав идею обнаружения спама по приближенным дубликатам, можно отфильтровать значительную sm% sm% Рис. 5.8. Зависимость sm% от hm% для коллекции Spam Track 2006 для двух способов присваивания score – по среднему и по максимальному уровню, для n = 1000 и n = ших почтовых серверов в качестве одного из модулей системы обнаружения спама. Чем централизованнее почтовый сервис и чем большее у него число пользователей, тем больший процент отфильтрованного спама можно ожидать.

sm% Рис. 5.9. ROC-кривая для разных значений K при L = 1 для коллекций Spam Track 2005 и Spam Track ближенных копий, будут особенно эффективны в больших почтовых сервисах типа Gmail [47]. Поскольку спам всегда направляется огромному числу получателей, на почтовом сервисе обнаружить его намного легче, чем в рамках почтового ящика индивидуального пользователя, куда похожий спам приходит в гораздо более скромных масштабах. Для индивидуальных пользователей подобный подход можно применять, перейдя к кооперативному обнаружению спама. В качестве примера можно привести распределенную систему обнаружения спама Vipul’s Razor [117], которая использует сокращенные представления сообщений, отмеченных как спам участниками системы. В качестве таких сокращенных представлений можно рассмотреть использование разработанных распределенных представлений – хеш-векторов.

5.2.3. Поиск генов и гиперчувствительных сайтов в Поиск новых генов – это фундаментальная задача вычислительной биологии, состоящая в алгоритмизированном поиске биологически функциональных участков генетических последовательностей. Генами называются определенные подпоследовательности нуклеиновых баз (нуклеотидов) дезоксирибонуклеиновой кислоты (ДНК), которые в процессе транскрипции кодируют различных аминокислот, использующихся для создания протеинов. Гены высших организмов (эукариотов) состоят из несмежных участков – экзонов (по 140 нуклеотидов в среднем). Между экзонами находятся гораздо более длинные некодирующие, «мусорные» последовательности, не относящиеся к генам – интроны [120], у человека суммарно составляющие до 99% длины всего генома [95].

Биологи все мира каждый год генерируют около 10 миллиардов мегабайт данных, а объем базы генов GenBank [44] удваивается каждые 15 месяцев [14]. Поэтому поиск генов невозможен без эффективных вычислительных инструментов анализа большого количества длинных последовательностей.

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

Другой важной задачей является поиск гомологичных некодирующих участков в локус-контролирующих областях (locus control region, LCR) бета-глобина, которые управляют транскрипцией в локусе. Известно, что последовательности бета-глобина содержат хорошо сохранившиеся в процессе эволюции области, называемые гиперчувствительными сайтами ДНКазы [42, 21], что позволяет идентифицировать эти области в бета-глобине исследуемых организмов.

Нуклеотиды можно представить, как алфавит из четырех символов A, G, T и C, а цепи молекулы ДНК – как последовательности таких символов. Степень отличия двух цепей может быть определена как расстояние редактирования между последовательностями составляющих их нуклеотидов.

Для поиска экзонов будем использовать подход рассуждений на основе примеров, где роль примеров играют экзоны последовательностей обучающей выборки. По таким примерам ищутся экзоны в тестовых последовательностях (п. 5.2.3.2), либо участки гиперчувствительных сайтов одного организма (п. 5.2.3.4), по которым необходимо найти такие же в бета-глобине другого организма. Для повышения эффективности поиска используются описанные в разделе 3 методы.

5.2.3.1. Базы данных для экспериментального исследования Для первого эксперимента по поиску экзонов обучающей базой был выбран набор HMR195, использованный в [93] для тестирования программ обнаружения генов (195 последовательностей с 948 экзонами, средняя длина последовательностей 7096). Тестовой выборкой служила база последовательностей Burset-Guigo из [22] (570 последовательностей, 2649 экзонов). В обеих базах экзоны размечены.

Для второго эксперимента по поиску коротких некодирубщих участков ДНК использовалась LCR-последовательность бета-глобина мыши (длиной 12 Кб, GenBank Z13985) и человека (первые 20 Кб GenBank U01317) из [21].

В качестве обучающей выборки был принят бета-глобин мыши, тестовой – человека.

5.2.3.2. Методика классификации нуклеотидов для поиска экзонов Цель первого эксперимента – оценить эффективность предложенного метода поиска сходных строк в задаче поиска экзонов в генетических последовательностях позвоночных по известным примерам экзонов других организмов.

Поиск экзонов осуществлялся путем распознавания принадлежности экзону отдельных нуклеотидов. Каждому i-му нуклеотиду всех тестовых последовательностей ставился в соответствие счетчик ci, изначально инициализированный нулем. Для каждого экзона gi из обучающей последовательности принималось P = {gi } и строился LSH-лес. Далее все тестовые последовательности y «нарезались» скользящим окном шириной |gi | (ссылка). Подстроки вида y[i, i+|gi |1] поочередно служили запросом к построенному LSH-лесу.