Прогнозирование формы множества

Материал из MachineLearning.

---

Версия 07:35, 11 июля 2010

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

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

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

Если признаки бинарные то можно выбрать в качестве мета-признака элементарную дизъюнкцию. В данном слуаче можно рассмотреть обучающую выборку как булеву формулу в виде совершенной ДНФ. Искомые мета-признаки, описывающие форму множества точек класса, можно рассмотреть как элементарные дизъюнкции содержащиеся в булевой формуле в виде минимальной КНФ полученной путем преобразования на основе совершенной ДНФ (обучающая выборка). Имея минимальную КНФ можно без труда вычислять вероятность того что заданная точка принадлежит множеству точек класса при условии того что она принадлежит некоторому набору множеств мета-признаков.

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

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

Для случая бинарных признаков был проведен эксперимент распознавания рукописных цифр. Была использована выборка "Optical Recognition of Handwritten Digits Data Set" (E. Alpaydin, C. Kaynak, Department of Computer Engineering, Bogazici University, 80815 Istanbul Turkey). Каждая цифра представляла собой матрицу черно-белых пикселей размером 6*6. Признаками являлись 36 пикселей. Был применен приближенный метод поиска минимальной КНФ по причине высокой ресурсоемкости метода алгебраической минимизации. Полученная точность распознавания не превышала точность существующих методов. Можно предположить что причинами низкой точности являлось недостаточный размер матрицы и недостаточная точность приближенного метода поиска минимальной КНФ.

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