Формализация оценки достаточного уровня декомпозиции модели предметной области
В статье сформулирован принцип достаточности декомпозиции. Предложен количественный показатель для измерения степени рациональности декомпозиции, выполнено модельное исследование его поведения. У статті сформульовано принцип достатності декомпозиції. Запропоновано кількісний показник для вимірювання...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58664 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Формализация оценки достаточного уровня декомпозиции модели предметной области / В.В. Любченко // Штучний інтелект. — 2010. — № 4. — С. 590-595. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860244427435409408 |
|---|---|
| author | Любченко, В.В. |
| author_facet | Любченко, В.В. |
| citation_txt | Формализация оценки достаточного уровня декомпозиции модели предметной области / В.В. Любченко // Штучний інтелект. — 2010. — № 4. — С. 590-595. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | В статье сформулирован принцип достаточности декомпозиции. Предложен количественный показатель для измерения степени рациональности декомпозиции, выполнено модельное исследование его поведения.
У статті сформульовано принцип достатності декомпозиції. Запропоновано кількісний показник для вимірювання ступеня раціональності декомпозиції, проведено модельне дослідження його поведінки.
The principle of decomposition sufficiency is formulated. The quantitative measure for rationality degree of decomposition is offered, the model research of its behavior is executed.
|
| first_indexed | 2025-12-07T18:34:42Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2010 590
7Л
УДК 004.82
В.В. Любченко
Одесский национальный политехнический университет, г. Одесса, Украина
vira.lyubchenko@gmail.com
Формализация оценки достаточного уровня
декомпозиции модели предметной области
В статье сформулирован принцип достаточности декомпозиции. Предложен количественный показатель
для измерения степени рациональности декомпозиции, выполнено модельное исследование его
поведения.
Введение
При построении моделей предметной области методом декомпозиции иссле-
дуемая предметная область условно разделяется на ряд подобластей (компонент,
элементов). Следует понимать, что детальность декомпозиции предметной области
на компоненты зависит от уровня знаний о предметной области и целевого назна-
чения ее модели.
Для структуризации процесса построения модели целесообразно выполнять де-
композицию итеративно, что дает возможность анализировать иерархическую структуру
и представить ее в виде дерева декомпозиции. В этом случае компонентам пред-
метной области C={c1,…,cn} соответствует множество вершин дерева V={v1,…,vn}
(каждая вершина vi∈V представляет отдельный компонент ci∈C), связанных между
собой множеством ребер E={e1,…,em}.
В дереве декомпозиции ребра могут соединять только вершины, принадлежащие
разным уровням. При этом ребро между вершинами vi и vj соответствует отношению
есть-часть (is-a-part) между соответствующими компонентами, то есть
( ) ( ) ( ), &i j i j i je v v depth v depth v c c∃ > → ⊂ , (1)
где depth(vi) – длина пути от вершины vi к корневой вершине.
Объединив вершины, находящиеся на одной глубине, можно сформировать
уровневые множества вершин дерева декомпозиции. Каждое уровневое множество
соответствует определенному уровню детализации представления в модели предметной
области.
Так как процедура декомпозиции выполняется итеративно, то важным вопросом
является выбор критерия остановки. Очевидно, что с увеличением глубины декомпо-
зиции растет информативность получаемой структуры. Но при этом возрастает и
сложность получаемой структуры. Можно предположить, что на определенном этапе
продолжение выполнения декомпозиции станет нерациональным, так как информация
о предметной области приобретет большую подробность, чем это необходимо. Это
приведет к получению значительной сложности дерева декомпозиции, увеличению
трудоемкости выполнения декомпозиции или росту значений других характеристик
сложности. То есть должен существовать некоторый оптимальный с точки зрения
соотношения показателей информативность-сложность уровень детализации, при до-
стижении которого становится нецелесообразным продолжение итеративного вы-
полнения декомпозиции.
Формализация оценки достаточного уровня декомпозиции модели...
«Штучний інтелект» 4’2010 591
7Л
Целью данной работы является определение критерия, позволяющего выбрать
оптимальную глубину дерева декомпозиции.
Принцип достаточности декомпозиции
Анализ ситуации показывает, что для всех компонент предметной области
существует достаточный уровень детализации, который обеспечивает их конструктив-
ное использование. Степень достаточности определяется исходя из целей построения
модели и ожидаемых результатов ее использования. Чаще всего этот процесс протекает
на интуитивном уровне, и эксперт не фиксирует в достаточной мере внимание на
принципах, которыми руководствуется. Тем не менее, этот момент является одним
из важнейших при формировании модели предметной области. Таким образом, по-
является необходимость в формализации данного принципа – принципа достаточности
декомпозиции.
Сформулируем принцип достаточности декомпозиции: всегда существует до-
статочный (не избыточный) уровень детализации модели предметной области, который
может быть задан на основе формализованного анализа целей и задач использования
этой модели.
Принцип достаточности декомпозиции можно рассматривать как развитие прин-
ципа существенности [1] и принципа достаточности [2], которые используют при
формировании моделей сложных объектов.
Рассмотрим, каким образом можно оценить рациональность декомпозиции мо-
дели предметной области.
Показатель рациональности декомпозиции
В [3] показано, что для измерения информативности неориентированных графов
можно использовать показатель информационной емкости, основанный на значениях
степеней вершин
∑
=
=
vN
i
ii aaI
1
2log , (2)
где VNv = – количество вершин графа, ai – степень i-й вершины, т.е. количество
инцидентных ей ребер.
В [3] показано, что мерой сложности неориентированного графа может служить
значение максимальной энтропии для этого графа, которое вычисляется по формуле
AAH 2max log= , (3)
где ∑
=
=
vN
i
iaA
1
– смежность графа.
Тогда в качестве показателя рациональности декомпозиции можно использо-
вать отношение
maxH
IKR = , (4)
где I, Hmax определяются формулами (2) и (3) соответственно. Справедливо следую-
щее утверждение.
Утверждение. При увеличении глубины дерева декомпозиции значение коэф-
фициента рациональности декомпозиции уменьшается.
Любченко В.В.
«Искусственный интеллект» 4’2010 592
7Л
Для доказательства справедливости утверждения необходимо показать, что
значение показателя информационной емкости I с увеличением глубины дерева
декомпозиции растет медленнее значения максимальной энтропии Hmax, т.е. ∆I<∆Hmax
или ∆Hmax – ∆I >0.
( ) ( ) ( ) ( )11
max
22
max
121
max
2
maxmax IHIHIIHHIH −−−=−−−=∆−∆ . (5)
Шеннон определил информацию как меру сокращения энтропии для системы с
постоянным количеством элементов [4]:
HHI −= max , (6)
где H – остаточная энтропия системы. Используя (6), можем записать (5) как
( ) ( )2 2 1 1 2 1
max max .H I H I H H H− − − = − = ∆ (7)
Известно, что увеличение количества элементов всегда должно увеличивать
полную энтропию системы, т.е. ∆H>0, поэтому действительно ∆Hmax – ∆I > 0.
Рассмотрим поведение показателя рациональности при увеличении глубины
дерева декомпозиции. Модельные исследования проводились для бинарного и тернар-
ного дерева с изменением значения глубины от 3 до 10. Результаты исследований
приведены в табл. 1.
Таблица 1 – Зависимость показателя рациональности декомпозиции от глубины
дерева декомпозиции
Значение показателя рациональности Kr Глубина дерева
декомпозиции L для бинарного дерева для тернарного дерева
3 0,268 0,261
4 0,227 0,206
5 0,193 0,167
6 0,168 0,140
7 0,148 0,122
8 0,132 0,105
9 0,119 0,093
10 0,108 0,084
Как видно из таблицы, модельный эксперимент подтверждает утверждение о том,
что при увеличении глубины дерева декомпозиции значение показателя рациональности
декомпозиции уменьшается. Аппроксимирующие зависимости для показателя рацио-
нальности декомпозиции Kr в случае регулярных деревьев имеют схожий характер:
1, 27 ,
1,65
1,20 0,02,
1,64
r
если дерево бинарное
L
K
если дерево тернарное
L
+=
−
+
, (8)
где L – глубина дерева декомпозиции.
На рис. 1 показано, как изменяется показатель рациональности декомпозиции с
увеличением глубины дерева.
Необходимо обратить внимание на то, что значение показателя рациональности
декомпозиции зависит не только от количества уровней декомпозиции и количества
вершин на каждом из уровней, но также зависит и от структуры соединений между
вершинами, принадлежащими разным уровням. Пример влияния нарушений структуры
дерева приведен в табл. 2.
Формализация оценки достаточного уровня декомпозиции модели...
«Штучний інтелект» 4’2010 593
7Л
0,050
0,100
0,150
0,200
0,250
0,300
3 4 5 6 7 8 9 10 L
Kr
0,050
0,100
0,150
0,200
0,250
0,300
3 4 5 6 7 8 9 10
L
Kr
a) б)
Рисунок 1 – Графики изменения значений Kr для бинарного (а)
и для тернарного (б) дерева. L – глубина дерева декомпозиции
Таблица 2 – Численные показатели для разных структур дерева декомпозиции
глубины 4
Структура дерева I Hmax Kr
30,529 134,606 0,227
31,020 134,606 0,230
31,510 134,606 0,234
32,000 134,606 0,238
33,510 134,606 0,249
Как и следовало ожидать, чем больше нарушается регулярность структуры со-
единений, тем больше становится значение показателя рациональности декомпозиции.
Нарушение структуры деревьев приводит к тому, что аппроксимирующие зави-
симости для показателя рациональности декомпозиции Kr не имеют схожий характер.
Например, в случае искажения структуры бинарного дерева, были получены такие
зависимости:
( )
( )
1,27 ,
1,65
0,07 exp 0,23 0,89 ,
4,130,21
36,20 exp
r
если дерево бинарное без искажений
L
K L если дерево с регулярными искажениями
если дерево с нерегулярными искажениями
L
+= + − −
+
+
. (9)
Однако тенденция уменьшения показателя рациональности декомпозиции Kr с уве-
личением ее глубины сохраняется (рис. 2).
Любченко В.В.
«Искусственный интеллект» 4’2010 594
7Л
Рисунок 2 – Графики изменения значений Kr
в зависимости от глубины дерева декомпозиции L
Критерий достаточности декомпозиции
Свойство уменьшения значения показателя рациональности с увеличением глу-
бины дерева декомпозиции позволяет сформулировать критерий остановки для итера-
тивной процедуры декомпозиции модели предметной области.
Можно утверждать, что всегда найдется такое значение Kmin, для которого
увеличение глубины декомпозиции (то есть Kr<Kmin) приведет к необоснованной детали-
зации. Это означает, что детальность описания предметной области растет, но с большой
вероятностью модель будет в дальнейшем использоваться не в полном объеме.
С другой стороны, всегда существует такое значение Kmax, для которого умень-
шение глубины декомпозиции (то есть Kr>Kmax) не обеспечивает детализации, необхо-
димой для достижения целей и задач использования модели предметной области.
На базе общего принципа достаточности декомпозиции становится возможным
сформулировать три основных условия, которые являются формализованными крите-
риями целенаправленного формирования модели предметной области:
1) условие недостаточной детализации модели:
Kr > Kmax; (10)
2) условие избыточной детализации модели:
Kr < Kmin; (11)
3) условие конструктивной декомпозиции:
Kmin ≤Kr ≤ Kmax. (12)
Выводы
Подводя итог, следует отметить, что принцип достаточности декомпозиции
обосновывает необходимость введения количественного показателя рациональности
декомпозиции.
Свойство уменьшения значения показателя рациональности декомпозиции с уве-
личением степени детализации декомпозиции позволяет сформулировать критерий
Формализация оценки достаточного уровня декомпозиции модели...
«Штучний інтелект» 4’2010 595
7Л
остановки для итеративной процедуры декомпозиции. Таким критерием может быть
достижение заданного априори критического значения показателя. Использование
данного критерия позволяет на этапе формализации представления предметной об-
ласти корректно задать модель предметной области в виде дерева ее декомпозиции.
Литература
1. Математическое моделирование химических производств / [Кроу К., Гамилец А., Хофман Т. и др.]. –
М. : Мир, 1973. – 392 с.
2. Крисилов В.А. Информационная технология принятия решений в задачах АСУ на базе коли-
чественной интегральной оценки сложных объектов : дис. ... доктора техн. наук / Крисилов В.А. –
Одесса : ОНПУ, 2004. – 242 с.
3. Bonchev D. Shannon’s Information and Complexity / D. Bonchev // Mathematical Chemistry Series. – 2003. –
Vol. 7, Complexity in Chemistry. – P. 155-187.
4. Шеннон К.Э. Работы по теории информации и кибернетике / Шеннон К.Э. – М. : Иностр. лит.,
1963. – 829 с.
В.В. Любченко
Формалізація оцінки достатнього рівня декомпозиції моделі предметної області
У статті сформульовано принцип достатності декомпозиції. Запропоновано кількісний показник для
вимірювання ступеня раціональності декомпозиції, проведено модельне дослідження його поведінки.
V. Liubchenko
Formalization of Sufficient Level Evaluation for Domain Model Decomposition
The principle of decomposition sufficiency is formulated. The quantitative measure for rationality degree of
decomposition is offered, the model research of its behavior is executed.
Статья поступила в редакцию 28.05.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58664 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:34:42Z |
| publishDate | 2010 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Любченко, В.В. 2014-03-29T11:51:44Z 2014-03-29T11:51:44Z 2010 Формализация оценки достаточного уровня декомпозиции модели предметной области / В.В. Любченко // Штучний інтелект. — 2010. — № 4. — С. 590-595. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58664 004.82 В статье сформулирован принцип достаточности декомпозиции. Предложен количественный показатель для измерения степени рациональности декомпозиции, выполнено модельное исследование его поведения. У статті сформульовано принцип достатності декомпозиції. Запропоновано кількісний показник для вимірювання ступеня раціональності декомпозиції, проведено модельне дослідження його поведінки. The principle of decomposition sufficiency is formulated. The quantitative measure for rationality degree of decomposition is offered, the model research of its behavior is executed. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Обучающие и экспертные системы Формализация оценки достаточного уровня декомпозиции модели предметной области Формалізація оцінки достатнього рівня декомпозиції моделі предметної області Formalization of Sufficient Level Evaluation for Domain Model Decomposition Article published earlier |
| spellingShingle | Формализация оценки достаточного уровня декомпозиции модели предметной области Любченко, В.В. Обучающие и экспертные системы |
| title | Формализация оценки достаточного уровня декомпозиции модели предметной области |
| title_alt | Формалізація оцінки достатнього рівня декомпозиції моделі предметної області Formalization of Sufficient Level Evaluation for Domain Model Decomposition |
| title_full | Формализация оценки достаточного уровня декомпозиции модели предметной области |
| title_fullStr | Формализация оценки достаточного уровня декомпозиции модели предметной области |
| title_full_unstemmed | Формализация оценки достаточного уровня декомпозиции модели предметной области |
| title_short | Формализация оценки достаточного уровня декомпозиции модели предметной области |
| title_sort | формализация оценки достаточного уровня декомпозиции модели предметной области |
| topic | Обучающие и экспертные системы |
| topic_facet | Обучающие и экспертные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58664 |
| work_keys_str_mv | AT lûbčenkovv formalizaciâocenkidostatočnogourovnâdekompoziciimodelipredmetnoioblasti AT lûbčenkovv formalízacíâocínkidostatnʹogorívnâdekompozicíímodelípredmetnoíoblastí AT lûbčenkovv formalizationofsufficientlevelevaluationfordomainmodeldecomposition |