strtree — классификатор строк на основе регулярных выражений
Вы хотите найти короткие регулярные выражения, полно и точно отделяющие один класс строк от другого? Это статья для вас. Мы поговорим про задачу классификации строк с помощью автоматически определяемых паттернов, а в конце я предоставлю пример такой процедуры с кодом на Python. Пользоваться мы будем небольшой open-source библиотекой strtree – в названии присутствует слово tree, поскольку регулярные выражения в ней располагаются в форме бинарного дерева, у каждой вершины которого всего одно исходящее ребро.
Зачем же вообще нам пользоваться регулярными выражениями для классификации строк? Такая задача может возникать при следующих условиях:
Мы имеем дело со строками небольшой длины, состоящие из одного или нескольких слов – токенизировать такие строки для применения стандартных алгоритмов часто не имеет смысла;
Порядок символов строки часто оказывается критически важен;
Мы предполагаем, что среди строк одного из классов есть что-то общее, что к тому же отличает их от другого класса;
Строки по большей части уникальны.
Такими данными могут быть, например, IP-адреса, модели смартфонов, компьютеров, деталей от них, имена пользователей, адреса электронных почт и прочее. В этих случаях привычный bag-of-words с дальнейшей классификацией табличными данных слабо применим: bag-of-words стирает разницу между строками с одними и теми же символами, но разным порядком. Для нас "ABC-1" и "1-CBA" – это две принципиально разные строки, описывающие два разных объекта (например, два разных устройства). Bag-of-words хорошо работает, например, для sentiment analysis, но при классификации чувствительных к перемешиванию символов строк он показывает себя хуже. Хорошо подобранные регулярные выражения, с другой стороны, не обладают такой проблемой.
Еще одно преимущество регулярных выражений в поставленных условиях – хорошая производительность для коротких строк и небольшого числа примеров. При этом методы-конкуренты (например, нейронные сети), могли бы не успеть уловить паттерн в таких условиях.
Конечно, вручную находить короткие и точные регулярные выражения для реальных данных сложно. Особенно когда паттерн не проглядывается, данных много или когда задачу нужно повторять ежедневно. Очевидно, что в этом случае регулярные выражения хочется искать автоматически. И именно этим мы и займемся!
Итак, эта статья предлагает метод автоматического составления регулярных выражений, которые с нужной точностью отделяет один класс строк от другого. Этот метод и реализован в библиотеке stretree, которую я упомянул выше. А сейчас предлагаю начать изучать сам алгоритм и рассмотреть пример с кодом.
Алгоритм
Для начала опишем задачу чуть более формально.
Мы имеем два набора строк соответствующих классов:
Наша цель – найти такой набор регулярных выражений
Вы можете подумать, что ответ классификатора может только абсолютный: строка либо принадлежит классу
Составляем регулярные выражения
Как получить необходимые регулярные выражения? Начнем с того, что нужный нам набор всегда существует. В качестве него мы можем просто использовать все строки из класса
Для этого каждое регулярное выражение мы будем создавать инкрементно, начиная с пустого паттерна и удлиняя его до тех пор, пока мы либо не достигнем минимальной допустимой точности (т.е. доли строк из класса
Как же мы будем удлинять регулярное выражение? Мы будем добавлять к нему по одному токену (по одному строительному блоку для регулярного выражения; об этом – ниже), и среди комбинаций выражения и токенов находить лучший вариант удлинения с точки зрения f1_score на непокрытых на данный момент строках. Если при добавлении токенов новое выражение не покрывает ни одной строки из непокрытой части класса
Немного про токены. Токены – это преобразованные n-граммы длина 1, полученные из строк класса
Допустим,
Вероятность принадлежности к классу
Я упомянул, что классификатор способен выдавать не только бинарные значения, но и вероятность принадлежности строки к классу
"Псевдокод"
Повторять, пока все строки из
Создать пустое регулярное выражение;
Повторять, пока удлинение выражения не перестанет существует или его точность не достигнет minPrecision:
Удлинить регулярное выражение путем перебора токенов и выбора комбинации токена и выражения с самым высоким f1-score на непокрытых строках;
Если последнее регулярное выражение существует и его точность больше или равна 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
Если у вас остались вопросы касательно работы или применения алгоритма, библиотеки, или вам просто хочется поболтать, приглашаю вас в комментарии!