Математические модели и методы идентификации объектов нечисловой природы в хранилищах данных

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

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

Проведен также анализ практических аспектов применения различных методов принятия решений для поставленной задачи идентификации объектов нечисловой природы в БД. Рассмотрены таблицы и деревья принятия решений, фреймовые модели, нейросетевые методы, теория нечетких множеств и генетические алгоритмы. Предпочтение отдано методам многомерного шкалирования и деревьям принятия решений.

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

Классификатор символьных полей, не имеющих сложной внутренней структуры можно представить в виде кортежа <U, V, S, A, Y, Z>, где множества слов, входящих в состав – первого реквизита, – второго реквизита, – множества стоп-слов для данного реквизита, A – оператор, определяющий нечисловое равенство реквизитов. К стоп-словам относятся слова, самостоятельно не имеющие идентификационной нагрузки.

_{Далее пороговые значения Y – расстояния редактирования, при котором строки (слова) считаются похожими. Если Y = 0, похожими являются посимвольно равные строки; Z – суммы равных и похожих слов, входящих в сравниваемые строки, при котором они считаются похожими. Вычленим из рассмотрения стоп-слова. Пусть}

                                                ₍₁₎

                                                ₍₂₎

где и – количество слов в строках и соответственно. Под операцией «/» здесь понимается операция вычитания множеств. Тогда количество посимвольно равных слов будет равно

,                                                      (3)

где

                                            (4)

Количество похожих слов равно

,                                                (5)

где

                                 (6)

Здесь под подразумевается расстояние редактирования с учетом транспозиции соседних символов с единичным весом. Результат сравнения реквизитов вычисляется по следующей формуле:

                                  (7)

где – строки посимвольно равны, – сравниваемые строки похожи,  
– не равны и не похожи, – отсутствует одна или обе строки. В случае, когда нужен числовой результат:

                                   8)

Параметры Y, Z задаются оператором или экспертами предметной области на основе анализа представленных данных или методом подбора. Параметр Z можно вычислять автоматически по формуле

Z = min (q, w).                                                                (9)

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

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

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

Числовые поля обычно рассматривают, не учитывая физический смысл информации, что не всегда допустимо. Ряд этих полей с содержательной смысловой нагрузкой следует отнести к номинальной или порядковой шкале, например ИНН, ОКПО, расчетный счет для юридических лиц, ISBN для литературы, серия и номер паспорта физического лица, номер дома. Арифметические операции со значениями таких полей не имеют смысла.

Априори неверно, когда нечисловые данные, например почтовый индекс, хранятся в БД в числовых полях, так как категориальные данные числами не являются. Соответственно храниться и обрабатываться они должны как строковые. Если информация относится к номинальной шкале, а в источнике данных хранится в числовом поле, то необходимо при импорте в хранилище преобразовать ее к строковому типу. Наличие числового формата при вводе информации вносит искажения. Например, значение реквизита должно быть «126», однако из-за опечатки в БД хранится «16». Сравнивая эти значения на основе точного равенства, получим числовую оценку существенного различия этих двух реквизитов. Приняв поля, значения которых состоят из чисел, и числовые поля как строковые и сравнив их классификатором символьных полей, не имеющих сложной внутренней структуры, получим результат « », что является более близким к истине.

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

Третья глава содержит описание результатов применения предложенных методов для идентификации юридических лиц при решении задачи построения хранилища данных УФСНП РФ по Саратовской области по БД, полученных из различных государственных органов и коммерческих предприятий.

В общем виде рассматриваемое хранилище данных является набором схем данных в СУБД Oracle. Основная схема данных с именем IDB состоит из отношений, содержащих объекты хранилища. Относительно юридических лиц, на примере которых описано применение разработанных моделей и методов идентификации, информация хранится в таблице IDB.FIRM (см. табл. 1), и в наборе отсылочных таблиц с формализованными именами IDB.IDB_{Имя схемы БД} (см. табл. 2).

Таблица 1

Юридические лица (таблица  IDB.FIRM)

№   п/п	Наименование  поля	Описание поля	Тип   данных	Длина поля
1.	Firm_id	Первичный ключ таблицы	Varchar2	30
2.	Fname	Полное наименование	Varchar2	300
3.	Name	Краткое наименование	Varchar2	100
4.	OKPO	Код ОКПО	Varchar2	8
5.	INN	Код ИНН	Varchar2	10
6.	KPP	Код КПП	Varchar2	9
7.	UrAddr	Юридический почтовый адрес	Varchar2	200
8.	FactAddr	Фактический почтовый адрес	Varchar2	200
9.	MainRS	Главный расчетный счет в банке	Varchar2	20

Таблица 2

Отсылочная таблица (таблица IDB.IDB_{Имя схемы БД})

№   п/п	Наименование поля	Описание поля	Тип   данных	Длина поля
1.	To_IDB	Ссылка на объект в схеме IDB	Varchar2	30
2.	To_DB	Ссылка на объект в схеме   {Имя схемы БД}	Varchar2	30

Совместно с экспертами предметной области для идентификации юридических лиц отобраны следующие реквизиты: ОКПО (Общероссийский классификатор предприятий и организаций), ИНН/КПП (Идентификационный номер налогоплательщика/ Код причины постановки), Наименование ЮЛ, Почтовый адрес, Расчетный счет в банке, Регистрационный номер в Администрации, серия и номер лицензии.

Перечисленные реквизиты, отобранные экспертами для идентификации, кроме почтового адреса, не имеют  сложной внутренней структуры и  сравниваются описанным выше классификатором. Для почтового адреса (см. табл.3) приведены математическая модель почтового адреса и алгоритм сравнения. Наиболее удобно представить адрес в виде фрейма, состоящего из ряда слотов, которые содержат семантически одинаковые подстроки, набора эвристик, с помощью которых производится разбиение на подстроки, и ограничений на содержимое слотов. В качестве опорной базы данных, используемой для отнесения слова к той или иной адресной составляющей, используется Ведомственный классификатор адресов России (КЛАДР), доступный для свободного скачивания с WEB сайта Федеральной налоговой службы России (http://www.nalog.ru).

Таблица 3

Протофрейм  почтового адреса

Имя слота	Фасет
Индекс	Состоит из цифр. Длина равна 6 ± 1.
Тип региона	[«Республика», «край», «область»,  «Автономный округ», «Респ.», «кр.», «обл.», «АО», …], значение предшествует или находится после имени региона
Регион
Тип населенного пункта	[«город», «село», «поселок», «поселок  городского типа», «г.», «с.», «п.», …], значение предшествует или находится после имени населенного пункта
Имя населенного пункта
Тип поселка	[«поселок», «микрорайон», …], значение предшествует или находится после имени поселка
Название поселка
Тип местоположения	[«улица», «площадь»,  «проезд», «шоссе», …], значение предшествует или находится после имени местоположения
Название   местоположения
Номер дома
Строение, корпус
Квартира, офис
ConstruePostAddress(Addr) Процедура заполнения фрейма данными из строки
ComparePostAddress(ResultFormat) Функция сравнения двух фреймов

Деревья принятия решений. В результате анализа выявлено, что из имеющихся реквизитов ОКПО встречается в БД чаще и содержит меньше ошибок/опечаток. В связи с этим реквизит ОКПО перенесен в корень дерева. Вторым в рейтинге встречаемости в БД является ИНН. Проведены эксперименты, результаты которых оценены экспертами предметной области. Построено дерево принятия решений по идентификации юридических лиц. После проведения оптимизации получен окончательный вид дерева, приведенный на рис. 3. Однако полученное дерево оказалось оптимальным не для всех имеющихся БД, которые включались в состав хранилища. Связано это с различиями БД по метаданным и качеству присутствующей информации. Например, в интегрируемой БД отсутствует поле ОКПО либо поле есть, но значения заполнены с опечатками, или отсутствуют.

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

Рис. 3. Дерево принятия решений по идентификации ЮЛ

Структурный метод  принятия решений. Воспользуемся методами многомерного шкалирования. Как описано выше, реквизиты, участвующие в процессе идентификации, заранее отобраны экспертами предметной области. Отобранные реквизиты сохраняются в виде массива данных (табл. 4), содержащего наименования реквизитов и их идентификационную значимость. Если значение реквизита хотя бы одного из объектов равно пустой строке, данный реквизит исключается из рассмотрения.

Таблица 4

Идентификационная значимость реквизитов

№ п/п	Реквизит	Вес реквизита
1	ОКПО	1
2	ИНН	0.8
3	КПП	0.2
4	Наименование	0.5
5	Почтовый адрес	0.5
6	Расчетный счет в банке	1
7	Регистрационный номер в Администрации	1
8	Серия и номер лицензии	1

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