Введение

Привет, я Игорь Буянов, работаю в MTS AI старшим разработчиком в департаменте машинного обучения в команде разметки и сбора данных.

В этом руководстве я покажу, как на основе Википедии можно сделать текстовый датасет, метки которого будут иметь иерархию. Необходимость в таком датасете возникла при тестировании различных подходов к эксплуатации иерархичности меток [3]. Иерархией меток могут представлены интенты, которые распознает чат-бот при запросе пользователя: является ли обращение пользователя заявлением о проблем с медленным интернетом или тем, что он вообще отсутствует. Общим классом здесь будет интернет, а подклассом будет скорость и отсутствие интернета, соответственно. Материалы доступны на нашем гитхабе.

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

Подготовка

Для работы необходимо скачать дампы Википедии по этой ссылкe

• ruwiki-latest-category.sql.gz

• ruwiki-latest-categorylinks.sql.gz

• ruwiki-latest-page.sql.gz

• ruwiki-latest-pages-articles.xml.bz2

Дампы баз данных необходимо импортировать в локальную СУБД. Далее я покажу действия для MySQL, которая легко устанавливается на Ubuntu 16.04 (18.04) с помощью команды:

sudo apt-get install mysql-server

Для входа в консоль необходимо выполнить команду:

mysql -u root -p

Имя пользователя и пароль задается во время установки. Если этого не произошло, тогда следует ввести следующие команды

$ sudo service mysql stop
$ sudo mysqld_safe --skip-grant-tables
$ mysql -u root
mysql> UPDATE mysql.user SET Password=PASSWORD('password') WHERE User='root';
mysql> use mysql; 
mysql> update user set authentication_string=password('password') where user='root'; 
sudo mysql start

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

mysql> create database db_name;
mysql> use db_name;
mysql> SET autocommit=0 ; source the_sql_file.sql ; COMMIT ;

Импорт БД может занять продолжительное время, вплоть до суток. 

Также необходимо извлечь сами страницы из архива ruwiki-latest-pages-articles.xml. Сделать это можно при помощи WikiExtractor.py. Для его запуска нужно выполнить следующие команды

$ mkdir wiki_categories
$ python WikiExtractor.py --output wiki_categories ruwiki-latest-pages-articles.xml

Это процесс может занять до часа.

Основная часть

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

select page_title, cl_to from categorylinks.categorylinks join page.page on cl_from = page_id  where page_title in (select cat_title from category) INTO outfile '/var/lib/mysql-files/category.csv' FIELDS terminated by '|' enclosed by '"' lines terminated by '\n';

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

select cat_title, cat_pages-cat_subcats-cat_files as num_pages FROM  category.category INTO outfile '/var/lib/mysql-files/num_pages_per_category.csv' FIELDS terminated by ';' enclosed by '"' lines terminated by '\n';

Полученные файлы num_pages_per_category.csv и category.csv необходимо будет указать в ноутбуке category_investigation.ipynb и выполнить его, следуя подсказкам в комментариях. Файлы лучше перенести туда, где этот ноутбук и лежит. 

$ sudo su
$ mv /var/lib/mysql-files/category.csv /home/ibuyanov//wikipedia_dataset/
$ mv /var/lib/mysql-files/num_pages_per_category.csv /home/ibuyanov/wikipedia_dataset/

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

После получения начального подграфа, мы раскрываем циклы, эвристически удаляя последнее ребро в цикле. Затем мы применяем транзитивное сокращение [1] в результате которого будут выброшены все лишние ребра. Оно не гарантирует нам создание дерева, но упрощает граф, убирая избыточные связи. В случае, если граф остается слабо связным, то мы собираем все вершины, в которые не входит ни одно ребро, и объединяем их с помощью вершины, которое становится искусственным корнем будущего дерева. 

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

• связность - все вершины должны иметь ребро. Честно украл из статьи [2]

• окно количества статей - суммарное количество статей должно быть не больше N, и не меньше M (по дефолту, M=1)

• окно количества вершин в дереве - вершин может быть не больше N статей, и не меньше M

• единственность предка - каждая вершина должна иметь только одного родителя

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

Наконец, можно посмотреть на то, как наше дерево выглядит.

Если вам не нравятся одиночные вершины на уровне, вы можете также их удалить, используя индекс. У меня получился вот такой конечный вариант.

Распределение количества статей выглядит так

В итоге, у нас получатся два файла. В первом содержатся метки классов с иерархией в формате суперкласс/подкласс/подкласс_подкласса (по умолчанию categoryies_classes.txt), во втором файле —  все категории, которые были выбраны (по умолчанию categoryies.txt).

Далее необходимо все полученные категории импортировать в mysql. Сделать это можно следующими командами, предварительно переместив файл с категориями в /var/lib/mysql-files

$ mv categoryies.txt /var/lib/mysql-files/
create database chosen;
create table chosen.chosen_cat(cat varbinary(255));
LOAD DATA INFILE '/var/lib/mysql-files/categoryies.txt'  INTO TABLE chosen.chosen_cat CHARACTER SET UTF8 FIELDS TERMINATED BY ','  ENCLOSED BY '' LINES TERMINATED BY '\n';

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

select * from chosen.chosen_cat limit 10;

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

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

mysql > select page_title from categorylinks.categorylinks join page.page on cl_from = page_id  where cl_to in (select * from chosen.chosen_cat) and cl_type = "page" INTO outfile '/var/lib/mysql-files/titles.csv' FIELDS terminated by '|' enclosed by '"' lines terminated by '\n';
mysql > exit;
$ mv /var/lib/mysql-files/titles.csv /home/ibuyanov/wikipedia_dataset/
$ mv /var/lib/mysql-files/categoryies.txt /home/ibuyanov/wikipedia_dataset/

После этого необходимо выполнить ноутбук extract_text_with_categories.ipynb, суть которого заключается в экстракции статей по отобранными нами категориям, с последующим форматированием и сохранением датасета в виде csv.

Датасет, который получился у меня, содержит 61 метку и 2031 записей. Ниже представлено распределение количества статей по меткам.

Ниже представлено, как выглядит датасет

Заключение

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

Надеюсь, данное руководство поможет вам в своих проектах или вдохновит на создание своего метода - здесь есть, что улучшать.

Ссылки

[1] https://ru.wikipedia.org/wiki/Транзитивное_сокращение

[2] Filippova and Strube, Dependency Tree Based Sentence Compression

[3] Jia Deng et al., Large-Scale Object Classification using Label Relation Graphs