Рабочая программа дисциплины подготовка публикаций направление подготовки

Основной недостаток такого подхода заключается в том, что для современных дискретных устройств объем ДИ очень велик. Для сокращения объема ДИ были предложены различные методы [1–5]. Некоторые из них связаны с применением так называемых масок [2–5]. Маска определяет, какие позиции полной реакции на диагностический тест будут сохраняться в составе ДИ. Таким образом, вместо полных реакций на диагностический тест ДИ будет содержать некоторое подмножество этих реакций, полученное из полных реакций «наложением» маски. Маску называют единой (общей), если при составлении ДИ она применяется к реакциям на тест всех неисправных модификаций ДУ.

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

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

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

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

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

Обозначим через матрицу, полученную из удалением всех столбцов, кроме тех, чьи номера содержатся в маске . Матрицу назовем результатом применения маски к ДИ . Эта матрица и представляет сокращенную диагностическую информацию.

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

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

Деревья решений для задач

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

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

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

Для построении деревьев решений часто используется алгоритм C4.5 предложенный Р. Квинланом (R. Quinlan) [6] в 1993 г. Напомним основные моменты этого алгоритма.

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

Построение дерева происходит сверху вниз. Сначала создается корень дерева, затем потомки корня и т. д. Каждому узлу дерева ставится в соответствие некоторое подмножество множества . Корню дерева ставится в соответствие само множество .

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

Пусть данному узлу дерева соответствует множество объектов классов из , а – количество элементов из множества , принадлежащих классу . Тогда величина

где  – количество элементов в множестве , дает оценку среднего количества информации, необходимой для идентификации объекта из множества .

Если произвести разбиение множества в зависимости от значений атрибута на подмножеств, то ту же оценку, но уже после разбиения дает выражение

. (2)

В принятых обозначениях алгоритм C4.5 состоит из следующих шагов:

1. 
   Необходимо выбрать такой атрибут , который доставляет максимум величины
   

2. 
   Для данного узла дерева создать потомков.
   
3. 
   Каждому потомку данного узла поставить в соответствие определенное подмножество объектов из множества , имеющих одно и то же значение атрибута , а дугу от узла к потомку пометить соответствующим значением.
   

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

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

Поскольку каждый класс представлен лишь одним объектом в обучающей выборке, то формула (1) примет следующий вид:

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

Формула (5) получена из (3) с учетом (4). Очевидно, что в (5) будет иметь максимум в том случае, если множество делится по значениям атрибута на два подмножества с равным числом элементов.

В Табл. 1 приведены результаты работы алгоритма получения маски ДИ с помощью алгоритма C4.5 для диагностической информации ДУ из набора схем каталога ISCAS’89.

Заметим, что данные, приведенные в табл. 1–3, получены для вероятностных тестов, содержащих 100 входных наборов, и число обнаруженных такими тестами неисправностей представлено во втором слева столбце этих таблиц. Как показывает опыт, значительное увеличение длины вероятностного диагностического теста приводит к довольно малому росту числа обнаруженных с его помощью неисправностей. По этой причине увеличение длины теста, следствием которого является возрастание объема ДИ, по-видимому, может только улучшить показатели в последнем столбце таблиц, но не ухудшить их.

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

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

Как видно из сравнения результатов, модификация алгоритма C4.5 привела к сокращению объема маски до 30% по отношению к результату исходного алгоритма.

Авторами доклада разработан новый алгоритм, базирующийся на идеях алгоритма C4.5, но направленный на нахождение упомянутого единого множества атрибутов.

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

, (6)

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

и

. (8)

Так же как и в алгоритме C4.5, процесс

Таблица 3
Результат применения алгоритма для поиска единой маски ДИ
Наименование ДУ	Число неисправностей в ДУ	Длина полной реакции на диагностический тест, (в битах)	Объем ДИ, (в битах)	Объем маски	Размер сокращенной ДИ по отношению к полной ДИ
S298	92	600	55200	36	6.00%
S344	184	1100	202400	50	4.55%
S349	184	1100	202400	48	4.36%
S386	136	700	95200	55	7.86%
S510	447	700	312900	71	10.14%
S641	253	2400	607200	107	4.46%
S713	252	2300	579600	105	4.57%
S820	159	1900	302100	66	3.47%
S832	159	1900	302100	66	3.47%
S8381	86	100	8600	18	18.00%

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

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

В Табл. 3 приведены результаты работы предложенного алгоритма. Как видно из сравнения данных этой таблицы с данными из Табл. 1 улучшение объема маски предложенным алгоритмом составляет до 50% по отношению к объему маски, полученной алгоритмом C4.5.
Заключение
Статистические данные, полученные в результате проведенных численных экспериментов с полутора десятками устройств из международного каталога ISCAS’89, подтверждают достаточно высокую эффективность алгоритмов, предложенных в работе. Так, эти алгоритмы осуществляют поиск решения за приемлемое время: в худшем случае оно не превышало 5 мин. при их реализации на LISP в среде LispWorks PE 4.4 на PC Intel Celeron 1.70GHz, 256MB RAM. Получаемое решение дает возможность сократить ДИ до объема в диапазоне 418% от первоначального, что в практическом плане является хорошим результатом.
Литература
1. Ryan P. G., Fuchs W. K., Pomeranz I. Fault dictionary compression and equivalence class computation for sequential circuits. // Proc. IEEE International Conference on Computer-Aided Design (ICCAD’93). – Santa Clara, CA, USA: 1993. – Pp. 508–511

2. Барашко А. С., Скобцов Ю. А., Сперанский Д. В. Моделирование и тестирование дискретных устройств. – Киев: Наукова думка, 1992.

3. Вознесенский С. С., Раздобреев А. Х. Трудоемкость поиска неисправностей как критерий качества при сокращении объема диагностической информации // Электронное моделирование – 1980. – №4. – С. 83–86.

4. Чипулис В. П. Методы минимизации разрешающей способности и диагностической информации // Автоматика и телемеханика – 1975. – №3. – С. 133–141.

5. Шаршунов С. Г. Особенности диагноза технического состояния многовыходных объектов с использованием таблиц неисправностей // Автоматика и телемеханика – 1973. –№12. – С. 161 – 168.

6. Quinlan J. R. C4.5: programs for machine learning. – San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1993.