Алгоритмы поиска маски ориентированы на решение задач сокращения ДИ. Вместе с тем эти алгоритмы могут быть использованы и для решения других задач. В качестве примера приведем задачи классификации объектов, часто встречающиеся в практических приложениях. В подобного рода задачах каждый объект из заданного множества характеризуется некоторой совокупностью признаков, имеющих конкретные числовые (и/или иного типа) значения. Поскольку упомянутая совокупность признаков может иметь большую мощность, то для идентификации предъявленного объекта, характеризуемого конкретным набором значений признаков, потребуется хранить большой объем информации. В этой ситуации проблема сокращения исходной информации эквивалентна проблеме сокращения диагностической информации. Проводя аналогию между задачей классификации объектов по совокупности значений их признаков и задачей сокращения диагностической информации, можно сказать, что упомянутая совокупность признаков в первой задаче идентична ТФН для конкретной неисправности во второй, а полная информация об объектах 1-ой задачи идентична полной ТФН во 2-ой задаче.
Проводя дальнейшую аналогию между задачами классификации и сокращения ДИ с помощью масок обратимся к алгоритмам решения задач классификации с целью их применения к задачам поиска маски, предложенным в [2].
Одним из популярных подходов к решению проблемы сокращения исходной информации является использование механизма деревьев решений.
Деревья решений представляют собой иерархическую структуру классифицирующих правил типа "если ... то ...", имеющую вид дерева. Для того чтобы решить, к какому классу отнести некоторый объект, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная от его корня. Формулировка такого вопроса обычно заключается в проверке значения некоторого атрибута предъявленного объекта. Дуги, исходящие из узла дерева к его потомкам, помечаются вариантами ответов на вопрос, заданный в данном узле. Каждый лист такого дерева соответствует классу со значениями атрибутов, приписанными дугам пути от корня до этого листа.
Таким образом, имея построенное дерево решений, отпадает необходимость в хранении всей совокупности признаков: можно хранить информацию только о тех атрибутах, которые упоминаются в узлах дерева решений.
Для построении деревьев решений часто используется алгоритм C4.5, предложенный в [1]. Напомним основные моменты этого алгоритма.
Пусть задано множество объектов
Построение дерева происходит сверху вниз. Сначала создается
Процесс построения дерева заключается в следующем. Первоначально построим дерево, состоящее только из корня. Следующие шаги необходимо выполнить для каждого листа уже построенного дерева, которому соответствует множество объектов более чем одного класса.
Пусть данному узлу дерева соответствует множество объектов P' P классов из $$C'=\{c_{i_1},\ldots,c_{i_n}\}$$, а $$freq(c_j,P')$$ - количество элементов из множества $$P'$$, принадлежащих классу $$c_j$$. Тогда величина
$$ I(P')=-\sum\limits_{j=1}^{n}{\cfrac{freq(c_{i_j},P')}{|P'|}} \cdot\log_2{\left(\cfrac{freq(c_{i_j},P')}{|P'|}\right)}, $$где $$|P'|$$ - количество элементов в множестве $$P'$$, дает оценку среднего количества информации, необходимой для идентификации объекта из множества $$P'$$.
Если произвести разбиение множества $$P'$$ в зависимости от значений атрибута $$x\in X$$ на $$z_x$$ подмножеств, то ту же оценку, но уже после разбиения, дает выражение
$$I_x(P')=\sum\limits_{j=1}^{z_x}{\cfrac{|P'_j|}{|P'|}}\cdot I(P'_j) $$В принятых обозначениях алгоритм C4.5 состоит из следующих шагов:
Процесс построения дерева заканчивается, когда всем
Для задачи сокращения ДИ признаки, проверяемые в узлах дерева решений, могут быть взяты в качестве элементов маски ДИ.
С учетом обозначений, введенных ранее, множество технических состояний $$S$$ выступает в роли множества $$P$$ для алгоритма C4.5. Это же самое множество $$S$$ представляет набор классов $$C$$, т. е. в нашем случае каждый класс представлен лишь одним объектом в обучающей выборке. СПР представляет исходные данные для построения дерева решений: каждая точка проверки ДУ выполняет роль атрибута объектов, а каждая строка СПР описывает значения этих атрибутов.
Поскольку каждый класс представлен лишь одним объектом в обучающей выборке, то формула (31.1) примет следующий вид:
$$I(P')=\log_2{|P'|}.$$В связи с тем, что возможных значений атрибутов всего два (0 или 1), получаемое дерево решений является бинарным, где в каждом конкретном узле множество $$P'$$ разделяется на два подмножества $$P'_0$$ и $$P'_1$$ в соответствии со значениями атрибута , доставляющего максимум величине
$$ G(x,P')=\log_2{| P'|}-\cfrac{ |P'_0|}{| P'|}\cdot\log_2{| P'_0|}- \cfrac{ |P'_1|}{| P'|}\cdot\log_2{| P'_1|} $$Формула (31.5) получена из (31.3) с учетом (31.4). Очевидно, что $$G(x,P')$$ в (31.5) будет иметь максимум в том случае, если множество $$P'$$ делится по значениям атрибута $$x$$ на два подмножества с равным числом элементов.
Так как количество листьев в результирующем дереве равно $$(N+1)$$, а само дерево является бинарным, можно сделать вывод, что количество внутренних узлов дерева, т. е. узлов, в которых производится проверка значений атрибутов, не превышает величины $$N$$.
При наилучшем исходе алгоритм C4.5 строит идеально
Алгоритм C4.5 ориентирован на построение дерева решений наиболее приближенного к идеально сбалансированному, т. е. на сокращение среднего числа атрибутов, необходимого для идентификации предъявленного объекта. Таким образом, для каждого класса выбирается индивидуальная совокупность атрибутов, необходимая для идентификации его объектов. По сути, построение дерева решений ориентировано на построение алгоритма классификации объекта с минимальным числом шагов и при этом не преследуется цели сокращения используемой информации, необходимой для такого алгоритма. Но в случае сокращения ДИ алгоритм получения реакции на диагностический тест уже известен, а для большего сокращения информации целесообразно найти некое единое множество атрибутов, по которому можно было бы идентифицировать любой объект. Естественно, объединение упомянутых индивидуальных совокупностей для всех классов может иметь существенно большую мощность, чем такое единое множество.
Следующий алгоритм [3], базирующийся на идеях алгоритма C4.5, направлен на нахождение упомянутого единого множества атрибутов.
Отличие предлагаемого алгоритма от алгоритма C4.5 состоит в том, что построение дерева производится по уровням, с выбором одного атрибута для проверки во всех узлах уровня. На начальном уровне присутствует только один узел -
где $$\tilde{P}$$ - совокупность множеств объектов, соответствующих узлам текущего уровня, а величины $$I'(\tilde{P})$$ и $$I'_x(\tilde{P})$$ равны соответственно
$$ I'(\tilde{P})=\sum\limits_{P'\in P}\cfrac{|P'|}{|\tilde{P}|}I(P')$$и
$$ I'_x(\tilde{P})=\sum\limits_{P'\in P}\cfrac{|P'|}{|\tilde{P}|}I_x(P').$$Так же как и в алгоритме C4.5, процесс построения дерева заканчивается, если на очередном уровне каждому узлу дерева будет соответствовать множество объектов одного класса.
Содержательный смысл такого построения состоит в следующем: на каждом уровне дерева выбирается атрибут, проверка которого максимально уменьшает среднее количество информации, необходимой для идентификации любого объекта из множества $$P$$.
Переформулируем последний алгоритм применительно к задаче поиска маски. В этом случае стоит учесть, что роль атрибутов выполняют точки проверки ЦУ. Также обратим внимание на то, что после вычисления множеств, соответствующих вершинам очередного уровня дерева, необходимость в хранении информации о предшествующих уровнях отпадает. Совокупность множеств, соответствующих вершинам очередного уровня дерева, представляет разбиение исходного множества классов - в нашем случае множества $$S$$. Т. е. в ходе очередной итерации алгоритма достаточно по разбиению множества $$S$$, соответствующего предыдущему уровню дерева, построить разбиение, соответствующее очередному уровню.
Разбиение множества технических состояний $$S$$ производится в соответствии со значениями в точках проверки. Каждая точка проверки разбивает множество технических состояний $$S$$ на два блока (подмножества) следующим образом: технические состояния, для которых значение в данной точке проверки равно единице, помещаются в первый блок, а неисправности, для которых значение равно нулю - во второй. Можно производить дальнейшее разбиение каждого из полученных блоков в соответствии со значениями в других точках проверки. Если СПР обладает свойством различения всех технических состояний, то, производя последовательно разбиение множества $$S$$ с помощью всех точек проверки, получим в результате одноэлементные блоки.
В целях решения задачи оптимизации маски можно ввести ограничение объема полученной маски. Такое ограничение будет заключаться в установке предельного значения количества уровней дерева, или, другими словами, определении числа итераций алгоритма.
Итак, исходя из изложенного, сформулируем формальное описание алгоритма.
Алгоритм 1 ( Жадный алгоритм поиска единой маски ДИ ).
Вход: Словарь полной реакции; $$S$$ - множество технических состояний; $$M$$ - максимальный объем маски результата (по умолчанию $$M=|S|-1$$).
Выход: $$h$$ - маска ДИ.
Замечение 1. Ограничение объема возвращаемой маски в алгоритме 1 по умолчанию числом $$(|S|-1)$$ носит условный характер, так как при отказе от этого ограничения объем любой маски, полученной с помощью этого алгоритма, не превысит величины $$(|S|-1)$$.
Действительно, при добавлении в алгоритме очередной точки проверки в маску $$h$$ происходит дополнительное разбиение блоков в $$\tilde{S}_k$$. Из того, что $$S_0=\{S\}$$ следует, что провести разбиение блока из $$\tilde{S}_0$$ на одноэлементные блоки можно максимум за $$|S|-1$$ итераций.
Рассмотрим работу полученного алгоритма на примере схемы C17 (рис. 27.1). Найдем единую маску для СПР, представленного в табл. 27.5. После первых двух шагов алгоритма имеем: $$\tilde{S}_0=\{\{ s_0,s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8\}\}$$, $$J_0=3.16993$$, $$Р=\varnothing$$. На третьем шаге алгоритма получаем следующие результаты:
$$ I'_{1:1}= I'_{1:2}= I'_{3:1}=2.17885,\\ I'_{2:1}=2.40572,\\ I'_{2:2}= I'_{4:1}=2.66667,\\ I'_{3:2}=2.25163,\\ I'_{4:2}=3.16993.$$Следовательно величина (6.9) достигает своего максимума при использовании точек проверки $$1:1$$, $$1:2$$ и $$3:1$$. Выполним шаги Ошибка! Источник ссылки не найден.-Ошибка! Источник ссылки не найден. алгоритма, предполагая, что на третьем шаге выбрана точка проверки $$1:1$$. После первой итерации алгоритма получим
$$ \tilde{S}_0=\{\{ s_0,s_1, s_7,s_8\},\{s_2,s_3,s_4,s_5,s_6\}\}, \\ J_1=2.17885,\\ h=\{1:1\}.$$На третьем шаге следующей итерации алгоритма получаем:
$$ I'_{1:2}=1.19499,\\ I'_{2:1}=1.73440,\\ I'_{2:2}=1.81828,\\ I'_{3:1}= I'_{4:1}=1.77778,\\ I'_{3:2}=1.27886,\\ I'_{4:2}=2.17885.$$что означает однозначный выбор точки проверки $$1:2$$. Ситуация после окончания второй итерации становится следующей:
$$ \tilde{S}_0=\{\{ s_0,s_8\},\{s_1, s_7\},\{s_2,s_3\},\{s_4,s_5,s_6\}\}, \\ J_2=1.19499,\\ h=\{1:1,1:2\}.$$На очередном проходе алгоритма вычисления дают следующие результаты.
$$ I'_{2:1}=0.75054,\\ I'_{2:2}= I'_{3:1}=0.97277,\\ I'_{3:2}=0.44444,\\ I'_{4:1}=0.88889,\\ I'_{4:2}=1.19499.$$откуда получаем
$$ \tilde{S}_0=\{\{ s_0,s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5,s_6\}\}, \\ J_3=0.44444,\\ h=\{1:1,1:2,3:2\}.$$Как видим, после трех итераций алгоритма остались неразличимыми две пары технических состояний $$\{s_0,s_8\}$$ и $$\{s_5,s_6\}$$. Следующая итерация приводит к величинам
$$ I'_{2:1}=I'_{2:2}=I'_{4:1}=0.22222,\\ I'_{3:1}=I'_{4:2}=0.44444$$означающим, что любая из точек проверок $${2:1}$$,$${2:2}$$,$${4:1}$$ различает одну из этих пар состояний. Выбор точки проверки $${2:1}$$ приведет к значениям
$$ \tilde{S}_0=\{\{ s_0\},\{s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5,s_6\}\}, \\ J_4=0.22222,\\ h=\{{1:1},{1:2},{2:1},{3:2}\},$$после чего на пятой итерации получим
$$ I'_{2:2}= I'_{3:1}=I'_{4:2}=0.22222,\\ I'_{4:1}=0$$и включая в маску получим
$$ \tilde{S}_0=\{\{ s_0\},\{s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5\},\{s_6\}\}, \\ J_5=0.22222,\\ h=\{{1:1},{1:2},{2:1},{3:2},{4:1}\},$$На шестой итерации алгоритма получаем значения $$J_5=J_6=0$$, после чего алгоритм завершает свою работу. Результат работы алгоритма - маска $$h=\{{1:1},{1:2},{2:1},{3:2},{4:1}\}$$.
СПР для единой маски, полученной сокращением СПР с помощью алгоритма1, для диагностического теста схемы C17 приведен в табл. 31.1.
| $$s_0$$ | 11011 |
| $$s_1$$ | 10111 |
| $$s_2$$ | 00011 |
| $$s_3$$ | 00001 |
| $$s_4$$ | 01001 |
| $$s_5$$ | 01011 |
| $$s_6$$ | 01010 |
| $$s_7$$ | 10001 |
| $$s_8$$ | 11111 |
Уточним верхнюю оценку объема маски, возвращаемой с помощью алгоритма 1. Но вначале сформулируем следующую лемму, которая потребуется для вывода этой оценки.
Лемма 1. На любом шаге $$k$$ работы алгоритма 1 справедливо неравенство
$$ J_{k+1}\le J_k\left (1 - \cfrac{1}{M}\right),$$где $$M$$ - объем минимальной маски заданного СПР.
Доказательство. Заметим сначала, что для любой точки проверки $$i:j$$ и для любого $$k\ge 0$$ величина (31.9) неотрицательна. Действительно, (31.9) является конкретизацией выражения (31.6) , в котором вместо атрибута $$x$$ используется точка проверки $$i:j$$. Подставляя в (31.5) сначала (31.7) и (31.8), а затем (31.1) и (31.2) получим
$$ J_k-I'_{i:j}(\tilde{S}_k)= \cfrac{1}{|\tilde{S}_k|}\sum\limits_{S'\in\tilde{S}_k}{|S'|\log_2|S'|}-\sum\limits_{S''\in\tilde{S'} }{|S''|\log_2|S''|}$$где $$\tilde{S'}$$ обозначает разбиение множества $$S'$$ согласно значениям точки проверки $$i:j$$. Из того, что каждое слагаемое внешней суммы в (31.11) неотрицательно, следует неотрицательность (31.9). Отсюда вытекает, что последовательность
$$J_1-J_0,J_2-J_1,\ldots,J_k-J_{k-1},\ldots$$- невозрастающая.
Пусть после $$k$$ итераций алгоритма 1 получена маска $$h$$ и величина $$J_k$$ - среднее количество информации, необходимой для идентификации любого технического состояния из блоков разбиения $$\tilde{S}_k$$. Пусть для того чтобы разбить блоки $$\tilde{S}_k$$ на одноэлементные подмножества оптимальным образом, требуется включение в маску $$h$$ дополнительно минимум $$M'$$ точек проверки. Тогда на следующей итерации алгоритма должно выполняться неравенство
$$ J_{k+1}\le J_k\left ( 1-\cfrac{J_k}{M}\right )$$Т. к. $$M' < M$$, из (31.12) следует (31.10).
Теорема 2. Объем маски, полученной с помощью алгоритма 1, не превышает величины
$$ M\cdot\left ( 1+ln\cfrac{|S|\log_2|S|}{2}\right ),$$где $$M$$ - объем минимальной маски заданного СПР.
Доказательство. Согласно лемме 1
$$J_k\le\left (1-\cfrac{1}{M}\right )^k\log_2|S|\le e^{-\cfrac{k}{M}}\log_2|S|$$Исходя из представления (6.7), минимально-возможное ненулевое значение, которое может принимать $$J_k$$, равно $$2/|S|$$.
Пусть $$k_0$$ - максимальное целое число такое, что
$$e^{-\frac{k}{M}}\log_2|S|\ge\cfrac{2}{|S|}$$Тогда для $$k_1=k_0+1$$ будет выполнено $$J_{k_1}< 2/|S|$$.Из (6.13) следует
$$\cfrac{k_1-1}{M}\le ln\cfrac{|S|\log_2|S|}{2} $$что влечет
$$k_1\le 1+M ln\cfrac{|S|\log_2|S|}{2} \le M\left (1+ln\cfrac{|S|\log_2|S|}{2}\right )$$Следствие 1. Объем маски, полученной с помощью алгоритма 1, не превышает величины
$$\min\left\{|S|-1,M\cdot\left (1+ln\cfrac{|S|\log_2|S|}{2}\right )\right\}$$где $$M$$ - объем минимальной маски данного СПР.
Справедливость следствия вытекает из теоремы 2 и замечания к алгоритму.
С точки зрения задачи оптимизации маски представляет интерес получение оценки глубины диагностирования с использованием маски, полученной с помощью алгоритма 1 при ограничении ее объема. В качестве оцениваемой величины возьмем значение диагностического разрешения $$\rho_3$$, определяемое равенством
$$\rho_3=\cfrac{|S|^2-\sum\limits_{S_j}|S_j|^2}{|S|^2-|S|}$$Теорема 3. Пусть для СПР существует оптимальная маска $$\tilde{h}$$ объема $$r$$, а $$\tilde{\rho}_3$$ - величина диагностического разрешения при диагностировании с использованием $$СПР_{\tilde{h}}$$. Тогда, если $$h$$ - маска объема $$r$$, найденная с помощью алгоритма 1, и $$\rho_3$$ - диагностическое разрешение при диагностировании с помощью $$СПР_h$$, то справедливо следующее неравенство
$$\rho_3\ge\rho_3\left(1-\cfrac{1}{e}\right ). $$Доказательство. Разбиение $$\tilde{S}_k$$ на $$k$$-ой итерации алгоритма можно интерпретировать как множество СПН, получаемое при диагностировании с помощью $$СПР_h$$, где $$h$$ - маска, полученная после $$k$$ итераций алгоритма. Обозначим через $$\rho_3(\tilde{S}_k)$$ значение диагностического разрешения при диагностировании с помощью этого $$СПР_h$$.
Очевидно, что последовательность
$$ \rho_3(\tilde{S}_0), \rho_3(\tilde{S}_1),\ldots, \rho_3(\tilde{S}_k),\ldots$$неубывающая. Действительно, на каждой последующей итерации алгоритма $$S_{k+1}$$ получается из $$S_k$$ разбиением одного или нескольких блоков на более мелкие блоки. Диагностическое разрешение (отношение количества различимых пар состояний к общему числу пар состояний) от этого может только увеличиться.
Более того, можно легко показать, что последовательность
$$ \rho_3(\tilde{S}_1)- \rho_3(\tilde{S}_0), \rho_3(\tilde{S}_2)- \rho_3(\tilde{S}_1),\ldots, \rho_3(\tilde{S}_{k+1})- \rho_3(\tilde{S}_k),\ldots$$не возрастает.
Из сказанного следует, что
$$ \rho_3(\tilde{S}_{k+1})\ge \rho_3(\tilde{S}_k)+\cfrac{\tilde{\rho}_3-\rho_3(\tilde{S}_k)}{r}=\cfrac{\tilde{\rho}_3}{r}+\rho_3(\tilde{S}_k)\left (1+\cfrac{1}{r}\right )$$Тогда
$$ \rho_3(\tilde{S}_{r})\ge \cfrac{\tilde{\rho}_3}{r}\left ( \left (1+\cfrac{1}{r}\right ) + \left (1+\cfrac{1}{r}\right )^2 +\ldots + \left (1+\cfrac{1}{r}\right )^{r-1} \right ) =\\ \cfrac{\tilde{\rho}_3}{r}\left ( \cfrac{1-\left (1-\cfrac{1}{r}\right )^r }{\cfrac{1}{r}} \right ) ={\tilde{\rho}_3}\left ( {1-\left (1-\cfrac{1}{r}\right )^r }\right )\ge {\tilde{\rho}_3} \left (1-\cfrac{1}{e}\right )$$Последнее неравенство и доказывает теорему.
Содержательный смысл последней теоремы заключается в том, если маска $$h$$ заданного объема вычислена с помощью алгоритма 1, то потеря в степени диагностирования с использованием $$СПР_h$$ не превосходит 40% от степени диагностирования с $$СПР_{\tilde{h}}$$, построенного с помощью оптимальной маски того же объема.
Теперь перейдем к оценке сложности алгоритма 1.
Теорема 4. Вычислительная сложность алгоритма 1 оценивается величиной $$O(|S|^2m|\tau|)$$. Объем необходимой для функционирования алгоритма памяти равен $$O(|S|)$$.
Доказательство. Оценим сначала вычислительную сложность алгоритма.
Как отмечалось ранее, максимальное количество итераций алгоритма равно $$(|S|-1)$$. На каждой итерации производится поиск точки проверки, доставляющей минимум величине (31.9). Общее количество точек проверки есть $$m|\tau|$$, а для того чтобы подсчитать (31.9) для конкретной точки проверки, необходимо выполнить $$O(|S|)$$ операций для вычисления $$I'_{i:j}$$. Таким образом, общее количество операций в алгоритме
$$(|S|-1)\cdot m|\tau|\cdot O(|S|)=O(|S|^2m|\tau|).$$Оценивая емкостную сложность алгоритма заметим, что в ходе его работы необходима память для хранения текущей маски, разбиения $$\tilde{S}_k$$, счетчика итераций $$k$$ и двух значений $$J_k$$ и $$J_{k+1}$$. Ни одно из значений $$k$$, $$J_k$$ и $$J_{k+1}$$ не превышает по величине $$|S|$$. Суммарное количество элементов в блоках разбиения $$S_k$$ равно $$|S|$$. Согласно следствию из теоремы 2 объем маски не превышает $$|S|$$. Отсюда получаем оценку емкостной сложности, приведенную в формулировке теоремы.
Экспериментальным данным для оценки эффективности алгоритма 1 и еще одного жадного алгоритма, о котором речь пойдет в следующей лекции, на ДИ, порождаемой реальными устройствами, будет посвящена отдельная лекция.
Жадный алгоритм - алгоритм, основанный на принятии локально оптимальных решений на каждом этапе его работы в расчете на возможность получения глобального оптимума.
Дерево принятия решений - граф, обычно применяемый для решения задач классификации объектов. Он представляет собой дерево,на ребрах которого записаны атрибуты, являющиеся аргументами целевой функции, а в листьях записаны значения этой целевой функции. Во всех прочих вершинах дерева записаны атрибуты, по которым различаются классифицируемые объекты.
В лекции описан жадный алгоритм поиска единой маски ДИ, базирующийся на использовании конструкции дерева принятия решений, призводится оценка объема получаемой маски и вычислительной сложности алгоритма.
Алгоритмы поиска маски ориентированы на решение задач сокращения ДИ. Вместе с тем эти алгоритмы могут быть использованы и для решения других задач. В качестве примера приведем задачи классификации объектов, часто встречающиеся в практических приложениях. В подобного рода задачах каждый объект из заданного множества характеризуется некоторой совокупностью признаков, имеющих конкретные числовые (и/или иного типа) значения. Поскольку упомянутая совокупность признаков может иметь большую мощность, то для идентификации предъявленного объекта, характеризуемого конкретным набором значений признаков, потребуется хранить большой объем информации. В этой ситуации проблема сокращения исходной информации эквивалентна проблеме сокращения диагностической информации. Проводя аналогию между задачей классификации объектов по совокупности значений их признаков и задачей сокращения диагностической информации, можно сказать, что упомянутая совокупность признаков в первой задаче идентична ТФН для конкретной неисправности во второй, а полная информация об объектах 1-ой задачи идентична полной ТФН во 2-ой задаче.
Проводя дальнейшую аналогию между задачами классификации и сокращения ДИ с помощью масок обратимся к алгоритмам решения задач классификации с целью их применения к задачам поиска маски, предложенным в [2].
Одним из популярных подходов к решению проблемы сокращения исходной информации является использование механизма деревьев решений.
Деревья решений представляют собой иерархическую структуру классифицирующих правил типа "если ... то ...", имеющую вид дерева. Для того чтобы решить, к какому классу отнести некоторый объект, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная от его корня. Формулировка такого вопроса обычно заключается в проверке значения некоторого атрибута предъявленного объекта. Дуги, исходящие из узла дерева к его потомкам, помечаются вариантами ответов на вопрос, заданный в данном узле. Каждый лист такого дерева соответствует классу со значениями атрибутов, приписанными дугам пути от корня до этого листа.
Таким образом, имея построенное дерево решений, отпадает необходимость в хранении всей совокупности признаков: можно хранить информацию только о тех атрибутах, которые упоминаются в узлах дерева решений.
Для построении деревьев решений часто используется алгоритм C4.5, предложенный в [1]. Напомним основные моменты этого алгоритма.
Пусть задано множество объектов
Построение дерева происходит сверху вниз. Сначала создается
Процесс построения дерева заключается в следующем. Первоначально построим дерево, состоящее только из корня. Следующие шаги необходимо выполнить для каждого листа уже построенного дерева, которому соответствует множество объектов более чем одного класса.
Пусть данному узлу дерева соответствует множество объектов P' P классов из $$C'=\{c_{i_1},\ldots,c_{i_n}\}$$, а $$freq(c_j,P')$$ - количество элементов из множества $$P'$$, принадлежащих классу $$c_j$$. Тогда величина
$$ I(P')=-\sum\limits_{j=1}^{n}{\cfrac{freq(c_{i_j},P')}{|P'|}} \cdot\log_2{\left(\cfrac{freq(c_{i_j},P')}{|P'|}\right)}, $$где $$|P'|$$ - количество элементов в множестве $$P'$$, дает оценку среднего количества информации, необходимой для идентификации объекта из множества $$P'$$.
Если произвести разбиение множества $$P'$$ в зависимости от значений атрибута $$x\in X$$ на $$z_x$$ подмножеств, то ту же оценку, но уже после разбиения, дает выражение
$$I_x(P')=\sum\limits_{j=1}^{z_x}{\cfrac{|P'_j|}{|P'|}}\cdot I(P'_j) $$В принятых обозначениях алгоритм C4.5 состоит из следующих шагов:
Процесс построения дерева заканчивается, когда всем
Для задачи сокращения ДИ признаки, проверяемые в узлах дерева решений, могут быть взяты в качестве элементов маски ДИ.
С учетом обозначений, введенных ранее, множество технических состояний $$S$$ выступает в роли множества $$P$$ для алгоритма C4.5. Это же самое множество $$S$$ представляет набор классов $$C$$, т. е. в нашем случае каждый класс представлен лишь одним объектом в обучающей выборке. СПР представляет исходные данные для построения дерева решений: каждая точка проверки ДУ выполняет роль атрибута объектов, а каждая строка СПР описывает значения этих атрибутов.
Поскольку каждый класс представлен лишь одним объектом в обучающей выборке, то формула (31.1) примет следующий вид:
$$I(P')=\log_2{|P'|}.$$В связи с тем, что возможных значений атрибутов всего два (0 или 1), получаемое дерево решений является бинарным, где в каждом конкретном узле множество $$P'$$ разделяется на два подмножества $$P'_0$$ и $$P'_1$$ в соответствии со значениями атрибута , доставляющего максимум величине
$$ G(x,P')=\log_2{| P'|}-\cfrac{ |P'_0|}{| P'|}\cdot\log_2{| P'_0|}- \cfrac{ |P'_1|}{| P'|}\cdot\log_2{| P'_1|} $$Формула (31.5) получена из (31.3) с учетом (31.4). Очевидно, что $$G(x,P')$$ в (31.5) будет иметь максимум в том случае, если множество $$P'$$ делится по значениям атрибута $$x$$ на два подмножества с равным числом элементов.
Так как количество листьев в результирующем дереве равно $$(N+1)$$, а само дерево является бинарным, можно сделать вывод, что количество внутренних узлов дерева, т. е. узлов, в которых производится проверка значений атрибутов, не превышает величины $$N$$.
При наилучшем исходе алгоритм C4.5 строит идеально
Алгоритм C4.5 ориентирован на построение дерева решений наиболее приближенного к идеально сбалансированному, т. е. на сокращение среднего числа атрибутов, необходимого для идентификации предъявленного объекта. Таким образом, для каждого класса выбирается индивидуальная совокупность атрибутов, необходимая для идентификации его объектов. По сути, построение дерева решений ориентировано на построение алгоритма классификации объекта с минимальным числом шагов и при этом не преследуется цели сокращения используемой информации, необходимой для такого алгоритма. Но в случае сокращения ДИ алгоритм получения реакции на диагностический тест уже известен, а для большего сокращения информации целесообразно найти некое единое множество атрибутов, по которому можно было бы идентифицировать любой объект. Естественно, объединение упомянутых индивидуальных совокупностей для всех классов может иметь существенно большую мощность, чем такое единое множество.
Следующий алгоритм [3], базирующийся на идеях алгоритма C4.5, направлен на нахождение упомянутого единого множества атрибутов.
Отличие предлагаемого алгоритма от алгоритма C4.5 состоит в том, что построение дерева производится по уровням, с выбором одного атрибута для проверки во всех узлах уровня. На начальном уровне присутствует только один узел -
где $$\tilde{P}$$ - совокупность множеств объектов, соответствующих узлам текущего уровня, а величины $$I'(\tilde{P})$$ и $$I'_x(\tilde{P})$$ равны соответственно
$$ I'(\tilde{P})=\sum\limits_{P'\in P}\cfrac{|P'|}{|\tilde{P}|}I(P')$$и
$$ I'_x(\tilde{P})=\sum\limits_{P'\in P}\cfrac{|P'|}{|\tilde{P}|}I_x(P').$$Так же как и в алгоритме C4.5, процесс построения дерева заканчивается, если на очередном уровне каждому узлу дерева будет соответствовать множество объектов одного класса.
Содержательный смысл такого построения состоит в следующем: на каждом уровне дерева выбирается атрибут, проверка которого максимально уменьшает среднее количество информации, необходимой для идентификации любого объекта из множества $$P$$.
Переформулируем последний алгоритм применительно к задаче поиска маски. В этом случае стоит учесть, что роль атрибутов выполняют точки проверки ЦУ. Также обратим внимание на то, что после вычисления множеств, соответствующих вершинам очередного уровня дерева, необходимость в хранении информации о предшествующих уровнях отпадает. Совокупность множеств, соответствующих вершинам очередного уровня дерева, представляет разбиение исходного множества классов - в нашем случае множества $$S$$. Т. е. в ходе очередной итерации алгоритма достаточно по разбиению множества $$S$$, соответствующего предыдущему уровню дерева, построить разбиение, соответствующее очередному уровню.
Разбиение множества технических состояний $$S$$ производится в соответствии со значениями в точках проверки. Каждая точка проверки разбивает множество технических состояний $$S$$ на два блока (подмножества) следующим образом: технические состояния, для которых значение в данной точке проверки равно единице, помещаются в первый блок, а неисправности, для которых значение равно нулю - во второй. Можно производить дальнейшее разбиение каждого из полученных блоков в соответствии со значениями в других точках проверки. Если СПР обладает свойством различения всех технических состояний, то, производя последовательно разбиение множества $$S$$ с помощью всех точек проверки, получим в результате одноэлементные блоки.
В целях решения задачи оптимизации маски можно ввести ограничение объема полученной маски. Такое ограничение будет заключаться в установке предельного значения количества уровней дерева, или, другими словами, определении числа итераций алгоритма.
Итак, исходя из изложенного, сформулируем формальное описание алгоритма.
Алгоритм 1 ( Жадный алгоритм поиска единой маски ДИ ).
Вход: Словарь полной реакции; $$S$$ - множество технических состояний; $$M$$ - максимальный объем маски результата (по умолчанию $$M=|S|-1$$).
Выход: $$h$$ - маска ДИ.
Замечение 1. Ограничение объема возвращаемой маски в алгоритме 1 по умолчанию числом $$(|S|-1)$$ носит условный характер, так как при отказе от этого ограничения объем любой маски, полученной с помощью этого алгоритма, не превысит величины $$(|S|-1)$$.
Действительно, при добавлении в алгоритме очередной точки проверки в маску $$h$$ происходит дополнительное разбиение блоков в $$\tilde{S}_k$$. Из того, что $$S_0=\{S\}$$ следует, что провести разбиение блока из $$\tilde{S}_0$$ на одноэлементные блоки можно максимум за $$|S|-1$$ итераций.
Рассмотрим работу полученного алгоритма на примере схемы C17 (рис. 27.1). Найдем единую маску для СПР, представленного в табл. 27.5. После первых двух шагов алгоритма имеем: $$\tilde{S}_0=\{\{ s_0,s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8\}\}$$, $$J_0=3.16993$$, $$Р=\varnothing$$. На третьем шаге алгоритма получаем следующие результаты:
$$ I'_{1:1}= I'_{1:2}= I'_{3:1}=2.17885,\\ I'_{2:1}=2.40572,\\ I'_{2:2}= I'_{4:1}=2.66667,\\ I'_{3:2}=2.25163,\\ I'_{4:2}=3.16993.$$Следовательно величина (6.9) достигает своего максимума при использовании точек проверки $$1:1$$, $$1:2$$ и $$3:1$$. Выполним шаги Ошибка! Источник ссылки не найден.-Ошибка! Источник ссылки не найден. алгоритма, предполагая, что на третьем шаге выбрана точка проверки $$1:1$$. После первой итерации алгоритма получим
$$ \tilde{S}_0=\{\{ s_0,s_1, s_7,s_8\},\{s_2,s_3,s_4,s_5,s_6\}\}, \\ J_1=2.17885,\\ h=\{1:1\}.$$На третьем шаге следующей итерации алгоритма получаем:
$$ I'_{1:2}=1.19499,\\ I'_{2:1}=1.73440,\\ I'_{2:2}=1.81828,\\ I'_{3:1}= I'_{4:1}=1.77778,\\ I'_{3:2}=1.27886,\\ I'_{4:2}=2.17885.$$что означает однозначный выбор точки проверки $$1:2$$. Ситуация после окончания второй итерации становится следующей:
$$ \tilde{S}_0=\{\{ s_0,s_8\},\{s_1, s_7\},\{s_2,s_3\},\{s_4,s_5,s_6\}\}, \\ J_2=1.19499,\\ h=\{1:1,1:2\}.$$На очередном проходе алгоритма вычисления дают следующие результаты.
$$ I'_{2:1}=0.75054,\\ I'_{2:2}= I'_{3:1}=0.97277,\\ I'_{3:2}=0.44444,\\ I'_{4:1}=0.88889,\\ I'_{4:2}=1.19499.$$откуда получаем
$$ \tilde{S}_0=\{\{ s_0,s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5,s_6\}\}, \\ J_3=0.44444,\\ h=\{1:1,1:2,3:2\}.$$Как видим, после трех итераций алгоритма остались неразличимыми две пары технических состояний $$\{s_0,s_8\}$$ и $$\{s_5,s_6\}$$. Следующая итерация приводит к величинам
$$ I'_{2:1}=I'_{2:2}=I'_{4:1}=0.22222,\\ I'_{3:1}=I'_{4:2}=0.44444$$означающим, что любая из точек проверок $${2:1}$$,$${2:2}$$,$${4:1}$$ различает одну из этих пар состояний. Выбор точки проверки $${2:1}$$ приведет к значениям
$$ \tilde{S}_0=\{\{ s_0\},\{s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5,s_6\}\}, \\ J_4=0.22222,\\ h=\{{1:1},{1:2},{2:1},{3:2}\},$$после чего на пятой итерации получим
$$ I'_{2:2}= I'_{3:1}=I'_{4:2}=0.22222,\\ I'_{4:1}=0$$и включая в маску получим
$$ \tilde{S}_0=\{\{ s_0\},\{s_8\},\{s_1\},\{ s_7\},\{s_2\},\{s_3\},\{s_4\},\{s_5\},\{s_6\}\}, \\ J_5=0.22222,\\ h=\{{1:1},{1:2},{2:1},{3:2},{4:1}\},$$На шестой итерации алгоритма получаем значения $$J_5=J_6=0$$, после чего алгоритм завершает свою работу. Результат работы алгоритма - маска $$h=\{{1:1},{1:2},{2:1},{3:2},{4:1}\}$$.
СПР для единой маски, полученной сокращением СПР с помощью алгоритма1, для диагностического теста схемы C17 приведен в табл. 31.1.
| $$s_0$$ | 11011 |
| $$s_1$$ | 10111 |
| $$s_2$$ | 00011 |
| $$s_3$$ | 00001 |
| $$s_4$$ | 01001 |
| $$s_5$$ | 01011 |
| $$s_6$$ | 01010 |
| $$s_7$$ | 10001 |
| $$s_8$$ | 11111 |
Уточним верхнюю оценку объема маски, возвращаемой с помощью алгоритма 1. Но вначале сформулируем следующую лемму, которая потребуется для вывода этой оценки.
Лемма 1. На любом шаге $$k$$ работы алгоритма 1 справедливо неравенство
$$ J_{k+1}\le J_k\left (1 - \cfrac{1}{M}\right),$$где $$M$$ - объем минимальной маски заданного СПР.
Доказательство. Заметим сначала, что для любой точки проверки $$i:j$$ и для любого $$k\ge 0$$ величина (31.9) неотрицательна. Действительно, (31.9) является конкретизацией выражения (31.6) , в котором вместо атрибута $$x$$ используется точка проверки $$i:j$$. Подставляя в (31.5) сначала (31.7) и (31.8), а затем (31.1) и (31.2) получим
$$ J_k-I'_{i:j}(\tilde{S}_k)= \cfrac{1}{|\tilde{S}_k|}\sum\limits_{S'\in\tilde{S}_k}{|S'|\log_2|S'|}-\sum\limits_{S''\in\tilde{S'} }{|S''|\log_2|S''|}$$где $$\tilde{S'}$$ обозначает разбиение множества $$S'$$ согласно значениям точки проверки $$i:j$$. Из того, что каждое слагаемое внешней суммы в (31.11) неотрицательно, следует неотрицательность (31.9). Отсюда вытекает, что последовательность
$$J_1-J_0,J_2-J_1,\ldots,J_k-J_{k-1},\ldots$$- невозрастающая.
Пусть после $$k$$ итераций алгоритма 1 получена маска $$h$$ и величина $$J_k$$ - среднее количество информации, необходимой для идентификации любого технического состояния из блоков разбиения $$\tilde{S}_k$$. Пусть для того чтобы разбить блоки $$\tilde{S}_k$$ на одноэлементные подмножества оптимальным образом, требуется включение в маску $$h$$ дополнительно минимум $$M'$$ точек проверки. Тогда на следующей итерации алгоритма должно выполняться неравенство
$$ J_{k+1}\le J_k\left ( 1-\cfrac{J_k}{M}\right )$$Т. к. $$M' < M$$, из (31.12) следует (31.10).
Теорема 2. Объем маски, полученной с помощью алгоритма 1, не превышает величины
$$ M\cdot\left ( 1+ln\cfrac{|S|\log_2|S|}{2}\right ),$$где $$M$$ - объем минимальной маски заданного СПР.
Доказательство. Согласно лемме 1
$$J_k\le\left (1-\cfrac{1}{M}\right )^k\log_2|S|\le e^{-\cfrac{k}{M}}\log_2|S|$$Исходя из представления (6.7), минимально-возможное ненулевое значение, которое может принимать $$J_k$$, равно $$2/|S|$$.
Пусть $$k_0$$ - максимальное целое число такое, что
$$e^{-\frac{k}{M}}\log_2|S|\ge\cfrac{2}{|S|}$$Тогда для $$k_1=k_0+1$$ будет выполнено $$J_{k_1}< 2/|S|$$.Из (6.13) следует
$$\cfrac{k_1-1}{M}\le ln\cfrac{|S|\log_2|S|}{2} $$что влечет
$$k_1\le 1+M ln\cfrac{|S|\log_2|S|}{2} \le M\left (1+ln\cfrac{|S|\log_2|S|}{2}\right )$$Следствие 1. Объем маски, полученной с помощью алгоритма 1, не превышает величины
$$\min\left\{|S|-1,M\cdot\left (1+ln\cfrac{|S|\log_2|S|}{2}\right )\right\}$$где $$M$$ - объем минимальной маски данного СПР.
Справедливость следствия вытекает из теоремы 2 и замечания к алгоритму.
С точки зрения задачи оптимизации маски представляет интерес получение оценки глубины диагностирования с использованием маски, полученной с помощью алгоритма 1 при ограничении ее объема. В качестве оцениваемой величины возьмем значение диагностического разрешения $$\rho_3$$, определяемое равенством
$$\rho_3=\cfrac{|S|^2-\sum\limits_{S_j}|S_j|^2}{|S|^2-|S|}$$Теорема 3. Пусть для СПР существует оптимальная маска $$\tilde{h}$$ объема $$r$$, а $$\tilde{\rho}_3$$ - величина диагностического разрешения при диагностировании с использованием $$СПР_{\tilde{h}}$$. Тогда, если $$h$$ - маска объема $$r$$, найденная с помощью алгоритма 1, и $$\rho_3$$ - диагностическое разрешение при диагностировании с помощью $$СПР_h$$, то справедливо следующее неравенство
$$\rho_3\ge\rho_3\left(1-\cfrac{1}{e}\right ). $$Доказательство. Разбиение $$\tilde{S}_k$$ на $$k$$-ой итерации алгоритма можно интерпретировать как множество СПН, получаемое при диагностировании с помощью $$СПР_h$$, где $$h$$ - маска, полученная после $$k$$ итераций алгоритма. Обозначим через $$\rho_3(\tilde{S}_k)$$ значение диагностического разрешения при диагностировании с помощью этого $$СПР_h$$.
Очевидно, что последовательность
$$ \rho_3(\tilde{S}_0), \rho_3(\tilde{S}_1),\ldots, \rho_3(\tilde{S}_k),\ldots$$неубывающая. Действительно, на каждой последующей итерации алгоритма $$S_{k+1}$$ получается из $$S_k$$ разбиением одного или нескольких блоков на более мелкие блоки. Диагностическое разрешение (отношение количества различимых пар состояний к общему числу пар состояний) от этого может только увеличиться.
Более того, можно легко показать, что последовательность
$$ \rho_3(\tilde{S}_1)- \rho_3(\tilde{S}_0), \rho_3(\tilde{S}_2)- \rho_3(\tilde{S}_1),\ldots, \rho_3(\tilde{S}_{k+1})- \rho_3(\tilde{S}_k),\ldots$$не возрастает.
Из сказанного следует, что
$$ \rho_3(\tilde{S}_{k+1})\ge \rho_3(\tilde{S}_k)+\cfrac{\tilde{\rho}_3-\rho_3(\tilde{S}_k)}{r}=\cfrac{\tilde{\rho}_3}{r}+\rho_3(\tilde{S}_k)\left (1+\cfrac{1}{r}\right )$$Тогда
$$ \rho_3(\tilde{S}_{r})\ge \cfrac{\tilde{\rho}_3}{r}\left ( \left (1+\cfrac{1}{r}\right ) + \left (1+\cfrac{1}{r}\right )^2 +\ldots + \left (1+\cfrac{1}{r}\right )^{r-1} \right ) =\\ \cfrac{\tilde{\rho}_3}{r}\left ( \cfrac{1-\left (1-\cfrac{1}{r}\right )^r }{\cfrac{1}{r}} \right ) ={\tilde{\rho}_3}\left ( {1-\left (1-\cfrac{1}{r}\right )^r }\right )\ge {\tilde{\rho}_3} \left (1-\cfrac{1}{e}\right )$$Последнее неравенство и доказывает теорему.
Содержательный смысл последней теоремы заключается в том, если маска $$h$$ заданного объема вычислена с помощью алгоритма 1, то потеря в степени диагностирования с использованием $$СПР_h$$ не превосходит 40% от степени диагностирования с $$СПР_{\tilde{h}}$$, построенного с помощью оптимальной маски того же объема.
Теперь перейдем к оценке сложности алгоритма 1.
Теорема 4. Вычислительная сложность алгоритма 1 оценивается величиной $$O(|S|^2m|\tau|)$$. Объем необходимой для функционирования алгоритма памяти равен $$O(|S|)$$.
Доказательство. Оценим сначала вычислительную сложность алгоритма.
Как отмечалось ранее, максимальное количество итераций алгоритма равно $$(|S|-1)$$. На каждой итерации производится поиск точки проверки, доставляющей минимум величине (31.9). Общее количество точек проверки есть $$m|\tau|$$, а для того чтобы подсчитать (31.9) для конкретной точки проверки, необходимо выполнить $$O(|S|)$$ операций для вычисления $$I'_{i:j}$$. Таким образом, общее количество операций в алгоритме
$$(|S|-1)\cdot m|\tau|\cdot O(|S|)=O(|S|^2m|\tau|).$$Оценивая емкостную сложность алгоритма заметим, что в ходе его работы необходима память для хранения текущей маски, разбиения $$\tilde{S}_k$$, счетчика итераций $$k$$ и двух значений $$J_k$$ и $$J_{k+1}$$. Ни одно из значений $$k$$, $$J_k$$ и $$J_{k+1}$$ не превышает по величине $$|S|$$. Суммарное количество элементов в блоках разбиения $$S_k$$ равно $$|S|$$. Согласно следствию из теоремы 2 объем маски не превышает $$|S|$$. Отсюда получаем оценку емкостной сложности, приведенную в формулировке теоремы.
Экспериментальным данным для оценки эффективности алгоритма 1 и еще одного жадного алгоритма, о котором речь пойдет в следующей лекции, на ДИ, порождаемой реальными устройствами, будет посвящена отдельная лекция.
Жадный алгоритм - алгоритм, основанный на принятии локально оптимальных решений на каждом этапе его работы в расчете на возможность получения глобального оптимума.
Дерево принятия решений - граф, обычно применяемый для решения задач классификации объектов. Он представляет собой дерево,на ребрах которого записаны атрибуты, являющиеся аргументами целевой функции, а в листьях записаны значения этой целевой функции. Во всех прочих вершинах дерева записаны атрибуты, по которым различаются классифицируемые объекты.
В лекции описан жадный алгоритм поиска единой маски ДИ, базирующийся на использовании конструкции дерева принятия решений, призводится оценка объема получаемой маски и вычислительной сложности алгоритма.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.