Мера отличия классификаций
Методы определения изоморфизма графов неприменимы к определению изоморфизма классификаций, так как не учитывают неделимости некоторых классов классификации. В то же время, структурное подобие не является отражением семантики классификации, что весьма важно при определении меры отличия двух классифик...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2016
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/115833 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Мера отличия классификаций / Г.А. Кравцов // Электронное моделирование. — 2016. — Т. 38, № 4. — С. 81-97. — Бібліогр.: 19 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-115833 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1158332025-02-23T19:00:30Z Мера отличия классификаций Measure of Difference Between Classifications Кравцов, Г.А. Математическое моделирование и вычислительные методы Методы определения изоморфизма графов неприменимы к определению изоморфизма классификаций, так как не учитывают неделимости некоторых классов классификации. В то же время, структурное подобие не является отражением семантики классификации, что весьма важно при определении меры отличия двух классификаций. Предложено понятие полной корректной классификации и введена дуальная мера отличия, отражающая известную проблему формы и содержания в философии. Методи визначення ізоморфізму графів не можуть бути застосовані до класифікацій, тому що вони не враховують неподільність деяких класів класифікації. В той же час, структурна схожість не є відображенням семантики класифікації, що досить важливо при визначенні міри відмінності двох класифікацій. Запропоновано поняття повної коректної класифікації та введено дуальну міру відмінності, що є відображенням відомої філософської проблеми форми і змісту. Methods for determining graph isomorphism are not applicable to determining isomorphism of classifications because of ignoring the indivisibility of certain classes of classification. At the same time structural similarity does not reflect the classification semantics that is very important in determining the measure of difference between the two classifications. The author proposes the concept of total correct classification and introduces the dual measures the difference reflecting the known problem of form and content in philosophy. 2016 Article Мера отличия классификаций / Г.А. Кравцов // Электронное моделирование. — 2016. — Т. 38, № 4. — С. 81-97. — Бібліогр.: 19 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/115833 004.932 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы |
| spellingShingle |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы Кравцов, Г.А. Мера отличия классификаций Электронное моделирование |
| description |
Методы определения изоморфизма графов неприменимы к определению изоморфизма классификаций, так как не учитывают неделимости некоторых классов классификации. В то же время, структурное подобие не является отражением семантики классификации, что весьма важно при определении меры отличия двух классификаций. Предложено понятие полной корректной классификации и введена дуальная мера отличия, отражающая известную проблему формы и содержания в философии. |
| format |
Article |
| author |
Кравцов, Г.А. |
| author_facet |
Кравцов, Г.А. |
| author_sort |
Кравцов, Г.А. |
| title |
Мера отличия классификаций |
| title_short |
Мера отличия классификаций |
| title_full |
Мера отличия классификаций |
| title_fullStr |
Мера отличия классификаций |
| title_full_unstemmed |
Мера отличия классификаций |
| title_sort |
мера отличия классификаций |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2016 |
| topic_facet |
Математическое моделирование и вычислительные методы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/115833 |
| citation_txt |
Мера отличия классификаций / Г.А. Кравцов // Электронное моделирование. — 2016. — Т. 38, № 4. — С. 81-97. — Бібліогр.: 19 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT kravcovga meraotličiâklassifikacij AT kravcovga measureofdifferencebetweenclassifications |
| first_indexed |
2025-11-24T12:20:04Z |
| last_indexed |
2025-11-24T12:20:04Z |
| _version_ |
1849674227827867648 |
| fulltext |
ÓÄÊ 004.932
Ã.À. Êðàâöîâ, êàíä. òåõí. íàóê,
Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå
èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû
(Óêðàèíà, 03164, Êèåâ, Ãåíåðàëà Íàóìîâà, 15,
e-mail: hryhoriy.kravtsov@gmail.com)
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
Ìåòîäû îïðåäåëåíèÿ èçîìîðôèçìà ãðàôîâ íåïðèìåíèìû ê îïðåäåëåíèþ èçîìîðôèçìà
êëàññèôèêàöèé, òàê êàê íå ó÷èòûâàþò íåäåëèìîñòè íåêîòîðûõ êëàññîâ êëàññèôèêàöèè. Â
òî æå âðåìÿ, ñòðóêòóðíîå ïîäîáèå íå ÿâëÿåòñÿ îòðàæåíèåì ñåìàíòèêè êëàññèôèêàöèè,
÷òî âåñüìà âàæíî ïðè îïðåäåëåíèè ìåðû îòëè÷èÿ äâóõ êëàññèôèêàöèé. Ïðåäëîæåíî ïî-
íÿòèå ïîëíîé êîððåêòíîé êëàññèôèêàöèè è ââåäåíà äóàëüíàÿ ìåðà îòëè÷èÿ, îòðàæàþùàÿ
èçâåñòíóþ ïðîáëåìó ôîðìû è ñîäåðæàíèÿ â ôèëîñîôèè.
Ìåòîäè âèçíà÷åííÿ ³çîìîðô³çìó ãðàô³â íå ìîæóòü áóòè çàñòîñîâàí³ äî êëàñèô³êàö³é, òîìó
ùî âîíè íå âðàõîâóþòü íåïîä³ëüí³ñòü äåÿêèõ êëàñ³â êëàñèô³êàö³¿.  òîé æå ÷àñ, ñòðóêòóð-
íà ñõîæ³ñòü íå º â³äîáðàæåííÿì ñåìàíòèêè êëàñèô³êàö³¿, ùî äîñèòü âàæëèâî ïðè âèçíà-
÷åíí³ ì³ðè â³äì³ííîñò³ äâîõ êëàñèô³êàö³é. Çàïðîïîíîâàíî ïîíÿòòÿ ïîâíî¿ êîðåêòíî¿ êëà-
ñèô³êàö³¿ òà ââåäåíî äóàëüíó ì³ðó â³äì³ííîñò³, ùî º â³äîáðàæåííÿì â³äîìî¿ ô³ëîñîôñüêî¿
ïðîáëåìè ôîðìè ³ çì³ñòó.
Ê ë þ ÷ å â û å ñ ë î â à: êëàññèôèêàöèÿ, ïîëíîòà, êîððåêòíîñòü, ìåðà, äóàëüíîñòü.
Ïîñòàíîâêà çàäà÷è. Àêòóàëüíîé çàäà÷åé ñåìàíòè÷åñêîãî ïîèñêà [1] ÿâ-
ëÿåòñÿ àâòîìàòè÷åñêîå íàõîæäåíèå áëèçêèõ ïî çíà÷åíèþ êîíöåïòóàëüíûõ
ïîíÿòèé [2]. Åñëè ïðåäñòàâèòü êîíöåïòóàëüíîå ïîíÿòèå êàê íåêîòîðóþ
êëàññèôèêàöèþ, òî óêàçàííàÿ çàäà÷à ñâîäèòñÿ ê íàõîæäåíèþ ìåðû ìåæäó
äâóìÿ êëàññèôèêàöèÿìè.
Áóäåì èñïîëüçîâàòü òåðìèíû èç ðàáîò [3—7]:
êëàññèôèêàöèÿ — îðèåíòèðîâàííîå äåðåâî, îòðàæàþùåå ñèñòåìó ìå-
ðåîëîãè÷åñêèõ èëè òàêñîíîìè÷åñêèõ äåëåíèé (ÌÒÄ);
êëàññèôèöèðîâàíèå — ïðîöåññ ïîñòðîåíèÿ êëàññèôèêàöèè;
îïðåäåëåíèå êëàññîâîé ïðèíàäëåæíîñòè — îòíåñåíèå îáúåêòà ê íåêî-
òîðîìó êëàññó ïîñòðîåííîé ðàíåå êëàññèôèêàöèè ñ òî÷íîñòüþ, íå íèæå
çàäàííîé;
êëàññèôèöèðîâàííûé îáúåêò — îáúåêò, îòíîñèòåëüíî êîòîðîãî âûïîë-
íåíà çàäà÷à îïðåäåëåíèÿ êëàññîâîé ïðèíàäëåæíîñòè.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 81
� Ã.À. Êðàâöîâ, 2016
Êàæäàÿ êëàññèôèêàöèÿ ÿâëÿåòñÿ îðèåíòè-
ðîâàííûì äåðåâîì [8], íî íå êàæäîå îðèåí-
òèðîâàííîå äåðåâî ÿâëÿåòñÿ êëàññèôèêàöèåé.
Íàïðèìåð, îðèåíòèðîâàííîå äåðåâî, ïðåäñòàâ-
ëåííîå íà ðèñ. 1, íå ÿâëÿåòñÿ êëàññèôèêàöèåé.
Ðåøåíèå ïîñòàâëåííîé çàäà÷è ïðåäñòàâëÿåòñÿ íåòðèâèàëüíûì, òàê êàê
òðåáóåòñÿ íàéòè ñåìàíòè÷åñêóþ áëèçîñòü èñõîäÿ èç èçâåñòíîé ïðîáëåìû
ôîðìû è ñîäåðæàíèÿ â ôèëîñîôèè [9]. Îäíàêî, äëÿ òîãî ÷òîáû ãàðàíòè-
ðîâàòü êîððåêòíîñòü íàõîæäåíèÿ íåêîòîðîé ìåðû ìåæäó êëàññèôèêàöèÿ-
ìè, ñëåäóåò ïîòðåáîâàòü êîððåêòíîñòè ñàìèõ êëàññèôèêàöèé êàê èñõîä-
íûõ äàííûõ. Ïðèíöèïû êîððåêòíîãî è ýôôåêòèâíîãî êëàññèôèöèðîâàíèÿ
îïèñàíû Êîðîòêîâûì [10]. Íåñîáëþäåíèå èõ âåäåò ê ðÿäó îøèáîê ïðè
ïîñòðîåíèè êëàññèôèêàöèé [3], à èìåííî: íåïîëíîå äåëåíèå, äåëåíèå ñ
èçëèøíèìè ÷ëåíàìè, ñáèâ÷èâîå äåëåíèå, ñêà÷åê â äåëåíèè.
Òàêèì îáðàçîì, çàäà÷à íàõîæäåíèÿ ìåðû áëèçîñòè èëè ìåðû îòëè÷èÿ
ìåæäó äâóìÿ êëàññèôèêàöèÿìè ÿâëÿåòñÿ àêòóàëüíîé. Ïðè ýòîì âàæíà íå
òîëüêî êîððåêòíîñòü êëàññèôèêàöèé, íî è èõ îäíîçíà÷íîñòü, êîòîðàÿ ãà-
ðàíòèðóåòñÿ ïîðÿäêîì ïðèìåíåíèÿ êðèòåðèåâ äåëåíèÿ. Îäíàêî, åñëè êëàñ-
ñèôèêàöèè ïîñòðîåíû ñ ïðèìåíåíèåì îäíîãî è òîãî æå ìíîæåñòâà êðè-
òåðèåâ ðàçäåëåíèÿ, òî îíè ÿâëÿþòñÿ ñèíîíèìè÷íûìè.  òî æå âðåìÿ, åñëè
ïðåäïîëîæèòü, ÷òî äâóì ýêñïåðòàì ïðåäëîæåíî âûïîëíèòü êëàññèôèöè-
ðîâàíèå îäíîãî è òîãî æå êîíöåïòóàëüíîãî ïîíÿòèÿ, íåò óâåðåííîñòè, ÷òî
îáà ýêñïåðòà äëÿ ðåøåíèÿ çàäà÷è ñôîðìèðóþò ðàâíûå ìíîæåñòâà êðè-
òåðèåâ äåëåíèÿ.
Ôîðìàëèçì êîððåêòíî ïîñòðîåííîé êëàññèôèêàöèè. Êëàññèôèêà-
öèÿ — ýòî îðèåíòèðîâàííîå äåðåâî [8], â óçëàõ êîòîðîãî íàõîäÿòñÿ ìàòå-
ìàòè÷åñêèå êëàññû, ñåìàíòè÷åñêè îïðåäåëÿþùèå ñèñòåìó ÌTÄ. Ýòî óò-
âåðæäåíèå îñíîâàíî íà îïèñàíèè ìàòåìàòè÷åñêîãî êëàññà ñ èñïîëüçîâà-
íèåì ïîíÿòèÿ êîíãëîìåðàòà êëàññîâ [11].
 ðàáîòå [12] âûäåëåíû ïëîñêèå è ïðîñòðàíñòâåííûå êëàññèôèêàöèè.
Ñëåäóåò çàìåòèòü, ÷òî ïëîñêàÿ êëàññèôèêàöèÿ åñòü ïëàíàðíîå îðèåíòèðî-
âàííîå äåðåâî ñ ñåìàíòèêîé äåëåíèÿ. Ñîãëàñíî [12] AI
i îçíà÷àåò íåêîòîðûé
êëàññ â ïëîñêîñòè äåëåíèÿ êëàññèôèêàöèè i, èìåþùèé ïóòü óòî÷íåíèÿ I,
êîòîðûé îäíîçíà÷íî îïðåäåëÿåò ïóòü â ãðàôå îò ñàìîãî îáùåãî êëàññà
êëàññèôèêàöèè äî íåêîòîðîãî óòî÷íåíèÿ AI
i .
Ïîä êîððåêòíî ïîñòðîåííîé ïëîñêîé êëàññèôèêàöèåé áóäåì ïîíèìàòü
òàêóþ ñèñòåìó ÌÒÄ, ïðè êîòîðîé äëÿ äâóõ êëàññîâ êëàññèôèêàöèè, AI
i è AY
i ,
Ã.À. Êðàâöîâ
82 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
A
i
A[1]
i
Ðèñ. 1. Îðèåíòèðîâàííîå äåðåâî, íå ÿâëÿþùååñÿ êëàñ-
ñèôèêàöèåé
òàêèõ, ÷òî äëÿ îòíîñèòåëüíûõ ðàññòîÿíèé R A A AI
i
I
i
Y
i( , )� è R A A AY
i
I
i
Y
i( , )� , ãäå
îòíîñèòåëüíîå ðàññòîÿíèå îçíà÷àåò ÷èñëî ïåðåõîäîâ ìåæäó êëàññàìè
êëàññèôèêàöèè [12], òàêèìè, ÷òî
R A A A R A A AI
i
I
i
Y
i
Y
i
I
i
Y
i( , ) ( , )� � � �1, (1)
ãäå A AI
i
Y
i� — àññîöèàòèâíàÿ áèíàðíàÿ îïåðàöèÿ îáîáùåíèÿ êëàññîâ êëàñ-
ñèôèêàöèè, à Q A AI
i
Y
i( , ) /�2 3 — òåîðåòè÷åñêîå çíà÷åíèå ìåðû îòëè÷èÿ
äâóõ êëàññîâ, óòî÷íÿþùèõ îäèí è òîò æå êëàññ,
Q A A
R A A A
R A A A R A A
I
i
Y
i I
i
Y
i
I
i
Y
i
I
i
I
i
( , )
( , )
( , ) ( ,
� �
� �
� � �
1
1
A R A A AY
i
Y
i
I
i
Y
i) ( , )� � �1
,
âûïîëíÿåòñÿ ñëåäóþùàÿ ñèñòåìà ðàâåíñòâ:
Q A A A Q A A AI
i
I
i
Y
i
Y
i
I
i
Y
i( , ) ( , )� � � ,
Q A AI
i
Y
i( , ) /�2 3 . (2)
Ñèñòåìà óðàâíåíèé (2) è òðåáîâàíèå (1) (ñîãëàñíî êîòîðîìó êëàññû AI
i
è AY
i èìåþò îäèí è òîò æå ðàíã K �1) ñëåäóåò ïîíèìàòü òàê: åñëè ó ïðîèç-
âîëüíîãî êëàññà A AI
i
Y
i� ðàíãà K ñóùåñòâóåò ìåíåå äâóõ óòî÷íÿþùèõ êëàñ-
ñîâ AI
i è AY
i ðàíãà K + 1, òî ìåðà îòëè÷èÿ ìåæäó êëàññàìè îäíîé êëàññè-
ôèêàöèè [12] íà ïëîñêîñòè äåëåíèÿ (èçìåðåíèè) Q A AI
i
Y
i( , ) åñòü âåëè÷èíà
ïîñòîÿííàÿ, ðàâíàÿ 2/3, íåçàâèñèìî îò âûáîðà AI
i è AY
i , åñëè I Y� .
Îòñþäà âûòåêàåò ñëåäóþùåå òðåáîâàíèå: ó ëþáîãî êëàññà, ÿâëÿþùå-
ãîñÿ âåðøèíîé îðèåíòèðîâàííîãî äåðåâà, — êëàññèôèêàöèè, äîëæíî áûòü
íå ìåíåå äâóõ óòî÷íÿþùèõ êëàññîâ, ðàíã êîòîðûõ íà åäèíèöó áîëüøå
ðàíãà ïðîèçâîëüíî âûáðàííîãî êëàññà, èëè íå äîëæíî áûòü íè îäíîãî.
Èìåííî ïîýòîìó íå êàæäîå ïðîèçâîëüíî îðèåíòèðîâàííîå äåðåâî ÿâëÿåò-
ñÿ êëàññèôèêàöèåé.
Èíòóèòèâíî ïîíÿòíî, ÷òî ïðè äåëåíèè êëàññà íà óòî÷íÿþùèå êëàññû
ìîæíî äîïóñòèòü îøèáêó: E A A O A AI
i
Y
i
Y
i
I
i( , ) / ( , )� �2 3 o , ãäå O A AY
i
I
i
o( , ) —
íàáëþäàåìàÿ ìåðà îòëè÷èÿ ìåæäó êëàññàìè îäíîé êëàññèôèêàöèè íà
ïëîñêîñòè äåëåíèÿ (èçìåðåíèè), à I Y� . Ñëó÷àé, êîãäà I Y� , ÿâëÿåòñÿ
èñêëþ÷åíèåì, òàê êàê îøèáêà E A AI
i
Y
i( , ) åñòü ëèíåéíàÿ ôóíêöèÿ îò îòíî-
ñèòåëüíîãî ðàññòîÿíèÿ R A AI
i
Y
i( , ), êîòîðîå ïðè I Y� ðàâíî íóëþ [12].
Ïîýòîìó îøèáêà ìîæåò âîçíèêíóòü òîëüêî ïðè íàáëþäåíèè ìåðû ìåæäó
äâóìÿ ðàçíûìè êëàññàìè.  òàêîì ñëó÷àå îïðåäåëèì îøèáêó ïðè íàáëþ-
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 83
äåíèè ìåðû îòëè÷èÿ ìåæäó äâóìÿ ðàçíûìè êëàññàìè êàê ðàçíîñòü ìåæäó
òåîðåòè÷åñêîé ìåðîé îòëè÷èÿ, ðàâíîé 2 3/ , è íàáëþäàåìîé ìåðîé â âèäå
Q A A A Q A A AI
i
I
i
Y
i
Y
i
I
i
Y
i( , ) ( , )� � � �1,
E A A O A AI
i
Y
i
Y
i
I
i( , ) / ( , )� �2 3 o ,
(3)
ãäå O A AY
i
I
i
o( , ) — íàáëþäàåìîå çíà÷åíèå ìåðû îòëè÷èÿ ìåæäó äâóìÿ
êëàññàìè AI
i è AY
i ; E A AI
i
Y
i( , ) — îøèáêà íàáëþäåíèÿ ìåðû îòëè÷èÿ, òàêàÿ,
÷òî � � �05 2 3, ( , ) /E A AY
i
I
i , åñëè I Y� , è E A AY
i
I
i( , ) �0 , åñëè I Y� .
Î÷åâèäíî, ÷òî åñëè íåêîòîðûé êëàññ Ai äåëèòñÿ íà N êëàññîâ A j
i
[ ], ãäå
j N�1, , òî ñóùåñòâóåò N 2 íåóíèêàëüíûõ çíà÷åíèé E A Aj
i
k
i( , )[ ] [ ] , ãäå k N�1, .
Ïîñêîëüêó O A A O A Aj
i
k
i
k
i
j
i
o o( , ) ( , )[ ] [ ] [ ] [ ]� [12], òî ñîãëàñíî (3) E A Aj
i
k
i( , )[ ] [ ] �
� E A Ak
i
j
i( , )[ ] [ ] . Òåîðåòè÷åñêè ÷èñëî óíèêàëüíûõ çíà÷åíèé E A Aj
i
k
i( , )[ ] [ ] ðàâ-
íî ( ) /N N2 2� . Ñðåäíåå àáñîëþòíîå çíà÷åíèå îøèáêè íàáëþäåíèÿ ìåðû
îòëè÷èÿ ñîñòàâèò
E A
N N
E A Ai
j
N
k
N
j
i
k
i( ) | ( , )|,[ ] [ ]�
� � �
1
2
1 1
(4)
ãäå | ( , )|[ ] [ ]E A Aj
i
k
i — àáñîëþòíîå çíà÷åíèå îøèáêè. Î÷åâèäíî, ÷òî åñëè
ìåðà îòëè÷èÿ O A AY
i
I
i
o( , ) /�2 3äëÿ ëþáûõ äâóõ êëàññîâ, óäîâëåòâîðÿþùèõ
(3) è òàêèõ, ÷òî I Y� , òî E Ai( ) �0. Ïî ñóòè, âåëè÷èíà (4) ïðåäñòàâëÿåò
ñîáîé èíòåãðàëüíûé ïîêàçàòåëü ñîãëàñîâàííîñòè (óñðåäíåííóþ îøèáêó)
äåëåíèÿ êëàññà ðàíãà K íà êàññû ðàíãà K + 1 è óäîâëåòâîðÿåò óñëîâèþ
0 2 3� �E AI
i( ) / .
Ðàññìîòðèì â êà÷åñòâå ïðèìåðà íåêîòîðóþ ïëîñêóþ êëàññèôèêàöèþ
(ðèñ. 2, à). Çàìåíèì îáîçíà÷åíèÿ êëàññîâ èíòåãðàëüíûì ïîêàçàòåëåì ñîã-
ëàñîâàííîñòè äåëåíèÿ E Ai( ) êëàññà ðàíãà K íà êëàññû ðàíãà K + 1 (ðèñ. 2, á).
Î÷åâèäíî, ÷òî ñîãëàñíî (4) èíòåãðàëüíûé ïîêàçàòåëü ñîãëàñîâàííîñòè äå-
ëåíèÿ E Ai( ) â ëèñòüÿõ äåðåâüåâ ðàâåí íóëþ. Êîëè÷åñòâåííûé ïîêàçàòåëü
ñîãëàñîâàííîñòè (consistency) ïëîñêîé êëàññèôèêàöèè îïðåäåëèì êàê
C A E Ai
I
I
i R A AI
i i M
( ) ( )
( , ) )
�
�1
, (5)
ãäå I — ìíîæåñòâî èçâåñòíûõ ïóòåé óòî÷íåíèÿ êëàññèôèêàöèè Ai ; M —
ñðåäíåå ÷èñëî óòî÷íÿþùèõ êëàññîâ â óçëàõ îðèåíòèðîâàííîãî äåðåâà,
íå ÿâëÿþùèõñÿ ëèñòüÿìè (ïàðàìåòð ïîëíîòû). Âûðàæåíèå (5) ñåìàíòè-
÷åñêè åñòü ñóììà äåéñòâèòåëüíûõ çíà÷åíèé îøèáîê E Ai( ) íà èíòåðâàëå
Ã.À. Êðàâöîâ
84 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
0 2 3� �E AI
i( ) / , âîçâåäåííûõ â ñòåïåíü, îòðàæàþùóþ óäàëåííîñòü êëàññà
îò êîðíÿ äåðåâà êëàññèôèêàöèè, ïðè óñëîâèè, ÷òî îøèáêà äëÿ êîðíåâîãî
êëàññà èìååò çíà÷åíèå 1. Ýòî íå óìåíüøàåò àáñîëþòíîãî çíà÷åíèÿ îøèáêè
ïðè ïîíèìàíèè ôàêòà, ÷òî ëþáàÿ áîëüøàÿ åäèíèöû ïîëîæèòåëüíàÿ ñòå-
ïåíü âåùåñòâåííîãî ÷èñëà â óêàçàííîì äèàïàçîíå ìåíüøå èñõîäíîãî çíà-
÷åíèÿ îøèáêè.
Çàìåíèâ íà ðèñ. 2, à, îáîçíà÷åíèÿ êëàññîâ ðàíãà K ÷èñëàìè, ðàâíûìè
êîëè÷åñòâó óòî÷íÿþùèõ êëàññîâ ðàíãà K + 1, ïîëó÷èì ïðåäñòàâëåíèå êëàñ-
ñèôèêàöèè â âèäå êîëè÷åñòâà óòî÷íÿþùèõ êëàññîâ (ðèñ. 3). Î÷åâèäíî, ÷òî
íà ðèñ. 3 íóëÿìè îáîçíà÷åíû ëèñòüÿ äåðåâà. Äëÿ òàêîé êëàññèôèêàöèè
ïàðàìåòð ïîëíîòû ñëåäóþùèé:
M �
� �
�
2 3 2
3
2 3( ) . (6)
Êàê âèäèì, äëÿ ïîëíûõ îðèåíòèðîâàííûõ äåðåâüåâ M åñòü àðíîñòü (äëÿ
ïîëíîãî áèíàðíîãî îðèåíòèðîâàííîãî äåðåâà M � 2).
Ñåìàíòè÷åñêè (5) åñòü èíòåãðàëüíàÿ îöåíêà âíóòðåííåé ñîãëàñîâàí-
íîñòè ïëîñêîé êëàññèôèêàöèè Ai , ïðèìåíÿåìîé ïðè îöåíêå îòíîñèòåëü-
íîé êîìïåòåíòíîñòè â îáñóæäàåìîì âîïðîñå ÷ëåíîâ ãðóïïû äëÿ ïðèíÿòèÿ
ãðóïïîâûõ ðåøåíèé [13], êîãäà îáñóæäàåìûì âîïðîñîì ÿâëÿåòñÿ íåêî-
òîðàÿ êëàññèôèêàöèÿ.
Ââåäåì ïîíÿòèå âåðòèêàëüíî ïîëíîé êëàññèôèêàöèè, îçíà÷àþùåå òà-
êóþ êëàññèôèêàöèþ, ïðåäñòàâèìóþ îðèåíòèðîâàííûì äåðåâîì, ó êîòîðîé
êëàññû, ïðåäñòàâëÿþùèå ñîáîé ëèñòüÿ îðèåíòèðîâàííîãî äåðåâà, ñåìàí-
òè÷åñêè íåäåëèìû ïî îïðåäåëåíèþ (ò.å. êëàññ íå ìîæåò áûòü ðàçäåëåí íà
ïîäêëàññû ñ ñåìàíòèêîé).
Ãîðèçîíòàëüíî ïîëíîé êëàññèôèêàöèåé íàçîâåì êëàññèôèêàöèþ, ó êî-
òîðîé êàæäûé îáîáùàþùèé êëàññ ïîäåëåí íà óòî÷íÿþùèå êëàññû òàê, ÷òî
óòî÷íÿþùèå êëàññû ïîêðûâàþò âñå âîçìîæíûå âàðèàíòû äåëåíèÿ, è
ìåæäó äâóìÿ ðàçëè÷íûìè óòî÷íÿþùèìè êëàññàìè ìåðà îòëè÷èÿ óäîâëåò-
âîðÿåò ñèñòåìå (2).
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 85
Ðèñ. 2. Ïëîñêàÿ êëàññèôèêàöèÿ (à) è ðàñïðåäåëåíèå èíòåãðàëüíîãî ïîêàçàòåëÿ ñîãëàñî-
âàííîñòè (á)
Ïîëíîé êîððåêòíîé êëàññèôè-
êàöèåé íàçîâåì òàêóþ, êîòîðàÿ ÿâ-
ëÿåòñÿ ãîðèçîíòàëüíî ïîëíîé è âåð-
òèêàëüíî ïîëíîé îäíîâðåìåííî.
Èç îïðåäåëåíèÿ ïîëíîé êîððåêò-
íîé êëàññèôèêàöèè ñëåäóåò, ÷òî êàæ-
äûé óòî÷íÿþùèé êëàññ, èìåþùèé
óòî÷íÿþùèå êëàññû, ÿâëÿåòñÿ ïîë-
íîé êîððåêòíîé êëàññèôèêàöèåé. Ýòî
ïîçâîëÿåò îïðåäåëèòü ìåòîä íèñõîäÿùåé äåêîìïîçèöèè: ëþáàÿ ïîëíàÿ
êîððåêòíàÿ êëàññèôèêàöèÿ ìîæåò áûòü ðàçëîæåíà íà ñîñòàâëÿþùèå èñ-
êëþ÷èòåëüíî ïåðå÷èñëåíèåì ïîëíûõ êîððåêòíûõ êëàññèôèêàöèé óòî÷-
íÿþùèõ êëàññîâ.
Ðàññìîòðèì êëàññèôèêàöèþ À (ñì. ðèñ. 2, à) è êëàññèôèêàöèè Â è Ñ
(ðèñ. 4). Ïðåäñòàâèì êëàññèôèêàöèþ À â âèäå äåêîìïîçèöèè. Ñîãëàñíî äàí-
íîìó âûøå îïðåäåëåíèþ ïîëó÷èì äâå ïîëíûå êëàññèôèêàöèè (ðèñ. 5, à). Â
ðåçóëüòàòå äåêîìïîçèöèè ïîëíûõ êîððåêòíûõ êëàññèôèêàöèé Â è Ñ ïîëó-
÷èì ïîëíûå êëàññèôèêàöèè  è Ñ (ðèñ. 5, á, â).
Îïèñàííûé ñïîñîá äåêîìïîçèöèè èìååò ïðèíöèïèàëüíîå çíà÷åíèå
ïðè îïðåäåëåíèè ñòðóêòóðíîãî îòëè÷èÿ äâóõ êëàññèôèêàöèé.
Èçîìîðôíîñòü êëàññèôèêàöèé. Ñòðóêòóðíóþ ìåðó îòëè÷èÿ îïðåäå-
ëèì êàê èçîìîðôèçì êëàññèôèêàöèé. Íàïîìíèì, ÷òî â òåîðèè ãðàôîâ
èçîìîðôèçìîì ãðàôîâ G V EG G� , è H V EH H� , íàçûâàåòñÿ áèåêöèÿ ìåæ-
äó ìíîæåñòâàìè âåðøèí ãðàôîâ f V VG H:
òàêàÿ, ÷òî ëþáûå äâå âåðøè-
íû, u è v, ãðàôà G ñìåæíû òîãäà è òîëüêî òîãäà, êîãäà âåðøèíû f u( ) è
f v( ) ñìåæíû â ãðàôå H. Çäåñü ãðàôû ñ÷èòàåì íåîðèåíòèðîâàííûìè è íå
èìåþùèìè âåñîâ âåðøèí è ðåáåð.  ñëó÷àå, åñëè ïîíÿòèå èçîìîðôèçìà
ïðèìåíÿåòñÿ ê îðèåíòèðîâàííûì èëè âçâåøåííûì ãðàôàì, íàêëàäûâàþò-
ñÿ äîïîëíèòåëüíûå îãðàíè÷åíèÿ íà ñîõðàíåíèå îðèåíòàöèè äóã è çíà÷å-
íèé âåñîâ.
Èçîìîðôèçìó ãðàôîâ ïîñâÿùåíî ìíîæåñòâî ðàáîò. Íàïðèìåð, â [14]
ïðåäëîæåí ïîäõîä, ïîçâîëÿþùèé ïðîâîäèòü ïîèñê èçîìîðôíûõ ïåðåñå-
÷åíèé äâóõ ãðàôîâ çà ïîëèíîìèàëüíîå âðåìÿ (íå áîëåå ÷åì O n( )4 ), îñíî-
âûâàÿñü íà îäíîì èç äâóõ èçâåñòíûõ ïîäõîäîâ — ïîèñêå ìàêñèìàëüíîãî
èçîìîðôíîãî ïåðåñå÷åíèÿ è ìèíèìàëüíîãî êîëè÷åñòâà ðåäàêòèðîâàíèé
(Minimal Edit Distance, MED). Íåñìîòðÿ íà ðàçëè÷èå ýòèõ ïîäõîäîâ ñîã-
ëàñíî ðåçóëüòàòàì ðàáîòû [15] ìåðû ïîäîáèÿ, ïîëó÷åííûå ýòèìè ñïîñîáà-
ìè, çàâèñÿò äðóã îò äðóãà ëèíåéíî. Òàê, â ìåòîäàõ MED ââîäÿòñÿ îïåðàòî-
ðû ðåäàêòèðîâàíèÿ ãðàôà, òàêèå êàê óäàëåíèå, äîáàâëåíèå, çàìåùåíèå
âåðøèí è äð. Ñóùåñòâóåò íàáîð îïåðàòîðîâ, êîòîðûå ïðåîáðàçóþò îäèí
Ã.À. Êðàâöîâ
86 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
2
3
0 0 0 0 0
2
Ðèñ. 3. Ïðåäñòàâëåíèå êëàññèôèêàöèè (ñì.
ðèñ. 2, à) êîëè÷åñòâîì óòî÷íÿþùèõ êëàññîâ
ãðàô â äðóãîé. Ìèíèìàëüíûé èç òàêèõ íàáîðîâ îïðåäåëÿåò ìåðó ïîäîáèÿ
ìåæäó ãðàôàìè.
 ìåòîäàõ, îñíîâàííûõ íà ïîèñêå ìàêñèìàëüíîãî èçîìîðôíîãî ïåðåñå-
÷åíèÿ, äëÿ äâóõ ãðàôîâ ïðîâîäèòñÿ ïîèñê ïàð ïîäãðàôîâ, ïðèíàäëåæàùèõ
ýòèì äâóì ãðàôàì, êîòîðûå ÿâëÿþòñÿ èçîìîðôíûìè äðóã äðóãó è
îïðåäåëÿþò èçîìîðôíîå ïåðåñå÷åíèå. Èçîìîðôíîå ïåðåñå÷åíèå, èìåþ-
ùåå ìàêñèìàëüíîå ÷èñëî âåðøèí, îïðåäåëÿåò ìåðó ïîäîáèÿ ìåæäó ãðà-
ôàìè. Âîîáùå ãîâîðÿ, çàäà÷à ïîèñêà ìàêñèìàëüíîãî èçîìîðôíîãî ïåðå-
ñå÷åíèÿ ÿâëÿåòñÿ NP-ïîëíîé è íå ðåøàåòñÿ çà ïîëèíîìèàëüíîå âðåìÿ.
Îäíàêî â íàñòîÿùåå âðåìÿ ðàçðàáîòàíî ìíîæåñòâî ìåòîäîâ, ïîçâîëÿþùèõ
ïóòåì ââåäåíèÿ íåêîòîðûõ îãðàíè÷åíèé è äîïîëíèòåëüíûõ óñëîâèé ðå-
øàòü äàííóþ çàäà÷ó çà ïîëèíîìèàëüíîå âðåìÿ [16]. Ïðåäëîæåííûå â [14,
16] è â àíàëîãè÷íûõ ðàáîòàõ ïîäõîäû íå ìîãóò áûòü èñïîëüçîâàíû äëÿ
êëàññèôèêàöèé, òàê êàê â íèõ ïðè îïðåäåëåíèè ëþáûõ äâóõ èçîìîðôíûõ
ïîäãðàôîâ èãíîðèðóåòñÿ òðåáîâàíèå íåäåëèìîñòè ëèñòüåâ îðèåíòèðîâàííîãî
äåðåâà êëàññèôèêàöèè.
Ïðèíÿòî èñïîëüçîâàòü êîäèðîâàíèå ãðàôîâ äëÿ ðàññìîòðåíèÿ èõ
ñâîéñòâ [17], â ÷àñòíîñòè ñìûñëîâîãî ïîäîáèÿ, â ìåòàýâðèñòèêå [18], äëÿ
êîìïàêòíîãî õðàíåíèÿ è ïîèñêà â áàçàõ äàííûõ. Êîä Ïðþôåðà [17], ïîç-
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 87
Ðèñ. 4. Êëàññèôèêàöèè Â è Ñ
Ðèñ. 5. Äåêîìïîçèöèè êëàññèôèêàöèé À, Â è Ñ
âîëÿþùèé çàïèñàòü äåðåâî n-ãî ïî-
ðÿäêà (ò.å. ñ ïðîíóìåðîâàííûìè âåð-
øèíàìè) ïîñëåäîâàòåëüíîñòüþ n �2
åãî âåðøèí, îêàçûâàåòñÿ áåñïîëåç-
íûì äëÿ êîäèðîâàíèÿ îðèåíòèðî-
âàííîãî äåðåâà, òàê êàê íå ïîçâî-
ëÿåò îòðàçèòü îðèåíòàöèþ ðåáåð
ïðè ïðîèçâîëüíîé íóìåðàöèè âåð-
øèí. Íàïîìíèì, ÷òî êîäèðîâàíèå
Ïðþôåðà ïåðåâîäèò ïîìå÷åííûå äåðåâüÿ ïîðÿäêà n â ïîñëåäîâàòåëüíîñòü
÷èñåë îò åäèíèöû äî n ïî òàêîìó àëãîðèòìó: ïîêà êîëè÷åñòâî âåðøèí
áîëüøå äâóõ, âûáèðàåòñÿ ëèñò v ñ ìèíèìàëüíûì íîìåðîì è â êîä Ïðþôåðà
äîáàâëÿåòñÿ íîìåð âåðøèíû, ñìåæíîé ñ v, à âåðøèíà v è èíöèäåíòíîå åé
ðåáðî óäàëÿþòñÿ èç äåðåâà. Îäíàêî, åñëè ïðåäïîëîæèòü, ÷òî ñóùåñòâóåò
íåêîòîðûé ñòðîãèé àëãîðèòì íóìåðàöèè âåðøèí êëàññèôèêàöèè, òî êîä
Ïðþôåðà ìîæåò îêàçàòüñÿ ïîëåçíûì.
Ïîëîæèì, ÷òî âûáîð ïðèíöèïîâ ðàçìåòêè íå îãðàíè÷åí è ðàññìîòðèì
ñëåäóþùèå ïðèíöèïû.
Âîñõîäÿùèé ðàíãîâûé ïðèíöèï ðàçìåòêè. Ëþáàÿ âåðøèíà êëàññè-
ôèêàöèè ðàíãà K èìååò áîëüøèé íîìåð ðàçìåòêè, ÷åì ëþáàÿ âåðøèíà
ðàíãà K �1.
Ñîãëàñíî âîñõîäÿùåìó ðàíãîâîìó ïðèíöèïó ðàçìåòêè îäíèì èç âîç-
ìîæíûõ âàðèàíòîâ ðàçìåòêè êëàññèôèêàöèè, èçîáðàæåííîé íà ðèñ. 2, à,
ìîæåò áûòü âàðèàíò, ïðåäñòàâëåííûé íà ðèñ. 6. Íåñëîæíî ïîêàçàòü, ÷òî
êîä Ïðþôåðà äëÿ îðèåíòèðîâàííîãî äåðåâà (ñì. ðèñ. 5, à) áóäåò âûãëÿäåòü
òàê: 6, 6, 6, 7, 7, 8. Êàê âèäèì, ïðè âîñõîäÿùåì ðàíãîâîì ïðèíöèïå
ðàçìåòêè êîä Ïðþôåðà óêàçûâàåò íà êîðåíü äåðåâà 8. Áîëåå êîðîòêàÿ
çàïèñü ìîæåò áûòü ïðåäñòàâëåíà â âèäå 63 72 81, ãäå êîðåíü äåðåâà åñòü 8.
Î÷åâèäíî, ÷òî ó 7 ñóùåñòâóåò äâà óòî÷íÿþùèõ êëàññà, à ó 6 — òðè. Íî
ó 8 â êîäå çíà÷èòñÿ òîëüêî îäèí óòî÷íÿþùèé êëàññ, ÷òî íå ñîîòâåòñòâóåò
äåéñòâèòåëüíîñòè. Äàííûé ôàêò — ñëåäñòâèå èç àëãîðèòìà ôîðìèðîâàíèÿ
êîäà Ïðþôåðà. ×òîáû îòâåòèòü íà âîïðîñ, ñêîëüêî âñåãî óòî÷íÿþùèõ
êëàññîâ ïåðâîãî ðàíãà ó êëàññèôèêàöèè, äîñòàòî÷íî ïîêàçàòåëü ñòåïåíè
ïðè êîðíå óâåëè÷èòü íà åäèíèöó. Äëÿ óäîáñòâà áóäåì èñïîëüçîâàòü çàïèñü
63 72 82, êîòîðóþ íàçîâåì ìîäèôèöèðîâàííûì êîäîì Ïðþôåðà.
Ðàññìîòðèì ñëåäóþùóþ êëàññèôèêàöèþ, èçîìîðôíóþ êëàññèôèêà-
öèè, ïðåäñòàâëåííîé íà ðèñ. 2, à. Ïðåäñòàâèì âàðèàíò ðàçìåòêè êëàññè-
ôèêàöèè (ðèñ. 7, à) ñîãëàñíî âîñõîäÿùåìó ïðèíöèïó (ðèñ. 7, á). Çàïèøåì
êîä Ïðþôåðà äëÿ êëàññèôèêàöèè, èçîáðàæåííîé íà ðèñ. 7, á, 6, 6, 7, 7, 7, 8
è ïðåäñòàâèì åãî â âèäå ìîäèôèöèðîâàííîãî êîäà: 62 73 82.
Ã.À. Êðàâöîâ
88 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
8
6
1 2 3 4 5
7
Ðèñ. 6. Âàðèàíò ðàçìåòêè êëàññèôèêàöèè,
ïðåäñòàâëåííîé íà ðèñ. 2
Èòàê, äëÿ äâóõ èçîìîðôíûõ êëàññèôèêàöèé (ñì. ðèñ. 2, à, è ðèñ. 6)
ïîëó÷åíû ìîäèôèöèðîâàííûå êîäû ñîîòâåòñòâåííî 63 72 82 è 62 73 82.
Î÷åâèäíî, ÷òî ðåøàþùóþ ðîëü èãðàåò ÷èñëî óòî÷íÿþùèõ êëàññîâ êëàñ-
ñèôèêàöèé, ÷òî ìîæíî ðàññìàòðèâàòü êàê êðèòè÷åñêèé ïàðàìåòð àëãîðèò-
ìà íóìåðàöèè âåðøèí êëàññèôèêàöèè. Èç ðèñ. 3 âèäíî, ÷òî ïðåäëîæåííûé
ïðèíöèï ðàçìåòêè îáåñïå÷èâàåò ðàçìåòêó, ïðåäñòàâëåííóþ íà ðèñ. 6.
Âîñõîäÿùèé ðàíãîâî-àðíûé ïðèíöèï ðàçìåòêè. Ëþáàÿ âåðøèíà
êëàññèôèêàöèè ðàíãà K èìååò áîëüøèé íîìåð ðàçìåòêè, ÷åì ëþáàÿ âåð-
øèíà ðàíãà K �1, ïðè óñëîâèè, ÷òî äëÿ ëþáûõ äâóõ âåðøèí ðàíãà K âåð-
øèíà ñ áîëüøèì ÷èñëîì óòî÷íÿþùèõ êëàññîâ èìååò ìåíüøèé íîìåð ðàç-
ìåòêè è åå óòî÷íÿþùèå êëàññû èìåþò ìåíüøèå íîìåðà ðàçìåòêè, ÷åì
óòî÷íÿþùèå êëàññû êëàññà ñ ìåíüøèì ÷èñëîì óòî÷íÿþùèõ êëàññîâ. Î÷å-
âèäíî, ÷òî âîñõîäÿùàÿ ðàíãîâî-àðíàÿ ðàçìåòêà åñòü âàðèàíò âîñõîäÿùåé
ðàíãîâîé ðàçìåòêè. Äëÿ êëàññèôèêàöèè, ïðèâåäåííîé íà ðèñ. 2, à, âîñõî-
äÿùàÿ ðàíãîâî-àðíàÿ ðàçìåòêà ïîêàçàíà íà ðèñ. 7, á.
Âûïîëíèì ðàíãîâî-àðíóþ ðàçìåòêó äëÿ èçîìîðôíîé êëàññèôèêàöèè,
ïðèâåäåííîé íà ðèñ. 7, à. Çàïèøåì êîä Ïðþôåðà äëÿ êëàññèôèêàöèè ñ
ðàçìåòêîé 6, 6, 6, 7, 7, 8 è ïðåäñòàâèì åãî â âèäå ìîäèôèöèðîâàííîãî êîäà:
63 72 82 (ðèñ. 8). Ïîëó÷åííûé êîä ñîâïàäàåò ñ êîäîì ïðè âîñõîäÿùåé
ðàíãîâî-àðíîé ðàçìåòêå èçîìîðôíîé êëàññèôèêàöèè íà ðèñ. 2, à. Îòñþäà
ñëåäóåò: åñëè ìîäèôèöèðîâàííûå êîäû Ïðþôåðà îðèåíòèðîâàííûõ äå-
ðåâüåâ, ðàçìå÷åííûõ ñîãëàñíî âîñõîäÿùåìó ðàíãîâî-àðíîìó ïðèíöèïó,
ñîâïàäàþò, òî îðèåíòèðîâàííûå äåðåâüÿ èçîìîðôíû.
Íèñõîäÿùèé ðàíãîâûé ïðèíöèï ðàçìåòêè. Ëþáàÿ âåðøèíà êëàññè-
ôèêàöèè ðàíãà K èìååò ìåíüøèé íîìåð ðàçìåòêè, ÷åì ëþáàÿ âåðøèíà ðàí-
ãà K �1. Ïðåäñòàâèì âàðèàíò ðàçìåòêè êëàññèôèêàöèè, ïðåäñòàâëåííûé íà
ðèñ. 2, à, ñîãëàñíî íèñõîäÿùåìó ðàíãîâîìó ïðèíöèïó (ðèñ. 9, à).
Çàïèøåì êîä Ïðþôåðà äëÿ êëàññèôèêàöèè ñ ðàçìåòêîé 2, 2, 3, 3, 3, 1 è
ïðåäñòàâèì åãî â âèäå ìîäèôèöèðîâàííîãî êîäà 22 33 12. Ñëåäóåò îáðàòèòü
âíèìàíèå, ÷òî 1 — êîðåíü îðèåíòèðîâàííîãî äåðåâà. Åñëè ïî êîäó 62 73 82
âèäíî, ÷òî â êëàññèôèêàöèè, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé êîðåíü, âîñåìü
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 89
Ðèñ. 7. Èçîìîðôíàÿ êëàññèôèêàöèÿ (îòíîñèòåëüíî êëàññèôèêàöèè, ïîêàçàííîé íà ðèñ. 2)
(à) è åå ðàçìåòêà (á)
êëàññîâ ïî 8, òî êàê ïîíÿòü, ÷òî êîä 22 33
12 òàêæå ïðåäñòàâëÿåò êëàññèôèêàöèþ
èç âîñüìè êëàññîâ? Ýòî ïðîñòî: åñëè ê
ñóììå ñòåïåíåé ìîäèôèöèðîâàííîãî êî-
äà äîáàâèòü åäèíèöó, òî ïîëó÷èì ÷èñëî
êëàññîâ êëàññèôèêàöèè (âåðøèí îðèåí-
òèðîâàííîãî äåðåâà). Â òàáë. 1 ïðèâåäå-
íû íåêîòîðûå ñâîéñòâà ìîäèôèöèðîâàí-
íîãî êîäà Ïðþôåðà äëÿ êëàññèôèêàöèè, ïðåäñòàâëåííîé íà ðèñ. 2, à.
Ïîñêîëüêó ñôîðìóëèðîâàííûé íèñõîäÿùèé ðàíãîâûé ïðèíöèï ðàçìåòêè
íå ïîçâîëÿåò ñóäèòü îá èçîìîðôíîñòè êëàññèôèêàöèé, óòî÷íèì åãî.
Íèñõîäÿùèé ðàíãîâî-àðíûé ïðèíöèï ðàçìåòêè. Ëþáàÿ âåðøèíà
êëàññèôèêàöèè ðàíãà K èìååò ìåíüøèé íîìåð ðàçìåòêè, ÷åì ëþáàÿ âåð-
øèíà ðàíãà K �1, ïðè óñëîâèè, ÷òî äëÿ ëþáûõ äâóõ âåðøèí ðàíãà K âåð-
øèíà ñ áîëüøèì ÷èñëîì óòî÷íÿþùèõ êëàññîâ èìååò ìåíüøèé íîìåð ðàç-
ìåòêè è åå óòî÷íÿþùèå êëàññû èìåþò ìåíüøèå íîìåðà ðàçìåòêè, ÷åì
óòî÷íÿþùèå êëàññû êëàññà ñ ìåíüøèì ÷èñëîì óòî÷íÿþùèõ êëàññîâ.
Ïðåäñòàâèì âàðèàíò ðàçìåòêè êëàññèôèêàöèè (ñì. ðèñ. 2, à) ñîãëàñíî
íèñõîäÿùåìó ðàíãîâî-àðíîìó ïðèíöèïó (ðèñ. 9, á). Çàïèøåì êîä Ïðþôåðà
äëÿ êëàññèôèêàöèè ñ ðàçìåòêîé 3, 3, 2, 2, 2, 1 è ïðåäñòàâèì åãî â âèäå ìî-
äèôèöèðîâàííîãî êîäà 32 23 12. Äëÿ îäíîé è òîé æå êëàññèôèêàöèè ïîëó-
÷èì ñëåäóþùèå êîäû: âîñõîäÿùèé — 62 73 82, íèñõîäÿùèé — 32 23 12.
Î÷åâèäíî, ÷òî ïîðÿäîê ñëåäîâàíèÿ ñòåïåíåé ìîäèôèöèðîâàííîãî êî-
äà Ïðþôåðà íå çàâèñèò îò âûáîðà íàïðàâëåíèÿ ðàíãîâî-àðíîãî ïðèíöèïà
ðàçìåòêè (âîñõîäÿùèé èëè íèñõîäÿùèé), ò.å. äëÿ ïîäòâåðæäåíèÿ èçîìîðô-
íîñòè äâóõ êëàññèôèêàöèé äîñòàòî÷íî ïîëó÷èòü ñòåïåíè ìîäèôèöèðîâàí-
íîãî êîäà Ïðþôåðà. Çàïèñè 2, 3, 2, êîòîðóþ íàçîâåì ðàíãîâî-àðíûì êî-
äîì, äîñòàòî÷íî, ÷òîáû âîññòàíîâèòü ñòðóêòóðó êëàññèôèêàöèè.
Èç òàáë. 2 âèäíî, ÷òî îðèåíòèðîâàííîå äåðåâî, êàê ìàòåìàòè÷åñêóþ
ôîðìàëèçàöèþ êëàññèôèêàöèè, ìîæíî çàêîäèðîâàòü ìåíüøèì êîëè÷åñò-
âîì ñèìâîëîâ, ÷åì ýòî îïðåäåëåíî òåîðåìîé Êýëè [17], ñîãëàñíî êîòîðîé
íà n âåðøèíàõ, ïðîíóìåðîâàííûõ ÷èñëàìè îò 1 äî n, ñóùåñòâóåò ðîâíî
nn�2 ðàçëè÷íûõ äåðåâüåâ, è ýòè äåðåâüÿ ìîãóò áûòü çàêîäèðîâàíû ïîñëåäî-
âàòåëüíîñòüþ èç n �2÷èñåë. Ïðè èñïîëüçîâàíèè ðàíãîâî-àðíûõ ïðèíöèïîâ
ðàçìåòêè äëèíà êîäèðóþùåé ïîñëåäîâàòåëüíîñòè ðàâíà ÷èñëó êëàññîâ,
êîòîðûå íå ÿâëÿþòñÿ ëèñòüÿìè îðèåíòèðîâàííîãî äåðåâà.
Íèñõîäÿùèé ðàíãîâî-àðíûé ïðèíöèï ðàçìåòêè èìååò ñëåäóþùèå ïðå-
èìóùåñòâà ïåðåä âîñõîäÿùèì ðàíãîâî-àðíûì ïðèíöèïîì. Åñëè â êëàññè-
ôèêàöèþ äîáàâëÿåòñÿ èëè óäàëÿåòñÿ âåðøèíà, ïðè èñïîëüçîâàíèè âîñõî-
äÿùåãî ðàíãîâî-àðíîãî ïðèíöèïà íåîáõîäèìî ïåðåðàçìåòèòü âñå îñòàëü-
íûå âåðøèíû. Ïðè èñïîëüçîâàíèè íèñõîäÿùåãî ðàíãîâî-àðíîãî ïðèíöèïà
Ã.À. Êðàâöîâ
90 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
8
7
4 5 1 2 3
6
Ðèñ. 8. Ðàçìåòêà èçîìîðôíîé êëàññè-
ôèêàöèè 6, 6, 6, 7, 7, 8
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 91
Ñâîéñòâî
êëàññèôèêàöèè
Çíà÷åíèå
Àëãîðèòì ïîëó÷åíèÿ çíà÷åíèÿ èç êîäà
âîñõîäÿùåãî 6
2
7
3
8
2
íèñõîäÿùåãî 2
2
3
3
1
2
×èñëî êëàññîâ 8 Ñóììà ñòåïåíåé êîäà, óâåëè÷åííàÿ íà åäèíèöó:
2 + 3 + 2 + 1 = 8
×èñëî ëèñòüåâ 5 ×èñëî êëàññîâ ìèíóñ ÷èñëî óíèêàëüíûõ îñíîâàíèé â
êîäå: 8 – 3 = 5
Ìàêñèìàëüíûé ðàíã
êëàññà â êëàññèôèêàöèè
2 Ðàíã êîðíÿ êëàññèôèêàöèè, êîòîðûé çàïèñàí êàê
ñàìîå ïðàâîå ÷èñëî, ðàâåí íóëþ [12]. Ñòåïåíü êîðíÿ
ïîêàçûâàåò, ñêîëüêî ýëåìåíòîâ êîäà èìååò ðàíã, íà
åäèíèöó áîëüøèé, ÷åì ðàíã êîðíÿ, ò.å. 1. Òàêèõ ÷èñåë
äâà. Ïîñëåäíèì ÷èñëîì, èìåþùèì ðàíã 1, åñòü ïîñ-
ëåäíåå ÷èñëî â ìîäèôèöèðîâàííîì êîäå. Ïîñêîëüêó
â êîäå íå îòðàæåíû óòî÷íÿþùèå êëàññû, ìàêñè-
ìàëüíûé ðàíã ðàâåí 2
Ïàðàìåòð ïîëíîòû M 2.(3)
2 3 2
3
2 3
� �
� .( )
Òàáëèöà 1. Ñâîéñòâà ìîäèôèöèðîâàííîãî êîäà Ïðþôåðà
Øàã âîññòàíîâëåíèÿ
Ðàíãîâî-àðíûé ïðèíöèï ðàçìåòêè
Âîñõîäÿùèé Íèñõîäÿùèé
Êîëè÷åñòâî êëàññîâ â êëàññèôèêàöèè 2 + 3 + 2 + 1 = 8 2 + 3 + 2 + 1 = 8
Ìîäèôèöèðîâàííûé êîä Ïðþôåðà 62 73 82 32 23 12
Êîðîòêèé êîä Ïðþôåðà 62 73 81 32 23 11
Ïîëíûé êîä Ïðþôåðà 6, 6, 7, 7, 7, 8 3, 3, 2, 2, 2, 1
Ãðàôè÷åñêîå ïðåäñòàâëåíèå äåðåâà ñ
ðàçìåòêîé Ðèñ. 7, á Ðèñ. 9
Èñõîäíàÿ êëàññèôèêàöèÿ (îðèåíòèðî-
âàííîå äåðåâî) Ðèñ. 2, à Ðèñ. 2, à
Òàáëèöà 2. Àëãîðèòì âîññòàíîâëåíèÿ äåðåâà ïî ðàíãîâî-àðíîìó ïðèíöèïó
ðàçìåòêè äëÿ êîäà 2, 3, 2
Ðèñ. 9. Ðàçìåòêà ñîãëàñíî íèñõîäÿùèì ðàíãîâîìó (à) è ðàíãîâî-àðíîìó (á) ïðèíöèïàì
ýòî íå ïîòðåáóåòñÿ, òàê êàê ðàçìåòêà êîðíÿ äåðåâà â ýòîì ñëó÷àå íèêîãäà
íå ìåíÿåòñÿ. Ñòðóêòóðà äàííûõ, ïðåäñòàâëÿþùàÿ äåðåâî, ïåðåäàåòñÿ óêà-
çàòåëåì íà êîðåíü, à ðåêóðñèâíàÿ ðàçìåòêà, íà÷èíàþùàÿñÿ ñ êîðíÿ, ÿâ-
ëÿåòñÿ ïðèîðèòåòíîé. Ïîýòîìó èñïîëüçîâàíèå íèñõîäÿùåãî ðàíãîâî-àð-
íîãî ïðèíöèïà ðàçìåòêè ñòàíîâèòñÿ öåëåñîîáðàçíûì.
Ðàíãîâî-àðíàÿ ñòðóêòóðà è ïðîâåðêà êîððåêòíîñòè ðàíãîâî-àð-
íîãî êîäà. Ðàíãîâî-àðíàÿ ñòðóêòóðà äàííûõ îòðàæàåò ñòðóêòóðó êëàññè-
ôèêàöèè, ðàçìå÷åííîé ñîãëàñíî ðàíãîâî-àðíîìó ïðèíöèïó è ïðåäñòàâëåí-
íîé ìîäèôèöèðîâàííûì êîäîì Ïðþôåðà. Àëãîðèòì ïðîâåðêè ïîñòðîåíèÿ
êîäà 2, 3, 2 ñëåäóþùèé (êîä ÷èòàåòñÿ ñïðàâà íàëåâî).
1. Çàïèñûâàåì ïåðâîå çíà÷åíèå ñòåïåíè, ñîîòâåòñòâóþùåå íóëåâîé
àðíîñòè:
Ðàíã Ïîêàçàòåëü ñòåïåíè
×èñëî êëàññîâ
Îæèäàåìîå Ðåàëüíîå Îøèáêà
0 2 1 1 0
2. Ñóììà ïîêàçàòåëåé ñòåïåíåé ñâèäåòåëüñòâóåò î òîì, ÷òî ñëåäóåò
îæèäàòü äâà ïîêàçàòåëÿ ñòåïåíè, ðåëåâàíòíûõ ïåðâîìó ðàíãó:
Ðàíã Ïîêàçàòåëü ñòåïåíè
×èñëî êëàññîâ
Îæèäàåìîå Ðåàëüíîå Îøèáêà
0 2 1 1 0
1 2, 3 2 2 0
3. Ïîñêîëüêó âûáðàíû âñå ïîêàçàòåëè ñòåïåíåé èç êîäà 2, 3, 2, ïîñòðîå-
íèå ðàíãîâî-àðíîé ñòðóêòóðû äàííûõ çàâåðøåíî.
Ñëåäóåò îáðàòèòü âíèìàíèå íà òî, ÷òî ÷èñëî îæèäàåìûõ êëàññîâ
íóëåâîãî ðàíãà âñåãäà ðàâíî åäèíèöå ïî îïðåäåëåíèþ, òàê êàê óêàçûâàåò
íà êîðåíü äåðåâà. Êàæäîå ïîñëåäóþùåå îæèäàåìîå ÷èñëî ñîäåðæèò ñóììó
ïîêàçàòåëåé ñòåïåíåé ïðåäûäóùåé ñòðîêè. Íà ýòîì îñíîâàí ïîäõîä ê
ïðîâåðêå êîððåêòíîñòè ðàíãîâî-àðíîãî êîäà.
Ðàññìîòðèì êîä 2, 3, 3 â âèäå ðàíãîâî-àðíîé ñòðóêòóðû:
Ðàíã Ïîêàçàòåëü ñòåïåíè
×èñëî êëàññîâ
Îæèäàåìîå Ðåàëüíîå Îøèáêà
0 3 1 1 0
1 2, 3 3 2 1
Ïðåäëîæåííàÿ ñòðóêòóðà äàííûõ ïîçâîëÿåò îïðåäåëèòü, ÿâëÿåòñÿ ëè íå-
êîòîðàÿ ïîñëåäîâàòåëüíîñòü ÷èñåë ðàíãîâî-àðíûì êîäîì.
Ã.À. Êðàâöîâ
92 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
Ïðåäñòàâèì A, B è C â âèäå êîðòåæà ìîäèôèöèðîâàííûõ êîäîâ Ïðþ-
ôåðà â êîìáèíàöèè ñ ðàíãîâî-àðíîé ðàçìåòêîé (òàáë. 3). Âîñïîëüçîâàâ-
øèñü èäååé ìåðû Æàêêàðà [19], îïðåäåëèì ñòðóêòóðíóþ ìåðó ïîäîáèÿ
êîðòåæåé I X Z( , ), ðàâíóþ âåëè÷èíå åäèíèöà ìèíóñ îòíîøåíèå ÷èñëà îäè-
íàêîâûõ êîäîâ â êîðòåæàõ ê ñóììå îäèíàêîâûõ (íåóíèêàëüíûõ) è îòëè÷-
íûõ (óíèêàëüíûõ) êîäîâ â êîðòåæàõ, ãäå X Z, — íåêîòîðûå ïîëíûå êîð-
ðåêòíûå êëàññèôèêàöèè.
Ïðåäñòàâëåííàÿ íà ðèñ. 10 ìåðà îòëè÷èÿ äëÿ êëàññèôèêàöèé D è F
ñâèäåòåëüñòâóåò î òîì, ÷òî êëàññû, äåëèìûå íà ðàçíîå ÷èñëî óòî÷íÿþùèõ
êëàññîâ, ÿâëÿþòñÿ àáñîëþòíî ðàçëè÷íûìè, à ñèñòåìà äåëåíèÿ òàêèõ êëàñ-
ñîâ — ðàçëè÷íûìè êëàññèôèêàöèÿìè. Êëàññèôèêàöèè, ïðåäñòàâëåííûå
êîäàìè (2, 3, 4, 3) è (2, 3, 2) ñ ó÷åòîì äåêîìïîçèöèè I (( , , , ), ( , , ))2 3 4 3 2 3 2 �
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 93
Êëàññèôèêàöèÿ Äåêîìïîçèöèÿ êëàññèôèêàöèè Èçîáðàæåíèå
A (2,3,2), (3), (2) Ðèñ. 1 è 3
B (3,3,2), (3), (3) Ðèñ. 2, à è 4, à
C (2,2,2), (2), (2) Ðèñ. 2, á è 4, á
Òàáëèöà 3. Êîðòåæè ìîäèôèöèðîâàííûõ êîäîâ Ïðþôåðà
Ìîäèôèöèðîâàííûé êîä Ïðþôåðà Äåêîìïîçèöèÿ êëàññèôèêàöèè
(2,3,4,3) (2,3,4,3), (2), (3), (4)
(2,3,2) (2,3,2), (2), (3)
Òàáëèöà 4. Äåêîìïîçèöèÿ ìîäèôèöèðîâàííûõ êîäîâ Ïðþôåðà
Øàã
Êëàññèôèêàöèÿ
À (ðèñ. 2, à) D (ðèñ. 10)
Ìîäèôèöèðîâàííûé êîä Ïðþôåðà 2,3,2 3
Êîðòåæ ìîäèôèöèðîâàííûõ êîäîâ
Ïðþôåðà, îïðåäåëÿþùèé äåêîìïîçèöèþ
êëàññèôèêàöèè
(2, 3, 2), (3), (2) �3)
Îïðåäåëåíèå êîðòåæà ìèíèìàëüíîé äëèíû Äëèíà êîðòåæà: 3
(êîðòåæ ìàêñèìàëü-
íîé äëèíû)
Äëèíà êîðòåæà: 1
(êîðòåæ ìèíè-
ìàëüíîé äëèíû)
Ñàìûé äëèííûé êîä êîðòåæà (2, 3, 2) �3)
Ñîäåðæèò ëè êîðòåæ ìàêñèìàëüíîé äëèíû
íàèáîëåå äëèííûé êîä èç êîðòåæà ìèíè-
ìàëüíîé äëèíû
Äà: (3) Äà: (3)
Òàáëèöà 5. Àëãîðèòì îïðåäåëåíèÿ âëîæåíèÿ îäíîé êëàññèôèêàöèè â äðóãóþ
� � �1
2
5
06, , ñâèäåòåëüñòâóþò î òîì, ÷òî óòî÷íåíèå íåäåëèìûõ êëàññîâ êëàñ-
ñèôèêàöèé D è F ïîçâîëÿåò çíà÷èòåëüíî óìåíüøèòü ìåðó îòëè÷èÿ äâóõ
êëàññèôèêàöèé (òàáë. 4).
Ñîãëàñíî îïèñàííîìó ïîâåäåíèþ ìåðû ñòðóêòóðíîãî îòëè÷èÿ äëÿ
êëàññèôèêàöèé, çàêîäèðîâàííûõ ïîñëåäîâàòåëüíîñòÿìè ( , ,..., , )k k k m è
( , ,..., , )n n n m , ãäå n k, � 2 , k n� è k n m N, ,
, ìåðà ñòðóêòóðíîãî îòëè÷èÿ
èìååò âèä I k k k m n n n m(( , ,..., , ),( , ,..., , )) �1. Òîãäà íåñëîæíî îïðåäåëèòü,
ÿâëÿåòñÿ ëè îäíà êëàññèôèêàöèÿ êëàññîì äðóãîé ïî êîðòåæó ìîäèôèöèðî-
âàííûõ êîäîâ Ïðþôåðà. Äëÿ ýòîãî äîñòàòî÷íî âûïîëíèòü øàãè, óêàçàííûå
â òàáë. 5.
Ñëåäîâàòåëüíî, äëÿ òîãî ÷òîáû îïðåäåëèòü, ñîäåðæèò ëè îäíà êëàññè-
ôèêàöèÿ äðóãóþ, äîñòàòî÷íî îòâåòèòü íà âîïðîñ: ñîäåðæèò ëè êîðòåæ
ìîäèôèöèðîâàííûõ êîäîâ Ïðþôåðà ìàêñèìàëüíîé äëèíû íàèáîëåå äëèí-
íûé êîä èç êîðòåæà ìèíèìàëüíîé äëèíû.
Ñèíîíèìè÷íûå êëàññèôèêàöèè è äóàëèçì ìåðû îòëè÷èÿ. Ñôîð-
ìóëèðóåì ñëåäóþùóþ ãèïîòåçó: åñëè ó äâóõ êëàññèôèêàöèé ñîâïàäàåò
ñòðóêòóðà è âñå êëàññû, êðîìå êëàññà íóëåâîãî ðàíãà, òî êëàññû íóëåâîãî
ðàíãà ýòèõ êëàññèôèêàöèé ñåìàíòè÷åñêè åñòü ñèíîíèìû. Íàïîìíèì, ÷òî
ñèíîíèìàìè â áèîëîãè÷åñêîé òàêñîíîìèè ÿâëÿþòñÿ äâà èëè áîëåå íàçâà-
íèÿ, îòíîñÿùèåñÿ ê îäíîìó è òîìó æå áèîëîãè÷åñêîìó òàêñîíó [4].
Ã.À. Êðàâöîâ
94 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
iD
[1]
iD [1]
iF[2]
iD [2]
iF[3]
iD
iF
Ðèñ. 10. Ìåðà I D F( , ) �1äëÿ êëàññèôèêàöèé D è F
iF
iF
iH
iH
[1]
iD [2]
iD [3]
iD
[1]
iF
[1]
iH [2]
iH
[2]
iF
[1,1]
iD [2,1]
iD
[1,2]
iD [2,2]
iD
[1,3]
iD
a á
Ðèñ. 11. Êëàññèôèêàöèè H è F ñ îäèíàêîâîé ñòðóêòóðîé è îäèíàêîâûìè íåäåëèìûìè
êëàññàìè
Åñëè äàííàÿ ãèïîòåçà âåðíà äëÿ êëàññèôèêàöèé, ïðåäñòàâëåííûõ íà
ðèñ. 11, à, òî îíà âåðíà è äëÿ êëàññèôèêàöèé, ïðåäñòàâëåííûõ íà ðèñ. 11, á,
÷òî ìîæíî îáúÿñíèòü, êàê ïðåäñòàâëåíèå ìíîæåñòâà ýëåìåíòîâ â âèäå ìíî-
æåñòâà åäèíè÷íûõ ìíîæåñòâ ýëåìåíòîâ èñõîäíîãî ìíîæåñòâà:{ , , , }a b c d
{{ },{ },{ },{ }}a b c d . Îòñþäà ñëåäóåò âûâîä: äâå êëàññèôèêàöèè ÿâëÿþòñÿ
ñèíîíèìè÷íûìè, åñëè ó íèõ îäèíàêîâûå íåäåëèìûå êëàññû.
Ýòî ïîçâîëÿåò ââåñòè åùå îäíó ìåðó íà êëàññèôèêàöèÿõ — ìåðó íå-
ñèíîíèìè÷íîñòè, êîòîðàÿ ýêâèâàëåíòíà ìíîæåñòâåííîé ìåðå Æàêêàðà
[19] äëÿ ìíîæåñòâ íåäåëèìûõ êëàññîâ äâóõ êëàññèôèêàöèé:
S A B
n L A L B
n L A L B
( , )
( ( ) ( ))
( ( ) ( ))
� �1
�
�
,
ãäå n L A( ( ))— ìîùíîñòü ìíîæåñòâà íåäåëèìûõ êëàññîâ êëàññèôèêàöèè A;
L A( ) — ìíîæåñòâî íåäåëèìûõ êëàññîâ êëàññèôèêàöèè A; n L B( ( )) — ìîù-
íîñòü ìíîæåñòâà íåäåëèìûõ êëàññîâ êëàññèôèêàöèè B; L B( )— ìíîæåñòâî
íåäåëèìûõ êëàññîâ êëàññèôèêàöèè B.
Òàêèì îáðàçîì, äëÿ äâóõ êëàññèôèêàöèé, A è B , ìîãóò áûòü îïðåäå-
ëåíû äâå ìåðû — ìåðà ñòðóêòóðíîãî îòëè÷èÿ I A B( , ) è ìåðà íåñèíîíè-
ìè÷íîñòè S A B( , ), ãäå ìåðà I A B( , ) îòâå÷àåò çà ôîðìó, à ìåðà S A B( , ) — çà
ñîäåðæàíèå. Äóàëüíàÿ ìåðà îòëè÷èÿ êëàññèôèêàöèé, íå ÿâëÿÿñü ñòðîãî
ìàòåìàòè÷åñêîé ìåðîé, åñòü äâîéêà âèäà M A B I A B S A B( , ) ( ( , ), ( , ))� , îò-
ðàæàþùàÿ èçâåñòíóþ ïðîáëåìó ôîðìû è ñîäåðæàíèÿ â ôèëîñîôèè [9].
Âûâîäû
Ðåøåíèå àêòóàëüíîé çàäà÷è ñåìàíòè÷åñêîãî ïîèñêà ñâîäèòñÿ ê íàõîæäå-
íèþ ìåðû îòëè÷èÿ ìåæäó äâóìÿ êëàññèôèêàöèÿìè, êîòîðàÿ èìååò äóàëü-
íóþ ïðèðîäó è ïðåäëîæåíà êàê äâîéêà ìåð ñòðóêòóðíîãî îòëè÷èÿ è íåñè-
íîíèìè÷íîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Áàñèïîâ À.À., Äåìè÷ Î.Â. Ñåìàíòè÷åñêèé ïîèñê: ïðîáëåìû è òåõíîëîãèè // Âåñò. Àñò-
ðàõàíñêîãî ãîñóäàðñòâåííîãî òåõíè÷åñêîãî óíèâåðñèòåòà. Ñåðèÿ: Óïðàâëåíèå, âû÷èñ-
ëèòåëüíàÿ òåõíèêà è èíôîðìàòèêà. — 2012. — ¹ 1. — Ñ. 104—111.
2. Áîëäà÷åâ À. Õàáðàõàáð. Êîíöåïòóàëüíîå îïèñàíèå èíäèâèäîâ. — [Ýëåêòðîííûé ðå-
ñóðñ]. — Ðåæèì äîñòóïà: https://habrahabr.ru/post/276271/ . — Äàòà äîñòóïà: ìàé, 2016.
3. Èâëåâ Þ.Â. Ëîãèêà // ÒÊ «Âåëáè». — Ì. : èçä-âî «Ïðîñïåêò», 2008. — 304 ñ.
4. Øàòàëêèí À.È. Òàêñîíîìèÿ. Îñíîâàíèÿ, ïðèíöèïû è ïðàâèëà. — Ì. : Òîâàðèùåñòâî
íàó÷íûõ èçäàíèé ÊÌÊ, 2012. — 600 ñ.
5. Óøàêîâ Ä.Í. Òîëêîâûé ñëîâàðü ðóññêîãî ÿçûêà. — Ì. : Àëüòà-Ïðèíò, 2005. — 1216 ñ.
6. Âüþãèí Â. Ìàòåìàòè÷åñêèå îñíîâû òåîðèè ìàøèííîãî îáó÷åíèÿ è ïðîãíîçèðîâàíèÿ. —
Ì. : ÌÖÍÌÎ, 2013. — 387 ñ.
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 95
7. Ãîëäáëàòò Ð. Òîïîñû. Êàòåãîðíûé àíàëèç ëîãèêè. — Ì. : Ìèð, 1983. — 488 ñ.
8. Àëüôñ Áåðçòèññ Ñòðóêòóðû äàííûõ. — Ì. : Ñòàòèñòèêà, 1974. — 408 ñ.
9. Êàðåëèíà Å.Â. Òåîðåòè÷åñêàÿ ñòðîãîñòü êàê ñîîòâåòñòâèå ñèñòåìû è ìåòîäà â ôèëî-
ñîôèè. — Êðàñíîÿðñê: Ñèáèðñêèé ôåäåðàëüíûé óíèâåðñèòåò, 2012. — 120 ñ.
10. Êîðîòêîâ Ý.Ì. Èññëåäîâàíèå ñèñòåì óïðàâëåíèÿ. — Ì. : ÄåÊÀ, 2004. — 336 ñ.
11. Adamek J., Herrlich H., Strecker G.E. Abstract and Concrete Categories. The Joy of Cats.
Availabe: http://katmat.math.uni-bremen.de/acc/acc.pdf. [Aceess: February of 2016]
12. Êðàâöîâ Ã.À. Ìîäåëü âû÷èñëåíèé íà êëàññèôèêàöèÿõ // Ýëåêòðîí. ìîäåëèðîâàíèå.—
2016. — 38, ¹ 1. — Ñ. 73—87.
13. Òîöåíêî Â.Ã. Ìåòîäû è ñèñòåìû ïîääåðæêè ïðèíÿòèÿ ðåøåíèé. Àëãîðèòìè÷åñêèé
àñïåêò. — Êèåâ: Íàóê. äóìêà. — 2002. — 382 ñ.
14. Àãàðêîâ À.Â. Ìåòîä ñðàâíåíèÿ äâóõ ãðàôîâ çà ïîëèíîìèàëüíîå âðåìÿ // Èñêóññò-
âåííûé èíòåëëåêò. — 2003. — ¹ 4. — Ñ. 172—184.
15. Bunke H. On a relation between graph edit distance and maximum common subgraph // Pat-
tern Recognition Letters. — 1997. — Vol. 18. — P. 689—694.
16. Messmer B.T., Bunke H. Subgraph Isomorphism in Polynomial Time. — University of Bern,
Institut fur Informatik und angewandte Mathematik. — [On-line] Available from: http://
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.870&rep=rep1&type=pdf. [Accessed:
March, 2016]
17. Êàñüÿíîâ Â.Í., Åâñòèãíååâ Â.À. Ãðàôû â ïðîãðàììèðîâàíèè: îáðàáîòêà, âèçóàëèçàöèÿ
è ïðèìåíåíèå — Ñàíêò-Ïåòåðáóðã: ÁÕÂ-Ïåòåðáóðã. — 2003. — 1104 ñ.
18. Ëþê Ø. Îñíîâû ìåòàýâðèñòèê [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://
qai.narod.ru/GA/metaheuristics.html . — Äàòà äîñòóïà: ìàé 2016.
19. Ñåìêèí Á.È., Ãîðøêîâ Ì.Â. Àêñèîìàòè÷åñêîå ââåäåíèå ìåð ñõîäñòâà, ðàçëè÷èÿ, ñîâìåñ-
òèìîñòè è çàâèñèìîñòè äëÿ êîìïîíåíòîâ áèîðàçíîîáðàçèÿ // Èçâ. Äàëüíåâîñòî÷íîãî
ôåäåðàëüíîãî óíèâåðñèòåòà. Ýêîíîìèêà è óïðàâëåíèå. — 2008. — ¹ 4. — Ñ. 31—46.
H.A. Kravtsov
MEASURE OF DIFFERENCE BETWEEN CLASSIFICATIONS
Methods for determining graph isomorphism are not applicable to determining isomorphism of
classifications because of ignoring the indivisibility of certain classes of classification. At the
same time structural similarity does not reflect the classification semantics that is very important
in determining the measure of difference between the two classifications. The author proposes the
concept of total correct classification and introduces the dual measures the difference reflecting
the known problem of form and content in philosophy.
K e y w o r d s: classification, completeness, correctness, measure, duality.
REFERENCES
1. Basipov, À.À. and Demich, O.V. (2012), “Semantic search: problems and technology”,
Vestnik Astrakhanskogo gosudarstvennogo universiteta, Seria: Upravlenie, vychislitelnaya
tekhnika i informatika, no. 1, pp. 104-111.
2. Boldachev, A. “Habrahabr: Conceptual description of individuals”, available at: https://
habrahabr.ru/post/276271/ (assessed May, 2016).
3. Ivlev, Yu.V. (2008), Logika [Logic], TK Velbi, Prospekt, Moscow, Russia.
4. Shatalkin, A.I. (2012), Taksonomiya. Osnovaniya, printsipy i pravila [Taxonomy. Grounds,
principles, and rules], Tovarishchestvo nauchnykh izdaniy KMK, Moscow, Russia.
Ã.À. Êðàâöîâ
96 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 4
5. Ushakov, D.N. (2005), Tolkovyi slovar russkogo yazyka [Explanatory dictionary of the Rus-
sian language], Alta-Print, Moscow, Russia.
6. Vyugin, V. (2013), Matematicheskie osnovy teorii mashinnogo obucheniya i prognoziro-
vaniya [Mathematical grounds of the theory of computer teaching and prediction], MTsNMO,
Moscow, Russia.
7. Goldblatt, R. (1983), Toposy. Kategornyi analiz logiki [Toposes. Category analysis of
logic], Mir, Moscow Russia.
8. Alfs Berztiss (1974), Struktura dannykh [Data structure], Statistika, Moscow, Russia.
9. Karelina, E.V. (2012), Teoreticheskaya strogost kak sootvetstvie sistemy i metoda v filosofii
[Theoretical strictness as correspondence of the system and method in philosophy], Siberian
Federal University, Krasnoyarsk, Russia.
10. Korotkov, E.M. (2004), Issledovanie system upravleniya [Study of control systems], DeKA,
Moscow, Russia.
11. Adamek, J., Herrlich, H. and Strecker, G.E. “Abstract and concrete categories. The Joy of
Cats”, available at: http://katmat.math.uni-bremen.de/acc/acc.pdf. (accessed February, 2016).
12. Kravtsov, H.A. (2016), “Model of computations on classifications”, Elektronnoe modeliro-
vanie, Vol. 38, no. 1, pp.73-87.
13. Totsenko, V.G. (2002), Metody i sistemy podderzhki prinyatiya resheniy. Algoritmicheskiy
aspect [Models and systems for decision making support], Naukova dumka, Kiev, Ukraine.
14. Agarkov, A.V. (2003), “Method of comparison of two graphs for polynomial time”, Iskusst-
vennyi intellect, no. 4, pp.172-184.
15. Bunke, H. (1997), “On a relation between graph edit distance and maximum common sub-
graph”, Pattern Recognition Letters, Vol. 18, pp. 689-694.
16. Messmer, B.T. and Bunke, H. “Subgraph Isomorphism in Polynomial Time”, University of
Bern, Institut fur Informatik und angewandte Mathematik, available at: http://citeseerx.
ist.psu.edu/viewdoc/download?doi=10.1.1.43.870&rep=rep1&type=pdf. (accessed March,
2016).
17. Kasyanov, V.N. and Evstigneyev, V.A. (2003), Grafy v programmirovanii: obrabotka,
vizualizatsiya, primenenie [Graphs in programming: processing, visualization and applica-
tion], BHV-Petersburg, St.-Petersburg, Russia.
18. Lyuk, S. (2013), “Essentials of metaheuristics”, available at: http://qai.narod.ru/GA/
metaheuristics.html (accessed May, 2016).
19. Semkin, B.I. and Gorshkov, M.V. (2008), “Axiomatic introduction of the measures of simi-
larity, difference, compatibility and dependence for biodiversity components”, Izvestiya
Dalnevostochnogo federalnogo universiteta. Ekonomika i upravlenie, no. 4, pp. 31-46.
Ïîñòóïèëà 25.02.16;
ïîñëå äîðàáîòêè 26.05.16
ÊÐÀÂÖÎÂ Ãðèãîðèé Àëåêñååâè÷, êàíä. òåõí. íàóê, äîêòîðàíò Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â
ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû.  2000 ã. îêîí÷èë Ñåâàñòîïîëüñêèé âîåííî-ìîðñêîé
èí-ò èì. Ï.Ñ. Íàõèìîâà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå,
êèáåðáåçîïàñíîñòü ñìàðò-ãðèä, êðèïòîãðàôèÿ, ðàçðàáîòêà ðàñïðåäåëåííûõ ãåòåðîãåííûõ
âû÷èñëèòåëüíûõ ñèñòåì.
Ìåðà îòëè÷èÿ êëàññèôèêàöèé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 4 97
|