Множественная модель деревьев


Содержание

Множественная модель деревьев

Personnel:
emp boss salary
==========================
‘Jerry’ NULL 1000.00
‘Bert’ ‘Jerry’ 900.00
‘Chuck’ ‘Jerry’ 900.00
‘Donna’ ‘Chuck’ 800.00
‘Eddie’ ‘Chuck’ 700.00
‘Fred’ ‘Chuck’ 600.00

Эта модель имеет преимущества и недостатки. ПЕРВИЧНЫЙ КЛЮЧ — emp, но столбец boss — функционально зависит от него, следовательно мы имеем проблемы с нормализацией. REFERENCES не даст вам возможность указать начальником, того кто не является сотрудником. Однако, что произойдет, когда ‘Jerry’ изменяет имя на ‘Geraldo’, чтобы получить телевизионное ток-шоу? Вы также должны сделать каскадные изменения в строках ‘Bert’ и ‘Chuck’.
Другой недостаток этой модели — то трудно вывести путь. Чтобы найти имя босса для каждого служащего, используется самообъединяющийся запрос, типа:

delphi
SELECT B1.emp, ‘bosses’ , E1.emp
FROM Personnel AS B1, Personnel AS E1
WHERE B1.emp = E1.boss;

Но кое-что здесь отсутствует. Этот запрос дает Вам только непосредственных начальников персонала. Босс Вашего босса также имеет власть по отношению к Вам, и так далее вверх по дереву. Чтобы вывести два уровня в дереве, Вам необходимо написать более сложный запрос самообъединения, типа:

delphi
SELECT B1.emp, ‘bosses’ , E2.emp
FROM Personnel AS B1, Personnel AS E1, Personnel AS E2
WHERE B1.emp = E1.boss AND E1.emp = E2.boss;

Чтобы идти более чем на два уровня глубже в дереве, просто расширяют образец:

delphi
SELECT B1.emp, ‘bosses’ , E3.emp
FROM Personnel AS B1, Personnel AS E1,
Personnel AS E2, Personnel AS E3
WHERE B1.emp = E1.boss
AND E1.emp = E2.boss
AND E2.emp = E3.boss;

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

delphi
SELECT *
FROM Personnel AS E1
WHERE NOT EXISTS(
SELECT *
FROM Personnel AS E2
WHERE E1.emp = E2.boss);

У корня дерева boss — NULL:

delphi
SELECT *
FROM Personnel
WHERE boss IS NULL;

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

Total Salaries
emp boss salary
==========================
‘Jerry’ NULL 4900.00
‘Bert’ ‘Jerry’ 900.00
‘Chuck’ ‘Jerry’ 3000.00
‘Donna’ ‘Chuck’ 800.00
‘Eddie’ ‘Chuck’ 700.00
‘Fred’ ‘Chuck’ 600.00

Множественная модель деревьев.
Другой путь представления деревьев состоит в том, чтобы показать их как вложенные множества. Это более подходящая модель, т.к. SQL — язык, ориентированный на множества. Корень дерева — множество, содержащее все другие множества, и отношения предок-потомок описываются принадлежностью множества потомков множеству предка.
Имеются несколько способов преобразования организационной диаграммы во вложенные наборы. Один путь состоит в том, чтобы вообразить, что Вы перемещаете подчиненные «овалы» внутри их родителей, использующих линии края как веревки. Корень — самый большой овал и содержит все другие узлы. Листья — самые внутренние овалы, ничего внутри не содержащие, и вложение соответствует иерархическим отношениям. Это — естественное представление модели «перечень материалов», потому что заключительный блок сделан физически из вложенных составляющих, и разбирается на отдельные части.
Другой подход состоит в том, чтобы представить небольшой червь, ползающий по «узлам и дугам» дерева. Червь начинает сверху, с кореня, и делает полную поездку вокруг дерева.
Но теперь давайте представим более сильный червь со счетчиком, который начинается с единицы. Когда червь прибывает в узел, он помещает число в ячейку со стороны, которую он посетил и увеличивает счетчик. Каждый узел получит два номера, одино для правой стороны и одино для левой стороны.
Это дает предсказуемые результаты, которые Вы можете использовать для формирования запросов. Таблица Personnel имеет следующий вид, с левыми и правыми номерами в виде:

delphi
CREATE TABLE Personnel(
emp CHAR ( 10 ) PRIMARY KEY,
salary DECIMAL( 6 , 2 ) NOT NULL,
left INTEGER NOT NULL,
right INTEGER NOT NULL);

Personnel
emp salary left right
==============================
‘Jerry’ 1000.00 1 12
‘Bert’ 900.00 2 3
‘Chuck’ 900.00 4 11
‘Donna’ 800.00 5 6
‘Eddie’ 700.00 7 8
‘Fred’ 600.00 9 10

Корень всегда имеет 1 в левом столбце и удвоенное число узлов (2*n) в правом столбце. Это просто понять: червь должен посетить каждый узел дважды, один раз с левой стороны и один раз с правой стороны, так что заключительный количество должено быть удвоенное число узлов во всем дереве.
В модели вложенных множеств, разность между левыми и правыми значениями листьев — всегда 1. Представте червя, поворачивающегся вокруг листа, пока он ползет по дереву. Поэтому, Вы можете найти все листья следующим простым запросом:

delphi
SELECT *
FROM Personnel
WHERE (right — left) = 1 ;

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

delphi
SELECT *
FROM Personnel
WHERE left = (right — 1 );

Причина увеличения производительности в том, что SQL может использовать индекс по левому столбцеу, когда он не испорльзуется в выражении. Не используйте (left — right) = 1, потому что это дает воспользоваться преимуществами индекса.
В модели вложенных — имножеств, пути показываются как вложенные множества, которые представлены номерами вложенных множеств и предикатами BETWEEN. Например, чтобы определить всех боссов определенного сотрудника необходимо написать:

delphi
SELECT :myworker, B1.emp, (right — left) AS height
FROM Personnel AS B1, Personnel AS E1
WHERE E1.left BETWEEN B1.left AND B1.right
AND E1.right BETWEEN B1.left AND B1.right
AND E1.emp = :myworker;

Чем больше height, тем дальше по иерархии босс от служащего. Модель вложенных множеств использует факт, что каждое содержащее другие множество является большим в размере (где размер = (right — left)) чем множества, в нем содержащиеся. Очевидно, корень будет всегда иметь самый большой размер.
Уровень, число дуг между двумя данными узлами, довольно просто вычислить. Например, чтобы найти уровни между заданным рабочим и менеджером, Вы могли бы использовть:

delphi
SELECT E1.emp, B1.emp, COUNT(*) — 1 AS levels
FROM Personnel AS B1, Personnel AS E1
WHERE E1.left BETWEEN B1.left AND B1.right
AND E1.right BETWEEN B1.left AND B1.right
AND E1.node = :myworker
AND B1.node = :mymanager;

(COUNT(*) — 1) используется для того, чтобы удалить двойной индекс узла непосредственно как нахождение на другом уровне, потому что узел — нулевые уровни, удаленные из себя.
Вы можете построить другие запросы из этого шаблона. Например, чтобы найти общих боссов двух служащих, объединяют пути и находят узлы который имеют (COUNT(*) > 1). Чтобы найти самых близких общих предков двух узлов, объединяют пути, находят узлы, которые имеют (COUNT(*) > 1), и выбирают с наименьшей глубиной.

delphi
SELECT ‘Mary’ ,
P1.emp, (P1.rgt — P1.lft) AS size
FROM Personnel AS P1, Personnel AS P2
WHERE P2.emp = ‘Mary’
AND P2.lft BETWEEN P1.lft AND P1.rgt;

Mary emp size
==== === ====
Mary Albert 27
Mary Charles 13
Mary Fred 9
Mary Jim 5
Mary Mary 1

Заметьте, что, когда size = 1, Вы имеете дело С Мэри как с ее собственным боссом. Вы можете исключить этот случай.
Модель вложенная множеств использует факт, что каждый вешний набор имеет больший size (size = right — left) чем множества, которые оно содержит. Очевидно, корень будет всегда иметь самый большой size. JOIN и ORDER BY не нужны в модели вложенных множеств, как модели графа смежности. Плюс, результаты не зависят от порядка, в котором отображаются строки.
Уровень узла — число дуг между узлом и корнем. Вы можете вычислять уровень узла следующим запросом:

delphi
SELECT P2.emp, COUNT(*) AS level
FROM Personnel AS P1, Personnel AS P2
WHERE P2.lft BETWEEN P1.lft AS P2
GROUP BY P2.emp;

Этот запрос находит уровни среди менеджеров, следующим образом:

emp level
=== =====
Albert 1
Bert 2
Charles 2
Diane 2
Edward 3
Fred 3
George 3
Heidi 3
Igor 4
Jim 4
Kathy 4
Larry 4
Mary 5
Ned 5

В некоторых книгах по теории графов, корень имеет нулевой уровнь вместо первого. Если Вам нравится это соглашение, используйте выражение «(COUNT(*)-1)».
Самообъединения в комбинации с предикатом BETWEEN- основной шаблон для других запросов.
Агрегатные функции в деревьях.
Получение простой суммы зарплаты подчиненных менеджера работает на том же самом принципе. Заметьте, что эта общая сумма будет также включать зарплату босса:

delphi
SELECT P1.emp, SUM (P2.salary) AS payroll
FROM Personnel AS P1, Personnel AS P2
WHERE P2.lft BETWEEN P1.lft AND P1.rgt
GROUP BY P1.emp;

emp payroll
=== =======
Albert 7800.00
Bert 1650.00
Charles 3250.00
Diane 1900.00
Edward 750.00
Fred 1600.00
George 750.00
Heidi 1000.00
Igor 500.00
Jim 300.00
Kathy 100.00
Larry 100.00
Mary 100.00
Ned 100.00

поддеревьев
Следующий запрос будет брать уволенного служащего как параметр и удалять поддерево, расположенное под ним/ней. Уловка в этом запросе — то, что Вы используете ключ, но Вы должны заставить работать левые и правые значения. Ответ — набор скалярных подзапросов:

delphi
DELETE FROM Personnel
WHERE lft BETWEEN
(SELECT lft FROM Personnel WHERE emp = :downsized)
AND
(SELECT rgt FROM Personnel WHERE emp = :downsized);

Проблема состоит в том, что после этого запроса появляются промежутки в последовательности номеров множеств. Это не мешает выполнять большинство запросов к дереву, т.к. свойство вложения сохранено. Это означает, что Вы можете использовать предикат BETWEEN в ваших запросах, но другие операции, которые зависят от плотности номеров, не будут работать в дереве с промежутками. Например, Вы не сможете находить листья, используя предикат (right-left=1), и не сможете найти число узлов в поддереве, используя значения left и right его корня.
К сожалению, Вы потеряли информацию, которая будет очень полезна в закрытии тех промежутков — а именно правильные и левые номера корня поддерева. Поэтому, забудьте запрос, и напишите вместо этого процедуру:

delphi
CREATE PROCEDURE DropTree (downsized IN CHAR ( 10 ) NOT NULL)
BEGIN ATOMIC
DECLARE dropemp CHAR ( 10 ) NOT NULL;
DECLARE droplft INTEGER NOT NULL;
DECLARE droprgt INTEGER NOT NULL;

—Теперь сохраним данные поддерева:

SELECT emp, lft, rgt
INTO dropemp, droplft, droprgt
FROM Personnel
WHERE emp = downsized;

—Удаление, это просто.

DELETE FROM Personnel
WHERE lft BETWEEN droplft and droprgt;

—Теперь уплотняем промежутки:

UPDATE Personnel
SET lft = CASE
WHEN lft > droplf
THEN lft — (droprgt — droplft + 1 )
ELSE lft END ,
rgt = CASE
WHEN rgt > droplft
THEN rgt — (droprgt — droplft + 1 )
ELSE rgt END ; END ;

Реальная процедура должна иметь обработку ошибок, но я оставляю это как упражнение для читателя.
Удалениеузла
Удаление одиночного узла в середине дерева тяжелее чем удаление полных поддеревьев. Когда Вы удаляете узел в середине дерева, Вы должны решить, как заполнить отверстие. Имеются два пути. Первый метод к повышает одного из детей к позиции первоначального узла (предположим, что отец умирает, и самый старший сын занимает бизнес, как показано на рисунке 2). Самый старший потомок всегда показывается как крайний левый дочерний узел под родителем. Однако с этой этой операцией имеется проблема. Если старший ребенок имеет собственнх детей, Вы должны решить, как обработать их, и так далее вниз по дереву, пока Вы не добираетесь к листу.
Второй метод для удаления одиночного узла в середине дерева состоит в том, чтобы подключить потомков к предку первоначального узла (можно сказать, что мамочка умирает, и дети приняты бабушкой), как показано на рисунке 3. Это получается автоматически во модели вложенных множеств, Вы просто удаляете узел, и его дети уже содержатся в узлах его предка. Однако, Вы должны быть осторожны, при закрытии промежутка, оставленного стиранием. Имеется различие в изменении нумерации потомков удаленного узла и изменения нумерации узлов справа. Ниже — процедура выполняющая это:

delphi
CREATE PROCEDURE DropNode (downsized IN CHAR ( 10 ) NOT NULL)
BEGIN ATOMIC
DECLARE dropemp CHAR ( 10 ) NOT NULL;
DECLARE droplft INTEGER NOT NULL;
DECLARE droprgt INTEGER NOT NULL;

—Теперь сохраним данные поддерева:

SELECT emp, lft, rgt
INTO dropemp, droplft, droprgt
FROM Personnel
WHERE emp = downsized;

—Удаление, это просто.

DELETE FROM Personnel
WHERE emp = downsized;

—Теперь уплотняем промежутки:

UPDATE Personnel
SET lft = CASE
WHEN lft BETWEEN droplft AND droprgt THEN lft — 1
WHEN lft > droprgt THEN lft — 2
ELSE lft END
rgt = CASE
WHEN rgt BETWEEN droplft AND droprgt THEN rgt — 1
WHEN rgt > droprgt THEN rgt — 2
ELSE rgt END ;
WHERE lft > droplft;
END ;

delphi
CREATE TABLE Personnel
(emp CHAR ( 10 ) PRIMARY KEY,
salary DECIMAL( 8 , 2 ) NOT NULL CHECK(salary > = 0.00 ),
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL,
CHECK(lft INSERT INTO Personnel VALUES ( ‘Albert’ , 1000.00 , 1 , 28 );
INSERT INTO Personnel VALUES ( ‘Bert’ , 900.00 , 2 , 5 );
INSERT INTO Personnel VALUES ( ‘Charles’ , 900.00 , 6 , 19 );
INSERT INTO Personnel VALUES ( ‘Diane’ , 900.00 , 20 , 27 );
INSERT INTO Personnel VALUES ( ‘Edward’ , 750.00 , 3 , 4 );
INSERT INTO Personnel VALUES ( ‘Fred’ , 800.00 , 7 , 16 );
INSERT INTO Personnel VALUES ( ‘George’ , 750.00 , 17 , 18 );
INSERT INTO Personnel VALUES ( ‘Heidi’ , 800.00 , 21 , 26 );
INSERT INTO Personnel VALUES ( ‘Igor’ , 500.00 , 8 , 9 );
INSERT INTO Personnel VALUES ( ‘Jim’ , 100.00 , 10 , 15 );
INSERT INTO Personnel VALUES ( ‘Kathy’ , 100.00 , 22 , 23 );
INSERT INTO Personnel VALUES ( ‘Larry’ , 100.00 , 24 , 25 );
INSERT INTO Personnel VALUES ( ‘Mary’ , 100.00 , 11 , 12 );
INSERT INTO Personnel VALUES ( ‘Ned’ , 100.00 , 13 , 14 );


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

Второй метод для удаления одиночного узла в середине дерева состоит в том, чтобы подключить потомков к предку первоначального узла (можно сказать, что мамочка умирает, и дети приняты бабушкой).
© Joe Celko
DBMS Online — April 1996
Translated by SDM
Деревья в SQL. Часть 3.
Давайте продолжим наше обсуждение модели вложенных множеств для деревьев в SQL. Я не собираюсь рассматривать любую из моих предидущих статей и буду предполагать, что Вы все еще имеете копию таблицы Personnel, которую я использовал для примеров (DBMS, март 1996, страница 24). Если Вы не имеете прошлых выпусков, Вы можете осчастливить моего издателя, приобретя их.
Меня спрашивают, почему я не показываю больше процедурного кода в примерах. Прямо сейчас, ANSI и ISO пробуют договориться о стандартном процедурном языке для триггеров и хранимых процедур называемом SQL/PSM. Однако, этот стандарт еще не утвержден, что означает, что я должен использовать или свой собственный псевдо-код или выбирать одного производителя. Я решил использовать пока Английские комментарии, но я буду начинать использовать SQL/PSM, когда он будет завершен.
Наиболее хитрая часть обработки деревьев в SQL это нахождение способа конвертировать модель матрицы смежности в модель вложенных множеств в пределах структуры чистого SQL. Было бы довольно просто загрузить таблицу матрицы смежности в программу, и затем использовать рекурсивную программу преобразование дерева из учебника колледжа, чтобы построить модель вложенных множеств.
Честно говоря, такое преобразованиме дерева могло бы быть быстрее чем то, что я собираюсь показать Вам. Но я хочу сделать это в чистом SQL, чтобы доказать следующее: Вы можете делать на декларативном языке то же, что Вы можете делать на процедурном языке. Поскольку это обучающее упражнение, я буду объяснять с болезненной детальностью.
Классический подход к решению проблемы состоит в том, чтобы брать самое простой случай проблемы, и смотреть, можете ли Вы применять его к более сложным случаям. Если дерево не имеет узлов, то преобразование просто — ничего не делать. Если дерево имеет один узел, то преобразование простое — устанавливают левое значение в 1 и правое значение в 2. Природа матрицы смежности такова, что Вы можете двигаться только по одному уровню одновременно, так что давайте посмотрим на дерево с двумя уровнями — корень и непосредственные потомки. Таблица модели смежности напоминала бы следующее:

delphi
CREATE TABLE Personnel
(emp CHAR ( 10 ) NOT NULL PRIMARY KEY,
boss CHAR ( 10 ));

emp boss
=================
‘Albert’ NULL
‘Bert’ ‘Albert’
‘Charles’ ‘Albert’
‘Diane’ ‘Albert’

Давайте поместим модель вложенных множеств в ее собственную рабочую таблицу:

delphi
CREATE TABLE WorkingTree(
emp CHAR ( 10 ),
boss CHAR ( 10 ),
lft INTEGER NOT NULL DEFAULT 0 ,
rgt INTEGER NOT NULL DEFAULT 0 );

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

delphi
INSERT INTO WorkingTree
—convert the root node
SELECT P0.boss, P0.boss, 1 ,
2 * (SELECT COUNT(*) + 1
FROM Personnel AS P1
WHERE P0.boss = P1.boss)
FROM Personnel AS P0;

Теперь, Вы должны добавить потомков в таблицу вложенных множеств. Первоначальный босс останется тот же самый. Порядок потомков — естественный порядок ключа; в данном случае emp char(10):

delphi
INSERT INTO WorkingTree
—convert the children
SELECT DISTINCT P0.emp, P0.boss,
2 * (SELECT COUNT(DISTINCT emp)
FROM Personnel AS P1
WHERE P1.emp AND P0.boss IN (P1.emp, P1.boss)),
2 * (SELECT COUNT(DISTINCT emp)
FROM Personnel AS P1
WHERE P1.emp AND P0.boss IN (P1.boss, P1.emp)) + 1
FROM Personnel AS P0;

Фактически, Вы можете использовать эту процедуру, чтобы конвертировать модель матрицы смежности в лес деревьев, каждое из которых — модель вложенных множеств, идентифицированная ее корневым значением. Таким образом, генеалогическое дерево Альберта — набор строк, которые имеют Альберта как предка, генеалогическое дерево Берта — набор строк, которые имеют Берта как предка, и так далее. (Эта концепция иллюстрирована в рисунках 1 и 2.
Поскольку первоначальная таблица матрицы смежности повторяет нелистовые узлы, некорневые узлы, в столбцах emp и boss, таблица WorkingTree дублирует узлы как корень в одном дереве и как потомок в другом. Запрос также будет странно себя вести со значением NULL в столбце boss первоначальной таблицы матрицы смежности, так что Вы будете должны очистить таблицу WorkingTree следующим запросом:

delphi
DELETE FROM WorkingTree
WHERE boss IS NULL OR emp IS NULL;

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

delphi
CREATE PROCEDURE TreeMerge(superior NOT NULL, subordinate NOT NULL)
BEGIN
DECLARE size INTEGER NOT NULL;
DECLARE insert_point INTEGER NOT NULL;
SET size = 2 * (SELECT COUNT(*) FROM WorkingTree WHERE emp = subordinate);
SET insert_point = (
SELECT MIN (lft)
FROM WorkingTree
WHERE emp = subordinate AND boss = superior) — 1 ;

UPDATE WorkingTree
SET boss = CASE WHEN boss = subordinate
THEN CASE WHEN emp = subordinate
THEN NULL
ELSE superior END
ELSE boss END ,

lft = CASE WHEN (boss = superior AND lft > size)
THEN lft + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN lft + insert_point
ELSE lft END
END ,

rgt = CASE WHEN (boss = superior AND rgt > size)
THEN rgt + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN rgt + insert_point
ELSE rgt END
END

WHERE boss IN (superior, subordinate);

—Удаляем избыточные копии корня подчиненного дерева
DELETE FROM WorkingTree WHERE boss IS NULL OR emp IS NULL;

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

delphi
CREATE VIEW AllPairs (superior, subordinate)
AS
SELECT W1.boss, W1.emp
FROM WorkingTree AS W1
WHERE EXISTS( SELECT * FROM WorkingTree AS W2 WHERE W2.boss = W1.emp)
AND W1.boss <> W1.emp;

Но Вы хотели бы получить только одну пару, которую Вы передатите в только что разработанную процедуру. Чтобы переместить одну пару, берем крайнюю левую пару из прошлого запроса:

delphi
CREATE VIEW LeftmostPairs(superior, subordinate)
AS
SELECT DISTINCT superior,
(SELECT MIN (subordinate)
FROM AllPairs AS A2
WHERE A1.superior = A2.superior)
FROM AllPairs AS A1
WHERE superior = (SELECT MIN (superior) FROM AllPairs);

Теперь все, что Вам осталось сделать — поместить этот запрос в ранее разработанную процедуру — и у вас будет процедура, которая сольет вместе лес деревьев слева направо. Используя цикл WHILE, контролируюший наличие значений в LeftmostPairs делайте вызовы процедуры. Это единственная процедуральная структура во всей хранимой процедуре.

Примеры запросов к модели дерева принятия решений

Область применения: SQL Server Analysis Services Azure Analysis Services Power BI Premium

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

В этом разделе описывается создание запросов к моделям, основанным на алгоритме дерева принятия решений Microsoft .

Запросы содержимого

Прогнозирующие запросы

Поиск сведений о модели дерева принятия решений

Для создания осмысленных запросов к содержимому модели дерева принятия решений необходимо изучить структуру содержимого модели и сведения, содержащиеся в каждом типе узла. Дополнительные сведения см. в разделе Содержимое моделей интеллектуального анализа данных для моделей дерева принятия решений (службы Analysis Services — интеллектуальный анализ данных).

Образец запроса 1: Получение параметров модели из набора строк схемы интеллектуального анализа данных

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

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

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

Этот запрос возвращает все узлы, имеющие тип 2; то есть узлы верхнего уровня деревьев, представляющих определенные прогнозируемые атрибуты.

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

MODEL_NAME NODE_NAME NODE_CAPTION NODE_SUPPORT CHILDREN_CARDINALITY
TM_DecisionTree 000000001 All 12939 5

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

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

Столбец SUPPORT вложенной таблицы должен быть заключен в скобки, чтобы отличаться от зарезервированного ключевого слова с таким же именем.

NODE_NAME NODE_CAPTION T.ATTRIBUTE_NAME T.ATTRIBUTE_VALUE Псевдоним
00000000100 Number Cars Owned = 0 Покупатель велосипеда Missing
00000000100 Number Cars Owned = 0 Покупатель велосипеда 1067
00000000100 Number Cars Owned = 0 Покупатель велосипеда 1 1875
00000000101 Число автомобилей во владении = 3 Покупатель велосипеда Missing
00000000101 Число автомобилей во владении = 3 Покупатель велосипеда 678
00000000101 Число автомобилей во владении = 3 Покупатель велосипеда 1 473

Исходя из этих результатов можно определить, что среди клиентов, купивших велосипед ([Bike Buyer] = 1), 1067 клиентов не имели автомобиля, а 473 клиента имели по 3 автомобиля.

Образец запроса 3: Получение поддеревьев из модели

Допустим, что необходимо узнать больше о клиентах, купивших велосипед. Дополнительные сведения о любом из вложенных деревьев можно просматривать с помощью функции IsDescendant (DMX) в запросе, как это показано в следующем примере. Запрос возвращает число клиентов, купивших велосипед, возвращая конечные узлы (NODE_TYPE = 4) из дерева, в котором содержатся клиенты, возраст которых превышает 42 года. Запрос ограничивает строки вложенной таблицы теми, в которых Bike Buyer = 1.


10. 1. Общие понятия о модельных деревьях

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

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

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

10.2. Способы таксации леса по моделям

Способ средней модели. В лесной таксации дерево, у которого диаметр на высоте груди, высота и видовое число равны среднему диаметру, средней высоте и среднему видовому числу данного насаждения, называется средней моделью насаждения. Средняя модель, перечисленные параметры которой вычислены теоретическим путем, называется расчетной. Если объем средней расчетной модели V умножить на число деревьев в насаждении N. получим общий запас насаждения М

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

Площадь сечения расчетной модели определяется по формуле

Отсюда число деревьев N будет

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

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

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

Следовательно, запас древесины во всем насаждении может быть найден по следующей формуле:

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

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

Общий запас древесины по этому способу определяется по следующей формуле:

где n и m – число моделей в классе;

Г — сумма площадей сечений всех срубленных моделей.

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

Способ определения запаса по моделям, взятым по ступеням толщины. Чтобы избежать в лесу громоздких расчетов, связанных с определением размеров моделей по отдельным классам, в таксационной практике определяют запас по моделям, срубаемым от каждой ступени толщины. Для этого в таксируемом участке делают перечет и по каждой ступени толщины находят сумму площадей сечений деревьев. Для каждой ступени толщины выбирают по две-три наиболее типичные модели с таким расчетом, чтобы диаметры их были по возможности близки к середине соответствующих ступеней толщины. Выбранные модели срубают и находят их объем по сложной формуле серединных сечений. Объемы моделей, взятых для каждой ступени толщины (Vc), суммируют, а затем находят сумму площадей сечений этих моделей на высоте груди (γс).

Запас древесины по каждой ступени толщины определяют по формуле

и получают общий запас таксируемого насаждения.

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

Модель вложенных множеств

Теоретический материал

Подходы к организации иерархических структур

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

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

Существует 3 основных подхода к организации иерархических данных:

· метод вложенных множеств;

· модель материализованного пути.

Родитель-потомок

Метод родитель-потомок или модель списка смежных вершин (adjacency list model) – является одним из первых методов, разработанных для хранения иерархий в реляционных БД.

Это интуитивно понятный способ организации иерархической структуры, который представляет собой рефлексивную связь – замыкание связи таблицы БД на саму себя (Рисунок 1).

Рисунок 1. Пример рефлексивной связи

Как известно из теории, граф можно представить в виде матрицы, где на пересечении i-й строки и j-го столбца стоит 1, если между узлами (вершинами) графа с номерами i и j есть связь (ребро, дуга), или 0 в противном случае. Такая абстракция называется матрицей смежности.

Матрица смежности может быть также представлена в виде списка (множества) пар с номерами (идентификаторами, кодами) вершин по принципу: есть пара – есть связь, нет пары – нет связи.

Корневые вершины отличаются от других пар пустой (NULL) ссылкой на предка, в приведенном примере это поле «BuyerIDParent».


Выборка непосредственных родителей или потомков при такой организации иерархических данных представляет собой простой SQL-запрос, в то время как для выборки поддерева по заданному узлу потребуется рекурсивный запрос

—Выборка непосредственных потомков некоторого узла

SELECT * FROM dbo.Buyer where Buyer >

—Выборка всех потомков некоторого узла

WITH BuyerChild(BuyerID, BuyerIDParent, [Name], [Level]) AS

SELECT BuyerID, BuyerIDParent, [Name], 1

SELECT dbo.Buyer.BuyerID, dbo.Buyer.BuyerIDParent, dbo.Buyer.[Name], [Level]+1

FROM dbo.Buyer INNER JOIN BuyerChild ON BuyerChild.Buyer >

SELECT * FROM BuyerChild ORDER BY [Level], BuyerIDParent

Преимущества и недостатки модели списка смежных вершин приведены в таблице1.

Таблица 1. Преимущества и недостатки подхода родитель-потомок

Характеристика Модель списка смежных вершин
Простота структуры (количество таблиц/ссылок/ минимальное количество полей) 1/1/3
Прямая выборка детей узла Да
Прямая выборка поддерева (всех потомков узла) Нет, рекурсия
Прямая выборка пути от узла до корня (всех предков узла) Нет, рекурсия
Порядок следования узлов при сортировке Нет
Быстрая вставка новых узлов Да
Быстрое перемещение поддерева Да
Быстрое удаление поддерева Да, рекурсия
Избыточность хранения Нет
Количество уровней дерева Не ограничено
Дополнительная поддержка целостности (кроме ссылочной) Не нужна

Модель вложенных множеств

Модель вложенных множеств или множественная модель дерева (nested-set model of trees) была предложена Джо Селко и представляет собой хранение маршрута обхода графа в префиксном порядке (Рисунок 2).

Квадратик на рисунке обозначает узел, цифра в левом его углу является порядковым номером этапа маршрута при входе в узел, а цифра справа — при выходе. При префиксном порядке обхода сначала посещается корень графа, вершина «Федоров Егор Иванович», а затем выполнятся префиксный обход поддеревьев с корнями «Кравцов Евгений Николаевич», …, «Петько Татьяна Филиповна» в указанной последовательности.

Рисунок 2. Пример префиксного маршрута обхода

Как нетрудно заметить, номера потомков всегда располагаются в интервале между соответствующими номерами предка, сколь угодно дальнего. Храня такой порядок обхода дерева в БД (Рисунок 3), при выборке потомков/предков некоторого узла можно избежать рекурсии

Рисунок 3. Пример таблицы с полями для хранения префиксного порядка обхода

—Выборка всех потомков некоторого узла

SELECT b2.* FROM dbo.Buyer b1 INNER JOIN dbo.Buyer b2 ON b2.[left] BETWEEN b1.[left] AND b1.[right]

Очевидная сложность модели вложенных множеств – это пересчет порядка обхода при добавлении новых или перемещении имеющихся узлов.

Для вычисления значений и right вершин используется следующий алгоритм:

1. Обход начинается с корневой вершины. Значению корня присваивается 1. Счетчику присваивается 2.

2. Если для текущей вершины не существует ни одного прямого потомка или среди потомков нет таких, для которых значение не присвоено, то значение этой вершины равно . . Переход на 5.

3. Прямому потомку текущей вершины, для которого значение еще не было присвоено, назначается . .

4. Текущей вершиной становится прямой потомок, которому было присвоено значение . Переход на 2.

5. Если для текущей вершины существует родитель, то текущей вершиной становится этот родитель. Переход на 2. Иначе конец алгоритма.

Преимущества и недостатки множественной модели дерева приведены в таблице 2.

Таблица 2. Преимущества и недостатки множественной модели дерева

Множественная модель деревьев

Деревья решений (Breiman at al., 1984; Quinlan, 1986) осуществляют разбиение пространства объектов в соответствии с некоторым набором правил разбиения (splitting rule). Эти правила являются логическими утверждениями в отношении той или иной переменной и могут быть истинными или ложными. Ключевыми здесь являются три обстоятельства: а) правила позволяют реализовать последовательную дихотомическую сегментацию данных, б) два объекта считаются похожими, если они оказываются в одном и том же сегменте разбиения, в) на каждом шаге разбиения увеличивается количество информации относительно исследуемой переменной (отклика).

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

  1. Деревья решений позволяют получать очень легко интерпретируемые модели, представляющие собой набор правил вида “если…, то…”. Интерпретация облегчается, в том числе, за счет возможности представить эти правила в виде наглядной древовидной структуры.
  2. В силу своего устройства деревья решений позволяют работать с переменными любого типа без необходимости какой-либо предварительной подготовки этих переменных для ввода в модель (например, логарифмирование, преобразование категориальных переменных в индикаторные, и т.п.).
  3. Исследователю нет необходимости в явном виде задавать форму взаимосвязи между откликом и предикторами, как это, например, происходит в случае с обычными регрессионными моделями. Это оказывается особенно полезным при работе с данными большого объема, о свойствах которых мало что известно.
  4. Деревья решений, по сути, автоматически выполняют отбор информативных предикторов и учитывают возможные взаимодействия между ними. Это, в частности, делает деревья решений полезным инструментом разведочного анализа данных.
  5. Деревья решений можно эффективно применять к данным с пропущенными значениями, что очень полезно при решении практических задач, где наличие пропущенных значений – это, скорее, правило, чем исключение.
  6. Деревья решений одинаково хорошо применимы как к количественным, так и к качественным зависимым переменным.

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

Алгоритм CART (Classification and Regression Tree) рекурсивно делит исходный набор данных на подмножества, которые становятся все более и более гомогенными относительно определенных признаков, в результате чего формируется древовидная иерархическая структура. Деление осуществляется на основе традиционных логических правил в виде ЕСЛИ (А) ТО (В) , где А — некоторое логическое условие, а В — процедура деления подмножества на две части, для одной из которых условие А истинно, а для другой — ложно. Примеры условий: Xi==F, Хi = V и др., где Хi – один из предикторов исходной таблицы, F — выбранное значение категориальной переменной, V — специально подобранное опорное значение (порог).

На первой итерации корневой узел дерева связывается с наиболее оптимальным условным суждением, и все множество объектов делится на две группы. От каждого последующего узла-родителя к узлам-потомкам также может отходить по две ветви, в свою очередь связанные c граничными значениями других наиболее подходящих переменных и определяющие правила дальнейшего разделения (splitting criterion). Конечными узлами дерева являются “листья”, соответствующие найденным решениям и объединяющие все разделенные на группы объекты обучающей выборки. Общее правило выбора опорного значения для каждого узла построенного дерева можно сформулировать следующим образом: “выбранный признак должен разбить множество \(\mathbf^*\) так, чтобы получаемые в итоге подмножества \(\mathbf_k^*, k = 1, 2, \dots, p\) , состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому”.

Описанный процесс относится к так называемым “жадным” алгоритмам, стремящимся, не считаясь ни с чем, построить максимально “кустистое” дерево (также “глубокое дерево”, deep tree). Естественно, чем обширнее и кустистее дерево, тем лучше будут результаты его тестирования на обучающей выборке, но не столь успешными – на проверочной выборке. Поэтому построенная модель должна быть еще и оптимальной по размерам, т.е. содержать информацию, улучшающую качество распознавания, и игнорировать ту информацию, которая его не улучшает. Для этого обычно проводят “обрезание” дерева (tree pruning) – отсечение ветвей там, где эта процедура не приводит к серьезному возрастанию ошибки.


Невозможно подобрать объективный внутренний критерий, приводящий к хорошему компромиссу между безошибочностью и компактностью, поэтому стандартный механизм оптимизации деревьев основан на перекрестной проверке (Loh, Shih, 1997). Для этого обучающая выборка разделяется, например, на 10 равных частей: 9 частей используется для построения дерева, а оставшаяся часть играет роль проверочной совокупности. После многократного повторения этой процедуры из некоторого набора деревьев-претендентов, у которых имеется практически допустимый разброс критериев качества модели, выбирается дерево, показавшее наилучший результат при перекрестной проверке.

4.3.1 Построение деревьев на основе рекурсивного разбиения

В общем случае может быть использовано несколько алгоритмов построения деревьев на основе различных схем и критериев оптимизации. Функция rpart() из одноименного пакета выполняет рекурсивный выбор для каждого следующего узла таких разделяющих значений, которые приводят к минимальной сумме квадратов внутригрупповых отклонений Dt для всех t узлов дерева. Для оценки качества построенного дерева \(\mathbf\) в ходе его оптимизации используется следующая совокупность критериев:

  • штраф за сложность модели (cost complexity), включающий штрафной множитель за каждую неотсечённую ветвь \(СС(\mathbf = \sum_t D_t + \lambda t)\) ;
  • девианс \(D_0\) для нулевого дерева (т.е. оценка изменчивости в исходных данных);
  • относительный параметр стоимости сложности \(Cp = \lambda / D_0\) ;
  • относительная ошибка обучения для дерева из \(t\) узлов \(REL_ = \sum_t D_t /D_0\) ;
  • ошибка перекрестной проверки ( \(CV_\) ) с разбиением на 10 блоков, также отнесенная к девиансу нуль-дерева \(D_0\) ; \(CV_\) , как правило, больше, чем \(REL_\) ;
  • стандартное отклонение ( \(SE\) ) ошибки перекрестной проверки.

Лучшим считается дерево, состоящее из такого количества ветвей \(t\) , для которого сумма ( \(CV_ + SE\) ) является минимальной.

В качестве примера рассмотрим построение дерева CART, прогнозирующего обилие водорослей группы a1 в зависимости от гидрохимических показателей воды и условий отбора проб в различных водотоках (см. разделы 3.4 и 4.1-4.2). Используем сначала пакет rpart , для работы с которым обычно применяется двухшаговая процедура: функция rpart() устанавливает связи между зависимой и независимыми переменными и формирует бинарное дерево, а функция prun() выполняет обрезание лишних ветвей.

Приведенной командой мы построили полное дерево без обрезания ветвей, состоящее из 9 узлов и 10 листьев, обозначенных в приведенном протоколе разбиения символом * . В каждой строке представлены по порядку: условие разделения, число наблюдений, соответствующих этому условию, девианс (в данном случае — это эквивалент суммы квадратов отклонений от группового среднего) и среднее значение отклика для выделенной ветви. Например, перед первой итерацией общее множество из 200 наблюдений имеет среднее значение m = 16.92 при девиансе D = 90694 . При PO4>=43.8 это множество делится на две части: 2) 148 наблюдений ( m =8.92 , D = 31359 ) и 3) 52 наблюдения с высоким уровнем обилия водорослей ( m =39.7 , D = 22863 ). Дальнейшие разбиения каждой из этих двух частей аналогичны.

Разумеется, лучший вариант – представить дерево графически. Популярны три варианта визуализации с использованием различных функций: plot() , prettyTree() из пакета DMwR и prp() из чрезвычайно продвинутого пакета rpart.plot (рис. 4.7):

Рисунок 4.7: Дерево rpart без обрезания ветвей

Полезно также проследить изменение перечисленных выше статистических критериев по мере выращивания дерева:

Функция rpart() и другие функции из пакета rpart имеют собственные возможности выполнить перекрестную проверку и оценить ее ошибку при различных значениях штрафа за сложность модели cp (рис. 4.8):

Рисунок 4.8: Зависимость относительной ошибки перекрестной проверки от штрафа за сложность модели cp

На рис. 4.8 видно, что минимум относительной ошибки при перекрестной проверке приходится на значение cp = 0.024 . 6 Выполним обрезку дерева при этом значении (рис. 4.9):

Рисунок 4.9: Дерево rpart c обрезанием ветвей при cp = 0.024

Выполним теперь дополнительную оптимизацию параметра ср с использованием функции train() из пакета caret (см раздел 3.5). Будем тестировать деревья регрессии при 30 значениях критерия ср , для каждого из которых выполним 10-кратную перекрестную проверку с 3 повторностями (рис. 4.10):

Рисунок 4.10: Оценка параметра cp с использованием функции train()

Рисунок 4.11: Дерево rpart c обрезанием ветвей при cp = 0.0277

При cp = 0.0277 было получено существенно урезанное дерево, которое, правда, значительно потеряло в своей объясняющей ценности.

4.3.2 Построение деревьев с использованием алгортма условного вывода

Обратимся теперь к принципиально другим методам рекурсивного разделения при построении деревьев, представленным в пакете party . Стандартный механизм проверки статистического гипотез, который предотвращает переусложнение модели, реализован в функции ctree() , использующей метод построения деревьев на основе “условного вывода” (conditional inference). Алгоритм принимает во внимание характер распределения отдельных переменных и осуществляет на каждом шаге рекурсивного разделения данных несмещенный выбор влияющих ковариат, используя формальный тест на основе статистического критерия \(c(\boldsymbol_j, \mu_j, \Sigma_j), j = 1, \dots, m\) , где \(\mu, \Sigma\) — соответственно среднее и ковариация (Hothorn et al., 2006). Оценка статистической значимости \(с\) -критерия выполняется на основе перестановочного теста, в результате чего формируются компактные деревья, не требующие процедуры обрезания.

Рисунок 4.12: Дерево cpart без оптимизации параметра mincriterion

Оптимизацию параметра mincriterion выполним с использованием функции train() при тех же условиях перекрестной проверки:

Рисунок 4.13: Дерево cpart после оптимизации параметра mincriterion

Здесь имел место обратный процесс: число узлов дерева было предложено увеличить с 7 до 11. Обратим также внимание на то, что в дереве появились категориальные переменные (размер и скорость течения реки), которые были проигнорированы rpart -деревьями.

4.3.3 Тестирование моделей с использованием дополнительного набора данных

Используем для прогноза набор данных (Torgo, 2011) из 140 наблюдений, который мы уже применяли в предыдущем разделе. Данные с восстановленными пропущенными значениями мы сохранили ранее в файле algae_test.RData (см раздел 4.1).

Оценим точность каждой модели на этом наборе данных по трем показателям: среднему абсолютному отклонению ( MAE ), корню из среднеквадратичного отклонения ( RSME ) и квадрату коэффициента детерминации Rsq = 1 — NSME , где NSME — относительная ошибка, равная отношению средних квадратов отклонений от модельных значений и от общего среднего:

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

Модели роста и взаимодействия деревьев Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Медведев Сергей Борисович, Пестунов Александр Игоревич, Пестунов Игорь Алексеевич, Федотов Анатолий Михайлович

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

Похожие темы научных работ по математике , автор научной работы — Медведев Сергей Борисович, Пестунов Александр Игоревич, Пестунов Игорь Алексеевич, Федотов Анатолий Михайлович,

MODELS OF GROWTH AND INTERACTION OF TREES

The paper deals with mathematical models of tree growth based on balance rations with limitations of soil nutrients and light energy. The fractal structures of tree crown and roots is shown to be a qualitative characteristic of the tree growth process. The model of growth and root systems interacting for two trees is built. Depending on the initial conditions, the trees could reach the same or different sizes.

Текст научной работы на тему «Модели роста и взаимодействия деревьев»

С. Б. Медведев \ А. И. Пестунов \ И. А. Пестунов \ А. М. Федотов 1 2

1 Институт вычислительных технологий СО РАН пр. Акад. Лаврентьева, 6, Новосибирск, 630090, Россия


2 Новосибирский государственный университет ул. Пирогова, 2, Новосибирск, 630090, Россия

serbormed@gmail.com, aps@ict.sbras.ru,pestunov@ict.nsc.ru fedotov@nsu.ru

МОДЕЛИ РОСТА И ВЗАИМОДЕЙСТВИЯ ДЕРЕВЬЕВ

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

Ключевые слова: модель роста дерева, фрактальная структура дерева, взаимодействие корневых систем деревьев.

Для изучения динамики лесных ценозов и разработки эффективных стратегий управления лесным хозяйством, обеспечивающих оптимальные сценарии восстановления и развития леса, широко применяются методы математического и компьютерного моделирования. В настоящее время наиболее популярными являются статистические модели регрессионного типа [1], имитационные [2; 3] и аналитические модели [4; 5].

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

Имитационные модели содержат большое число трудно контролируемых входных параметров. Эти модели достаточно точно описывают динамику лесных объектов, но не позволяют изучать влияние отдельных параметров на качественное поведение системы.

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

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

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

Медведев С. Б., Пестунов А. И., Пестунов И. А., Федотов А. М. Модели роста и взаимодействия деревьев // Вестн. Новосиб. гос. ун-та. Серия: Информационные технологии. 2015. Т. 13, вып. 2. С. 42-54.

ISSN 1818-7900. Вестник НГУ. Серия: Информационные технологии. 2015. Том 13, выпуск 2 © С. Б. Медведев, А. И. Пестунов, И. А. Пестунов, А. М. Федотов, 2015

вать параметры, которые можно реально измерить. Такими параметрами, например, служат линейные размеры дерева. В лесном хозяйстве процесс роста дерева принято характеризовать и измерять через диаметр ствола «на уровне груди» (

1,3 м). В предлагаемой модели для удобства расчета ее параметров выберем в качестве переменной радиус ствола «на уровне груди» Я, а для описания роста маленьких деревьев и саженцев — просто радиус ствола. Будем предполагать, что радиус ствола Я не уменьшается.

Модели роста деревьев

в ситуации целых пространственных размерностей

Одним из лимитирующих факторов роста дерева является наличие азотфиксирующих микроорганизмов, которые усваивают азот из атмосферного воздуха. По заключению Г. А. Заварзина [6], круговорот азота, серы и железа находится целиком под контролем кооперативной бактериальной системы, в том числе и систем почвы. Поскольку в таежной зоне основная масса корней залегает в поверхностном слое от 30 до 70 см, и толщина этого слоя сопоставима с радиусом ствола больших деревьев, это позволяет рассматривать рост корней в плоскости, т. е. с пространственной размерностью 2. Следует заметить, что минеральные породы, содержащие фосфор, калий и другие элементы, а также водоносный слой могут залегать достаточно глубоко, поэтому рассмотрение плоской корневой системы для данных ресурсов не всегда оправдано. Крону дерева будем считать «объемной», т. е. развивающейся с пространственной размерностью 3.

Итак, для больших деревьев полагаем, что радиус корневой системы пропорционален радиусу ствола на уровне груди с некоторым коэффициентом 5, зависящим от вида дерева и условий местности, т. е. К = 5-Я, причем 5 > 1, т. е. корни шире ствола. Поток Р1, который описывает получение питательных веществ деревом из почвы, пропорционален площади корневой системы Р1 =%■ К2 =%■ (5 — Я)2.

Поток веществ от корней идет через ствол на снабжение кроны дерева, заключенной в описанной сфере радиуса V — Я, где V > 1, т. е. радиус шара кроны больше радиуса ствола. Форма кроны ели, например, имеет ярко выраженную форму конуса. Для берез точнее будет выбирать форму кроны ближе к цилиндру, объем кроны свободно растущего кедра может стремиться к объему шара. Пусть коэффициент к, 0 1. Ствол дерева будем пред-

ставлять цилиндром с образующей I

к- Я и «средним» радиусом —. Поток вещества для

прироста ствола взрослого дерева определяется приращением объема ствола

СУ(Я) = п-к-Я2 — СЯ (рис. 1). Таким образом, получим третий поток Р3 =п-к-Я2—.

Модель роста одиночного дерева

при условии ограничения питательных веществ почвы

При ограничении питательных веществ почвы они распределяются на рост кроны и рост

ствола. Уравнение баланса потоков при условии ограничения веществ почвы выглядит так:

Р = Р2 + Р3, ^-(5-Я)2 = 3-к-(V-Я)3 к-Я2-С.. (1)

Учитывая, что Я > 0, мы можем поделить на Я2 и найти притягивающую стационарную величину Яя для радиуса ствола:

л Ж 2 4 , з „ „ 3 • 52 0 = — = 52—к • V3 • Яп ^ Яп = ■

При начальном значении R0 = Rst в рамках данной модели ствол и крона дерева не растут, питательные вещества почвы расходуются на поддержание текущего состояния дерева. При R0 > RSt имеет место сильный недостаток усваиваемых питательных веществ от корней, а поскольку по предположению модели радиус ствола не может уменьшаться, то крона дерева деградирует и нижние ветки отмирают. Коэффициенты к и v приближаются к критическим значениям: <к • v3 )^(к • v3

)Critjcal. Таким образом, в нашей модели при изначальном уменьшении объема кроны баланс потока веществ (1) смещается, и значение притягивающего стационарного состояния для переменной ствола дерева увеличивается. В том случае, когда листьев или хвои останется достаточно для поддержания стабильного уровня энергии, поступающей из кроны, питательные вещества почвы будут расходоваться на поддержание процессов в стабильном состоянии. Если же крона уменьшится до критического уровня, то возникнет дефицит в получаемой энергии света и одновременно дефицит веществ почвы. Более детально эта ситуация рассматривается ниже. При начальных данных R0 0, и дифференциальное уравнение первого по-

dR s2 4 • к • v3 „ Л

рядка примет следующий вид: — =—-R. Оно имеет решение, для нахождения ко-

торого обозначим a = —, b =-. Проинтегрируем уравнение с разделяющимися

f dR Г, 1П(a -b • R) 1n(a-b-R) -b


переменными -= \dt ^—— = t + Const ^ e 1 ‘= e Най-

дем константу из начальных данных (t = 0, R = R0): Const =—b- , запишем R как

функцию от времени и перейдем к исходным обозначениям:

R(t) = a -e ^ b a -e-bt •(a -b • R)

52 -e 3h -I 52—k-v3-R

Вывод 1. При недостатке только питательных веществ почвы и при Я0 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Утверждение 1. Если в начальный момент времени радиус ствола одного дерева был больше радиуса ствола второго, со сходными параметрами, т. е. Яя > Я0 > г0, то в последующие моменты времени это неравенство сохраняется:

+ — — e 3 — h -k-v3 — r0 3,

и радиусы стволов обоих деревьев стремятся к предельному Яя .

Вывод 2. Если предположить, что Яя соответствует средней высоте взрослых деревьев

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

Модель роста одиночного дерева при условии ограничения энергии света

Запишем уравнение баланса потоков при условии ограничения поступающей из кроны энергии:

i: P2 = P1 + P3, — — k — (v — R)3 = (5 — R)2 + h — R2 -ddR. При R, = Rst, как и в предыду-3 dt

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

52 + в1Г*-I4-k-v3-R0 — 52 I

V J Энергетическое ограничение л ‘

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

энергии, при условии постоянства параметров модели с целыми пространственными размерностями корней и кроны, рост ствола дерева не ограничен во времени. Это происходит из-за того, что крона объемная или, точнее, размерность кроны превосходит размерность корней. Однако из наблюдений дробная фрактальная размерность кроны меньше трех, и коэффициент величины кроны V возводится в степень (2 + Да) Яя .

Подробнее о рассмотрении дерева как фрактала можно прочитать в работе [7].

Модель роста одиночного дерева

при условии одновременного ограничения усвоения энергии света и питательных веществ почвы

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

во-вторых, обратное: недостаток в питательных веществах почвы, например азота К, приводит к угнетению кроны и дополнительному недостатку в энергии фотосинтеза. Одновременное ограничение в питании от корней и энергии от кроны определим различными моделями для разных начальных данных. Важно отметить, что искать решения для радиуса ствола модели с одновременными ограничениями на потоки вещества и энергии надо для области во времени, при которой эти решения не превосходят решение при ограничении для вещества и энергии в отдельности. Необходимо также учесть, что при начальных данных таких, что Я0 = Яя, эволюция ствола дерева остается неопределенной в рамках модели с целыми пространственными размерностями. Если же корни тоже считать объемными, т. е. растущими вглубь земли, то неопределенность появится при соотношении т-53 = 2- к^3, где коэффициент т вычисляется как доля в объеме полушара, в котором заключены корни, однако этот коэффициент без специальных приборов оценить невозможно. Учитывая результаты предыдущих моделей, можно сделать вывод, что подобные точки и их окрестности соответствуют умеренной нехватке в потоках энергии от кроны и веществ от корней дерева. Таким образом, в модели ограничений на вещества и энергию мы выколем особую точку Яя и рассмотрим

две ситуации: I при Я0 > Яя, II при Я0 Ят,

V /Энергетическое ограничение и г>1

Я0)М , Я0 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Модель информационного множества против модели дерева XSLT

Модель информационного множества против модели дерева XSLT

Разборщики XML передают только определенную информацию: как задается основной спецификацией информационного множества (Information Set) XML — которую можно найти по адресу www.w3.org/TR/xml-infoset, в то время как процессоры XSLT придерживаются модели дерева XSLT. Эти модели, а также элементы, считающиеся в них важными, различны, что может привести к проблемам.

Вот, например, два элемента XML, входящие в основное информационное множество, но невозможные в XSLT: примечания и пропущенные ссылки на сущности (ссылки на сущности, которые разборщик XML предпочел не раскрывать). На практике это означает, что даже если разборщик XML передал информацию для этих пунктов, процессор XSLT ничего не сможет с ней сделать. Однако примечания используются редко, и только отдельные разборщики XML генерируют пропущенные ссылки на сущности, поэтому это не является значимой проблемой.

С другой стороны, разборщики XML могут удалить из XML-документов комментарии, о чем вам следует знать, так как в модели XSLT комментарии включаются.

Кроме того, информация об объявлениях DTD не передается от разборщика XML в процессор XSLT (возможно, потому, что W3C планирует более широко использовать схемы XML в XSLT 2.0, хотя пока еще нет официального механизма связывания схем XML с документами XML). Как правило, это не образует проблемы, поскольку проверка документа XML входит в задачи разборщика XML, за исключением одного случая: когда атрибут объявлен с типом ID. В XML с типом ID можно объявить атрибут с любым именем, поэтому процессор XSLT не знает, какие атрибуты принадлежат к этому типу, если только у процессора нет доступа к DTD. Это важно при использовании таблиц стилей, встроенных в документы XML, поскольку в этом случае процессор XSLT должен быть способен распознать, в каком элементе документа содержится таблица стилей, нужная для преобразования документа. В этом случае некоторые процессоры XSLT, например, Saxon, идут дальше рекомендации XSLT и проверяют DTD, если они есть, чтобы узнать, какие атрибуты принадлежат к типу ID.

Еще несколько моментов могут представлять для вас интерес. Например, модель обработки XSLT открывает доступ к префиксам пространств имен во входном дереве, но предоставляет очень небольшие возможности управления ими в выходном дереве, где они обрабатываются автоматически. К тому же, в модели обработки XSLT для каждого узла в дереве определяется базовый URI, представляющий собой URI внешней сущности, от которой был произведен узел. (В рабочем проекте XSLT 1.1 эти возможности были расширены для поддержки спецификации XML Base, как вы увидите ближе к концу этой главы.) Однако в информационном множестве XML базовые URI считаются второстепенными, а это означает, что разборщик XML может не передать эту информацию в процессор XSL.

В общем, вам следует знать, что процессоры XSLT читают документы XML при помощи разборщиков XML, и что совместная работа этих программных единиц не бесшовна. Если вы обнаружите, что некоторая необходимая информация при преобразовании XSLT пропала, следует вспомнить этот момент. Фактически различие между информационным множеством XML и моделью дерева XSLT — это одна из проблем, которую призван исправить XSLT 2.0. Помимо прочего, в XSLT 2.0 должно быть проще восстанавливать ID и ключевую информацию из исходного документа, а также восстанавливать информацию из объявления XML исходного документа — например, версию XML и кодировку.

Руководство к использованию деревьев решений в машинном обучении и науке о данных

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

Деревья решений в реальной жизни


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

Этот пример хорошо демонстрирует дерево решений в реальной жизни. Мы построили дерево и смоделировали ряд последовательных, иерархических решений, которые, в конечном итоге, приводят к некоторому результату. Обратите внимание, что мы выбрали максимально общие варианты решения, чтобы дерево было маленьким. Дерево будет просто огромным, если мы установить много возможных вариантов погоды, например: 25 градусов, солнечно; 25 градусов, дождливо; 26 градусов, солнечно; 26 градусов, дождливо; 27 градусов, солнечно; 27 градусов, дождливо и т.д. Конкретная температура не важна. Нам нужно лишь знать, будет ли погода хорошей или нет.

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

Деревья решений в машинном обучении

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

Индукция

Индукция дерева решений проходит 4 главных этапа построения:

  1. Начните с обучающего набора данных, в котором должны содержаться признаки переменных и результаты классификации или регрессии.
  2. Определите «лучший признак » в наборе данных для их разбиения. О том, как определить этот «лучший признак » поговорим позже.
  3. Разбейте данные на подмножества, которые будут содержать возможные значения для лучшего признака. Такое разбиение в основном определяет узел на дереве, то есть каждый узел — это разделенная точка, основанная на определенном признаке из наших данных.
  4. Рекурсивно сгенерируйте новые узлы дерева с помощью подмножества данных, созданных на 3 этапе. Продолжайте разбиение до тех пор, пока не достигните точки, на которой будет находится оптимизированная каким-то способом максимальная точность. Старайтесь минимизировать количество разбиений и узлов.

Первый этап простой. Просто соберите свой набор данных!

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

Для дерева регрессии можно использовать простой квадрат ошибки в качестве функции стоимости:

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

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

Такая концепция единственного класса на узел в наборе данных называется «прирост информации». Посмотрите на пример ниже.

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

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

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

Отсечение

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

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

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

Пример в Scikit-learn

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

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

Кроме того, в Scikit-learn можно указать несколько параметров для модели дерева решений. Ниже приведем некоторые из таких параметров, позволяющих получить лучший результат:

  • max_depth: максимальная глубина дерева — точка, на которой останавливается разбиение узлов. Это похоже на выбор максимального количества слоев в глубокой нейронной сети. Меньшее количество сделает модель быстрой, но не точной. Большее количество увеличивает точность, но создает риски переобучения и замедляет процесс.
  • min_samples_split: необходимое минимальное количество выборок для разбиения узлов. Мы уже обсуждали это выше вместе с тем, как настроить высокое значение, чтобы минимизировать переобучение.
  • max_features: число признаков для поиска лучшей точки для разбиения. Чем больше число, тем лучше результат. Но в этом случае обучение займет больше времени.
  • min_impurity_split: порог для ранней остановки роста дерева. Узел разобьется только в том случае, если его точность будет выше указанного порога. Такой метод может служить в качестве компромисса между минимизацией переобучения (высокое значение, маленькое дерево) и высокой точностью (низкое значение, большое дерево).
  • presort: выбор того, нужно ли предварительно сортировать данные для ускорения поиска наилучшего разбиения при подборе. Если данные заранее отсортируются по каждому признаку, то алгоритму обучения будет гораздо проще найти хорошие значения для разбиения.

Советы по практическому применению деревьев решений

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

Дерево составляющих

Читайте также:

  1. V. «Дерево целей» фирмы.
  2. Анализ балансовой прибыли и ее составляющих
  3. Влияние побочных составляющих
  4. Выезд работников, осведомленных в сведениях, составляющих гос.т за границу.
  5. Генеалогическое дерево
  6. Гинкго двулопастный — дерево высотой до 40 метров и диаметром ствола до 4,5 м. Крона вначале пирамидальная, с возрастом разрастается.
  7. Дайте определение систематической и случайной составляющих погрешности измерений.
  8. Дерево высотой до 20 м или кустарник с узко-яйцевидной кроной и стволом диаметром до 50 см. Кора светло-серая, гладкая. Молодые ветви пушистые, не клейкие.
  9. Дерево каталогов
  10. Дерево решений
  11. Дерево решений

Следует подчеркнуть, что деревья зависимостей дают возможность рассматривать направленные связи, но только между отдельными словами, системы составляющих характеризуют синтаксическую структуру предложения иначе — с их помощью словосочетания (или синтагмы) описываются в явном виде, но игнорируется ориентация связей (т.е. не различаются «хозяин» и «слуга»).

Синтагма — совокупность нескольких слов, объединённых по принципу семантико-грамматической сочетаемости, единица синтагматики. Объём конкретной синтагмы определяется не только реальным употреблением слов в связке, но и самой возможностью объединения предметов, признаков и процессов окружающей действительности. Минимальной длиной синтагмы следует считать простые словосочетания.

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

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

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


Рисунок 9.5 – Схема связей

Здесь S — символ предложения, А – прилагательное, N – существительное, V глагол, Аdv – наречие, NР – именная группа, VР — глагольная группа.

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

Пусть х — произвольная непустая цепочка. Множество С отрезков це­почки х называется системой составляющих этой цепочки, если оно удовлетворяет двум условиям:

1) множество С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки x;

2) любые два отрезка из С либо не пересекаются, либо один из них содержится в другом.

Элементы С называются составляющими. Одноточечные от­резки называются точечными (тривиальными) составляющими.

При описании предложений естественного языка с помощью системы составляющих обычно используют размеченную систе­му составляющих, т. е. тройку , где С — система со­ставляющих, W — множество меток и φ — отображение С в 2 W . Поясним введенное определение на примере. Пусть цепочка ω имеет вид agbacdef. Определим на ней две системы составляю­щих C1 и С2. Для наглядного изображения системы составляю­щих будем заключать каждую нетривиальную составляющую в скобки, причем левую и правую скобки, отвечающие одной со­ставляющей, помечать одинаковой меткой, так чтобы разные па­ры скобок были помечены разными метками. В качестве меток можно использовать числа.

1 2 3 4 5 5 4 321

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

Система составляющих предложения указывает в нем словосочетания разных «уровней» не вводя при этом никакой иерархии среди словосочетаний од­ного уровня. Между тем в предложении естественного языка часто интуитивно ощущается «главенствование» некоторого сло­восочетания над другими, в нем не содержащимися. Для отра­жения указанного факта можно поступить следующим образом. Пусть С — система составляющих цепочки х. Для каждой пото­чечной составляющей АÎС выделим в множестве всех состав­ляющих, непосредственно вложенных в А, какую-либо одну со­ставляющую A’, которую будем называть главной. Множество всех главных составляющих обозначим через С’ и назовем иерархизацией системы С. Упорядоченную пару назовем иерархизированной системой составляющих.

В грамматике НС представление о двусоставности предложения сохранено. Но члены предложения (синтаксические функции) определяются в этой теории на основе формальных признаков: не по отношению к их возможному или реальному семантическому содержанию, а по отношению к тому месту, которое они занимают в дереве порождения предложения. Как уже было сказано, верхний узел дерева обозначается символом S (sentence – предложение). Предложение анализируется как конструкция, включающая две НС – именную группу (NP, noun phrase) и глагольную группу (VP, verb phrase). Подлежащее и сказуемое могут быть соответственно определены как узлы, непосредственно подчинённые узлу S. Дополнение может квалифицироваться как узел, который подчинён узлу VP. НС – структуру предложения можно представить в виде древовидного графа и в скобочной записи (значение символов: S – предложение, NP – именная группа, VP – глагольная группа, Adj – прилагательное, N – существительное, V – глагол). Например, для предложения Маленькие дети доставляют большие хлопоты скобочная запись будет иметь вид:

Дерево же составляющих показано на рисунке 9.6.

Рисунок 9.6. – Дерево составляющих для предложения

Маленькие дети доставляют большие хлопоты

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

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

Формальные грамматики работают, как правило, с синтаксическим представлением в виде дерева составляющих.

Грамматика деревьев служит не для порождения предложений, а для преобразования деревьев, интерпретируемых как деревья подчинения или деревья составляющих, например грамматика – система правил преобразования деревьев, интерпретируемых как «чистые» деревья подчинения предложений (без линейного порядка слов).

| следующая лекция ==>
Граф зависимости | Грамматики синтаксического уровня

Дата добавления: 2014-01-11 ; Просмотров: 3933 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Множественная модель деревьев

Personnel:
emp boss salary
==========================
‘Jerry’ NULL 1000.00
‘Bert’ ‘Jerry’ 900.00
‘Chuck’ ‘Jerry’ 900.00
‘Donna’ ‘Chuck’ 800.00
‘Eddie’ ‘Chuck’ 700.00
‘Fred’ ‘Chuck’ 600.00

Эта модель имеет преимущества и недостатки. ПЕРВИЧНЫЙ КЛЮЧ — emp, но столбец boss — функционально зависит от него, следовательно мы имеем проблемы с нормализацией. REFERENCES не даст вам возможность указать начальником, того кто не является сотрудником. Однако, что произойдет, когда ‘Jerry’ изменяет имя на ‘Geraldo’, чтобы получить телевизионное ток-шоу? Вы также должны сделать каскадные изменения в строках ‘Bert’ и ‘Chuck’.
Другой недостаток этой модели — то трудно вывести путь. Чтобы найти имя босса для каждого служащего, используется самообъединяющийся запрос, типа:

delphi
SELECT B1.emp, ‘bosses’ , E1.emp
FROM Personnel AS B1, Personnel AS E1
WHERE B1.emp = E1.boss;

Но кое-что здесь отсутствует. Этот запрос дает Вам только непосредственных начальников персонала. Босс Вашего босса также имеет власть по отношению к Вам, и так далее вверх по дереву. Чтобы вывести два уровня в дереве, Вам необходимо написать более сложный запрос самообъединения, типа:

delphi
SELECT B1.emp, ‘bosses’ , E2.emp
FROM Personnel AS B1, Personnel AS E1, Personnel AS E2
WHERE B1.emp = E1.boss AND E1.emp = E2.boss;

Чтобы идти более чем на два уровня глубже в дереве, просто расширяют образец:

delphi
SELECT B1.emp, ‘bosses’ , E3.emp
FROM Personnel AS B1, Personnel AS E1,
Personnel AS E2, Personnel AS E3
WHERE B1.emp = E1.boss
AND E1.emp = E2.boss
AND E2.emp = E3.boss;

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

delphi
SELECT *
FROM Personnel AS E1
WHERE NOT EXISTS(
SELECT *
FROM Personnel AS E2
WHERE E1.emp = E2.boss);

У корня дерева boss — NULL:

delphi
SELECT *
FROM Personnel
WHERE boss IS NULL;

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

Total Salaries
emp boss salary
==========================
‘Jerry’ NULL 4900.00
‘Bert’ ‘Jerry’ 900.00
‘Chuck’ ‘Jerry’ 3000.00
‘Donna’ ‘Chuck’ 800.00
‘Eddie’ ‘Chuck’ 700.00
‘Fred’ ‘Chuck’ 600.00

Множественная модель деревьев.
Другой путь представления деревьев состоит в том, чтобы показать их как вложенные множества. Это более подходящая модель, т.к. SQL — язык, ориентированный на множества. Корень дерева — множество, содержащее все другие множества, и отношения предок-потомок описываются принадлежностью множества потомков множеству предка.
Имеются несколько способов преобразования организационной диаграммы во вложенные наборы. Один путь состоит в том, чтобы вообразить, что Вы перемещаете подчиненные «овалы» внутри их родителей, использующих линии края как веревки. Корень — самый большой овал и содержит все другие узлы. Листья — самые внутренние овалы, ничего внутри не содержащие, и вложение соответствует иерархическим отношениям. Это — естественное представление модели «перечень материалов», потому что заключительный блок сделан физически из вложенных составляющих, и разбирается на отдельные части.
Другой подход состоит в том, чтобы представить небольшой червь, ползающий по «узлам и дугам» дерева. Червь начинает сверху, с кореня, и делает полную поездку вокруг дерева.
Но теперь давайте представим более сильный червь со счетчиком, который начинается с единицы. Когда червь прибывает в узел, он помещает число в ячейку со стороны, которую он посетил и увеличивает счетчик. Каждый узел получит два номера, одино для правой стороны и одино для левой стороны.
Это дает предсказуемые результаты, которые Вы можете использовать для формирования запросов. Таблица Personnel имеет следующий вид, с левыми и правыми номерами в виде:

delphi
CREATE TABLE Personnel(
emp CHAR ( 10 ) PRIMARY KEY,
salary DECIMAL( 6 , 2 ) NOT NULL,
left INTEGER NOT NULL,
right INTEGER NOT NULL);

Personnel
emp salary left right
==============================
‘Jerry’ 1000.00 1 12
‘Bert’ 900.00 2 3
‘Chuck’ 900.00 4 11
‘Donna’ 800.00 5 6
‘Eddie’ 700.00 7 8
‘Fred’ 600.00 9 10

Корень всегда имеет 1 в левом столбце и удвоенное число узлов (2*n) в правом столбце. Это просто понять: червь должен посетить каждый узел дважды, один раз с левой стороны и один раз с правой стороны, так что заключительный количество должено быть удвоенное число узлов во всем дереве.
В модели вложенных множеств, разность между левыми и правыми значениями листьев — всегда 1. Представте червя, поворачивающегся вокруг листа, пока он ползет по дереву. Поэтому, Вы можете найти все листья следующим простым запросом:

delphi
SELECT *
FROM Personnel
WHERE (right — left) = 1 ;

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

delphi
SELECT *
FROM Personnel
WHERE left = (right — 1 );

Причина увеличения производительности в том, что SQL может использовать индекс по левому столбцеу, когда он не испорльзуется в выражении. Не используйте (left — right) = 1, потому что это дает воспользоваться преимуществами индекса.
В модели вложенных — имножеств, пути показываются как вложенные множества, которые представлены номерами вложенных множеств и предикатами BETWEEN. Например, чтобы определить всех боссов определенного сотрудника необходимо написать:

delphi
SELECT :myworker, B1.emp, (right — left) AS height
FROM Personnel AS B1, Personnel AS E1
WHERE E1.left BETWEEN B1.left AND B1.right
AND E1.right BETWEEN B1.left AND B1.right
AND E1.emp = :myworker;

Чем больше height, тем дальше по иерархии босс от служащего. Модель вложенных множеств использует факт, что каждое содержащее другие множество является большим в размере (где размер = (right — left)) чем множества, в нем содержащиеся. Очевидно, корень будет всегда иметь самый большой размер.
Уровень, число дуг между двумя данными узлами, довольно просто вычислить. Например, чтобы найти уровни между заданным рабочим и менеджером, Вы могли бы использовть:

delphi
SELECT E1.emp, B1.emp, COUNT(*) — 1 AS levels
FROM Personnel AS B1, Personnel AS E1
WHERE E1.left BETWEEN B1.left AND B1.right
AND E1.right BETWEEN B1.left AND B1.right
AND E1.node = :myworker
AND B1.node = :mymanager;

(COUNT(*) — 1) используется для того, чтобы удалить двойной индекс узла непосредственно как нахождение на другом уровне, потому что узел — нулевые уровни, удаленные из себя.
Вы можете построить другие запросы из этого шаблона. Например, чтобы найти общих боссов двух служащих, объединяют пути и находят узлы который имеют (COUNT(*) > 1). Чтобы найти самых близких общих предков двух узлов, объединяют пути, находят узлы, которые имеют (COUNT(*) > 1), и выбирают с наименьшей глубиной.

delphi
SELECT ‘Mary’ ,
P1.emp, (P1.rgt — P1.lft) AS size
FROM Personnel AS P1, Personnel AS P2
WHERE P2.emp = ‘Mary’
AND P2.lft BETWEEN P1.lft AND P1.rgt;


Mary emp size
==== === ====
Mary Albert 27
Mary Charles 13
Mary Fred 9
Mary Jim 5
Mary Mary 1

Заметьте, что, когда size = 1, Вы имеете дело С Мэри как с ее собственным боссом. Вы можете исключить этот случай.
Модель вложенная множеств использует факт, что каждый вешний набор имеет больший size (size = right — left) чем множества, которые оно содержит. Очевидно, корень будет всегда иметь самый большой size. JOIN и ORDER BY не нужны в модели вложенных множеств, как модели графа смежности. Плюс, результаты не зависят от порядка, в котором отображаются строки.
Уровень узла — число дуг между узлом и корнем. Вы можете вычислять уровень узла следующим запросом:

delphi
SELECT P2.emp, COUNT(*) AS level
FROM Personnel AS P1, Personnel AS P2
WHERE P2.lft BETWEEN P1.lft AS P2
GROUP BY P2.emp;

Этот запрос находит уровни среди менеджеров, следующим образом:

emp level
=== =====
Albert 1
Bert 2
Charles 2
Diane 2
Edward 3
Fred 3
George 3
Heidi 3
Igor 4
Jim 4
Kathy 4
Larry 4
Mary 5
Ned 5

В некоторых книгах по теории графов, корень имеет нулевой уровнь вместо первого. Если Вам нравится это соглашение, используйте выражение «(COUNT(*)-1)».
Самообъединения в комбинации с предикатом BETWEEN- основной шаблон для других запросов.
Агрегатные функции в деревьях.
Получение простой суммы зарплаты подчиненных менеджера работает на том же самом принципе. Заметьте, что эта общая сумма будет также включать зарплату босса:

delphi
SELECT P1.emp, SUM (P2.salary) AS payroll
FROM Personnel AS P1, Personnel AS P2
WHERE P2.lft BETWEEN P1.lft AND P1.rgt
GROUP BY P1.emp;

emp payroll
=== =======
Albert 7800.00
Bert 1650.00
Charles 3250.00
Diane 1900.00
Edward 750.00
Fred 1600.00
George 750.00
Heidi 1000.00
Igor 500.00
Jim 300.00
Kathy 100.00
Larry 100.00
Mary 100.00
Ned 100.00

поддеревьев
Следующий запрос будет брать уволенного служащего как параметр и удалять поддерево, расположенное под ним/ней. Уловка в этом запросе — то, что Вы используете ключ, но Вы должны заставить работать левые и правые значения. Ответ — набор скалярных подзапросов:

delphi
DELETE FROM Personnel
WHERE lft BETWEEN
(SELECT lft FROM Personnel WHERE emp = :downsized)
AND
(SELECT rgt FROM Personnel WHERE emp = :downsized);

Проблема состоит в том, что после этого запроса появляются промежутки в последовательности номеров множеств. Это не мешает выполнять большинство запросов к дереву, т.к. свойство вложения сохранено. Это означает, что Вы можете использовать предикат BETWEEN в ваших запросах, но другие операции, которые зависят от плотности номеров, не будут работать в дереве с промежутками. Например, Вы не сможете находить листья, используя предикат (right-left=1), и не сможете найти число узлов в поддереве, используя значения left и right его корня.
К сожалению, Вы потеряли информацию, которая будет очень полезна в закрытии тех промежутков — а именно правильные и левые номера корня поддерева. Поэтому, забудьте запрос, и напишите вместо этого процедуру:

delphi
CREATE PROCEDURE DropTree (downsized IN CHAR ( 10 ) NOT NULL)
BEGIN ATOMIC
DECLARE dropemp CHAR ( 10 ) NOT NULL;
DECLARE droplft INTEGER NOT NULL;
DECLARE droprgt INTEGER NOT NULL;

—Теперь сохраним данные поддерева:

SELECT emp, lft, rgt
INTO dropemp, droplft, droprgt
FROM Personnel
WHERE emp = downsized;

—Удаление, это просто.

DELETE FROM Personnel
WHERE lft BETWEEN droplft and droprgt;

—Теперь уплотняем промежутки:

UPDATE Personnel
SET lft = CASE
WHEN lft > droplf
THEN lft — (droprgt — droplft + 1 )
ELSE lft END ,
rgt = CASE
WHEN rgt > droplft
THEN rgt — (droprgt — droplft + 1 )
ELSE rgt END ; END ;

Реальная процедура должна иметь обработку ошибок, но я оставляю это как упражнение для читателя.
Удалениеузла
Удаление одиночного узла в середине дерева тяжелее чем удаление полных поддеревьев. Когда Вы удаляете узел в середине дерева, Вы должны решить, как заполнить отверстие. Имеются два пути. Первый метод к повышает одного из детей к позиции первоначального узла (предположим, что отец умирает, и самый старший сын занимает бизнес, как показано на рисунке 2). Самый старший потомок всегда показывается как крайний левый дочерний узел под родителем. Однако с этой этой операцией имеется проблема. Если старший ребенок имеет собственнх детей, Вы должны решить, как обработать их, и так далее вниз по дереву, пока Вы не добираетесь к листу.
Второй метод для удаления одиночного узла в середине дерева состоит в том, чтобы подключить потомков к предку первоначального узла (можно сказать, что мамочка умирает, и дети приняты бабушкой), как показано на рисунке 3. Это получается автоматически во модели вложенных множеств, Вы просто удаляете узел, и его дети уже содержатся в узлах его предка. Однако, Вы должны быть осторожны, при закрытии промежутка, оставленного стиранием. Имеется различие в изменении нумерации потомков удаленного узла и изменения нумерации узлов справа. Ниже — процедура выполняющая это:

delphi
CREATE PROCEDURE DropNode (downsized IN CHAR ( 10 ) NOT NULL)
BEGIN ATOMIC
DECLARE dropemp CHAR ( 10 ) NOT NULL;
DECLARE droplft INTEGER NOT NULL;
DECLARE droprgt INTEGER NOT NULL;

—Теперь сохраним данные поддерева:

SELECT emp, lft, rgt
INTO dropemp, droplft, droprgt
FROM Personnel
WHERE emp = downsized;

—Удаление, это просто.

DELETE FROM Personnel
WHERE emp = downsized;

—Теперь уплотняем промежутки:

UPDATE Personnel
SET lft = CASE
WHEN lft BETWEEN droplft AND droprgt THEN lft — 1
WHEN lft > droprgt THEN lft — 2
ELSE lft END
rgt = CASE
WHEN rgt BETWEEN droplft AND droprgt THEN rgt — 1
WHEN rgt > droprgt THEN rgt — 2
ELSE rgt END ;
WHERE lft > droplft;
END ;

delphi
CREATE TABLE Personnel
(emp CHAR ( 10 ) PRIMARY KEY,
salary DECIMAL( 8 , 2 ) NOT NULL CHECK(salary > = 0.00 ),
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL,
CHECK(lft INSERT INTO Personnel VALUES ( ‘Albert’ , 1000.00 , 1 , 28 );
INSERT INTO Personnel VALUES ( ‘Bert’ , 900.00 , 2 , 5 );
INSERT INTO Personnel VALUES ( ‘Charles’ , 900.00 , 6 , 19 );
INSERT INTO Personnel VALUES ( ‘Diane’ , 900.00 , 20 , 27 );
INSERT INTO Personnel VALUES ( ‘Edward’ , 750.00 , 3 , 4 );
INSERT INTO Personnel VALUES ( ‘Fred’ , 800.00 , 7 , 16 );
INSERT INTO Personnel VALUES ( ‘George’ , 750.00 , 17 , 18 );
INSERT INTO Personnel VALUES ( ‘Heidi’ , 800.00 , 21 , 26 );
INSERT INTO Personnel VALUES ( ‘Igor’ , 500.00 , 8 , 9 );
INSERT INTO Personnel VALUES ( ‘Jim’ , 100.00 , 10 , 15 );
INSERT INTO Personnel VALUES ( ‘Kathy’ , 100.00 , 22 , 23 );
INSERT INTO Personnel VALUES ( ‘Larry’ , 100.00 , 24 , 25 );
INSERT INTO Personnel VALUES ( ‘Mary’ , 100.00 , 11 , 12 );
INSERT INTO Personnel VALUES ( ‘Ned’ , 100.00 , 13 , 14 );

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

Второй метод для удаления одиночного узла в середине дерева состоит в том, чтобы подключить потомков к предку первоначального узла (можно сказать, что мамочка умирает, и дети приняты бабушкой).
© Joe Celko
DBMS Online — April 1996
Translated by SDM
Деревья в SQL. Часть 3.
Давайте продолжим наше обсуждение модели вложенных множеств для деревьев в SQL. Я не собираюсь рассматривать любую из моих предидущих статей и буду предполагать, что Вы все еще имеете копию таблицы Personnel, которую я использовал для примеров (DBMS, март 1996, страница 24). Если Вы не имеете прошлых выпусков, Вы можете осчастливить моего издателя, приобретя их.
Меня спрашивают, почему я не показываю больше процедурного кода в примерах. Прямо сейчас, ANSI и ISO пробуют договориться о стандартном процедурном языке для триггеров и хранимых процедур называемом SQL/PSM. Однако, этот стандарт еще не утвержден, что означает, что я должен использовать или свой собственный псевдо-код или выбирать одного производителя. Я решил использовать пока Английские комментарии, но я буду начинать использовать SQL/PSM, когда он будет завершен.
Наиболее хитрая часть обработки деревьев в SQL это нахождение способа конвертировать модель матрицы смежности в модель вложенных множеств в пределах структуры чистого SQL. Было бы довольно просто загрузить таблицу матрицы смежности в программу, и затем использовать рекурсивную программу преобразование дерева из учебника колледжа, чтобы построить модель вложенных множеств.
Честно говоря, такое преобразованиме дерева могло бы быть быстрее чем то, что я собираюсь показать Вам. Но я хочу сделать это в чистом SQL, чтобы доказать следующее: Вы можете делать на декларативном языке то же, что Вы можете делать на процедурном языке. Поскольку это обучающее упражнение, я буду объяснять с болезненной детальностью.
Классический подход к решению проблемы состоит в том, чтобы брать самое простой случай проблемы, и смотреть, можете ли Вы применять его к более сложным случаям. Если дерево не имеет узлов, то преобразование просто — ничего не делать. Если дерево имеет один узел, то преобразование простое — устанавливают левое значение в 1 и правое значение в 2. Природа матрицы смежности такова, что Вы можете двигаться только по одному уровню одновременно, так что давайте посмотрим на дерево с двумя уровнями — корень и непосредственные потомки. Таблица модели смежности напоминала бы следующее:

delphi
CREATE TABLE Personnel
(emp CHAR ( 10 ) NOT NULL PRIMARY KEY,
boss CHAR ( 10 ));

emp boss
=================
‘Albert’ NULL
‘Bert’ ‘Albert’
‘Charles’ ‘Albert’
‘Diane’ ‘Albert’

Давайте поместим модель вложенных множеств в ее собственную рабочую таблицу:

delphi
CREATE TABLE WorkingTree(
emp CHAR ( 10 ),
boss CHAR ( 10 ),
lft INTEGER NOT NULL DEFAULT 0 ,
rgt INTEGER NOT NULL DEFAULT 0 );

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

delphi
INSERT INTO WorkingTree
—convert the root node
SELECT P0.boss, P0.boss, 1 ,
2 * (SELECT COUNT(*) + 1
FROM Personnel AS P1
WHERE P0.boss = P1.boss)
FROM Personnel AS P0;

Теперь, Вы должны добавить потомков в таблицу вложенных множеств. Первоначальный босс останется тот же самый. Порядок потомков — естественный порядок ключа; в данном случае emp char(10):

delphi
INSERT INTO WorkingTree
—convert the children
SELECT DISTINCT P0.emp, P0.boss,
2 * (SELECT COUNT(DISTINCT emp)
FROM Personnel AS P1
WHERE P1.emp AND P0.boss IN (P1.emp, P1.boss)),
2 * (SELECT COUNT(DISTINCT emp)
FROM Personnel AS P1
WHERE P1.emp AND P0.boss IN (P1.boss, P1.emp)) + 1
FROM Personnel AS P0;

Фактически, Вы можете использовать эту процедуру, чтобы конвертировать модель матрицы смежности в лес деревьев, каждое из которых — модель вложенных множеств, идентифицированная ее корневым значением. Таким образом, генеалогическое дерево Альберта — набор строк, которые имеют Альберта как предка, генеалогическое дерево Берта — набор строк, которые имеют Берта как предка, и так далее. (Эта концепция иллюстрирована в рисунках 1 и 2.
Поскольку первоначальная таблица матрицы смежности повторяет нелистовые узлы, некорневые узлы, в столбцах emp и boss, таблица WorkingTree дублирует узлы как корень в одном дереве и как потомок в другом. Запрос также будет странно себя вести со значением NULL в столбце boss первоначальной таблицы матрицы смежности, так что Вы будете должны очистить таблицу WorkingTree следующим запросом:

delphi
DELETE FROM WorkingTree
WHERE boss IS NULL OR emp IS NULL;

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

delphi
CREATE PROCEDURE TreeMerge(superior NOT NULL, subordinate NOT NULL)
BEGIN
DECLARE size INTEGER NOT NULL;
DECLARE insert_point INTEGER NOT NULL;
SET size = 2 * (SELECT COUNT(*) FROM WorkingTree WHERE emp = subordinate);
SET insert_point = (
SELECT MIN (lft)
FROM WorkingTree
WHERE emp = subordinate AND boss = superior) — 1 ;

UPDATE WorkingTree
SET boss = CASE WHEN boss = subordinate
THEN CASE WHEN emp = subordinate
THEN NULL
ELSE superior END
ELSE boss END ,

lft = CASE WHEN (boss = superior AND lft > size)
THEN lft + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN lft + insert_point
ELSE lft END
END ,

rgt = CASE WHEN (boss = superior AND rgt > size)
THEN rgt + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN rgt + insert_point
ELSE rgt END
END

WHERE boss IN (superior, subordinate);

—Удаляем избыточные копии корня подчиненного дерева
DELETE FROM WorkingTree WHERE boss IS NULL OR emp IS NULL;

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

delphi
CREATE VIEW AllPairs (superior, subordinate)
AS
SELECT W1.boss, W1.emp
FROM WorkingTree AS W1
WHERE EXISTS( SELECT * FROM WorkingTree AS W2 WHERE W2.boss = W1.emp)
AND W1.boss <> W1.emp;

Но Вы хотели бы получить только одну пару, которую Вы передатите в только что разработанную процедуру. Чтобы переместить одну пару, берем крайнюю левую пару из прошлого запроса:

delphi
CREATE VIEW LeftmostPairs(superior, subordinate)
AS
SELECT DISTINCT superior,
(SELECT MIN (subordinate)
FROM AllPairs AS A2
WHERE A1.superior = A2.superior)
FROM AllPairs AS A1
WHERE superior = (SELECT MIN (superior) FROM AllPairs);

Теперь все, что Вам осталось сделать — поместить этот запрос в ранее разработанную процедуру — и у вас будет процедура, которая сольет вместе лес деревьев слева направо. Используя цикл WHILE, контролируюший наличие значений в LeftmostPairs делайте вызовы процедуры. Это единственная процедуральная структура во всей хранимой процедуре.

Илон Маск рекомендует:  Выравниваем содержимое tcombobox по правую сторону
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL