Знание-ориентированный подход к адаптации алгоритмов
Предлагается методика формирования альтернативно адаптивных алгоритмов. Знания вырабатываются с использованием показателей степени превосходства и области превосходства алгоритмов. Для адаптации к исходным данным алгоритмов выявляются их атрибуты, по ним исходные данные кластеризуются методом мак...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6982 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Знание-ориентированный подход к адаптации алгоритмов / В.И. Шинкаренко // Штучний інтелект. — 2008. — № 3. — С. 388-395. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859807992957894656 |
|---|---|
| author | Шинкаренко, В.И. |
| author_facet | Шинкаренко, В.И. |
| citation_txt | Знание-ориентированный подход к адаптации алгоритмов / В.И. Шинкаренко // Штучний інтелект. — 2008. — № 3. — С. 388-395. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| description | Предлагается методика формирования альтернативно адаптивных алгоритмов. Знания вырабатываются с
использованием показателей степени превосходства и области превосходства алгоритмов. Для адаптации к
исходным данным алгоритмов выявляются их атрибуты, по ним исходные данные кластеризуются методом
максиминного расстояния. Разработано программное обеспечение для построения альтернативно адаптивных
алгоритмов. Экспериментально исследованы возможности их применения к решению задачи сжатия данных
без потерь.
Пропонується методика формування альтернативно адаптивних алгоритмів. Знання визначаються з
застосуванням показників ступеня та області переваги алгоритмів. Для адаптації до вхідних даних алгоритмів
виявляються їх атрибути, за ними вхідні дані кластеризуються методом максимінних відстаней. Розроблене
програмне забезпечення для формування альтернативно адаптивних алгоритмів. Експериментально досліджені
можливості їх застосування при стисканні файлів без втрат.
The method to alternatively adaptive algorithm‘s designing is offered. Knowledge extracts with use such
measures as degree of the superiority and area of the superiority of algorithms. The attributes of source data
of algorithm‘s are detected and clustered by method of minimum and maximum distances. The specific
software is developed for designing alternatively adaptive algorithms. Facilities of their application to the
decision of a problem of lost-free compression of data are experimentally investigated.
|
| first_indexed | 2025-12-07T15:17:32Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 3’2008 388
5Ш
УДК 004.051
В.И. Шинкаренко
Днепропетровский национальный университет железнодорожного транспорта
им. акад. В. Лазаряна, г. Днепропетровск, Украина
Знание-ориентированный подход
к адаптации алгоритмов
Предлагается методика формирования альтернативно адаптивных алгоритмов. Знания вырабатываются с
использованием показателей степени превосходства и области превосходства алгоритмов. Для адаптации к
исходным данным алгоритмов выявляются их атрибуты, по ним исходные данные кластеризуются методом
максиминного расстояния. Разработано программное обеспечение для построения альтернативно адаптивных
алгоритмов. Экспериментально исследованы возможности их применения к решению задачи сжатия данных
без потерь.
Введение
Для решения многих задач наука и практика выработали целый ряд методов
решения, иногда значительно отличающихся друг от друга применяемыми подхо-
дами, математическим аппаратом и способами обоснования.
Алгоритмы, реализующие различные методы решения одной задачи, образуют
некоторое множество функционально эквивалентных (или функционально близких)
алгоритмов.
Предметом данного исследования являются функционально эквивалентные,
нечетко специфицированные [1] алгоритмы, такие, как алгоритмы распознавания
образов, кластеризации, сжатия данных и др. К таким алгоритмам можно отнести
практически все алгоритмы искусственного интеллекта. Они отличаются от четко
специфицированных тем, что могут выполнять свое функциональное назначение не
однозначно, а лишь в некоторой мере хорошо.
Функциональная эффективность алгоритмов зависит от множества входных
данных, к которому они применяются.
Предлагается, с целью повышения функциональной эффективности алгоритмов
без дополнительных затрат по их совершенствованию, применить к решению задач
адаптивные алгоритмы, в терминах [2] – алгоритмы альтернативной адаптации.
Такая адаптация позволяет взять лучшее, что есть в каждом алгоритме и во
всех конкретных случаях применять наиболее подходящий алгоритм.
Постановка задачи
Пусть имеется несколько (N) нечетко специфицированных алгоритмов [1] с одина-
ковым функциональным назначением. Для определенности и конкретности далее будем
рассматривать достаточно представительный класс алгоритмов сжатия данных без
потерь. Как известно, сжатие данных принципиально невозможно, так как это практичес-
ки сводится к задаче преобразования вектора из одного пространства в другое, меньшей
размерности без потери данных [3]. Сжатие данных с последующим восстановлением
возможно лишь при наличии в данных излишней (шумовой, ненужной) информации
либо с учетом закономерностей в ее представлении.
Таким образом, любой алгоритм сжатия на конкретных данных может иметь
различную функциональную эффективность, проявляющуюся в различной степени
сжатия данных.
Знание-ориентированный подход к адаптации алгоритмов
«Штучний інтелект» 3’2008 389
5Ш
Область исходных данных, для которых некоторый алгоритм сжатия будет иметь
некоторую эффективность не ниже заданной, наперед неизвестно и практически может
быть определена лишь экспериментально, т.е. после выполнения алгоритма.
Повысить функциональную эффективность некоторого класса алгоритмов с
одинаковым функциональным назначением предлагается путем их адаптации к
исходным данным или частям исходных данных.
Необходимо выработать методику построения алгоритма альтернативной адап-
тации и апробировать ее на алгоритмах сжатия данных без потерь.
Алгоритмы альтернативной адаптации
Обозначим алгоритмы одинаковой функциональной направленности Y
XiA | , где
X – область определения, а Y – область значения алгоритмов. В нашем случае iA –
несколько алгоритмов сжатия, реализованных в программах-архиваторах файлов,
Xx∈ – множество файлов, подлежащих архивации, Yy∈ – архив файлов.
Задана +∈Ry)(ρ – оценка качества полученных алгоритмом результатов ( Yy∈ ),
для алгоритмов сжатия – размер архива.
Идея альтернативной адаптации алгоритмов iA отражена в следующем адап-
тивном алгоритме:
∏
=
⋅=⋅⋅⋅⋅=
N
i
Y
Xi
XXX
Xo
Y
XN
Y
X
Y
X
XXX
Xoa
i
i
NN
N
N AAAAAAA
1
,
21
, |||||| 212
2
1
1
21 …… … , (1)
где «·» – операция композиции, которая определяет последовательное выполнение
алгоритмов (краткая форма записи ∏
=
N
i
Y
Xi
i
i
A
1
| ). Алгоритм NXXX
XoA …21 ,| разбивает область
определения адаптируемого алгоритма X на подмножества NXXX …21, , такие, что
∪
N
i
i XX
1=
= , ∅=≠∀ ji XXji ∩| и ).()(|, jijjii yyYyYy ρρ <∈∈∀ (2)
Алгоритм aA состоит из адаптирующей части NXXX
XoA …21,| и адаптируемой
∏
=
N
i
Y
Xi
i
i
A
1
| . Функциональное назначение адаптируемой части остается тем же – сжатие
данных, а адаптирующей – максимально повысить эффективность этой функцио-
нальности применительно к конкретным входным данным.
Оптимальным будет такое разбиение множества X , при котором Xia AAS |),(
будет максимальным.
Здесь Xji AAS |),( – степень превосходства одного (i-го) алгоритма над другим
(j-ым) на ограниченном множестве X [1]:
%100
))|(),|(max(
)|()|(1|),( ⋅
−
= ∑
∈∈ Xx xixj
xixj
Xx
Xji
i ii
ii
i AA
AA
N
AAS
ρρ
ρρ
. (3)
Задача заключается в разработке алгоритма NXXX
XoA …21,| , чтобы выполнялись
условия (2) и целевая функция (3) была максимальной, с учетом того, что:
)()()(
2121 XXXX AAA ρρρ +≠∪ . (4)
Такой алгоритм существенно зависит от порядка сбора информации, необходимой
для адаптации и применения адаптивного алгоритма, что проявляется в режиме адаптации.
Шинкаренко В.И.
«Искусственный интеллект» 3’2008 390
5Ш
Режимы адаптации
Можно говорить о двух режимах адаптации. Назовем СНС (сегодня на сегодня)
адаптацией такую, при которой данные, к которым необходимо адаптировать
алгоритм, используются адаптирующим алгоритмом.
Если адаптирующий алгоритм использует ранее полученные статистические
данные результатов применения адаптируемых алгоритмов, будем говорить о СНЗ
(сегодня на завтра) адаптации.
СНЗ адаптация адаптирует алгоритм к последовательности входных данных,
при многократном выполнении алгоритма. Адаптация к данным при конкретном
выполнении использует знания о результатах предыдущих выполнений алгоритма.
Таким образом, СНС алгоритм адаптируется к самим исходным данным, а СНЗ – к
потоку входных данных при последовательности выполнений.
При СНС адаптации адаптирующий алгоритм:
Nji
jii
ji
j
j XXX
FXr
F
YXf
j i
Y
Xi
X
Xgo AAAAA …21,
,
, ,
,, |)|||( ⋅⋅⋅=∏∏ , (5)
где jX
XgA | – алгоритм выделения некоторого подмножества XX j ⊂ , ji
jii
F
YXfA ,
,,| –
алгоритм протоколирования результатов сжатия подмножества jX алгоритмом iA ,
NXXX
FXrA …21,
,| – алгоритм разбиения множества X на подмножества NXXX …21, .
Алгоритм fA предназначен для формирования базы фактов (базы данных).
Применительно к алгоритмам сжатия база фактов может состоять из таких кортежей:
идентификатор архиватора, атрибуты файла, начальный и конечный размер файла.
Алгоритм определения всех возможных подмножеств некоторого множества
принадлежит к классу NP – алгоритмов [4]. Его ( jX
XgA | ) вычислительная сложность
является )!(nO . Такие задачи даже при незначительных размерностях требуют недости-
жимых вычислительных ресурсов.
Общепринятый прием снижения вычислительной сложности заключается в пере-
ходе к приближенным алгоритмам, чаще всего стохастическим, либо упрощении задачи,
вводя некоторые допущения.
Пойдем вторым путем. Допустим неравенство (3) можно заменить равенством без
большого ущерба для результата. Очевидно, что такое предположение для алгоритмов
будет тем более обоснованным, чем больше и однороднее сжимаемые файлы.
Тогда алгоритмом ix
XgA | можно выполнить простой перебор элементов Xxi ∈ ,
т.е. последовательный выбор файлов для сжатия из обучающей выборки.
Алгоритм fA также упрощается. Элемент jx добавляется к множеству iX так,
что )|(max)|(| xjjxii AAXx ρρ =∈ .
Адаптирующий алгоритм СНЗ адаптации состоит из двух частей:
Q
Fz
F
YXf
M
j
NK
i
Y
Xi
X
Xgo AAAAA ji
jii
ji
j
j |)|||( ,
,
,
,
1 1
1, ⋅⋅⋅=∏∏
=
≤
=
и nXXX
QXro AA …21,
,2, |= , (6)
где zA – алгоритм извлечения знаний из базы фактов F и формирования базы знаний Q .
Алгоритм 1,oA может выполняться заблаговременно, до использования адап-
тивного алгоритма, однократно или периодически, а 2,oA – как часть адаптивного
алгоритма при необходимости сжатия данных.
Конечно, важным вопросом является вопрос эффективности альтернативной
адаптации. Для ответа на него выполнен ряд вычислительных экспериментов.
Знание-ориентированный подход к адаптации алгоритмов
«Штучний інтелект» 3’2008 391
5Ш
Экспериментальные исследования
Разработан исследовательский комплекс программ ResComp, позволяющий выпол-
нять численные эксперименты с отбором файлов для сжатия, выполнения самого
сжатия, определения размеров исходных файлов и архивов.
Для формирования адаптивных алгоритмов сжатия данных отобрано несколько
алгоритмов и их модификаций, реализованных в 12 архиваторах данных, имеющих
возможность запуска с командной строки (для выполнения из программы ResComp).
Каждый архиватор имеет от нескольких до десятков параметров, влияющих на
содержимое архивов и степень их сжатия. В данной работе параметры архиваторов
фиксированы и выбраны согласно рекомендациям в их help‘е, которые предполагают
наилучшую степень сжатия. Ниже перечислены архиваторы с указанием разработчиков,
версии, года выпуска и параметров командной строки для запуска архиваторов:
− Rar 3.71, Alexander Roshal, 2007, “a -m5 bbb all”;
− Ha 0999с, Harry Hirvola, 1995, “a2 bbb all\*.*”;
− Arj 3.14a, ARJ Software, 2006, “a -jm '+ ' bbb all”;
− 7_zip 4.58 beta, Igor Pavlov, 2008, “a -t7z bbb all -mx9”;
− Bzip2 1.0.4, Julian Seward, 2006, “--best -k all\*.*”;
− AlZip 7.0 beta1, ESTSoft corp, 2007, “-a -m0 all bbb.alz”;
− Rk 1.04.1 alpha, Malcolm Taylor, 2000, “-c bbb.rk @ccc2.txt”;
− Tar 1.12, “-c -k -z --files-from=ccc1.txt --file=bbb.tar”;
− Imp 1.12, Technelysium Pty ltd., 2000, “a -m3 bbb.imp all\*.*”;
− Jar 1.02, ARJ Software, 1997, “a -m4 bbb.jar all\*.*”;
− PKZIPC(R)_4.00, PKWARE inc., 2000, “-add bbb.zip all\*.*”;
− Gzip 1.3.12, Jean-loup Gailly, “--best all\*.*”.
Здесь “bbb” – имя архива, “ccc” – имя файла со списком файлов, подлежащих
архивации, “all” – имя папки с исходными файлами.
Сформировано 7 банков данных файлов различных форматов [5] (общая инфор-
мация в табл.1).
Таблица 1 – Основные характеристики банков данных
Банк
данных
Формат файлов
(расширение файлов)
К-во
файлов
Объем
БД, Гб
Минимальный
размер файла, б
Максимальный
размер файла,
Мб
1 BitMap File (bmp) 3037 2,03 104 2,25
2 “Deja-vu” (djvu) 513 1,19 8990 21,6
3 Microsoft Word(doc) 3611 1,31 0 23,0
4 Zsoft PaintBrush File (pcx) 1016 1,73 291 5,23
5 Portable Document Format (pdf) 566 0,79 5955 28,8
6 Tag Image File (tif) 1474 1,42 188 20,2
7 Microsoft Excel(xls) 6523 1,86 136 20,7
Всего 16740 10,33 0 28,8
Выполнено два численных эксперимента.
Подготовка к экспериментам заключается в формировании таблицы фактов. На
этом этапе выполнен алгоритм 1,oA применительно ко всем файлам банка данных и
всех архиваторов.
Алгоритм jX
XgA | (5 – 6) реализует последовательную выборку одиночного файла из
банка данных.
Файлы ix обладают некоторыми свойствами – атрибутами, ),( ii ax – входные
данные для однократного выполнения алгоритма и ia – набор атрибутов AXax ii ×∈),( .
Шинкаренко В.И.
«Искусственный интеллект» 3’2008 392
5Ш
Для всех данных набор атрибутов включает формат файла и, в зависимости от формата,
определяются остальные атрибуты. Так, для файлов формата MS Word, определяется
количество символов, количество строк, количество внедренных объектов MS Excel,
количество внедренных графических объектов.
Алгоритм ji
jii
F
YXfA ,
,,| (5 – 6) определяет набор и значения атрибутов файла и форми-
рует базу фактов со следующим содержимым: имя файла, его формат, атрибуты фай-
ла, размер архива при сжатии каждым архиватором, лучший архиватор для данного
файла.
Эксперимент 1. Исследуется СНС и СНЗ адаптация со знаниями на уровне
форматов файлов.
Для СНЗ адаптации алгоритм Q
FzA | определяет степень превосходства (3) и область
превосходства [1] алгоритмов архивации отдельно для файлов различного формата. Зна-
чения степени превосходства Xji AAS |),( для файлов формата MS Word с доверии-
тельными интервалами [1], [6], приведены в табл. 2. Есть явный «лидер» – алгоритм 4A .
Алгоритм Q
FzA | формирует базу знаний следующего формата:
если «формат данных = a», то лучший архиватор b. Например, если «формат
данных = DO», то лучший архиватор 4A .
Результаты эксперимента показали, что для каждой структуры данных выявлен
алгоритм, превосходящий остальные на 10 … 20 %.
Однако по области превосходства проявились различия. Для файлов форматов
xls, doc, pdf, djvu область превосходства лидера над остальными алгоритмами
находится в пределах 86 … 99,8 %. То есть лидер был лучшим практически всегда,
при архивации подавляющего большинства файлов. Иначе лидер появился при
архивации файлов форматов tif, pcx и bmp. Его превосходство над некоторыми
другими архиваторами составила лишь порядка 43 … 52 %. Здесь лидер был хуже
практически для половины файлов, хотя по степени превосходства может и явно
превосходил другие. В табл. 3 показано насколько часто каждый архиватор был
лучшим при сжатии данных определенного формата.
Таблица 2 – Степень превосходства i-го алгоритма над j-м
i j 1A 2A 3A 4A 5A 6A 7A 8A 9A 10A 11A 12A
1A 0,0 3,0
3,0-16,6+ 9,1
9,10,15 +
− 9,2
9,29,7- +
− 2,1
2,16,11 +
−
3,3
3,33,15 +
−
3,4
3,40,9 +
−
2,6
6,215,0+
−
2,7
7,26,0+
−
2,2
2,28,9 +
− 2,2
2,24,14 +
− 2,3
2,39,12 +
−
2A 3,0
3,0-16,6- + 0,0 9,1
9,16,2- +
− 9,0
9,09,22- +
− 7,3
7,33,6- +
−
1,1
1,11,2- +
−
7,1
7,17,8- +
−
2,1
2,16,2- +
−
7,1
7,14,11- +
−
5,4
5,49,7- +
− 6,1
6,12,3- +
− 1,1
1,17,4- +
−
3A 9,1
9,10,15- +
− 9,1
9,16,2 +
− 0,0 9,0
9,06,21- +
− 5,2
5,20,4- +
−
2,0
0,20,5+
−
7,2
7,26,6- +
−
0,1
0,14,3- +
−
6,0
6,06,9- +
−
1,3
1,36,5- +
− 4,0
4,07,0- +
− 7,1
7,13,2- +
−
4A 9,2
9,29,7 +
− 9,0
9,09,22 +
− 9,0
9,06,21 +
− 0,0 3,3
3,318,5+
−
0,8
0,8-21,9+ 1,3
3,116,2+
−
0,3
3,021,6+
−
0,9
9,013,5+
−
3,8
8,317,1+
− 0,8
8,021,2+
− 0,6
6,019,7 +
−
5A 2,1
2,16,11- +
− 7,3
7,33,6 +
− 5,2
5,20,4 +
− 3,3
3,318,5- +
− 0,0 4,2
2,44,5+
−
3,5
3,57,2- +
−
3,4
4,34,0+
−
4,3
4,39,5- +
−
3,1
3,17,1- +
− 2,9
9,23,3+
− 4,0
0,41,9+
−
6A 3,3
3,33,15- +
− 1,1
1,11,2 +
− 2,0
0,20,5- +
− 0,8
0,8-21,9- + 4,2
2,44,5- +
− 0,0 8,0
8,01,7- +
−
0,1
0,15,0- +
−
3,1
3,10,10- +
−
9,4
9,42,6- +
− 6,1
6,12,1- +
− 3,0
3,08,2- +
−
7A 4,2
2,49,0- +
− 7,1
7,17,8 +
− 7,2
7,26,6 +
− 1,3
3,116,2- +
− 3,5
3,57,2 +
−
8,0
8,01,7 +
− 0,0 1,7
7,16,6+
−
0,2
0,22,3- +
−
5,7
7,51,0+
− 3,2
2,36,0+
− 1,0
1,0-4,4+
8A 2,6
6,215,0- +
− 2,1
2,16,2 +
− 0,1
0,14,3 +
− 0,3
3,021,6- +
− 3,4
4,34,0- +
−
0,1
0,15,0 +
−
1,7
7,16,6- +
− 0,0 4,0
4,06,9- +
−
0,4
0,46,5- +
− 7,0
7,07,0- +
− 7,0
7,02,2- +
−
9A 2,7
7,26,0- +
− 7,1
7,14,11 +
− 6,0
6,06,9 +
− 0,9
9,013,5- +
− 4,3
4,39,5 +
−
3,1
3,10,10 +
−
0,2
0,22,3 +
−
4,0
4,06,9 +
− 0,0 7,3
3,7-4,1+ 3,0
0,3-9,0+ 1,1
1,1-7,4+
10A 2,2
2,28,9- +
− 5,4
5,49,7 +
− 1,3
1,36,5 +
− 3,8
8,317,1- +
− 3,1
3,17,1 +
−
9,4
9,42,6 +
−
5,7
7,51,0- +
−
0,4
0,46,5 +
−
7,3
3,7-4,1- + 0,0 5,3
5,30,5 +
− 4,7
7,43,7+
−
11A 2,2
2,24,14- +
− 6,1
6,12,3 +
− 4,0
4,07,0 +
− 0,8
8,021,2- +
− 2,9
9,23,3- +
−
6,1
6,12,1 +
−
3,2
2,36,0- +
−
7,0
7,07,0 +
−
3,0
0,3-9,0- + 5,3
5,30,5- +
− 0,0 3,1
3,15,1- +
−
12A 2,3
2,39,12- +
− 1,1
1,17,4 +
− 7,1
7,13,2 +
− 0,6
6,019,7- +
− 4,0
0,41,9- +
−
3,0
3,08,2 +
−
1,0
1,0-4,4- + 7,0
7,02,2 +
−
1,1
1,1-7,4- + 4,7
7,43,7- +
− 3,1
3,15,1 +
− 0,0
Знание-ориентированный подход к адаптации алгоритмов
«Штучний інтелект» 3’2008 393
5Ш
Таблица 3 – Распределение лучших архиваторов по форматам файлов
Архиватор Часть файлов, для которых архиватор оказался лучшим, %
bmp djvu doc pcx pdf tif xls
1A 35,3 2,7 7,0 4,8 1,8 28,4 4,8
2A 35,2 2,5 1,7 29,9 0 34,4 1,5
4A 14,9 0 90,4 6,3 83,4 22,3 93,3
5A 6,3 0 0,4 32,7 0,2 9,6 0,4
7A 4,0 0 0 26,4 1,6 0,4 0
9A 0 87,7 0 0 12,8 0,2 0
12A 4,4 7,0 0 0 0,4 4,6 0
В ходе эксперимента выполнено порядка 4000 опытов. Каждый опыт состоял в
том, что случайным образом из банка файлов отбиралось от 1 до 500 файлов. При
этом две трети банка использовались в качестве обучающей выборки, одна треть –
контрольной. Последовательно выполнялось сжатие каждым архиватором, СНС и
СНЗ адаптивными архиваторами с пополнением базы фактов. СНС адаптивный
архиватор выполнял сжатие согласно базы фактов предварительно определенным
лучшим архиватором. СНЗ адаптивный архиватор сжимал файлы согласно их
форматов и знаниям о лучшем архиваторе для данного формата.
Результаты эксперимента показали, что СНЗ адаптивный алгоритм в любых
случаях и вариантах выполнения имеет положительную степень превосходства над
отдельными архиваторами. При этом в для смеси файлов различной структуры это
превосходство достаточно небольшое, порядка 5 … 10 %. При гомонизации смеси, в
случае неудачно выбранного архиватора, степень превосходства СНЗ адаптивного
алгоритма может доходить до 20 % и более, что наглядно представлено в табл. 4.
Таблица 4 – Степень превосходства СНЗ адаптивного архиватора
Архиватор Форматы файлов
bmp djvu doc pcx pdf tif xls смесь файлов
1A 0 0,2 8 14 1 0 14 5
2A 7 0,8 23 0 5 3 21 8
4A 11 1,1 0 4 0 5 0 4
9A 23 0 14 16 1 16 20 10
Лучший из 1A … 12A 0 0 0 0 0 0 0 3
Интересно, что степень превосходства СНС адаптивного алгоритма по отношению
СНЗ адаптивного составляет всего 0,5 %. Учитывая то, что реализация адаптирующего
алгоритма в СНС адаптивном требует значительных вычислительных затрат, и то, что эти
затраты необходимы в момент потребности в архивации этот факт является сущест-
венным. При СНЗ адаптации сбор фактов и построение базы знаний можно выполнить
заранее. При этом время архивации СНЗ адаптивным архиватором практически такое же,
как обычным, а результат всегда лучше и часто значительно лучше.
Эксперимент 2. Выполняется адаптация алгоритмов к содержимому файлов.
Знания, необходимые для адаптации, основаны на значениях атрибутов файлов и
предварительно полученных результатах сжатия. Так как атрибуты у различных форма-
тов файлов различны, то естественно строить адаптивный алгоритм с учетом форматов.
Шинкаренко В.И.
«Искусственный интеллект» 3’2008 394
5Ш
Не целесообразно применять адаптивный алгоритм для файлов формата doc,
xls, djvu, pdf, что видно из предыдущего эксперимента. Для этих форматов выявлен
архиватор, явный лидер, который превосходит остальные почти всегда, и замена его
другим в тех редких случаях, когда он уступает, очень мало влияет на усредненный
показатель степени превосходства.
Остальные исследуемые форматы относятся к графическим. Рассмотрим адапта-
цию архиваторов к файлам формата tif. Он имеет большой набор внешних атрибутов и
в этом случае три архиватора в основном делят множество файлов на части, в
которых они лучшие.
Для исследования выбраны следующие атрибуты: размер файла, высота и
ширина изображения в пикселах, модель цвета, глубина цвета, способ сжатия,
вертикальное и горизонтальное разрешение.
При подготовке к экспериментам значения атрибутов вместе с результатами
сжатия занесены в базу фактов.
База знаний формировалась следующим образом. Значения атрибутов нормализова-
лись. Выполнялась кластеризация методом максиминного расстояния [7], с особенностью
в том, что новые кластеры образуются, если расстояние до нового центра кластера
превышает 1/6 среднего межкластерного расстояния (Евклидова).
Анализ показал, что порядка 70 … 80 % кластеров имеют своего лидера среди
архиваторов, который более чем в 90 % файлов кластера превосходит остальные.
Эксперимент заключался в отборе 40 … 150 файлов в качестве обучающей
выборки и 1 … 150 – в качестве контрольной.
Как оказалось, степень превосходства СНЗ адаптивного алгоритма над алго-
ритмом 1A (лучшим из остальных) составляет 1 … 2 %.
Хотя полученная система знаний хорошо отражает объект моделирования,
низкий результат объясняется тем, что область превосходства алгоритмов 1A … 12A
приходится на файлы небольших размеров и результаты их сжатия на средние
размеры влияют мало. Кроме того, неравенство (4) проявилось достаточно сильно.
Выводы
Предложенная методика формирования альтернативно адаптивного алгоритма позво-
ляет повысить функциональную эффективность множества функционально эквивалент-
ных алгоритмов. Применение СНЗ адаптивных алгоритмов требует предварительной
подготовки и практически не влияет на временную эффективность алгоритмов, что очень
важно ввиду больших потребностей в вычислениях алгоритмов искусственного интел-
лекта, для которых, в основном, и предназначена данная работа.
Существенным преимуществом СНЗ адаптации является:
− относительно высокая временная эффективность адаптирующей части алгоритма;
− эксплуатация адаптивного алгоритма в режиме близким к алгоритмам без адаптации;
− способность алгоритма к дообучению и повышению усредненных показателей
функциональной эффективности при длительной эксплуатации.
Предложен критерий оценки эффективности применения знаний в альтерна-
тивно адаптивных алгоритмах с применением показателей степени и области превосход-
ства алгоритмов. Эти показатели позволяют оценить потенциальные возможности
применения альтернативной адаптации алгоритмов.
Проявление лидера среди альтернативных алгоритмов, имеющего существенную
степень превосходства над всеми другими алгоритмами и область превосходства более
90 %, говорит о нецелесообразности адаптации в данной области применения алгоритмов.
Знание-ориентированный подход к адаптации алгоритмов
«Штучний інтелект» 3’2008 395
5Ш
Ускорить обучение и повысить эффективность адаптирующего алгоритма можно
за счет знаний, полученных из нескольких источников при применении таких алго-
ритмов в различных программных продуктах и централизованном сборе информации в
единой базе фактов.
Направления дальнейших исследований представляются в следующем.
Естественно, при первом выполнении алгоритма gA база знаний пуста. В этом
случае и в случае, когда знаний недостаточно, необходимо предусмотреть некоторую
стратегию выбора алгоритма сжатия. В качестве такой стратегии может быть предусмот-
рено поочередное выполнение алгоритмов, случайный выбор алгоритма, выбор в соот-
ветствии с наперед заданными (и изменяемыми в последствии) приоритетами.
Множество различных решений имеет и задача формирования базы знаний.
Отметим, что алгоритмы gA и zA также могут адаптироваться к своим данным.
В этом случае будем иметь двухуровневую адаптацию. На первом уровне адапти-
руется алгоритм заданного функционального назначения, а на втором, одновременно
с ним – адаптирующий алгоритм.
Литература
1. Шинкаренко В.И. Функциональная эффективность нечетко специфицированных алгоритмов // Проблемы
программирования. – 2006. – № 1. – С. 24-33.
2. Растригин Л.А. Адаптация сложных систем. – Рига: Зинатне, 1981. – 375 с.
3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие
изображений и видео. – М.: Диалог-МИФИ, 2002. – 384 с.
4. Успенский В.А., Семенов А.Л. Теория алгортмов: основные открытия и приложения. М.: Наука. Гл. ред.
физ.-мат. лит., 1987. – 288 с.
5. Борн Г. Форматы данных. – К.: Торгово-издательское бюро BHV, 1995. – 472 с.
6. Соболь И.М. Численные методы Монте-Карло. – М.: Наука. Гл. ред. физ.-мат. лит., 1973. – 311 с.
7. Ту Дж., Гонсалес Р. Принципы распознавания образов. – 1978. – 411 с.
В.І. Шинкаренко
Підхід до адаптації алгоритмів, орієнтований на знання
Пропонується методика формування альтернативно адаптивних алгоритмів. Знання визначаються з
застосуванням показників ступеня та області переваги алгоритмів. Для адаптації до вхідних даних алгоритмів
виявляються їх атрибути, за ними вхідні дані кластеризуються методом максимінних відстаней. Розроблене
програмне забезпечення для формування альтернативно адаптивних алгоритмів. Експериментально досліджені
можливості їх застосування при стисканні файлів без втрат.
V.I. Shynkarenko
Knowledge-Oriented Approach to Adaptation of Algorithms
The method to alternatively adaptive algorithm‘s designing is offered. Knowledge extracts with use such
measures as degree of the superiority and area of the superiority of algorithms. The attributes of source data
of algorithm‘s are detected and clustered by method of minimum and maximum distances. The specific
software is developed for designing alternatively adaptive algorithms. Facilities of their application to the
decision of a problem of lost-free compression of data are experimentally investigated.
Статья поступила в редакцию 18.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-6982 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T15:17:32Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Шинкаренко, В.И. 2010-03-22T13:02:09Z 2010-03-22T13:02:09Z 2008 Знание-ориентированный подход к адаптации алгоритмов / В.И. Шинкаренко // Штучний інтелект. — 2008. — № 3. — С. 388-395. — Бібліогр.: 7 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6982 004.051 Предлагается методика формирования альтернативно адаптивных алгоритмов. Знания вырабатываются с использованием показателей степени превосходства и области превосходства алгоритмов. Для адаптации к исходным данным алгоритмов выявляются их атрибуты, по ним исходные данные кластеризуются методом максиминного расстояния. Разработано программное обеспечение для построения альтернативно адаптивных алгоритмов. Экспериментально исследованы возможности их применения к решению задачи сжатия данных без потерь. Пропонується методика формування альтернативно адаптивних алгоритмів. Знання визначаються з застосуванням показників ступеня та області переваги алгоритмів. Для адаптації до вхідних даних алгоритмів виявляються їх атрибути, за ними вхідні дані кластеризуються методом максимінних відстаней. Розроблене програмне забезпечення для формування альтернативно адаптивних алгоритмів. Експериментально досліджені можливості їх застосування при стисканні файлів без втрат. The method to alternatively adaptive algorithm‘s designing is offered. Knowledge extracts with use such measures as degree of the superiority and area of the superiority of algorithms. The attributes of source data of algorithm‘s are detected and clustered by method of minimum and maximum distances. The specific software is developed for designing alternatively adaptive algorithms. Facilities of their application to the decision of a problem of lost-free compression of data are experimentally investigated. ru Інститут проблем штучного інтелекту МОН України та НАН України Обучающие и экспертные системы Знание-ориентированный подход к адаптации алгоритмов Підхід до адаптації алгоритмів, орієнтований на знання Knowledge-Oriented Approach to Adaptation of Algorithms Article published earlier |
| spellingShingle | Знание-ориентированный подход к адаптации алгоритмов Шинкаренко, В.И. Обучающие и экспертные системы |
| title | Знание-ориентированный подход к адаптации алгоритмов |
| title_alt | Підхід до адаптації алгоритмів, орієнтований на знання Knowledge-Oriented Approach to Adaptation of Algorithms |
| title_full | Знание-ориентированный подход к адаптации алгоритмов |
| title_fullStr | Знание-ориентированный подход к адаптации алгоритмов |
| title_full_unstemmed | Знание-ориентированный подход к адаптации алгоритмов |
| title_short | Знание-ориентированный подход к адаптации алгоритмов |
| title_sort | знание-ориентированный подход к адаптации алгоритмов |
| topic | Обучающие и экспертные системы |
| topic_facet | Обучающие и экспертные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6982 |
| work_keys_str_mv | AT šinkarenkovi znanieorientirovannyipodhodkadaptaciialgoritmov AT šinkarenkovi pídhíddoadaptacííalgoritmívoríêntovaniinaznannâ AT šinkarenkovi knowledgeorientedapproachtoadaptationofalgorithms |