Метрические свойства разбиений множеств произвольной природы
The interpretation of data content is closely connected with partition analysis. Different applications require different detailings of data partitions. For a system to be successful in a variety of problems, several partitions have to be ensured for cognitive-like techniques. A rational combination...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/1815 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метрические свойства разбиений множеств произвольной природы / А.Г. Каграманян, В.П. Машталир, Е.В. Скляр, В.В. Шляхов // Доп. НАН України. — 2007. — N 6. — С. 35–39. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859908635907325952 |
|---|---|
| author | Каграманян, А.Г. Машталир, В.П. Скляр, Е.В. Шляхов, В.В. |
| author_facet | Каграманян, А.Г. Машталир, В.П. Скляр, Е.В. Шляхов, В.В. |
| citation_txt | Метрические свойства разбиений множеств произвольной природы / А.Г. Каграманян, В.П. Машталир, Е.В. Скляр, В.В. Шляхов // Доп. НАН України. — 2007. — N 6. — С. 35–39. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | The interpretation of data content is closely connected with partition analysis. Different applications require different detailings of data partitions. For a system to be successful in a variety of problems, several partitions have to be ensured for cognitive-like techniques. A rational combination of low-level and high-level capabilities seems to be the most promising way to significantly improve the data understanding integrally. To reduce the gap between low-level features and high-level semantics in clustering, we propose, ground, and explore a new metric on partitions of an arbitrary measurable set.
|
| first_indexed | 2025-12-07T16:01:35Z |
| format | Article |
| fulltext |
Таким чином, в роботi наведено Y-подiбну модель ЖЦ ПЗ, яка вiдображує паралельне
проведення процесiв формалiзацiї вимог до проекту, проектування i кодування та вiдповiд-
них їм фаз тестування. На основi цiєї моделi запропонована класифiкацiя тестiв.
1. ISO 12207: 1995. – (ГОСТ Р – 1999). ИТ. Процессы жизненного цикла программных средств.
2. Didkovska M. Criteria for integration testing of component-based software // Электроника и связь. –
2004. – No 23. – С. 90–94.
3. Майерс Г. Искусство тестирования программ / Пер с англ. под ред. Б.А. Позина. – Москва: Финансы
и статистика, 1982. – 172 с.
Надiйшло до редакцiї 25.10.2006НТУ України “Київський
полiтехнiчний iнститут”
УДК 519.6
© 2007
А.Г. Каграманян, В.П. Машталир, Е.В. Скляр, В.В. Шляхов
Метрические свойства разбиений множеств
произвольной природы
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
The interpretation of data content is closely connected with partition analysis. Different appli-
cations require different detailings of data partitions. For a system to be successful in a vari-
ety of problems, several partitions have to be ensured for cognitive-like techniques. A rational
combination of low-level and high-level capabilities seems to be the most promising way to
significantly improve the data understanding integrally. To reduce the gap between low-level
features and high-level semantics in clustering, we propose, ground, and explore a new metric
on partitions of an arbitrary measurable set.
В задачах распознавания образов факторизация информации в том или ином признаковом
пространстве концептуально является одним из основных методов, лежащих в основе ин-
терпретации данных. С одной стороны, может требоваться идентификация объектов, про-
цессов или явлений с точностью до заданного или найденного в процессе анализа отношения
эквивалентности. С другой, построение классов эквивалентности — часто суть и цель обра-
ботки данных для последующего этапа тематической трактовки отдельных регистрируемых
представителей или даже фактор-множеств. В качестве типичного примера можно указать
традиционную кластеризацию данных [1], особенно с целью дальнейшего компаративного
распознавания [2]. Более детальным примером может служить сегментация изображений,
т. е. построение разбиения поля зрения, удовлетворяющее условию принадлежности носи-
теля “области интереса” одному классу эквивалентности [3]. В силу существенной неопре-
деленности входных данных и возможности применения различных алгоритмов можно по-
лучать различные результаты, в частности, чрезмерную (объект расположен в нескольких
факторах) или недостаточную (в классе эквивалентности находятся изображения фона)
сегментацию.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №6 35
Таким образом, достаточно очевидной и важной является задача получения инстру-
ментария для сравнения разбиений, отличия которых индуцированы либо вариативностью
их получения, либо различием источников информации. Принципиальное значение сопо-
ставление разбиений приобретает в задачах, когда характеристика факторов определяет
вычислительную эффективность обработки и интерпретации данных в целом [4, 5]. В рабо-
те вводится функционал, являющийся метрикой на разбиениях произвольных измеримых
множеств, и исследуются его свойства.
Постановка задачи. Пусть Ω — произвольное измеримое множество с мерой µ(◦),
которая может интерпретироваться как длина, площадь, объем, распределение масс, веро-
ятности, мощность множества. Пусть ΠΩ — множество конечных (по количеству факторов)
разбиений Ω, т. е. α ∈ ΠΩ, α = {X1,X2, . . . ,Xn}, Xi ⊆ Ω, µ(Xi) < ∞, i = 1, n, Ω =
n
⋃
i=1
Xi,
∀i, j ∈ {1, 2, . . . , n} : i 6= j ⇒ Xi
⋂
Xj = ∅. Требуется на ΠΩ × ΠΩ найти функционалы,
являющиеся метриками, и изучить их свойства.
Метрики на разбиениях множеств. Следует подчеркнуть, что для установления
мер сходства между разбиениями на концептуальном уровне необходимо учитывать степени
различия (в частности, в виде симметрических разностей) и сходства (в частности, в виде
пересечений) факторов. Доказана
Теорема 1. Для произвольного измеримого множества Ω с мерой µ(◦) и пары произ-
вольных его разбиений α, β ∈ ΠΩ, α = {X1,X2, . . . ,Xn}, β = {Y1, Y2, . . . , Ym} функционал
ρ(α, β) =
n
∑
i=1
m
∑
j=1
µ(Xi∆Yj)µ(Xi
⋂
Yj), (1)
где Xi∆Yj = (Xi \ Yj)
⋃
(Yj \ Xi) — симметрическая разность, является метрикой.
При доказательстве теоремы 1 найдено равносильное представление метрики (1)
ρ(α, β) =
n
∑
i=1
[µ(Xi)]
2 +
m
∑
j=1
[µ(Yj)]
2 − 2
n
∑
i=1
m
∑
j=1
[µ(Xi
⋂
Yj)]
2. (2)
Естественный интерес вызывает вопрос о связи метрики (1) с другими функционалами,
оценивающими сходство-различие. Сформулируем гипотезу об общем виде класса метрик
на произвольных разбиениях измеримых множеств.
Воспользуемся схемами геометрической вероятности. С одной стороны, разделим левую
и правую часть (1) на µ(Ω)2
ρ∗(α, β) =
ρ(α, β)
µ(Ω)2
=
n
∑
i=1
m
∑
j=1
µ(Xi∆Yj)
µ(Ω)
µ(Xi
⋂
Yj)
µ(Ω)
=
n
∑
i=1
m
∑
j=1
p(Xi∆Yj)p(Xi
⋂
Yj). (3)
Получаем: p(Xi∆Yj), p(Xi
⋂
Yj) — вероятности событий Xi∆Yj и Xi
⋂
Yj соответственно.
С другой стороны, напомним, что функционал, определяющий расстояние между двумя
ансамблями данных Q и R, зависит от условной энтропии H(Q,R) и взаимной энтропии
E(Q,R)
ρH(Q,R) = H(Q,R) − E(Q,R). (4)
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №6
Применительно к разбиениям метрика (4) конкретизируется следующим образом. Пусть
Ω ⊆ R
k, тогда мы имеем два вероятностных распределения: Q = (q1, q2, . . . , qn) и R =
= (r1, r2, . . . , rm), где qk = µ(Xk)/µ(Ω), k = 1, n, rl = µ(Yl)/µ(Ω), l = 1,m. Принимая во
внимание, что H(Q) = −
∑
i
qi ln qi, H(Q,R) = −
∑
i
qi
∑
j
rj(qi) ln rj(qi) и E(Q,R) = H(Q) +
+ H(R) − H(Q,R), окончательно находим
ρ∗(α, β) = ρ(P,Q) = −
m
∑
k=1
p(Xk) ln p(Xk) −
n
∑
l=1
p(Yl) ln p(Yl) +
+ 2
m
∑
k=1
n
∑
l=1
p(Xk
⋂
Yl) ln p(Xk
⋂
Yl). (5)
Перепишем (3) с учетом (2)
ρ(α, β) =
n
∑
i=1
[p(Xi)]
2 +
m
∑
j=1
[p(Yj)]
2 − 2
n
∑
i=1
m
∑
j=1
[p(Xi
⋂
Yj)]
2. (6)
Сравнивая (6) и (5), можно сделать предположение об общем виде метрики на разби-
ениях
ρ(α, β) =
n
∑
i=1
f(p(Xi)) +
m
∑
j=1
f(p(Yj)) −
n
∑
i=1
m
∑
j=1
f(p(Xi
⋂
Yj)). (7)
Отметим, что в метрике (6) или, что равносильно, (1) фактически использована функция
f(x) = x2, а метрика (5) базируется на функции f(x) = −x ln x. Вероятно, существуют
и другие функции, индуцирующие метрики на произвольных разбиениях измеримых мно-
жеств. Вопрос о свойствах функций в (7), которые бы обеспечивали выполнение аксиом реф-
лексивности, симметричности и главное — неравенства треугольника, остается открытым.
Варианты интерпретации метрики (1) на разбиениях множеств. Возвращаясь
к (3), проанализируем более общую вероятностную интерпретацию введенной метрики (1).
Если рассматривать множество Ω как пространство элементарных исходов, являющееся
элементом вероятностного пространства 〈Ω,FΩ, P 〉, где Ω — вообще говоря, произвольное
множество; FΩ — σ-алгебра его подмножеств, включающая в себя и Ω, и пустое множе-
ство, а P — вероятностная мера (или вероятность), относительно которой все элементы
FΩ измеримы, т. е. для любого X ∈ FΩ существует число 0 6 P (X) 6 1, удовлетворя-
ющее аксиоматике вероятности по Колмогорову [6], то на исходном пространстве можно
анализировать различные полные группы событий или наборы гипотез. Иными словами,
функционал (1) в виде (6) является метрикой на парах различных наборов гипотез или
полных группах событий.
Используя (3), можно ввести метрику и для сравнения дискретных случайных величин
ξ′ и ξ′′, заданных на исходном конечном вероятностном пространстве
ρ(ξ′, ξ′′)=
n
∑
i=1
[p(ξ′=xi)]
2
(
1−
m
∑
j=1
[p(ξ′′ = yi)]
2
)
+
m
∑
j=1
[p(ξ′′=yi)]
2
(
1−
n
∑
i=1
[p(ξ′ = xi)]
2
)
. (8)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №6 37
Теорема 2. Расстояние (в смысле функционала (1)) между двумя независимыми ко-
нечными равномерными распределениями с размерностями n и m имеет вид
ρ(ξ′, ξ′′) =
1
n
+
1
m
−
2
nm
.
Обратимся теперь к задачам, указанным во введении, которые привели к формализации
постановки задачи. Прежде всего, важным моментом является то, что на множестве Ω, как
правило, задана некоторая функция. Так, при сегментации изображений — это функция
распределения яркостей, построение “правильных” разбиений носителя которой и отвечает
задаче выделения из фона изображения объекта. В более общем случае, если в R
k задана
некоторая неотрицательная функция ϕ(x) > 0, для которой
∫
Ω
ϕ(x)dx < ∞, Ω ⊆ R
k, то она
индуцирует меру на X ⊆ Ω в виде интеграла µ(X) =
∫
X
ϕ(x)dx. Доказана
Теорема 3. Для произвольной области Ω ⊆ R
k и заданной на ней неотрицательной
(за исключением множества меры ноль) интегрируемой функции ϕ(x) имеет место не-
равенство
(
∫
Ω
ϕ(x)dx
)2
>
n
∑
i=1
m
∑
j=1
(
∫
Xi∩Yj
ϕ(x)dx
)2
+
n−1
∑
i=1
n
∑
i′=i+1
(
∫
Xi
ϕ(x)dx
)(
∫
Xi′
ϕ(x)dx
)
+
+
m−1
∑
j=1
m
∑
j′=j+1
(
∫
Yj
ϕ(x)dx
)(
∫
Yj′
ϕ(x)dx
)
,
где α = {Xi}
n
i=1, β = {Yj}
m
j=1, α, β ∈ ΠΩ — два произвольных разбиения Ω.
Доказанное неравенство позволяет формировать функцию невязки как разность левой
и правой частей и формулировать задачу поиска, например, разбиения α при заданном
β как задачу математического программирования, в которой ограничения индуцируются
требованиями к результатам кластеризации или сегментации.
Из теоремы 3 непосредственно следуют три интерпретации: для гипотез, полной группы
событий и дискретных случайных величин.
Следствие 1. Если в вероятностном пространстве заданы два набора гипотез A1 =
= {Si}
n
i=1 и A2 = {Tj}
m
j=1, то
n
∑
i=1
m
∑
j=1
[p(Si
⋂
Tj)]
2 +
n−1
∑
i=1
n
∑
i′=i+1
p(Si)p(Si′) +
m−1
∑
j=1
m
∑
j′=j+1
p(Tj)p(Tj′) 6 1.
Следствие 2. Если в некотором вероятностном пространстве произвольное событие
C разбито на два набора попарно непересекающихся подсобытий {Xi}
n
i=1, {Yj}
m
j=1, образу-
ющих полную группу, то
n
∑
i=1
m
∑
j=1
[p(Xi
⋂
Yj)]
2 +
n−1
∑
i=1
n
∑
i′=i+1
p(Xi)p(Xi′) +
m−1
∑
j=1
m
∑
j′=j+1
p(Yj)p(Yj′) 6 p[(C)]2.
38 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №6
Следствие 3. Если на одном вероятностном пространстве заданы две дискретные
случайные величины ξ′ и ξ′′ с конечным числом значений, то
n
∑
i=1
m
∑
j=1
[p(ξ′ = xi, ξ
′ = yj)]
2 +
n−1
∑
i=1
n
∑
i′=i+1
p(ξ′ = xi)p(ξ′ = xi′) +
+
m−1
∑
j=1
m
∑
j′=j+1
p(ξ′′ = yj)p(p(ξ′′ = yj′)) 6 1.
Введем на множестве разбиений ΠΩ функционал Φ(α) =
n
∑
i=1
[µ(Xi)]
2, тогда справедлива
Теорема 4. Для любых трех конечных разбиений α, β, γ ∈ ΠΩ множества Ω выпол-
няется
Φ(γ) > Φ(α
⋂
γ) + Φ(β
⋂
γ) − Φ(α
⋂
β).
Здесь пересечение разбиений трактуется как совокупность традиционных пересечений
отдельных факторов и соответствует более детальному представлению (измельчению)
фактор-множеств.
Результаты и перспективы исследований. Введена и изучена метрика на произ-
вольных разбиениях измеримых множеств. Показана ее связь с вероятностными интерпре-
тациями расстояний для наборов гипотез и полных групп событий. Высказана гипотеза
об общем виде класса метрик на разбиениях. Полезным направлением развития представ-
ляется конкретизация функционала (1) для сравнения разбиений, связанных отношением
частичного порядка. Это позволит улучшить некоторые схемы иерархической кластериза-
ции, основанные на ультраметриках. Особый интерес представляет нетривиальное (за счет
вынесения пересечений в отдельные факторы) продолжение метрики (1) на конечные по-
крытия измеримых множеств, что создаст предпосылки для постановки оптимизационных
задач факторизации произвольных измеримых множеств.
1. Jain A.K., Dubes R. C. Algorithms for clustering data. – Englewood Cliffs, New Jersey: Prentice Hall,
1988. – 320 p.
2. Машталир В.П., Шляхов В.В. Свойства мультиалгебраических систем в задачах компаративного
распознавания // Кибернетика и систем. анализ. – 2003. – № 6. – С. 12–32.
3. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. – Москва: Изд. дом “Вильямс”,
2004. – 928 с.
4. Kinoshenko D., Mashtalir V., Yegorova E. Clustering method for fast content-based image retrieval //
Computational Imaging and Vision / Ed M. A. Viergever. – Dordrecht: Springer. – 2006. – 32. – P. 946–952.
5. Kinoshenko D., Mashtalir V., Yegorova E., Vinarsky V. Hierarchical partitions for content image retrieval
from large-scale database // Machine Learning and Data Mining in Pattern Recognition / P. Perner.,
A. Imlya, eds. – Lecture Notes in Artificial Intelligence. – Berlin: Springer, 2005. – 3587. – P. 445–455.
6. Колмогоров А.Н. Основные понятия теории вероятностей. – Москва: Наука, 1974. – 120 с.
Поступило в редакцию 10.11.2006Харьковский университет радиоэлектроники
Щецинский университет, Институт математики, Польша
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №6 39
|
| id | nasplib_isofts_kiev_ua-123456789-1815 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T16:01:35Z |
| publishDate | 2007 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Каграманян, А.Г. Машталир, В.П. Скляр, Е.В. Шляхов, В.В. 2008-09-02T17:43:08Z 2008-09-02T17:43:08Z 2007 Метрические свойства разбиений множеств произвольной природы / А.Г. Каграманян, В.П. Машталир, Е.В. Скляр, В.В. Шляхов // Доп. НАН України. — 2007. — N 6. — С. 35–39. — Бібліогр.: 6 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/1815 519.6 The interpretation of data content is closely connected with partition analysis. Different applications require different detailings of data partitions. For a system to be successful in a variety of problems, several partitions have to be ensured for cognitive-like techniques. A rational combination of low-level and high-level capabilities seems to be the most promising way to significantly improve the data understanding integrally. To reduce the gap between low-level features and high-level semantics in clustering, we propose, ground, and explore a new metric on partitions of an arbitrary measurable set. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Метрические свойства разбиений множеств произвольной природы Article published earlier |
| spellingShingle | Метрические свойства разбиений множеств произвольной природы Каграманян, А.Г. Машталир, В.П. Скляр, Е.В. Шляхов, В.В. Інформатика та кібернетика |
| title | Метрические свойства разбиений множеств произвольной природы |
| title_full | Метрические свойства разбиений множеств произвольной природы |
| title_fullStr | Метрические свойства разбиений множеств произвольной природы |
| title_full_unstemmed | Метрические свойства разбиений множеств произвольной природы |
| title_short | Метрические свойства разбиений множеств произвольной природы |
| title_sort | метрические свойства разбиений множеств произвольной природы |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1815 |
| work_keys_str_mv | AT kagramanânag metričeskiesvoistvarazbieniimnožestvproizvolʹnoiprirody AT maštalirvp metričeskiesvoistvarazbieniimnožestvproizvolʹnoiprirody AT sklârev metričeskiesvoistvarazbieniimnožestvproizvolʹnoiprirody AT šlâhovvv metričeskiesvoistvarazbieniimnožestvproizvolʹnoiprirody |