strtree — классификатор строк на основе регулярных выражений

Вы хотите найти короткие регулярные выражения, полно и точно отделяющие один класс строк от другого? Это статья для вас. Мы поговорим про задачу классификации строк с помощью автоматически определяемых паттернов, а в конце я предоставлю пример такой процедуры с кодом на Python. Пользоваться мы будем небольшой open-source библиотекой strtree – в названии присутствует слово tree, поскольку регулярные выражения в ней располагаются в форме бинарного дерева, у каждой вершины которого всего одно исходящее ребро.

Зачем же вообще нам пользоваться регулярными выражениями для классификации строк? Такая задача может возникать при следующих условиях:

• Мы имеем дело со строками небольшой длины, состоящие из одного или нескольких слов – токенизировать такие строки для применения стандартных алгоритмов часто не имеет смысла;

• Порядок символов строки часто оказывается критически важен;

• Мы предполагаем, что среди строк одного из классов есть что-то общее, что к тому же отличает их от другого класса;

• Строки по большей части уникальны.

Такими данными могут быть, например, IP-адреса, модели смартфонов, компьютеров, деталей от них, имена пользователей, адреса электронных почт и прочее. В этих случаях привычный bag-of-words с дальнейшей классификацией табличными данных слабо применим: bag-of-words стирает разницу между строками с одними и теми же символами, но разным порядком. Для нас "ABC-1" и "1-CBA" – это две принципиально разные строки, описывающие два разных объекта (например, два разных устройства). Bag-of-words хорошо работает, например, для sentiment analysis, но при классификации чувствительных к перемешиванию символов строк он показывает себя хуже. Хорошо подобранные регулярные выражения, с другой стороны, не обладают такой проблемой.

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

Конечно, вручную находить короткие и точные регулярные выражения для реальных данных сложно. Особенно когда паттерн не проглядывается, данных много или когда задачу нужно повторять ежедневно. Очевидно, что в этом случае регулярные выражения хочется искать автоматически. И именно этим мы и займемся!

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

Алгоритм

Для начала опишем задачу чуть более формально.

Мы имеем два набора строк соответствующих классов: и . Одна и та же строка может появляться несколько раз; как только в одном, так и в обоих классах одновременно.

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

Вы можете подумать, что ответ классификатора может только абсолютный: строка либо принадлежит классу , либо не принадлежит. Однако, как я покажу далее, мы можем также получать и вероятность принадлежности строки к классу.

Составляем регулярные выражения

Как получить необходимые регулярные выражения? Начнем с того, что нужный нам набор всегда существует. В качестве него мы можем просто использовать все строки из класса  . Если набор слабо пересекается с классом , точность такого классификатора будет высокая – вплоть до 100% при полном отсутствии пересечений. Однако в этом случае набор может оказаться слишком длинным, а классификатор не будет работать верно при виде новых строк, которые не присутствовали в наборе . Кроме того, если вы будете использовать алгоритм для поиска общих паттернов в классе (например, для EDA), то никакой полезной информации из таких “паттернов“ вы не получите – они ничего не обобщают. Чтобы избежать таких проблем, нам нужно искать более короткие, но точные регулярные выражения.

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

Как же мы будем удлинять регулярное выражение? Мы будем добавлять к нему по одному токену (по одному строительному блоку для регулярного выражения; об этом – ниже), и среди комбинаций выражения и токенов находить лучший вариант удлинения с точки зрения f1_score на непокрытых на данный момент строках. Если при добавлении токенов новое выражение не покрывает ни одной строки из непокрытой части класса (т.е. f1_score = 0 для всех токенов), будем считать, что удлинения не существует, и начнем искать паттерн заново.

Немного про токены. Токены – это преобразованные n-граммы длина 1, полученные из строк класса . Он играет роль минимального паттерна, этакого строительного блока при построении регулярного выражения. Посмотрим на процесс составления токенов на примере. 

Допустим, состоит из одной строки "string 1". N-граммы длины 1 для набора – это "s", "t", "r", "i", "n", "g", " ", "1". После преобразования они станут токенами "s.+", ".+t.+", ".+r.+", …, ".+1",  а также такими токенами, как ".+\d" (вместо "1" в конце строки – любая цифра в конце), "[a-z].+" (вместо "s" в начале – любая строчная буква в начале), и прочие. То есть токены – это короткие паттерны, "в общих чертах" описывающие набор, которые будут добавляться к текущему регулярному выражению. Способов преобразовать n-грамму в токен может быть очень много. Чем шире токен после преобразования – тем шире могут быть регулярные выражения в конечном наборе.

Вероятность принадлежности к классу

Я упомянул, что классификатор способен выдавать не только бинарные значения, но и вероятность принадлежности строки к классу . Происходит это очень просто. При добавлении регулярного выражения в список мне проверяли его precision score, то есть долю строк из класса среди всех строк, подходящих под регулярное выражение. Таким образом, если произвольная строка подходит под какое-то регулярное выражение, мы можем использовать именно precision score этого регулярного выражения как приближение вероятности того, что строка относится к классу .

"Псевдокод"

Повторять, пока все строки из не будут помечены как "покрытые":

1. Создать пустое регулярное выражение;

2. Повторять, пока удлинение выражения не перестанет существует или его точность не достигнет minPrecision:

   1. Удлинить регулярное выражение путем перебора токенов и выбора комбинации токена и выражения с самым высоким f1-score на непокрытых строках;

3. Если последнее регулярное выражение существует и его точность больше или равна minPrecision, добавить выражение в список ;

Пометить строки из S1, подходящие под последнее найденное регулярное выражение, как "покрытые".

Пример

В этом простом примере с помощью библиотеки strtree ищутся регулярные выражения для классификации вымышленных наименований смартфонов. А именно, в примере:

• Определяются классифицирующие регулярные выражения

• Считается precision score и recall score для классификации тренировочных строк

• Получаются предсказания со сработавшими регулярными выражениями и их точностями для тренировочных строк

Установить библиотеку вы можете с помощью pip: pip install strtree

У библиотеки также есть небольшая документация.

import strtree


strings = ['Samsung X-500', 'Samsung SM-10', 'Samsung X-1100', 'Samsung F-10', 
           'Samsung X-2200', 'AB Nokia 1', 'DG Nokia 2', 'THGF Nokia 3', 
           'SFSD Nokia 4', 'Nokia XG', 'Nokia YO']
labels = [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0]

tree = strtree.StringTree()
tree.build(strings, labels, min_precision=0.75)

for leaf in tree.leaves:
    print(leaf)
# PatternNode(".+ .+a.+", right=None, left=PatternNode(.+0.+), n_strings=11, 
#              precision=1.0, recall=0.57)
# PatternNode(".+0.+", right=None, left=None, n_strings=7, 
#             precision=1.0, recall=1.0)

print('Precision: {}'.format(tree.precision_score(strings, labels)))
# Precision: 1.0

print('Recall: {}'.format(tree.recall_score(strings, labels)))
# Recall: 1.0

matches, matched_nodes = tree.match(strings, return_nodes=True)
# нou will receive a vector of the same size as strings, 
# containing 0's (no match) or 1's (match), 
# and also the nodes containing regular expression and its precisions for each sample

Если у вас остались вопросы касательно работы или применения алгоритма, библиотеки, или вам просто хочется поболтать, приглашаю вас в комментарии!