LINUX.ORG.RU

Data mining

 , , ,


1

3

Всем привет!

Мне иногда требуется анализировать большие текстовые файлы, хочется автоматизировать этот процесс. Написал PoC:

% find /usr/bin |head -300 |~/classifier.pl|tail -30
75      /usr/bin/*g
2       /usr/bin/idevice*proxy
2       /usr/bin/tri-*edgeflag
113     /usr/bin/*r
11      /usr/bin/*-config
2       /usr/bin/transmission-*
3       /usr/bin/tri-unfilled-*
4       /usr/bin/Magick*-config
14      /usr/bin/tri-*
29      /usr/bin/*y
19      /usr/bin/l*
2       /usr/bin/mate-*-properties
107     /usr/bin/*s
98      /usr/bin/*d
21      /usr/bin/m*
20      /usr/bin/c*
2       /usr/bin/tri-unfilled-userclip*
3       /usr/bin/x86_64-unknown-linux-gnu-*
108     /usr/bin/*l
2       /usr/bin/x86_64-unknown-linux-gnu-gcc-*
24      /usr/bin/i*
23      /usr/bin/g*
142     /usr/bin/*e
300     /usr/bin*
123     /usr/bin/*p
141     /usr/bin/*t
37      /usr/bin/t*
36      /usr/bin/p*
299     /usr/bin/*

Утилита находит наиболее длинные и общие wildcards и выводит количество совпавших строк stdin. (Звёздочек может быть больше одной).

К сожалению, сложность текущего алгоритма растёт пропорционально квадрату строк. Как подобное написать без квадратичной зависимости? Может есть готовая утилита?

К сожалению, сложность текущего алгоритма растёт пропорционально квадрату строк. Как подобное написать без квадратичной зависимости?

Ты бы хоть детали текущего алгоритма привел для начала.

yoghurt ★★★★★ ()
Ответ на: комментарий от Deleted

Да, сейчас ищу через эти них. Проблема в том, чтобы найти вайлдкарды, мне нужно найти LCS для N*N строк, а это очень долго для больших объёмов (22 секунды уже на пятистах строках).

disarmer ★★★ ()
Ответ на: комментарий от yoghurt

Вот код: http://disarmer.ru/ln/?1E

функция s2r - построение общего вайлдкарда для двух строк

Вкратце, читаю весь stdin в массив, потом прохожу по нему в двойном цикле для нахождения общих вайдкардов(отсюда и квадратичная сложность). Записываю найденные общие строки в ассоциативный массив с количеством повторов. Потом сортирую по количеству повторов и длине вайдкарда и вывожу

disarmer ★★★ ()
Ответ на: комментарий от disarmer

На ум приходит введение какой-нибудь метрики на основе расстояния Левенштейна или около того, либо построение radix tree для всех известных строк и анализ его

yoghurt ★★★★★ ()

1) по тобой же приведенной ссылке указана оценка сложности алгоритма.

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

psv1967 ★★★★★ ()
Ответ на: комментарий от psv1967

указана оценка сложности алгоритма.

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

сохранение кеша мемоизированной функции извлечения общей части строк

Проверил, стало дольше(25 секунд против 22). Оно и понятно - ведь в эту функцию передаются неповторяющиеся аргументы

disarmer ★★★ ()
Ответ на: комментарий от disarmer

А такое дерево сможет мне помочь, в чём-то кроме как подсчёте LCS?

Да в нем же все что нужно и будет? Все наиболее длинные подстроки, с количеством вхождений.

Там в статье как-то слишком уж адово изобразили суффиксное дерево, вот здесь http://en.wikipedia.org/wiki/Suffix_tree все нормально описано.

Суффиксные деревья легко программировать, идеи очень простые. Единственная неприятность - они требуют неприлично много памяти. Можно получить дерево порядка на 2 объемнее, чем исходные данные. Ну, если данных сотни килобайт, нормально.

Deleted ()
Ответ на: комментарий от Deleted

Да, подстроки из дерева можно извлечь, я легко смогу найти количество упоминаний например /usr/bin/t*, но как найти вайлдкарды с звёздочкой в середине, вроде /usr/bin/*-config?

Данных обычно немного, до десятка тысяч строк, в крайнем этого хватит для репрезентативной выборки. Ну и tradeoff в сторону памяти выгоднее, время выполнения важнее.

disarmer ★★★ ()
Ответ на: комментарий от Bell

Пока не вижу как применить к этой задаче, разве что учитывать связи между подстроками, но тут надо экспериментировать.

А в machine learning нет никаких готовых утилит для поиска закономерностей в тексте такого типа?

disarmer ★★★ ()
Ответ на: комментарий от disarmer

ML это немного другая область. У тебя именно Data mining. Я этим не занимался, посоветовать готовое решение не могу. Но задача типичная, поэтому можно искать так:
frequent Pattern Mining in Web Log Data
frequent pattern mining text/strings
sequential pattern mining

Вот что-то попалось:
http://www.philippe-fournier-viger.com/spmf/
http://stackoverflow.com/questions/19775978/fuzzy-pattern-search-in-a-string-...

Bell ()
Ответ на: комментарий от disarmer

как найти вайлдкарды с звёздочкой в середине, вроде /usr/bin/*-config?

Да, для такого, наверное, суффиксные деревья не помогут.

Тогда более правильная ссылка - http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

А какая конечная цель этого? Что нужно получить?

Я из любопытства сделал руками поиск наибольшей общей подпоследовательности и прогнал так же как и ты попарно названия файлов из /usr/bin/:

$ find /usr/bin/ | wc -l
1703
$ time find /usr/bin/ | ./a.out >/dev/null

real	0m3.720s
user	0m3.720s
sys	0m0.004s

То есть если пооптимизировать, можно, наверное и десятки тысяч строк обрабатывать за секунды

Вот код (на С++): https://gist.github.com/vmxdev/a795aa4a9b6d60896b9d/ , там главное это функция wildcard, пытается найти в двух строках максимально похожее и сгенерировать из этого шаблон со звездочками

Deleted ()
Ответ на: комментарий от Deleted

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

Longest_common_subsequence_problem

Я посмотрел внутрь модуля, оказывается мой алгоритм как раз последовательности ищет, а не подстроки

А какая конечная цель этого? Что нужно получить?

Попытаться получить наиболее частовстречающиеся шаблоны строк для первичного анализа. Например для анализа более-менее однообразных логов или списков файлов. Отфильтровать незначимые(вроде /usr/bin/*r*e*) можно по длине шаблона

В идеале хочется получить что-то вроде такого, на примере лога nginx:

150   2014/12/* [error] 19460#0: * open() "/*" failed (2: No such file or directory), client: *, server: , request: "HEAD /* HTTP/1.1", host: "disarmer.ru"
40   2014/12/01 [error] 19460#0: * open() "/*" failed (2: No such file or directory), client: *, server: , request: "HEAD /* HTTP/1.1", host: "disarmer.ru"
20    2014/12/* [error] 19460#0: * connect() failed (111: Connection refused) while connecting to upstream, client: *, server: disarmer.ru, request: "GET /* HTTP/1.1", upstream: "http://*",

Один взгляд на результат такого фильтра избавит от десятков выполнения grep

disarmer ★★★ ()
Ответ на: комментарий от disarmer

для анализа более-менее однообразных логов или списков файлов. Отфильтровать незначимые(вроде /usr/bin/*r*e*) можно по длине шаблона

А-а. Ну, возможно я неправильно понимаю задачу, но попарным сравнением особо много не увидишь?

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

Deleted ()
Ответ на: комментарий от Deleted

Да, мне кажется настраивать вывод в одну или другую сторону можно неким коэффициентом сортировки, увеличивающим вес длины строки:

15*length($a)+$pats{$a}
То есть, увеличив этот коэффициент, получим в выводе больший шанс на длинные шаблоны, уменьшив - более частые. Вот тут видно (добавил этот коэффициент в аргументы): http://disarmer.ru/ln/?2P

disarmer ★★★ ()
Ответ на: комментарий от disarmer

Это не совсем то, конечно, но достаточно близко и без изменения алгоритма

disarmer ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.