Метрики онтологических моделей

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

Из известных метрик зачастую используются следующие:

1. Метрики циклов
   
2. Метрики разнообразия количества связей
   
3. Метрики разнообразия количества связей концептов
   
4. Метрики глубины онтологии
   
5. Метрики ширины онтологии
   
6. Метрики запутанности
   
7. Метрики ветвистости
   
8. Метрики Ингве-Миллера
   

Метрики циклов

Наличие циклов не помогает восприятию. Желательно, чтобы их не было вообще.

• Количество различных циклов в графе. В хорошей онтологии оно должно быть равно

нулю

• Количество вершин, входящих в какой-нибудь цикл деленное на количество вершин в

графе. Чем значение этой метрики меньше, тем лучше для онтологии, оптимальное значение равно нулю. 𝑚=𝑁_𝑣∈𝐶÷𝑛_𝐺 , где 𝑛_𝐺 – количество вершин графа; 𝐶 - множество вершин графа, входящих в хотя бы один цикл; 𝑁𝑣∈𝐶 - количество вершин графа, входящих в какой-нибудь цикл.

Метрики разнообразия количества связей

• Количество различных типов связей в графе.
  

Чем больше различных типов связей используется в онтологии, тем сложнее она для восприятия.
𝑚=𝑁_{𝑡∈𝑇𝐸}, где 𝑇𝐸={𝑡𝑦𝑝𝑒(𝑒)|(𝑒∈𝐸)} - множество всех типов связей графа, 𝑁_{𝑡∈𝑇𝐸}- количество различных типов связей.

• Нормированное количество различных типов связей.
  

Используется для расчета допустимого количества различных типов связей.
𝑚=𝑁_{𝑡∈𝑇𝐸}÷𝑛_𝐺, где 𝑁_{𝑡∈𝑇𝐸} - количество различных типов связей, 𝑛𝐺 – количество вершин графа.

Метрики разнообразия количества связей концептов

• Вершины с разными типами исходящих связей по отношению ко всем вершинам графа.
  

𝑚=𝑁_{𝑣∈𝑉𝐷}÷𝑛_𝐺, где 𝑉𝐷={𝑣∈𝐺|𝑁𝑡𝑦𝑝𝑒(𝑒𝑣)>1} - множество всех вершин графа, с разными типами исходящих связей, 𝑡𝑦𝑝𝑒(𝑒𝑣) – множество типов исходящих из вершины 𝑣 связей.

• Вершины с разными типами входящих связей по отношению ко всем вершинам графа.
  

𝑚=𝑁_{𝑣∈𝑉𝐷̃}÷𝑛_𝐺 где 𝑉𝐷̃={𝑣∈𝐺|𝑁𝑡𝑦𝑝𝑒(𝑒̃𝑣)>1} - множество всех вершин графа, с разными типами входящих связей, 𝑡𝑦𝑝𝑒(𝑒̃𝑣) – множество типов входящих в вершины 𝑣 связей.

• Среднее число типов входящих связей вершины графа
  

𝑚=∑_𝑣∈𝐺𝑁_{𝑡𝑦𝑝𝑒(𝑒𝑣̃)}÷𝑛_𝐺

• Среднее число различных типов исходящих связей вершины графа
  

𝑚=∑_𝑣∈𝐺𝑁_{𝑡𝑦𝑝𝑒(𝑒𝑣̃)}÷𝑛_𝐺

Метрики глубины онтологии

• Абсолютная глубина
  

Сумма длин всех путей графа (т.е. путей от корневой вершины к листу)
𝑚=∑^𝑃_𝑗𝑁_𝑗∈𝑃, где 𝑁_𝑗∈𝑃 - длина каждого пути 𝑗 из множества путей P графа g

• Средняя глубина
  

Абсолютная глубина деленная на количество путей в графе
𝑚=(1÷𝑛_𝑝⊆𝑔)∑^𝑃_𝑗𝑁_𝑗∈𝑃, где 𝑁_𝑗∈𝑃 - длина каждого пути 𝑗 из множества путей P графа g, 𝑛_𝑝⊆𝑔 - количество всех путей.

• Максимальная глубина
  

Максимальная длина пути
𝑚=𝑁_𝑗∈𝑃 ∀𝑖(𝑁_𝑗∈𝑃≥𝑁_𝑖∈𝑃), где N_j∈P и N_i∈P - длины пути j и i из множества путей P графа g.

• Минимальная глубина
  

𝑚=𝑁_𝑗∈𝑃 ∀𝑖(𝑁_𝑗∈𝑃≤𝑁_𝑖∈𝑃), где N_j∈P и N_i∈P - длины пути j и i из множества путей P графа g.

• Медиана глубины.
  

Значение, при котором 50% «нижних» единиц ряда данных будет иметь значение длины пути не больше медианы, и 50% «верхних» - не меньше медианы
𝑚=𝑁_{𝑗∈𝑃̃}, где 𝑁_{𝑗∈𝑃̃} – медиана глубины графа.

• Линия 90% глубины.
  

Значение, ниже которого находится 90% значений глубины.
𝑚=𝑃₉₀(𝑁_𝑗∈𝑃), где 𝑃₉₀(𝑁_𝑗∈𝑃) – 90-ый процентиль глубины графа.

• Среднее квадратичное отклонение глубины
  

Дополнительная метрика оценки глубины онтологии
𝑚=∑^𝑃_j(𝑁_𝑗∈𝑃− ∑^𝑃_𝑗𝑁_𝑗∈𝑃÷𝑛_𝑃⊆𝑔)²÷𝑛_𝑝⊆𝑔−1

• Среднее квадратичное отклонение глубины по отношению к средней глубине
  

𝑚=∑^𝑃_j(𝑁_𝑗∈𝑃− ∑^𝑃_𝑗𝑁_𝑗∈𝑃÷𝑛_𝑃⊆𝑔)²÷𝑛_𝑝⊆𝑔−1÷∑^𝑃_𝑗𝑁_𝑗∈𝑃÷𝑛_𝑃⊆𝑔

Метрики ширины онтологии

• Абсолютная ширина
  

Сумма количества вершин для каждого уровня иерархии по всем уровням
𝑚=∑^𝐿_𝑗𝑁_𝑗∈𝐿, где 𝑁_𝑗∈𝐿 – количество вершин на уровне 𝑗 из множества уровней L графа g

• Средняя ширина
  

Абсолютная ширина деленная на количество уровней иерархии
𝑚=(1÷𝑛_𝐿⊆𝑔)∑^𝐿_𝑗𝑁_𝑗∈𝐿, где 𝑁_𝑗∈𝐿 - количество вершин на уровне 𝑗 из множества уровней L графа g, 𝑛_𝑝⊆𝑔 - количество всех уровней графа

• Максимальная ширина
  

Количество вершин на уровне, с наибольшим количеством вершин
𝑚=𝑁_𝑗∈𝐿 ∀𝑖(𝑁_𝑗∈𝐿≥𝑁_𝑖∈𝐿), где N_j∈P и N_i∈P – количество вершин уровней j и i из множества уровней L графа g

• Минимальная ширина
  

Количество вершин на уровне, с наименьшим количеством вершин
𝑚=𝑁_𝑗∈𝐿 ∀𝑖(𝑁_𝑗∈𝐿≤𝑁_𝑖∈𝐿), где N_j∈P и N_i∈P – количество вершин уровней j и i из множества уровней L графа g.

• Среднее отношение ширины соседних уровней
  

Дополнительная метрика оценки ширины онтологии
𝑚=(1÷𝑛_𝐿⊆𝑔−1)∑^{𝑛𝐿⊆𝑔}_𝑖=2𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿}

• Максимальное отношение ширины соседних уровней
  

𝑚=(𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿}) ∀𝑘(𝑁_{𝑙𝑖∈𝐿}𝑁_{𝑙𝑖−1∈𝐿}≥𝑁_{𝑙𝑘∈𝐿}𝑁_{𝑙𝑘−1∈𝐿})

• Медиана отношения ширины соседних уровней
  

𝑚=𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿̃}

• Линия 90% ширины
  

Пороговое значение, ниже которого находится 90% значений ширины
𝑚=𝑃₉₀(𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿}), где 𝑃₉₀(𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿}) – 90-ый процентиль ширины графа

• Среднее квадратичное отклонение ширины
  

Дополнительная метрика оценки глубины онтологии
𝑚=∑^{𝑛𝐿⊆𝑔}_𝑖=2((𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿})−(1÷𝑛_𝐿⊆𝑔)∑^{𝑛𝐿⊆𝑔}_𝑖=2𝑁_{𝑙𝑖∈𝐿}÷𝑁_{𝑙𝑖−1∈𝐿} )²÷𝑛_{𝐿⊆𝑔−1}

• Среднее квадратичное отклонение ширины по отношению к средней ширине
  

𝑚=(∑𝑛𝐿⊆𝑔𝑖=2((𝑁𝑙𝑖∈𝐿÷𝑁𝑙𝑖−1∈𝐿)−(1÷𝑛𝐿⊆𝑔)∑𝑛𝐿⊆𝑔𝑖=2𝑁𝑙𝑖∈𝐿÷𝑁𝑙𝑖−1∈𝐿)2÷𝑛𝐿⊆𝑔−1)÷(1÷(𝑛𝐿⊆𝑔)−1)∑𝑛𝐿⊆𝑔𝑖=2(𝑁𝑙𝑖∈𝐿÷𝑁𝑙𝑖−1∈𝐿)

Метрики запутанности

• Вершины с несколькими родителями
  

Количество вершин, имеющих более одного родителя

• Среднее количество родительских вершин у вершины графа
  

𝑚=(1÷𝑛_𝐺)∑^𝐺_𝑣𝑁_{𝑆𝑣∈𝐺}, где 𝑆𝑣={𝑎∈𝐺|𝑖𝑠𝑎(𝑣,𝑎)} - множество всех родителей вершины 𝑣; 𝑁𝑆𝑣∈𝐺 - количество всех родителей у вершин 𝑣.

• Количество вершин с множественным наследованием по отношению ко множеству всех вершин графа
  

Чем чаще множественное наследие используется в онтологии, тем хуже она с точки зрения эргономики
𝑚=𝑁_{𝑣∈𝑀𝐼}÷𝑛_𝐺, где 𝑀𝐼={𝑣∈𝐺|∃𝑎1,𝑎2(𝑖𝑠𝑎(𝑣,𝑎1)∧𝑖𝑠𝑎(𝑣,𝑎2))} - множество всех вершин графа с более чем одной входящей дугой отношения 𝑖𝑠𝑎; 𝑁𝑣∈𝑀𝐼 - количество всех элементов этого множества

Метрики ветвистости

• Количество вершин, у которых есть и листья, и нелистовые ноды в качестве детей, по отношению ко всем кол-ву вершин у которых есть листья среди детей
  

Количество связей не должно превышать 7±2
𝑚=𝑁_{𝑣∈𝑆𝐿𝐸𝐴&𝑆𝐼𝐵}÷𝑁_{𝑣∈𝑆𝐿𝐸𝐴}, где 𝑆𝐿𝐸𝐴&𝑆𝐼𝐵- множество вершин, имеющих среди потомков как листья, так и внутренние вершины; 𝑁_{𝑣∈𝑆𝐿𝐸𝐴&𝑆𝐼𝐵} - количество таких вершин; 𝑆_𝐿𝐸𝐴- множество вершин, имеющих среди потомков листовые ноды; 𝑁𝑣∈𝑆𝐿𝐸𝐴 - количество таких вершин

• Минимальное количество детей-листьев у предпоследних вершин в графе
  

Используется для нахождения минимально допустимого значения детей-листьев у предпоследних вершин в графе
𝑚=𝑁^{𝑗⊆𝐿𝐸𝐴}_{𝑗∈𝑆𝐼𝐵},∀𝑖(𝑁^{𝑗⊆𝐿𝐸𝐴}_{𝑗∈𝑆𝐼𝐵}≤𝑁^{𝑖⊆𝐿𝐸𝐴}_{𝑖∈𝑆𝐼𝐵}), где 𝑁^{𝑗⊆𝐿𝐸𝐴}_{𝑗∈𝑆𝐼𝐵} - количество листьев набора j, имеющих общего родителя

• Среднее квадратичное отклонение детей-листьев у предпоследних вершин в графе
  

𝑚=(∑_{𝑗∈𝑆𝐼𝐵𝐿𝐸𝐴}𝑁^{𝑗⊆𝐿𝐸𝐴}_{𝑗∈𝑆𝐼𝐵}− (∑_{𝑗∈𝑆𝐼𝐵𝐿𝐸𝐴}𝑁^{𝑗⊆𝐿𝐸𝐴}_{𝑗∈𝑆𝐼𝐵}÷𝑛_{𝑆𝐼𝐵𝐿𝐸𝐴})²)÷𝑛_{𝑆𝐼𝐵𝐿𝐸𝐴}−1

Метрики Ингве-Миллера

• Отношение количества вершин с нормальной степенью ко всем вершинам
  

𝑚=𝑁_{𝑣∈𝐺𝐷}÷𝑛_𝐺, где 𝑛_𝐺- количество вершин графа; 𝐺𝐷={𝑣𝐼𝐺|𝑑𝑒𝑔(𝑣)≤9} - множество вершин с нормальной степенью; 𝑁𝑣∈𝐺𝐷 - количество вершин с нормальной степенью

• Средняя степень вершины графа
  

𝑚=∑_𝑣∈𝐺deg⁡(𝑣)÷𝑛_𝐺, где ∑_𝑣∈𝐺deg⁡(𝑣)- сумма степеней вершин графа; 𝑛_𝐺 - количество ребер графа

• Медиана степени вершины графа
  

𝑚=deg⁡(𝑣)̃, где deg⁡(𝑣)̃ - медиана степени вершины графа (т.е. значение степени, при котором 50% «нижних» единиц ряда данных будет иметь степень не больше медианы, и 50% «верхних» - не меньше медианы)

• Среднее квадратичное отклонение степени вершины графа
  

𝑚=(∑_𝑣∈𝐺(deg(𝑣)−(∑_𝑣∈𝐺deg⁡(𝑣)÷𝑛_𝐺))²)÷𝑛_𝐺−1

Прочее

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

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

Ссылки

• http://img.avalon.ru/News/20100629/Bolotnikova.pdf
  
• http://ivdon.ru/ru/magazine/archive/n4y2011/600