 |
Алгоритм, основанный на метрике Хэмминга
|
|
|
|
Дерево решений – это по сути алгоритм, представленный в специальной форме. Рассмотрим алгоритм, который строит бинарное дерево на основании поиска существенного (разделяющего) значения некоторого признака. Каждой вершине дерева приписывается вопрос " Обладает ли пример данным значением признака? ", а дуги взвешиваются ответами (Да, Нет). Конечные (висячие) вершины дерева будут помечены утверждениями, соответствующими решениям.
Распознавание начинается с корневой вершины, откуда строится путь до конечной (висячей) вершины. В каждом внутреннем узле необходимо отвечать на вопрос и выбирать соответствующую дугу, ведущую к следующему вопросу. Заметим, что вершины с одинаковыми вопросами могут встречаться несколько раз в разных местах дерева, но в каждом конкретном пути от корня к " листу" каждый вопрос встретится только один раз.
Рассмотрим рекурсивный алгоритм построения бинарного дерева на основе обучающей выборки S (далее будем называть этот алгоритм АМХ - " Алгоритм, основанный на метрике Хемминга" ).
Для предъявленной обучающей выборки S ищется наиболее важный вопрос, который помещается в корневую вершину дерева. Например, при решении задачи выбора меню для обеда, в корневую вершину разумно поместить вопрос, является ли клиент вегетарианцем. Обучающее множество S в соответствии с ответами ДА, НЕТ разделяется на две подвыборки. Далее для каждой подвыборки снова ищется наиболее важный вопрос и порождаются две новые ветви. Процесс завершается, когда использованы все вопросы.
Для нахождения наиболее важного вопроса используется следующий подход. Предположим, обучающее множество S содержит К примеров. Построим метрику на множестве вопросов и упорядочим S по следующему правилу. Для каждого вопроса Q строится К-арный кортеж, где j –е значение в кортеже имеет значение
|
|
|
ì 1, если j-й пример из S дает ответ ДА на вопрос Q,
j= í
î 0 в противном случае.
Расстояние между двумя вопросами определяется как расстояние между двумя двоичными векторами по Хеммингу. Обозначим такое расстояние между векторами X и Y как Hd(X, Y). При этом из рассмотрения исключаются вопросы, на которые все примеры из S дают одинаковый ответ (все 0 или все 1).
Для искомого свойства Р и множества объектов S строится кортеж длины К по правилу: j-e значение в кортеже Р равно 1, если j-й пример из S обладает искомым свойством Р; j-e значение в кортеже Р равно 0, если j-й пример из S этим свойством не обладает. Чтобы выбрать наиболее важный вопрос, ищем среди всех подходящих вопросов Q такой, чья связь с Р наиболее тесная. Для этого воспользуемся правилом: ищем pm=min{Hd(P, Q), K-Hd(P, Q)},
то есть берем наименьшее расстояние по Хеммингу от Q до P и от Q до Ø P (pm далее называем псевдометрикой).
Когда наиболее важный вопрос выбран, выполняется расщепление обучающего множества на Sда и Sнет, затем для каждого подмножества выполняются аналогичные вычисления.
Рассмотрим пример построения дерева решений для анализа поведения Лондонского фондового рынка. Пусть главные факторы, влияющие на фондовый рынок, это
- состояние на вчерашний день;
- состояние фондового рынка в Нью-Йорке;
- банковские тарифы (ставки);
- процент безработицы;
- перспективы для Англии.
В таблице 3 приведено обучающее множество из шести примеров.
Т а б л и ц а 3
| Hd | pm | |||||||
| Наблюдается ли сегодня рост на фондовом рынке? | да | да | да | нет | нет | нет | ||
| Наблюдался ли рост вчера? | да | да | нет | да | нет | нет | ||
| Наблюдается ли сегодня рост в Нью-Йорке? | да | нет | нет | нет | нет | нет | ||
| Растут ли банковские ставки? | нет | да | нет | да | нет | да | ||
| Безработица растет? | нет | да | да | нет | нет | нет | ||
| Несет ли Англия убытки? | да | да | да | да | да | да |
|
|
|
Пусть наша цель – построить дерево, определяющее, наблюдается ли рост на Лондонском фондовом рынке. Искомое свойство " Сегодня наблюдается рост". Строим расстояние по Хеммингу (Hd) между этим свойством и каждым атрибутом. Так, для атрибута " Банковские ставки растут" расстояние по Хеммингу Hd(1 1 1 0 0 0, 0 1 0 1 0 1)=4 (значения различны в 4-х позициях). Тогда Hd=4, K-Hd=6-4=2, min(4, 2)=2. Cледовательно,
pm(" Сегодня наблюдается рост", " Банковские ставки растут" )=2.
Поскольку критерием выбора является минимальное значение pm, выбираем наиболее важный вопрос " Безработица растет? ". Проведем расщепление S: Sда включает примеры 2 и 3. В дереве эта вершина будет конечной (для всех примеров множества наблюдается рост на фондовом рынке). Sнет содержит примеры 1, 4, 5, 6. Результаты повторных вычислений приведены ниже в таблице 4.
Т а б л и ц а 4
| Hd | pm | |||||
| Наблюдается ли сегодня рост на фондовом рынке? | да | нет | нет | нет | ||
| Наблюдался ли рост вчера? | да | да | нет | нет | ||
| Наблюдается ли сегодня рост в Нью-Йорке? | да | нет | нет | нет | ||
| Растут ли банковские ставки? | нет | да | нет | да | ||
| Безработица растет? | нет | нет | нет | нет | ||
| Несет ли Англия убытки? | да | да | да | да |
Из результата видно, что, когда безработица не растет, Лондонский фондовый рынок в точности следует за Нью-Йоркским. Приведем ниже окончательное дерево решений (рис. 4. 7).
| Безработица растет? |
да нет
| Рост на Лондонском фондовом рынке |
| Есть рост на фондовом рынке Нью-Йорка? |
да нет
| Падение на Лондонском фондовом рынке |
| Рост на Лондонском фондовом рынке |
|
|
|
Рис. 4. 7.
Заметим, что в алгоритме АМХ, также, как и в представленном выше алгоритме ДРЕВ, выбор наиболее существенного признака может определяться на основании эвристических критериев, задаваемых пользователем.
|
|
|
