Программа для иерархической классификации веб-сайтов

Хорошей альтернативой сериализации в данном случае служит технология HDF5, которая представляет собой файловый формат и стек технологий для хранения и работы с разного рода коллекциями. HDF5 может поддерживать крупные файлы (больше 2 ГБ), имеет поддержку параллельного ввода/вывода, может содержать сложные структуры данных. Еще одним плюсом использования HDF5 является возможность открытия файлов в формате, удобном для чтения человеком.

Таким образом, сохранение результатов обучения в локальных файлах осуществляется с помощью HDF5. Для использования этой технологии необходимо установить библиотеку pytables, однако использовать ее в коде напрямую необязательно - сохранять данные и читать файл формата HDF5 можно с помощью библиотеки pandas. Для сохранения таблицы коэффициентов одного классификатора достаточно выполнить следующий код:

store = pd.HDFStore(filename) counter = 0 for row in clf.coef_: store['row' + str(counter)] = pd.DataFrame(row) counter += 1 store.close()

Отметим, что матрица коэффициентов coef_ классификатора clf хранится в формате numpy.array, однако для записи данных в файл HDF5 необходимо конвертировать данные в формат pandas.DataFrame. Аналогичным образом сохраняется массив intercept_, содержащие коэффициенты классов или константы для решающего правила (в зависимости от типа классификатора).

Следующий код загружает коэффициенты в классификатор:

# загружаем матрицу коэффициентов store = pd.HDFStore(filename) # конвертируем в numpy.array coefs = np.array([np.array(store['row' + str(i)]).T[0] for i in range(len(store) - 1])) store.close() # добавляем коэффициенты в классификатор clf.coef_ = coefs

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



6. Эксперименты

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

6.1 Экспериментальные данные

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

Для объединения необходимых данных из Яндекс.Каталога в единый структурированный документ был написан парсер, который по каждому сайту из каталога собирает информацию в следующем формате:

<имя_категории_верхнего_уровня>/<имя_подкатегории>/…/<имя_категории_сайта>;<URL адрес сайта>

Собранная выборка состоит из 160 тысяч ссылок на сайты с соответствующей им информацией о тематической классификации (представленной полным путем к категории). В выборке насчитывается 1993 уникальные категории. Категорий самого верхнего уровня (корневых категорий) в каталоге шестнадцать: "Hi-Tech", "Работа", "Учёба", "Дом", "Общество", "Развлечения", "Отдых", "Культура", "Спорт", "СМИ", "Бизнес", "Справки", "Авто", "Порталы" и "Универсальное". Распределение элементов по корневым категориям можно видеть на рис. 2.

Рисунок 2 - Распределение элементов по корневым категориям

Концевых категорий в построенном по собранной выборке дереве иерархии насчитывается 201. Глубина дерева иерархии равна девяти. Среднее количество прямых потомков у категории составляет приблизительно 4,5. Наиболее крупной категорией в выборке является категория "Универсальное", содержащая 1000 элементов. При этом 281 категория в выборке содержит только один элемент. Распределение элементов по всем категориям представлено на рис. 2.

Рисунок 3 - Распределение элементов по категориям в Яндекс.Каталоге



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

6.2 Оптимизация гиперпараметров модели

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

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

Оптимальные значения гиперпараметров, определенные в ходе жадного поиска приведены в таблице 2.

Таблица 2 - Оптимальные значения гиперпараметров модели

Алгоритм	Имя параметра	Оптимальное значение
Формирование признаков	максимально допустимая частота встречи терма в документах (в процентах от общего числа документов)	0.75
Формирование признаков	минимально допустимая частота терма	1
Формирование признаков	проводить ли бинаризацию признаков	False
Формирование признаков	метод нормализации	l2
Формирование признаков	метод сглаживания	сглаживание Лапласа
Формирование признаков	диапазон n-gram	(1,3)
SVM	размер штрафа	0.0005
SVM	метод регуляризации	l2
Лес решающих деревьев	количество деревьев	не ограничено
Лес решающих деревьев	критерий информативности	энтропия
Лес решающих деревьев	максимальная глубина дерева	не ограничена

6.3 Результаты экспериментов

Для оценивания качества работы модели и отдельных ее составляющих был проведен ряд экспериментов.

Оценки работы отдельных моделей и их объединения в один ансамбль находятся в таблице 3.

Таблица 3

Модель	Макро точность	Макро полнота	Макро Ф-мера
Плоский SVM	0.64	0.59	0.61
Плоский лес решающих деревьев	0.66	0.64	0.65
Поэтапный SVM	0.68	0.69	0.68
Объединенный ансамбль	0.75	0.76	0.75



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

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

Также отметим, что плоский лес решающих деревьев показал себя лучше плоского классификатора с использованием алгоритма опорных векторов по схеме «один-против-всех». В данном случае ключевую роль сыграло использование техники бэггинга для построения леса решающих деревьев. Это позволило снизить риск переобучения и сделать модель более устойчивое к шумовым объектам в выборке. Для успешного обучения леса решающих деревьев также необходима достаточно большая обучающая выборка, которая была собрана в ходе этой работы. Вполне вероятно, что на выборке меньшего объема лес решающих деревьев показал бы результаты худшие, чем плоский классификатор на основе SVM.

В таблице 4 приведены результаты классификации элементов относящихся к различным корневым категориям. Значения метрик вычислены отдельно для элементов каждой корневой категории.

Таблица 4

Корневая категория	Макро точность	Макро полнота	Макро Ф-мера
Бизнес	0.78	0.73	0.75
Дом	0.66	0.62	0.63
Культура	0.53	0.61	0.56
Hi-tech	0.62	0.78	0.69
Учеба	0.74	0.63	0.69
Отдых	0.71	0.52	0.6
Спорт	0.71	0.88	0.78
Авто	0.52	0.79	0.62
Общество	0.68	0.57	0.62
Развлечения	0.76	0.79	0.77
Справки	0.52	0.58	0.54
СМИ	0.46	0,54	0.5
Работа	0,75	0,78	0.76
Универсальное	0.21	0.34	0.26
Порталы	0.42	0.36	0,39

Наибольшее число ошибок наблюдается в категориях «Универсальное» и «Порталы». После анализа выборки было установлено, что тематики данных категорий в достаточно сильной степени пересекаются. Так, в обеих категориях присутствует значительное количество информационных порталов, в особенности порталов городов или других географических объектов. Другие элементы категории «Универсальное» достаточно разнородны по составу: часть из них являются разного рода новостными ресурсами, часть посвящена географическим объектам или географии в целом. Также в этой категории содержатся блоги, форумы, площадки для объявлений (например, avito.ru). Все эти факторы делают классификации данной категории затруднительной, а также вызывают ошибки при классификации элементов других категорий (которые иногда могут быть ошибочно отнесены к «Универсальным»).

Дальнейший анализ ошибок классификации показал, что многие из них были вызваны схожестью состава категорий «Спорт» и «СМИ» - в обеих категориях присутствует достаточно большое количество сайтов посвященных спортивной тематике, что вылилось в схожие признаковые описания объектов этих категорий и их подкатегорий.



Заключение

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

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

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

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

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



Список использованных источников

1. Onan A. Classifier and feature set ensembles for web page classification // Journal of Information Science, 2015.

2. Sebastiani F. Machine learning in automated text categorization // CSUR, Vol. 34, No. 1, 2002. pp. 1-47.

3. Qi X., Davison. Web page classification // CSUR, Vol. 41, No. 2, 2009. pp. 1-31.

4. An W., Liu Q. Hierarchical Text Classification Based on LDA and Domain Ontology // AMM, Vol. 411-414, 2013. pp. 1112-1116.

5. Chen X., Chen J. Class Hierarchical Structure-Based Text Classification // AMR, Vol. 255-260, 2011. pp. 2233-2237.

6. Mladenic D. Turning Yahoo into an automatic web-page classifier // Proceedings of the European Conference on Artificial Intelligence (ECAI). 1998. pp. 473-474.

7. Xin J., Rongyan L., Xian S., Rongfang B. Automatic Web Pages Categorization with ReliefF and Hidden Naive Bayes // DBLP.

8. Aizawa A. An information-theoretic perspective of tf-idf measures // Information Pro-cessing & Management, Vol. 39, 2003. pp. 45-65.

9. Chakrabarti S. Mining the Web : Discovering Knowledge from Hypertext Data // MorganKaufmann Publishers, 2003.

10. Rahmani A., Meshkizadeh S. Webpage Classification based on Compound of Using HTML Features & URL Features and Features of Sibling Pages.

11. Yahoo [Электронный ресурс] // Yahoo: [сайт]. URL: http://yahoo.com (дата обращения: 16.Апрель.2016).

12. Chen H., Dumais S. Hierarchical classification of Web content // in Proc. of the 23rd ACM Int. Conf. on Research and Development in Information Retrieval. Athens. 2000. pp. 256-263.

13. He Y., Wang K., Zhou S. Hierarchical classification of real life documents // Proc. of the 1st SIAM Int. Conf. on Data Mining. Chicago. 2001.

14. Sasaki M., Kita K. Rule-based text categorization using hierarchical categories // In Proc. of the IEEE Int. Conf. on Systems, Man, and Cybernetics. La Jolla. 1998. pp. 2827-2830.

15. Яндекс.Каталог [Электронный ресурс] // Яндекс.Каталог: [сайт]. URL: https://yandex.ru/yaca/

16. Яндекс.Каталог: habrahabr.ru [Электронный ресурс] // Яндекс.Каталог: [сайт]. URL: https://yandex.ru/yaca/?text=habrahabr.ru

17. Sun A., Lim E., Ng W. Performance measurement framework for hierarchical text classification // J. Am. Soc. Inf. Sci., Vol. 54, No. 11, 2003. pp. 1014-1028.

18. D'Alessio S., Murray K., Schiaffino R., Kershenbaum A. The effect of using hierarchical classifiers in text categorization // In Proc. of the 6th Int. Conf. “Recherche d'Information Assistee par Ordinateur”. Paris. 2000. pp. 302-313.

19. Koller D., Sahami M. Hierarchically classifying documents using very few words // In Proc. of the 14th Int. Conf. on Machine Learning. 1997.

20. Slattery S., Ghan R., Yang Y. Hypertext categorization using hyperlink patterns and meta data // ICML 01: Proceedings of the Eighteenth International Conference on Machine Learning. 2001. pp. 178-185.

21. Lee M., Oh H., Myaeng S. A practical hypertext categorization method using links and incrementally available class information // Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2000. pp. 264-271.

22. Porter M. An algorithm for suffix stripping // Morgan Kaufmann Publishers, 1997. pp. 313-316.

23. Russian stemming algorithm [Электронный ресурс] // Snowball: [сайт]. URL: http://snowball.tartarus.org/algorithms/russian/stemmer.html

24. Mitchell T. Machine Learning. McGraw-Hill Science/Engineering/Math, 1997.

25. Corinna Cortes V.V. Support-Vector Networks // Machine Learning, No. 20, 1995. pp. 273-297.

26. Data Analysis (Software Engineering) [Электронный ресурс] // Учебные курсы факультета компьютерных наук: [сайт]. URL: http://wiki.cs.hse.ru/Интеллектуальный_анализ_данных_(программная_инженерия) (дата обращения: 1.Апрель.2016).

27. Quinlan R. Induction of Decision Trees // Machine Learning, Vol. 1, 1985. pp. 81-106.

28. Профессиональный информационно-аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных [Электронный ресурс] // MachineLearning.ru: [сайт]. URL: http://www.machinelearning.ru/ (дата обращения: 1.Апрель.2016).

29. Powers D. Evaluation: From Precision, Recall and F-Measure to ROC, Informedness, Markedness & Correlation // Journal of Machine Learning Technologies, Vol. 1, No. 2, 2011. pp. 37-63.

30. Asch V.V. Macro- and micro-averaged evaluation measures, September 2013.

31. Справочное руководство по MySQL [Электронный ресурс] // MySQL.RU: [сайт]. URL: http:/www.mysql.ru/docs/man/Standards.html (дата обращения: 10.май.2016).

32. Известные ошибки и недостатки проектирования в MySQL [Электронный ресурс] // MySQL.ru: [сайт]. URL: http:/www.mysql.ru/docs/man/Bugs.html (дата обращения: 10.май.2016).

33. mysql-python.sourceforge.net [Электронный ресурс] // sourceforge.net: [сайт]. URL: http:mysql-python.sourceforge.net/MySQLdb.html (дата обращения: 10.май.2016).

34. Python Data Analysis Library [Электронный ресурс] // pandas.pydata.org: [сайт]. URL: http:/pandas.pydata.org (дата обращения: 10.май.2016).

35. Powers D.M.W. Proceedings of the Joint Conferences on New Methods in Language Processing and Computational Natural Language Learning // Applications and explanations of Zipf's law. 1998. pp. 151-160.

36. Aydin Buluз J.T.F.M.F.J.R.G.C.E.L. SPAA '09 Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures // Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. 2009. pp. 233-244.

37. Seungbeom Kim J.P. 19th International Unicode Conference // Automatic Detection of Character Encoding and Language. San Jose. 2001.

Размещено на Allbest.ru