Алгоритм ДРЕВ. В алгоритме ДРЕВ наиболее важное значение признака определяется с помощью одного из критериев существенности Ф1,Ф2,

Алгоритм ДРЕВ

Данный алгоритм является методом качественного обобщения по признакам. Он был предложен как развитие алгоритма обобщения Э. Ханта CLS. Ставится цель построения обобщенного понятия на основе анализа обучающей выборки S, содержащей примеры К⁺ и контрпримеры К^-. При этом формируется логическая функция принадлежности к обобщенному понятию, которая служит классифицирующим правилом. В этой логической функции булевы переменные, отражающие значения признаков, соединены операциями конъюнкции, дизъюнкции и отрицания.

На первом этапе работы алгоритма делается попытка сформировать обобщенное конъюнктивное понятие на основе поиска признаков, значения которых являются общими для всех объектов выборки К⁺  и не встречаются среди контрпримеров К^-. Результатом должна стать логическая функция, П_к, значение которой равно 1 на всех примерах из выборки К⁺ и 0 на всех контрпримерах из К^-.

Затем формируется обобщенное дизъюнктивное понятие П_д, построение которого начинается с выбора среди элементов К⁺ такого признака, A_i, который является наиболее существенным для обобщенного понятия. Для выбранного признака ищется значение, с', которое называют разделяющим значением, так как на его основе происходит разбиение выборок К⁺ и К^- на две пары подвыборок: К⁺₁ и К^-₁, К⁺_-1 и К^-_-1; здесь К⁺₁ и К^-₁ содержат примеры со значениями c' , а К⁺_-1 и К^-_-1 соответственно содержат примеры со значениями Ø c'.

В алгоритме ДРЕВ наиболее важное значение признака определяется с помощью одного из критериев существенности Ф¹, Ф²,..., Ф^q.

Критерии Ф¹, Ф²,..., Ф^q составляют набор эвристических правил, встраиваемых в алгоритм; эти правила могут взаимозаменяться в диалоге с пользователем и тем самым оказывать влияние на вид получаемой функции принадлежности или решающего дерева. Поскольку множества значений признаков не наделены никакой структурой, позволяющей извлекать дополнительную информацию, основным параметром, влияющим на существенность значений признаков в формулах, соответствующих Ф^j, служит частота появления их в К⁺ и К^- . В качестве примера критерия существенности может быть взят следующий:

где - частота появления j-го значения i-го признака в примерах и контрпримерах, а a- число различных значений i-го признака в примерах и контрпримерах. Здесь разделяющее значение c'=c , для которого этот критерий выполняется.

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

Перечислим основные шаги алгоритма ДРЕВ.

Алгоритм ДРЕВ.

1. Формирование П_к на множестве S=К⁺È К^-. В случае успеха переход к п. 2, иначе - к п. 3.

2. Печать П_к и исключение признаков, вошедших в П_к.

3. Выбор признака А_i и нахождение разделяющего значения с'.

4. Разбиение выборок на две пары подвыборок.

5. Формирование П_к на подвыборках. В случае неудачи - возврат к шагу 3, иначе - переход к шагу 6.

6. Формирование и печать П_д. Конец.

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

На первом этапе работы алгоритм пытается построить конъюнктивное обобщенное понятие :

= & & …& .

Для этого берётся теоретико-множественное пересечение

= K  K …  K ,

где каждое K  понимается как упорядоченное по признакам множество значений.

Построение  (дизъюнктивной формы обобщенного понятия) начинается с поиска среди элементов K такого значения c' признака , которое является наиболее существенным для формирования понятия. Наиболее важное значение признака определяется с помощью одного из критериев существенности Ф¹, Ф²,..., Ф^q.

 

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: