Как стать автором
Обновить

Новая библиотека для уменьшения размерности данных ITMO_FS — зачем она нужна и как устроена

Время на прочтение 4 мин
Количество просмотров 8.7K
Всего голосов 23: ↑22 и ↓1 +21
Комментарии 8

Комментарии 8

Я бы на вашем месте подумал над сменой названия.

UPPER CASE ни разу не способствует популяризации библиотеки… А еще FS больше напоминает File System, а не Feature Selection.

Но все равно круто, удачи вам :)
Студенты и сотрудники лаборатории Машинного обучения Университета ИТМО разработали библиотеку для Python

у которой:


1) Требования pep8 не выполняются;
2) Type annotations отсутствуют;
3) Docstrings отсутствуют.


Не любите вы своих пользователей...


P.S. Код метода fit у класса BestSum в файле https://github.com/ctlab/ITMO_FS/blob/master/ITMO_FS/ensembles/model_based/best_sum.py (точнее, использование параметра feature_names) ввел в ступор.

Согласен. Не очень понятно, как можно звать пользоваться библиотекой, с которой каждый раз надо будет лезть код, вместо простого открытия доки?
Все же Scikit-learn не в пользу ИТМОшной либы. Потому что у scikit-learn первоклассная документация. Что в вебе, что в самой либе.
Это все конечно интересно, но что может предложить библиотека в части алгоритма, по задаче группировки бинарных матриц символов, разной размерности, по степени их похожести?

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

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

Спасибо за ответ!

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

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

Вы правильно заметили, что здесь можно использовать «алгоритм кластеризации (или классификации)», но почему он не может быть основан на «выборе признаков»? Думаю, вполне может. Такими признаками могут быть:

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

Можно придумать и другие признаки, но пока достаточно. Это дает нам естественную кластеризацию или группировку символов по данным параметрам.

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

Таким образом, расстояние Хэмминга мы уже не используем, точнее, используем только нулевое расстояние. Да, это дает нам избыточное количество групп похожих матриц, но мы можем снизить его до приемлемого уровня за счет: а) снижения размерности сжатых матриц (7*7, 6*6, 5*5 или даже 4*4 – выбираем экспериментально) и б) увеличением количества признаков естественной, не пересекающейся кластеризации.

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

Да, все так! Только несколько замечаний:


  1. Среди "выбора признаков" вы приводите примеры не выбора, а построения новых признаков. Алгоритмы из библиотеки как раз выбирают наборы информативных признаков из существующих. В каких случаях это эффективнее, в статье написано (сохраняется семантика). Кажется, что в вашем случае именно выбор признаков не так полезен.
  2. Если у вас в матрицах символы, то мне кажется наиболее эффективно их различать, выделив признаки, которые характеризуют матрицы именно как символы — размеры, положение структурных элементов (линий, углов и т.п). Здесь актуальны не просто алгоритмы выделения признаков общего назначения, а специализированные алгоритмы для изображений.
  3. Эталонная задача для начинающих изучать нейросети — распознавание символов. Т.е. в интернетах куча туториалов и обученных сетей, которые можно воспроизвести за полчаса и получить точность классификации за 90%. И да, первым этапом там в основном снижение размера матрицы до 8х8 или около того, как вы предлагаете.
  4. В любом случае, после сокращения числа признаков вам нужен будет следующий этап — собственно отнесение матрицы к какому-нибудь классу (группировка), и здесь вам тоже придется какой-нибудь алгоритм применять. Классификатор максимального правдоподобия, метод опорных векторов, нейросети, если у вас есть обучающая выборка, или, там, к-средних, если выборки нет.
Ценю ваши подробные замечания!

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

В практическом плане задача решалась следующая. В типовом ролике «Easy French» порядка 6 тысяч кадров, на каждом из них несколько десятков символов, причем в первых строках французский текст, а во вторых – английский. Всего набегало порядка полмиллиона символов на одно видео. Символы разделялись (в т.ч., с помощью криволинейного контура), абсолютно точные дубликаты удалялись, в итоге их оставалось около 30 тысяч. Но в любом латинско подобном алфавите всего несколько десятков символов, со всякими там спецсимволами. Таким образом, на каждый уникальный символ приходится примерно несколько сотен бинарных матриц, разной размерности, их изображающих. Естественно, требуется сократить общее количество уникальных матриц символов до приемлемого количества, которое уже можно будет распознавать вручную.

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

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

Однако буквально сегодня пришли другие мысли, связанные с оптимизацией процесса. А именно:

1. Зачем обрабатывать все кадры с одинаковым текстом, если можно обработать только один кадр?

2. Зачем делать посимвольное распознавание, если можно делать распознавание вручную всего ключевого кадра сразу? Для одного ролика «Easy French» таких кадров порядка сотни, состоящих из двух строк текста.

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

4. Различать бинаризированные текстовые области кадров видео можно по некоторому хэш-коду.

Этот подход сильно упрощает процесс программирования. Сегодня я уже успел попробовать пункт 4 для хэша размерности 8*16, он дает коэффициент дублирования меньше двух. Конкретно, вместо примерно ста ключевых кадров (из 6 тысяч) выдает 185, что приемлемо.

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

А следующее видео можно уже будет распознавать автоматически (при необходимости с ручной корректировкой), на базе полученной информации.

Таким образом, конкретный подход дает конкретный результат. Очень удобно и главное все очевидно и понятно.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий