English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм

Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

Информационно-графовая модель данных с нечеткой логикой

Гасанов Э.Э., Фещук А.А.
Кафедра математической теории интеллектуальных систем, механико-математический факультет МГУ им М.В.Ломоносова

Резюме:

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

 

В соответствии с [1] введем понятие задачи информационного поиска. Пусть $X$ – множество запросов; $Y$ – множество записей (объектов поиска); $\rho$ – бинарное отношение на $X\times Y$, называемое отношением поиска; тройку $S=\langle X,Y,\rho \rangle$ будем называть типом; тройку $I=\langle X,V,\rho\rangle$, где $V$ – некоторое конечное подмножество множества $Y$, будем называть задачей информационного поиска (ЗИП) типа $S$, и будем считать, что ЗИП $I=\langle X,V,\rho\rangle$ содержательно состоит в перечислении для произвольно взятого запроса $x\in X$ всех тех и только тех записей $y\in V$, таких что $x \rho y $.

По аналогии с этим определением введем понятие задачи нечеткого поиска. Пусть как и ранее $X$ – множество запросов, $Y$ – множество записей. Пусть задано отображение $\eta(x,y): X \times Y \rightarrow [0,1]$, которое будем называть отношением нечеткого поиска. Тройку $S=\langle X,Y,\eta \rangle$ будем называть типом нечеткого поиска; тройку $I=\langle X,V,\eta\rangle$, где $V$ – некоторое конечное подмножество множества $Y$, будем называть задачей нечеткого поиска (ЗНП) типа $S$, и будем считать, что ЗНП $I=\langle X,V,\eta\rangle$ содержательно состоит в том, чтобы для произвольного числа $c\in [0,1]$ и произвольного запроса $x\in X$ перечислить все те и только те записи $y\in V$, такие что $\eta(x,y)\geq c$.

Введем несколько упрощенное по сравнению с [1] понятие информационного графа.

Пусть $F$ – множество символов одноместных предикатов, определенных на множестве $X$, называемое базовым множеством.

Понятие информационного графа (ИГ) над базовым множеством $F$, определяется следующим образом. Берется конечная многополюсная ориентированная сеть. В ней выбирается некоторый полюс, который называется корнем. Остальные полюса называются листьями и им приписываются записи из $Y$, причем разным листьям могут быть приписаны одинаковые записи. Ребрам приписываются предикаты из множества $F$. Таким образом нагруженную многополюсную ориентированную сеть называем ИГ над базовым множеством $F$.

Функционирование ИГ определяется следующим образом. Скажем, что: ребро проводит запрос $x\in X$, если предикат, приписанный этому ребру, принимает значение 1 на запросе $x$; ориентированная цепочка ребер проводит запрос $x\in X$, если каждое ребро цепочки проводит запрос $x$; запрос $x\in X$ проходит в вершину $\beta$ ИГ, если существует ориентированная цепочка, ведущая из корня в вершину $\beta$, которая проводит запрос $x$; запись $y$, приписанная листу $\alpha$, попадает в ответ ИГ на запрос $x\in X$, если запрос $x$ проходит в лист $\alpha$. Ответом ИГ $U$ на запрос $x$ назовем множество записей, попавших в ответ ИГ на запрос $x$, и обозначим его ${\cal J}_U(x)$. Эту функцию ${\cal J}_U(x)$ будем считать результатом функционирования ИГ $U$.

Пусть нам дана ЗИП $I=\langle X,V,\rho\rangle$. Скажем, что ИГ $U$ допустим для ЗИП $I=\langle X,V,\rho\rangle$, если $ {\cal J}_U(x) \equiv \{ y\in V: x\rho y \}.$

Множество ИГ над базовым множеством $F$, допустимых для ЗИП $I$, обозначим ${\cal U}(I,F)$.

Аналогично введем понятие нечеткого информационного графа.

Пусть ${\cal F}= \{ f_a\vert f_a:X\rightarrow [0,1], a\in A \} $ – базовое множество нечетких функций на $X$, где $A$ – некоторое множество индексов.

Понятие нечеткого информационного графа (НИГ) над базовым множеством ${\cal F}$, определяется следующим образом. Берется конечная многополюсная ориентированная сеть. В ней выбирается некоторый полюс, который называется корнем. Остальные полюса называются листьями и им приписываются записи из $Y$, причем разным листьям могут быть приписаны одинаковые записи. Ребрам приписываются функции из множества ${\cal F}$. Таким образом нагруженную многополюсную ориентированную сеть называем НИГ над базовым множеством ${\cal F}$.

Функционирование НИГ определяется следующим образом. Проводимостью ребра НИГ назовем функцию, равную функции, приписанной этому ребру; проводимостью ориентированной цепочки ребер НИГ назовем функцию, равную минимуму проводимостей ребер цепочки; функцией фильтра вершины $\beta$ НИГ (обозначается $\varphi_\beta(x)$), назовем функцию равную максимуму функций проводимости ориентированных цепочек, ведущих из корня НИГ в вершину $\beta$; скажем, что запись $y$, приписанная листу $\alpha$, попадает в ответ НИГ на запрос $x\in X$ для числа $c\in [0,1]$, если $\varphi_\alpha(x)\geq c$. Ответом НИГ $U$ на запрос $x$ для числа $c\in [0,1]$ назовем множество записей, попавших в ответ НИГ на запрос $x$ для числа $c\in [0,1]$, и обозначим его ${\cal J}_U(x,c)$. Эту функцию ${\cal J}_U(x,c)$ будем считать результатом функционирования НИГ $U$.

Скажем, что НИГ $U$ допустим для ЗНП $I=\langle X,V,\eta\rangle$, если для любого запроса $x\in X$ и любого числа $c\in [0,1]$ выполняется ${\cal J}_U(x,c) = \{y\in V:\eta(x,y)\ge c\}$.

Множество НИГ над базовым множеством ${\cal F}$, допустимых для ЗНП $I$, обозначим ${\cal U}(I,{\cal F})$.

Если $y\in Y$, то множество $O(y,\eta )=\{x\in X:\eta(x,y)>0\}$ назовем тенью записи $y$.

Пусть $U$ – некоторый НИГ, $y$ – запись из $Y$. Через $L_U(y)$ обозначим множество листьев НИГ $U$, которым соответствует запись $y$.

Справедлива следующая теорема.

Теорема 1   НИГ $U$ допустим для ЗНП $I=\langle X,V,\eta\rangle$ тогда и только тогда, когда
  1. для любой записи $y\in V$ такой, что $O(y,\eta) \ne \emptyset$, выполняется
    $L_U(y)\ne \emptyset$, и $\max\limits_{\alpha\in L_U(y)}\varphi_{\alpha}(x)\equiv\eta(x,y)$;
  2. для любой записи $y\in V$ такой, что $O(y,\rho)=\emptyset$, выполняется
    либо $L_U(y)=\emptyset$, либо $\max\limits_{\alpha\in L_U(y)}\varphi_{\alpha}(x)\equiv\eta(x,y)\equiv 0$.

Базовое множество ${\cal F}$ называется полным для типа $S=\langle X,Y,\eta \rangle$, если для любой ЗНП $I=\langle X,V,\eta\rangle$ типа $S$ существует НИГ $U$ над базовым множеством ${\cal F}$, допустимый для ЗНП $I$.

Справедлив следующий результат, относящийся к проблеме полноты для НИГ.

Теорема 2   Базовое множество $\cal F$ будет полным для типа $S=\langle X,Y,\eta \rangle$ тогда и только тогда, когда для любой записи $y\in Y$ такой, что $O(y,\eta) \ne \emptyset$, функция $\eta(x,y)$ как функция от $x$ может быть представлена формулой вида

\begin{displaymath}\eta(x,y)=\max\limits_{i=\overline{1,n}}\min\limits_{j=\overline{1,m_i}} f_{ij}(x),\end{displaymath}


где $f_{ij}\in \cal F$.

Теоремы 1 и 2 доказываются аналогично теоремам 1 и 2 из [2].

 

Введем некоторый способ перехода от задачи информационного поиска к задаче нечеткого поиска, такой, что для числа $c=1$ задача нечеткого поиска совпадает с исходной задачей информационного поиска.

Далее всюду будем считать, что множество запросов $X=[0,1]$ и записей $Y=[0,1]$.

Рассмотрим некоторую функцию $\mu:\mbox{$\mbox{\msbm R}$}^2 \rightarrow [0,1]$, такую, что $\mu (x,y)=1 \Leftrightarrow (x,y)=(0,0)$ и $\mu (\lambda x,\lambda y)$ – невозрастающая функция от $\vert\lambda\vert$ при фиксированном $(x,y)$. Рассмотрим некоторую функцию $\mu':\mbox{$\mbox{\msbm R}$}\rightarrow [0,1]$, такую, что $\mu'(x)=1 \Leftrightarrow x=0$ и $\mu'(\lambda x)$ – невозрастающая функция от $\vert\lambda\vert$. Пару $\phi=\langle\mu,\mu'\rangle$ назовем основанием перехода. Основание $\phi=\langle\mu,\mu'\rangle$ позволяет задать оператор перехода $\phi$, который каждой ЗИП позволяет сопоставить некоторую ЗНП, а каждому ИГ некоторый НИГ.

Пусть $\rho\subseteq[0,1]^2$ – отношение поиска. Через $\phi(\rho)$ обозначим нечеткое отношение $\eta(x,y)=\sup\limits_{(x_0,y_0)\in \rho}\mu(x-x_0,y-y_0)$

Каждой ЗИП $I=\langle [0,1],V,\rho\rangle$ сопоставим ЗНП $\phi(I)=\langle [0,1],V,\phi(\rho)\rangle$.

Пусть $F$ – некоторое базовое множество предикатов на $[0,1]$. Если $f\in F$, то обозначим $N_f =\{x\in [0,1]:f(x)=1\}$. Если $A\subseteq [0,1]$, то обозначим $\mu'(A)(x)=\sup\limits_{x_0\in A}\mu'(x-x_0)$. Предикату $f\in F$ сопоставим функцию $\phi(f)(x)=\mu'(N_f)(x)$. Множеству $F$ сопоставим базовое множество нечетких функций $\phi(F)=\{\phi(f):f\in F\}$.

Пусть $U$ – ИГ над базовым множеством $F$. Сопоставим ему НИГ $\phi(U)$ над базовым множеством $\phi(F)$, полученный из ИГ $U$ заменой для каждого ребра ИГ $U$ предиката $f$, приписанного этому ребру, на функцию $\phi(f)$.

Скажем, что базовое множество предикатов $F$ и основание $\phi=\langle\mu,\mu'\rangle$ согласованы, если

  • $\forall A, B \in \{ N_f: f\in F\}$ справедливо $ \min(\mu'(A),\mu'(B))\equiv \mu'(A\cap B)$,
  • $ \forall y\ne 0$ справедливо $\mu(x,y)=0$,
  • $\mu(x,0)\equiv\mu'(x)$.

Скажем, что базовое множество предикатов $F$ и основание $\phi=\langle\mu,\mu'\rangle$ вырождены, если для любого отношения $\rho\subseteq[0,1]^2$, любой ЗИП $I$ типа $\langle [0,1],[0,1],\rho \rangle$ и любого ИГ $U\in{\cal U}(I,F)$ выполняется $\phi(U)\in{\cal U}(\phi(I),\phi(F))$.

 

Теорема 3   Базовое множество предикатов $F$ и основание $\phi=\langle\mu,\mu'\rangle$ вырождены, тогда и только тогда, когда они согласованы.

Литература

1
Гасанов  Э. Э. Информационно-графовая модель хранения и поиска данных. Интеллектуальные системы (1998) 3,  3-4, 163-192.

2
Гасанов  Э. Э. Об одной математической модели информационного поиска. Дискретная математика (1991) 3,  2, 69-76.

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 98-01-00130)

Труды IV Международной конференции по математическому моделированию, Москва (27 июня – 4 июля 2000 г.), – том II, Из-во "Станкин", Москва, 2001.

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru