Московский Государственный Университет

имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Кафедра системного программирования

Курсовая работа

Исследование и разработка методов

иерархической классификации с

поддержкой дообучения

выполнил:

Студент 427 группы

Бабаков Александр Валентинович Научный руководитель:

Недумов Ярослав Ростиславович Москва 2013 Оглавление Введение

1 Постановка задачи

2 Обзор существующих решений

2.1 Иерархическая классификация

2.2. Дообучение классификатора

Winnow

Perceptron

Дообучаемый наивный байесовский классификатор (NB)

Дообучаемый K – nearest neighbors (KNN)

Выводы

3 Исследование и построение решения задачи

3.1 Разработка иерархических классификаторов

3.2 Проверка качества иерархических классификаторов

3.3 Результаты

4 Описание практической части

4.2 Общая схема работы

4.3 Общая архитектура системы

Заключение

Список литературы

Введение Задача иерархической классификации состоит в том, чтобы определить принадлежность объекта к одному или нескольким классам в иерархии. Иерархия представляет собой пару (C, ), где C является конечным множеством, содержащим все классы иерархии, а является отношением между классами иерархии *1+. Класс A является более специфичным, чем класс B, если выполнено отношение A B. Иерархия удовлетворяет следующим требованиям[2]:

Единственный “главный” элемент иерархии: !R: ci: ci R Асимметричность ci, cj C, if ci cj then cj not cj.

Антирефлексивность: ci C, ci not ci.

Транзитивность: ci, cj, ck C, ci cj and cj ck imply ci ck.

Иерархии классов часто получаются на основе отношений “IS A” (является) и “PART OF” (является частью). Например, из Волчарка “IS A” Собака, Собака “IS A” Животное Волчарка “IS A” Животное (Транзитивность). А из того, что Волчарка “IS A” собака не следует, что любая собака “IS A” Волчарка”, т.к. существуют, например, другие породы (асимметричность). На основе этих отношений можно построить граф, где дуга из a в b существует только в том случае, если выполнено отношение b a.

Графы, соответствующие иерархии отличаются по типу структуры. Обычно это или дерево, или ациклический ориентированный граф[3].

Рис. 1. Дерево (слева) и ациклический ориентированный граф (справа).

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

Для решения задачи классификации можно построить программный классификатор на основе одного из алгоритмов машинного обучения. При определении принадлежности объекта к классам иерархии (C, ) объект может принадлежать сразу к нескольким классам иерархии в связи с транзитивностью отношения. Иерархические классификаторы, определяющие принадлежность объекта к классу иерархии (т.е. к вершине дерева), различаются тем, насколько глубоко происходит классификация в иерархии[3]:

Ответом классификатора обязательно являются листовые вершины, т.е. вершины, не имеющие потомков (mandatory leaf node prediction).

Ответом классификатора могут являться как внутренние (имеющие потомков), так и листовые вершины (non-mandatory leaf node prediction).

Также существуют различные подходы к организации структуры иерархических классификаторов. Обычно выделяют 3 основных подхода[3]: “плоская” классификация, “локальная” классификация и “глобальная” классификация.

“Плоский” (flat) классификатор Плоский классификатор (рис. 2) является наиболее простым решением для иерархической классификации. Он не использует информацию об иерархии классов и определяет только классы, находящиеся на концевых вершинах дерева иерархии. Определив принадлежность к классу на концевой вершине дерева иерархии, классификатор также относит этот объект ко всем родительским вершинам этого класса, что также называется подходом “снизу-вверх”. Этот подход характеризуется высокой скоростью работы, но не использует информацию об иерархии классов для улучшения эффективности [2].

Рис. 2. “Плоский” подход к классификации.

Локальный классификатор Локальный подход к иерархической классификации (подход “сверху-вниз”) работает следующим образом. Сначала выбирается класс на самом верхнем уровне классификации, далее он использует выбранный класс для классификации на следующем уровне иерархии, и так далее, пока не процесс не остановится (например, пока не выбран листовой класс иерархии).

Существуют различные подходы к созданию локальных классификаторов.

Локальный классификатор для уровня (Local Classifier per Level, LCL) (рис. 3). Этот алгоритм создает классификатор для каждого уровня иерархии.

Рис. 3. Локальный классификатор для каждого уровня.

Локальный классификатор для каждой вершины (Local Classifier per Node, LCN) (рис. 4).

Этот алгоритм создает бинарный классификатор для каждой вершины.

Рис. 4. Локальный классификатор для каждой вершины.

Локальный классификатор для каждой родительской вершины (Local Classifier per Parent Рис. 5. Локальный классификатор для каждой родительской вершины.

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

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

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

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

Принадлежность объекта к классам определяется на основе анализа функции расстояния к Подход, основанный на модификации “плоских классификаторов”. Алгоритмы модернизируются так, чтобы в них учитывалась иерархия классов[4].

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

Иерархическая F-мера Иерархическая F-мера является модификацией F-меры.

где - это множество, состоящее из наиболее специфичных классов, к которым был отнесен тестовый объект i и все их родительские классы, - это множество, состоящее из всех истинных наиболее специфичных классов для тестового объекта i и всех их родительских классов. Суммирование ведется по всем тестовым объектам. hP – иерархическая точность, hR – иерархическая полнота, hF – иерархическая F мера.

Эта оценка учитывает специфику иерархических классификаторов и дает более высокую оценку ответам, совпадающим по некоторым уровням иерархии с правильным ответом, нежели ответам, не имеющих общих родительских вершин с правильным ответом[4].

Дообучение Машинное обучение с дообучением*5, 12] - это процесс машинного обучения, в котором данные приходят постоянно с течением времени. Классификация для каждого нового объекта происходит по следующей схеме:

1. Обучиться на уже имеющихся данных.

2. Классифицировать новый объект.

3. Получить истинное значение.

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

Использование дообучения необходимо в случаях, когда обучающая выборка отсутствует или гипотеза классификации должна постоянно изменяться [5].

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

1 Постановка задачи Задача курсовой работы состоит в следующем:

Исследовать существующие методы иерархической классификации и дообучения.

Построить метод иерархической классификации с дообучением.

Подобрать тестовые данные для оценивания иерархического классификатора.

Разработать иерархический классификатор с дообучением на Java.

Провести тестирование разработанного иерархического классификатора (измерить иерархическую F-меру по мере дообучения иерархического классификатора).

2 Обзор существующих решений В соответствии с поставленной задачей можно выделить два основных направления исследований:

Иерархическая классификация.

Дообучение классификатора.

Рассмотрим подробно каждое из этих направлений.

2.1 Иерархическая классификация В различных областях исследований применяются различные способы иерархической классификации*2+: применяются LCN и LCPN классификаторы (с различными вариантами локальных классификаторов), глобальные классификаторы, а также “плоские” классификаторы.

Качество результата классификации зависит от предметной области и от конкретных наборов данных. Например, в исследовании *14+ сравнивались “плоский”, LCN классификатор, LCPN и глобальный классификаторы, все из них были основаны на HC4.5 классификаторе. В этих экспериментах LCPN был лучшим на одном наборе данных (LCPN 73%, остальные не более 68 %), а глобальный классификатор – на другом (Global 82%, остальные не более 78%). В другом же исследовании *2,15] LCN классификатор показал более высокие результаты, чем LCNP классификатор (LCN 60.1%, LCPN 56%).

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

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

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

В работе Classifying web documents in a hierarchy[6] рассматривается иерархический классификатор с LCPN. В качестве локального классификатора в зависимости от эксперимента используется SVM классификатор или Naive Bayes классификатор. Для каждой вершины, имеющей потомков, создается локальный классификатор. Результаты исследования показали, SVM и “плоский” NB классификатор имеют большую точность (в среднем преимущество приблизительно равно 5%), чем иерархические LCN классификаторы на основе SVM и NB. Однако исследование серьезности ошибок (отклонение по иерархии от верного результата) показало, что иерархические классификаторы допускают менее серьезные ошибки*6+.

В 2007 году Ceci и Malerba исследовали иерархические LCPN классификаторы на основе NB и SVM и также обнаружили, что “плоский” LCPN классификатор имеет немного меньшую точность (потеря в точности достигает 3%), но при этом допускает менее серьезные ошибки при классификации чем “плоские” классификаторы [16].

В 2008 году в статье *17+ Rehab Duwairi и Rania Al-Zubaidi исследовали иерархический локальный классификатор на основе KNN. Иерархический KNN показал более высокую точность (выигрыш в accuracy от 3% до 10% при равном recall) по сравнению с “плоским” KNN.

Исследование производилось на текстовых данных с использованием TF-IDF в качестве метрики близости.

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

2.2. Дообучение классификатора Как уже было указано во введении, при дообучении классификатора происходит изменение гипотезы классификации. Рассмотрим некоторые алгоритмы дообучения.

Winnow Алгоритм winnow[18] – это алгоритм машинного обучения для создания линейного классификатора. Каждый объект представляет собой множество признаков - булевских переменных. Алгоритм содержит неотрицательные веса wi, i {1..n}, каждый из которых первоначально равен 1, веса для каждого признака. Когда классификатор получает объект (x 1, …, xn ), он использует следующее правило для распознавания:

Далее после получение истинного класса объекта (1 или 0) происходит изменение весов:

Если классификация корректна, то без изменений Если объект отнесен к 1, а верный результат 0, то веса, относящиеся к признакам объекта, установленными в 1, устанавливаются равными 0. (В winnow2 веса делятся на alpha.

Если объект отнесен к 1, а верный результат 0, то веса, относящиеся к признакам объекта, установленными в 1, умножаются на alpha.

Perceptron Алгоритм Perceptron[19], также как и Winnow, строит линейный классификатор. В отличие от Winnow, используется аддитивное изменение весов, а не мультипликативное.

Дообучаемый наивный байесовский классификатор (NB) Наивный байесовский классификатор — вероятностный классификатор, основанный на теореме Байеса предположении о статистической независимости случайных величин. В модели наивного байесовского классификатора содержится статистика по каждому признаку, а именно сколько раз объект, у которого признак A был равен, принадлежал к классу C. На основании статистики по всем признакам вычисляется вероятность принадлежности нового объекта к классам. Соответственно, при получении нового объекта с известной классовой принадлежностью необходимо обновить эту статистику.

Дообучаемый K – nearest neighbors (KNN) При использовании классификатора K-Nearest Neighbors(KNN) для нового объекта считается K ближайших “соседей” в обучающей выборке по заданной метрике. Далее определяется объекты какого класса являются большинством среди соседей объекта.

Рис. 6: Изменение решения классификатора KNN(k=3) при дообучении на один объект (синий квадрат).

Соответственно, при получении нового объекта необходимо добавить те данные нового объекта, которые необходимы для вычисления метрики (рис. 6). Этот метод был также применен в исследовании *7+.

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

Так как для поставленной задачи необходимо построить дообучаемый иерархический классификатор, то рассмотренные иерархические классификаторы не применимы без изменений (т.к. необходим механизм дообучения). Как было показано, существуют различные успешные варианты дообучения классификаторов. Алгоритмы winnow и perceptron используют бинарные признаки, что сужает область их применения. Дообучаемые KNN и NB применимы в качестве локальных классификаторов в случае построения иерархических LCN, LCPN классификаторов, а также в случае “плоского” классификатора без каких-либо очевидных ограничений.

3 Исследование и построение решения задачи Исходя из выводов, сделанных в обзоре, будем строить иерархический LCPN и “плоский” классификаторы, основанные на KNN и NB.

Чтобы полностью выполнить условия поставленной задачи, необходимо:

Разработать следующие иерархические классификаторы:

a. LCPN c дообучением на основе KNN b. LCPN c дообучением на основе NB c. “плоский” c дообучением на основе KNN d. “плоский” c дообучением на основе NB Разработать систему тестирования указанных иерархических классификаторов Протестировать построенные классификаторы Рассмотрим подробно каждую подзадачу:

3.1 Разработка иерархических классификаторов LCPN KNN классификатор отличается от LCPN NB классификатора тем, что локальные классификаторы в вершинах иерархии работают по разным алгоритмам машинного Рис. 7 и 8: NB (слева) и KNN (справа) LCPN иерархические классификаторы Каждый объект представляет собой набор численных признаков. Так как наивный байесовский классификатор лучше работает с фиксированным набором значений[13+, то проведем дискретизацию признаков по алгоритму Equal Width Interval Binning*20].

Рассмотрим построение общей части этих иерархических классификаторов.

Модель данных формируется по следующему принципу: классификатор в каждой вершине содержит данные только о классе, соответствующего этой вершине и его дочерних классах. Т.е., согласно рис. 7 локальный классификатор NaveBayes Classifier 2.1 не имеет данных о классах 1.1, 1.1.1-1.1.3. Это позволяет уменьшить влияние других классов при выборе очередного подкласса.

Получается, что каждому локальному классификатору соответствует нелистовой класс иерархии.

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

Обучение новому объекту LCPN иерархического классификатора происходит по следующей схеме:

1. В качестве текущего локального классификатора выбирается корневой локальный классификатор. Имеем объект для обучения: набор значений признаков и список классов, к которым принадлежит объект (от наименее специфичного класса к наиболее специфичному классу).

2. Из списка классов объекта выбирается класс, который является дочерним классом к классу, которому соответствует текущий локальный классификатор. Текущий локальный классификатор запоминает текущий объект как объект, принадлежащий к 3. В качестве текущего локального классификатора выбирается классификатор, соответствующий дочернему классу в иерархии. Если дочернему классу не соответствует классификатор (листовая вершина иерархии), то обучение новому объекту завершается.

Иерархический наивный байесовский классификатор, в отличие от KNN метода, позволяет обеспечить меньший рост размеров базы знаний при дообучении, так как не требует хранения всех объектов, полученных для дообучения. Наивный байесовский классификатор требует лишь набор статистических данных. Для добавления объекта в модель наивного байесовского классификатора необходимо изменить статистику вхождения признаков для класса текущего объекта.

Распознавание очередного объекта происходит по следующей схеме:

1. В качестве текущего локального классификатора выбирается корневой локальный классификатор, в качестве текущего класса – корневой класс.

2. Происходит классификация объекта в локальном классификаторе.

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

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

Существует единственный классификатор, который обучается только на корневых вершинах иерархии (т.е. на рис. 7 это объекты, принадлежащие классам 1.1.1-1.1.3, 1.2.1-1.2.2). Т.е. этот классификатор может отнести объект только к листовым вершинам.

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

3.2 Проверка качества иерархических классификаторов Наборы данных, удовлетворяющие поставленной задаче, были взяты с ресурса hmc_classification[8]. Собранные данные находятся в формате C4.5 и представляют собой набор векторов чисел. Каждый вектор представляет собой объект, который принадлежит к какому-либо элементу иерархии. Эти выборки уже участвовали в некоторых исследованиях иерархических классификаций *9,10].

3.3 Результаты Для исследования качества (иерархической F-меры) было проведено тестирование на трех выборках вышеуказанного ресурса hmc-classification[8]: ImageCLEF07D (рис. 9), ImageCLEF07A (рис.

10), Diatoms (рис. 11). Тестирование алгоритмов классификации происходило следующей схеме:

данные разбивались на обучающую и тестирующую выборки в соотношении 9:1. Далее, происходило обучение/дообучение алгоритма на часть обучающей выборки (10%) и поиск значения иерархической F-меры на тестирующей выборке. Для получения достоверной оценки тестирование проводилось с кросс-валидацией в 10 этапов.

Тестирование проводилось для всех построенных классификаторов.

Рис. 9: Результаты тестирования иерархических классификаторов на ImageCLEF07D Рис. 10: Результаты тестирования иерархических классификаторов на ImageCLEF07A Рис. 11: Результаты тестирования иерархических классификаторов на Diatoms Как видно из результатов, LCPN NB проигрывают FLAT NB. Это можно объяснить тем, что иерархический метод классификации на основе локальных классификаторов обобщает дочерние классы в один класс на этапе классификации локальной вершины. В случае, когда дочерние классы не похожи друг на друга по большинству признаков, это обобщение может привести к тому, что локальный классификатор произведет неверный выбор. Рассмотрим следующий пример.

Пусть имеется иерархия (рис. 11) и пусть объект принадлежит к классу “1”, если признак 1=1 и иначе к классу “2”. Пусть также объект принадлежит к классу 1.1, если он принадлежит к классу 1 и признак 2=1, иначе к классу 1.2. Также, пусть объект принадлежит к классу 2.1,если он принадлежит к классу 2 и признак 2=1, иначе к классу 2.2.

Рис. 11: Пример иерархии Рассмотрим следующую выборку:

Обучим LCPN NB и FLAT NB на объектах 1-4 и протестируем на объекте 5.

LCPN NB классифицирует объект 5 как принадлежащий к классу 1.2, в то время как FLAT NB классифицирует его в класс 2.2. Согласно спецификации выше, объект принадлежит к классу 2.2, следовательно, LCPN NB допускает ошибку там, где FLAT NB производит правильную классификации.

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

Иерархический классификатор на основе LCPN KNN показывает более высокий результат по сравнению с FLAT KNN за счет того, что для определения классовой принадлежности используется K “наиболее похожих” объектов. Следовательно, сильно непохожие классы не влияют на выбор и указанная выше проблема не возникает.

4 Описание практической части Согласно постановке задачи, программное средство было выполнено на языке Java.

Для реализации локальных классификаторов машинного обучения, которые применяются при создании различных иерархических классификаторов, была использована библиотека машинного обучения Java Machine Learning Library (Java-ML) [11+. Это свободное программное обеспечение для машинного обучения.

4.2 Общая схема работы Алгоритм работы программного средства заключается в следующем:

1) Происходит считывание набора данных с последующей дискретизацией.

2) Выполняются пункты 3-6 для каждой итерации кросс-валидации.

3) Набор данных разбивается на 2 части: обучающую выборку и набор данных для тестирования. Разбиение зависит от номера итерации кросс-валидации.

4) Набор данных для обучения также разбивается на несколько равных частей.

5) Происходит обучение иерархического классификатора. Классификатор последовательно дообучается на каждой части обучающей выборки. После каждого дообучения происходит тестирование качества (поиск иерархической F-меры) на наборе данных для тестирования 6) Получаем набор иерархических F-мер, каждое значение из набора соответствует конкретному этапу дообучения иерархического классификатора, построенного на текущей итерации кросс-валидации.

7) Вычисляем усредненные значения иерархической F-меры на каждом этапе дообучения для иерархического классификатора.

Диаграмма на рисунке 12 демонстрирует общую схему работы разработанного программного средства Рис. 12: Общая схема работы системы тестирования 4.3 Общая архитектура системы Интерфейс AbstractClassifierFactory - абстрактная фабрика классификаторов. Используется в иерархическом классификаторе при создании локальных классификаторов.

Класс NaiveBayesClassifierFactory – реализация интерфейса AbstractClassifierFactory. Фабрика, возвращающая в качестве классификатора наивный байесовский классификатор.

Класс KNearestNeighborsClassifierFactory - реализация интерфейса AbstractClassifierFactory.

Фабрика, возвращающая в качестве классификатора KNearestNeighbors классификатор.

Класс CrossvalidationDataset – класс, содержащий данные для тестирования и обучения.

Возвращает по запросу методу getTrainingInstances(Integer) набор данных для обучения для текущей итерации кроссвалидациии, по запросу getTestingInstances(Integer) набор данных для тестирования для текущей итерации кроссвалидациии. Discretize() осуществляет дискретизацию признаков, mixInstances() производит псевдослучайное перемешивание набора данных.

Класс HierarchicalFMeasureComputer – класс, вычисляющий значение иерархической F-меры по данному результату и истинному ответу.

Класс TestingProcessor – управляющий класс, который осуществляет тестирование, строя на основе данных из CrossvalidationDataset иерархический классификатор HierarchicalClassifierPerParentNode и проводит тестирование с помощью HierarchicalFMeasureComputer.

Рис. 13: Общая архитектура системы Заключение В ходе курсовой работы были исследованы существующие подходы к иерархической классификации, локальный, глобальный и “плоский. Также были исследованы методы дообучения классификаторов, такие как winnow (winnow2), perceptron, дообучение классификатора на основе метода K ближайших соседей (KNN) и наивного байесовского классификатора NB.

Были реализованы локальные иерархические классификаторы с поддержкой дообучения на основе классификаторов KNN и NB, а так же “плоские” иерархические классификаторы на основе KNN и NB.

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

Иерархические классификаторы на основе KNN имеет более высокие показатели иерархической F-меры, чем иерархические классификаторы на основе NB.

“Плоский” иерархический классификатор на основе NB показывает более высокие результаты, чем локальный иерархический классификатор на основе NB.

“Плоский” иерархический классификатор на основе KNN показывает менее высокие результаты, чем локальный иерархический классификатор на основе KNN.

В среднем процесс дообучения ведет к повышению иерархической F-меры для всех построенных классификаторов.

Список литературы 1. Wu F, Zhang J, Honavar V (2005) Learning classifiers using hierarchically structured class taxonomies.

2. Carlos N. Silla Jr. · Alex A. Freitas (2010) A survey of hierarchical classification across differentapplication domains.

3. Freitas AA, de Carvalho ACPLF (2007) Research and trends in data mining technologies and applications: tutorial on hierarchical classification with applications in bioinformatics.

4. Kiritchenko S, Matwin S, Famili AF (2005) Functional annotation of genes using hierarchical text categorization.

5. Nicol Cesa-Bianchi GborLugosi (2006) Prediction, learning, and games.

6. Michelangelo Ceci, Donato Malerba (2007) Classifying web documents in a hierarchy of categories.

7. Sotiris Kotsiantis (2013) Increasing the accuracy of incremental naive bayes classifier using instance based learning.

http://kt.ijs.si/DragiKocev/PhD/resources/doku.php 9. Ivica Dimitrovski, Dragi Kocev, Suzana Lokovska, Sao Deroski (2008) Hierarchical annotation of medical images.

10. Ivica Dimitrovski, Dragi Kocev, Suzana Lokovska, Sao Deroski (2011) Hierarchical Classification of Diatom Images using Predictive Clustering Trees.

11. Java Machine Learning Library (Java-ML) (2012) http://java-ml.sourceforge.net/ 12. Avrim Blum (2010) Online Algorithm in Machine Learning 13. Jonathan L. Lustgarten (2008) Improving Classification Performance with Discretization on Biomedical Datasets 14. Costa E, Lorena A, Carvalho A, Freitas AA, Holden N (2007b) Comparing several approaches for hierarchical classification of proteins with decision trees.

15. DeCoro C, Barutcuoglu Z, Fiebrink R (2007) Bayesian aggregation for hierarchical genre classification.

16. Ceci M, Malerba D (2007) Classifying web documents in a hierarchy of categories: a comprehensive study.

17. Rehab Duwairi и Rania Al-Zubaidi(2008) A Hierarchical K-NN Classifier for Textual Data.

18. Nick Littlestone (1989) Mistake bounds and logarithmic linear-threshold learning algorithms 19. Gallant, S. I. (1990) Perceptron-based learning algorithms.

20. James Doughherty, Ron Kohavi, Mehran Sahami (1995) Supervised and Unsupervised Discretization of Continious Features.

21. Labrou Y, Finin T (1999) Yahoo! as an ontology—using yahoo! categories to describe documents.