Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАСПОЗНАВАНИЯ ЗАПРОСОВ-ЗАДАЧ КОММУНИКАЦИОННЫХ УСЛУГ

Аль-Хашеди А.А. 1 Обади А.А. 1 Нуриев Н.К. 1 Печеный Е.А. 1
1 ФГБОУ ВО «Казанский национальный исследовательский технологический университет»
В статье рассматривается предметная область с конечным множеством различных объектов. Каждый объект имеет конечное множество себе подобных экземпляров. Любой объект из предметной области однозначно характеризуется конечным множеством признаков. При этом два различных объекта могут иметь общие признаки. Вся предметная область в целом характеризуется набором признаков входящих в нее объектов. В работе рассматриваются две взаимосвязанные задачи: задача 1, задача 2. В задаче 1 требуется разбить всю предметную область на классы объектов, т.е. представить её как объединение классов объектов. Для решения этой задачи разработана математическая модель и соответствующий алгоритм процедуры разбиения, который позволяет исходя из размерности признаков объекта и их содержания выделить отдельные классы объектов в предметной области. После установления всех классов в предметной области рассматривается задача 2, построения математической модели и алгоритма распознавания экземпляра объекта с точки зрения принадлежности его какому-то классу объектов предметной области. Эта задача решается на основе Байесовского подхода, т.е. с использованием формул полной вероятности и Байеса. Для разъяснения процедур классификации и распознавания в работе приводится пример использования предложенных алгоритмов.
распознавание образов
коммуникационные услуги
классификация
математическая модель
класс
признак
объект
вероятность
теорема Байеса
1. Лепский А.Е. Математические методы распознавания образов / А.Е. Лепский, А.Г. Броневич. – Таганрог: Курс лекций, 2009. – 155 с.
2. Патрик Э.А. Основы теории распознавания образов / Пер. с англ.; под ред. Б.Р. Левина. – М.: Советское радио, 1980. – 407 c.
3. Потапов A.C. Распознавание образов и машинное восприятие: общий подход на основе принципа минимальной длины описания. – СПб.: Политехника, 2007. – 548 с.
4. Чабан Л.Н. Теория и алгоритмы распознавания образов / Л.Н. Чабан. – М.: Учебное пособие, М.: МИИГАиК, 2004. – 70 с.
5. Goswami J.C. Fundamentals of wavelets. Theory, algorithms, and applications / J.C. Goswami, A.K. Chan. – Wiley, 2000. – 359 р.

Цель работы

Решить две взаимосвязанные задачи: ЗАДАЧА 1 – разработать математическую модель и алгоритм вычислительной процедуры, который позволял бы классифицировать объекты из одной предметной области, исходя из их свойств (признаков), при условии, что часть признаков разных объектов могут совпадать. ЗАДАЧА 2 – на основе вероятностного подхода построить модель и алгоритм вычислительной процедуры, позволяющий идентифицировать принадлежность экземпляра объекта определенному классу из предметной области.

Постановка задачи

Данное U множество образов коммуникационных задач с общими признаками allhah01.wmf, m – количество признаков предметной области (в приведенном ниже примере 1 allhah02.wmf, рис. 1). Это множество необходимо разделить на подмножества признаков, соответствующие классам запросов задач данной предметной области. Система составляет словарь признаков с помощью списка правил [1]. Это множество будем обозначать через X. Пока не поступила первая услуга на систему, существует только один общий класс ω, область предпочтения которого является X. Во множестве образов коммуникационных задач предметной области U нас интересуют некоторые подмножества – класс в зависимости от типов коммуникационных услуг. Множество классов Ω = {ω1,..., ωm }, является конечным (в данной задаче распознавания allhah04.wmf и равно числу классов услуг: ω1 – класс услуг интернета, ω2 – класс услуг тарифов, ω3 – класс услуг оплаты, ω4 – класс услуг поддержек), эти классы образуют полную группу подмножеств из U (разбиение множества образов U), т.е. allhah05.wmf, и allhah06.wmf. для всех i ≠ j. Классифицировать объект x∈U по классам ωi значит найти такую индикаторную функцию g: U → Y, которая ставит в соответствие образу x∈U метку yi∈Y того класса ωi, которому он принадлежит т.е. g(x) = yi, если allhah07.wmf, где Y = {yi}, а yi признаки объекта.

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

Пусть на систему появилась не идентифицированная услуга x, для которой по своим описывающим признакам allhah08.wmf, n ≤ m, n – количество признаков задачи, для данной услуги необходимо создать новый класс из множества признаков предметной области allhah09.wmf. Эта услуга описывается некоторыми признаками в данной предметной области. Эти признаки сравняются с признаками предметной области на совпадение. Если все эти признаки полностью совпадают или с большой вероятностью совпадают с некоторыми признаками предметной области allhah10.wmf, то создается новый класс ωi. Если большинство признаков совпадают, но не все признаки, то в предметной области выводятся новые признаки и создается новый класс. В случае, когда появляется новая задача и в предметной области уже существуют некоторые классы allhah11.wmf, то данная услуга проверяется на принадлежность некоторому из существующих классов, если данные признаки совпадают с признаками некоторого класса, то данная задача относится к данному классу. Но если признаки описывающие данную задачу не совпадают или вероятность совпадения allhah12.wmf с признаками существующих классов, то проверяется на совпадения с общими признаками предметной области, чтобы создать новый класс в данной предметной области.

Алгоритм образования новых классов

На рис. 1, блок А, показано, что X1 – область предпочтения первого класса ω1, а X2 – область предпочтения второго класса ω2. allhah13.wmf – общие признаки. allhah14.wmf – унифицированные признаки. И так далее при поступлении новых услуг в систему создаются новые классы.

На рис. 2 процедура выполнения данного алгоритма следующая:

1. В блоке 1, А является обучающая выборка объектов, в которой определяются правила выбора признаков и конечное число количество признаков данной предметной области. Множество X является совокупностью признаков предметной области, составляющейся из m признаков (в приведенном ниже примере 1 allhah15.wmf, рис. 1), x – вектор признаков распознаваемого образа, образующийся из n признаков и обычно n < m.

2. В блоке 2 сравняется m с n, если m = n, то множество остается таким и задача (распознаваемый образ) относится к общему классу.

allhahed1.tif

а б в

Рис. 1. Разбиение множества признаков на подмножества классов

3. В блоке 3, если n < m, то для сравнения определяется начальный признак множества предметной области i = 1 и начальный признак распознаваемого образа j = 1, и начинается сравнение начального признака распознаваемого образа на совпадение со всеми признаками множества предметной области начинается с первым. Если не совпадают с первым признаком предметной области, то сравнение на совпадение будет с вторым признаком предметной области i + 1 и т.д. до того, как найдётся совпадающий элемент в множестве признаков или i станет равным m (i = m), т.е. признак распознаваемого элемента сравняется со всеми признаками предметной области с первого признака i = 1 до последнего i = m. Затем на сравнение берем следующий признак распознаваемого образа j + 1, данный признак будем сравнивать на совпадение со всеми признаками предметной области и т.д. до того момента когда j = n (рис. 2).

4. В блоке 4. После сравнения всех признаков и условие того, что признаки распознаваемого образа совпадают с признаками в данной предметной области, выполняется т.е. xj = xi, то множество предметной области разбивается и появится новый класс ωi и allhah16.wmf. Появление нового класса зависит от значения вероятности совпадения признаков распознаваемого образа с признаками множества предметной области allhah17.wmf.

allhahed2.tif

Рис. 2. Логическая блок-схема алгоритма классификации предметной области

Пример классификации с помощью решающих функций

Одной из основных задач распознавания образов является задача описывания классов [1]. Как отметили выше, у нас имеются 4 класса коммуникационных услуг и каждый класс описывается некоторым набором признаков в множестве признаков, например класс интернета описывается следующими признаками: {x1 – интернет, x2 – номер телефона, x3 – название компании и т.д.}. А каждый образ x описывается некоторым набором признаков в множестве признаков – вектором x. Все множество признаков X разбивается на m + 1 попарно несовместных множеств (полную группу множеств, в зависимости от классов) [1, 3, 4], allhah18.wmf:allhah19.wmf, для всех i ≠ j в случае непересекающихся классов, а в случае пересекающих классов может быть такое равенство allhah20.wmf как на рис. 1, allhah21.wmf. Каждое множество Xi, является множеством предпочтения одного класса ωi в множестве X, рис. 1. Таким образом, классами распознаваемых образов будем считать области Xi (allhah22.wmf).

Автоматическое определение принадлежности объектов к классам – одна из основных задач теории распознавания образов [1, 2, 4]. Принадлежность распознаваемых объектов можно определять с помощью решающей функции.

Будем считать, что пространство признаков является конечным множеством. В этом случае предполагается, что существует m + 1 функции dj(x) так, что Xj = {x∈X: dj(x) > 0}. Можно считать, что образ x принадлежит классу ωi, если выполняется неравенство dj(x) < 0 для всех j ≠ i и di (x) > 0. Решающей называют функцию вида

allhah23.wmf

где x = (allhah24.wmf, 0) вектор признаков, а (allhah25.wmf) вектор весовых коэффициентов, линейных решающих функцийallhah26.wmf [1–3].

Пример 1: пусть на систему поступила такая задача (Set up mobile internet, phone number: +967774541452, model: Apple iPhone 4S, phone carrier: GSM, operating system: IOS). Данную задачу будем считать объектом со следующим вектором признаков

x1 – Set up, x2 – phone number, x3 – model, x4 – operating system, x5 – mobile, x6 – internet, x7 – phone carrier).

Для того чтобы определить решающую функцию каждого класса, будем считать предикаты всех признаков способом сравнения этих признаков с признаками пространства предметной области или с помощью булевых значений таблицы истинности, таким образом если allhah27.wmf т.е. признак объекта соответствует какому-то признаку класса ωi, allhah28.wmf, то P(allhah29.wmf) = 1, а если allhah30.wmf т.е. признак распознаваемого объекта не соответствует никакому признаку класса ωi, то P(allhah31.wmf) = 0.

На рис. 1 в блоке C множество признаков X разбивается на 4 группы подмножества признаков allhah32.wmf.

allhah33.wmf,

allhah34.wmf,

allhah35.wmf,

allhah36.wmf

allhah37.wmf.

Результат вычисления предикатов:

allhah38.wmf,

allhah39.wmf,

allhah40.wmf,

allhah41.wmf,

allhah42.wmf,

allhah43.wmf,

allhah44.wmf.

Поставим allhah45.wmf, тогда решающая функция будет иметь такой вид:

allhah46.wmf

allhah47.wmf, тогда получаем решающую функцию первого класса в таком виде:

allhah48.wmf;

allhah49.wmf, allhah50.wmf; allhah51.wmf решающая функция второго класса;

allhah52.wmf, allhah53.wmf; allhah54.wmf решающая функция третьего класса;

allhah87.wmf, allhah56.wmf; allhah57.wmf решающая функция четвертого класса.

Будем считать, что данный объект x принадлежит классу ωi в таком случае, если di(x) > 0 = z и 0 < dj(x) < z для всех i ≠ j. Другими словами если di(x) > dj(x), то x принадлежит классу ωi.

Однако можно считать вероятность принадлежности объекта одному классу условной вероятностью. Будем считать, что x принадлежит классу ωi, если выполняется следующее условие:

allhah59.wmf,

для этого вычисляется общая вероятность принадлежности признаков всем существующим классам, как показано в приведенном ниже примере 2.

Пример 2. Hi событие, что allhah60.wmf, где Yi признаки образа x, а Xi – признаки i-ого класса ωi, т.е. признаки распознаваемого объекта соответствуют признакам i-ого класса, A событие, что x∈ωi (объект x принадлежит i-тому классу ωi). Событие A может произойти только при выполнении события allhah63.wmf. Вероятность P(Hi) того, что allhah64.wmf, равна произведению вероятности Р(А) того, что x∈ωi, на вероятность allhah66.wmf того, что причиной события стало именно, что allhah67.wmf (событие Hi), а не другая причина. В данном примере:

P(Hi) = 0,25, вероятность того что данный образец принадлежит i-тому классу, так как у нас имеются 4 класса, т.е. вероятность что данный объект принадлежит одному классу

allhah68.wmf.

Через полученные значения предикатов в примере 1, вероятности выполнения события allhah69.wmf, при условии A будут равны следующим значениям:

allhah70.wmf

allhah71.wmf

allhah72.wmf

allhah73.wmf

Р(А) – полную вероятность наступления события A вычислим по формуле

allhah74.wmf, allhah75.wmf

тогда

allhah76.wmf

allhah77.wmf =

= (0,25 * 0,7 + 0,25 * 0,57 + 0,25 * 0,28 + 0,25 * 0,4) = 0,487.

По формуле Байеса получим

allhah78.wmf

allhah79.wmf – вероятность того, что объект x принадлежит первому классу, именно потому, что его признаки соответствуют признакам данного класса.

allhah80.wmf;

allhah81.wmf;

allhah82.wmf.

Вычисленные вероятности по формуле Байеса нам позволяет сократить перебор классов. Для этого проранжируем по убыванию значения вероятности, т.е.

allhah84.wmf

allhah85.wmf

allhah86.wmf

allhahed3.tif

Рис. 3. График вероятностей принадлежности объекта i-тому классу ωi, allhah83.wmf

allhahed4.tif

Рис. 4. Блок-схема алгоритма определения порядка идентификации

Идентификацию принадлежности события A определенному классу будем проверять в последовательности ω1, ω2, ω4, ω3.

Заключение

Решена задача 1, т.е. разработаны математическая модель и алгоритм вычислительной процедуры, который позволяет нам классифицировать объекты из одной предметной области, исходя из их свойств (признаков), при условии, что часть признаков разных объектов могут совпадать.

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

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


Библиографическая ссылка

Аль-Хашеди А.А., Обади А.А., Нуриев Н.К., Печеный Е.А. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАСПОЗНАВАНИЯ ЗАПРОСОВ-ЗАДАЧ КОММУНИКАЦИОННЫХ УСЛУГ // Фундаментальные исследования. – 2017. – № 6. – С. 9-14;
URL: https://fundamental-research.ru/ru/article/view?id=41539 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674