METHODS FOR IDENTIFYING CLUSTERS OF CELLS IN SPARSE DATA CUBES OF MULTIDIMENSIONAL INFORMATION SYSTEMS

Abstract

Моделью данных в информационных системах, построенных на базе многомерного подхода, является многомерный куб данных. В системах с многоаспектным описанием предметной области кубы данных характеризуются большой разреженностью, что затрудняет организацию хранения данных и порождает сложности в процессе анализа информации. Значимые ячейки куба могут быть представлены как допустимые сочетания значений измерений. Анализируя семантически связанные значения разных измерений можно выявить кластеры ячеек - наборы ячеек, которые обладают сходными свойствами. При этом для измерений, которые являются размерностями многомерного куба, выявляются группы их значений, которые семантически связаны с группами значений других измерений. Для построения кластеров ячеек могут быть использованы логические методы интеллектуального анализа. В рамках логического подхода сочетание значений измерений представляется в виде конъюнкции пар «Измерение» - «Значение измерения». К сочетаниям значений измерений может быть применено преобразование, сходное с преобразованием приведения к совершенной дизъюнктивной нормальной форме. Оно позволяет выявить группы значений измерений и кластеры сочетаний значений измерений. Эти кластеры могут быть использованы как элементы модели данных информационной системы.

-

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

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

Технология интеллектуального анализа данных (Data Mining) предназначена для поиска в бол объемах данных неочевидных закономерностей [ 4 ]. Инструменты Data Mтiniсnаgмосмтогяутельно находить такие закономерности и самостоятельно строить гипотезы о взаимосвязях между объек информационной системы. В основе технологии лежит, в том числе, концепция шаблонов, описыв закономерности, свойственные подвыборкам данкноытхо,рые могут быть выражены в форме, понятной человеку. Традиционные методы анализа данных, прежде всего статистические, ориентированы проверку заранее сформулированных гипотез, в то время как одно из основных св–ойств Data поиск неочевидных козаномерностей. В аспекте исследуемой задачи интересны предпринимаемые в последнее время попытки использовать системы Data Mining как часть технологии хранилищ дан К области Data Mining также относят задачи классификации, кластеризации, ренграелсисзиаонного а (поиск зависимости выходных данных от входных) и задачу выявления шаблонов (поиск на типичных или нетипичных шаблонов в последовательности данных), которые не связан потребностями, возникающими при анализе сочетаемости значений измденраекноий, моогут быть использованы при анализе значений показателей в зависимости от значений измерений.

Методы интеллектуального анализа данных можно классифицировать с разных точек зрения. способам обработки данных их можно разделить на следующитеатикслтаисчсеыск:иес, логические, эволюционные, нейросетевые. По типу предоставляемых данных, методы анализа данных разделяю на методы обучения «с учителем» (supervised), когда обучающие примеры помечены, «без уч (unsupervised), когда обучающие примеерыпонмечены, и другие виды обучения.

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

Логические методы анализа данных используют обобщение или специализацию данных, кото представлены в виде логических структур. Состиаевляютащких структур обычно записываются символами или цепочками символов, поэтому логические методы называют иногда символьн методами. Типичными представителями таких методов являются AQме[т6о]дыи ДСМ [ 7 ], которые применяются в том числе и для явыявплреинчиинн-оследственных отношений в данных [ 8 ]. Замечательным свойством логических методов является то, что результаты их работы представ собой легко интерпретируемые человеком правила. Интерпретируемость результатов в некотор задачах является критеискчи важным, поэтому применение таких методов часто становится безальтернативным. Не менее важное значение имеет также способность логических методов раб эффективно на обучающих данных небольшого объёма (от нескольких обучающих примеров). Учит вышесказанное, для решения поставленной задачи выявления структуры разреженного многомерно куба данных наиболее целесообразно применять логические методы интеллектуального анализа данн Анализ структуры многомерного куба данных методами data mining

Продемонстрируем возможность использования логических методов Data Mining списка сочетаний значений измерений многомерного куба, описывающего факты «Выдача кредитов в северных областях РФ».

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

на примере анал наблюдаемого явле

Вид кредита потребительский потребительский ипотечный ипотечный на пополнение cредств на покупку оборудования юр. лицо на пополнение оборотю.р. лицо cредств на покупку оборудования юр. лицо межбанковский юр. лицо

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

Пол Вид деятельн. Регион мужской не используется Яросл. область женский не используется Яросл. область мужской не используется Яросл. область женский не используется Яросл. область не используется розничн. торг. Яросл. область не используется розничн. торг. Яросл. область не используется произв. одежды Яросл. область не используется произв. одежды Яросл. обласьт не используется банковская Яросл. область

деят. мужской не используется Тверская область женский не используется Тверская область мужской не используется Тверская область женский не используется Тверская область не используется розничн. торг. Тверская область не используется розничн. торг. Тверская область не используется произв. одежды Тверская область не используется произв. одежды Тверская область не используется банковская Тверская область деят.

Представленная ваблтице 1 структура МДС определяется тем, что для юридических лиц не опр пол, при описании физических лиц не используется вид деятельности, заемщики разных типов брать кредиты разных видов. Такая сложная структура наблюдаемого явленияеди«тВоыв»дача кр является причиной разреженности многомерного куба данных, описывающего факты этого явления.

В терминологии методов интеллектуального анализа задачу распознавания структуры многомерно куба данных на основе анализа МДС, представленного вможтанболипцоеста1в,ить следующим образом: Имеется некоторый класс объектов, который описывается набором сочетаний значений измере (эти значения берутся из соответствующих измерениям справочников). Требуется сформирова описание этих объектов в компактнмойе. фЗоардача разбивается на две подзадачи:

1. Вычленение групп значений измерений из информации о сочетаемости значений этих измер в МДС;

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

Таким обраозм, задача распознавания структуры многомерного куба данных является описательно Исходные данные для задачи представлены в виде таблицы сочетаний. Такое представление с зрения методов анализа является множеством объектов, где описание катжадогзоадаоёбтсъяек признаками – столбцами таблицы, а каждый объект задаётся строкой в таблице. Тогда задача со получении описания множества объектов через возможные сочетания допустимых значений измере для рассматриваемых объектов.

Предварительный аналзи исходных данных показывает, что они обладают следующими особенностями:  Значения измерений образуют дискретный набор;  Количество имеющихся сочетаний ограничено;  Наличие одинаковых сочетаний исключено.

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

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

Из анализа структуры МДС, представленного в виде списка сочетаний, видно, что включение значений измерения ег«иРон» имеет особенности: набор сочетаний, со значением «Ярославская област повторяет набор сочетаний со значением «Тверская область». Это означает, что сочетаемость зн остальных измерений не зависит от значений измерения «Регион». Полнеырйенинйабомрожиетзм быть разбит на два слоя: пе–рсвоыстйоящий из единственного измерения «Регион», –встоосртоойящий из измерений {«Вид кредита», «Заемщик», «Пол», «Вид деятельности»}. Сочетаемость значений измерен одном слое не зависит от значений ийизмдерруегного слоя. Сочетания в слоях можно анализировать независимо друг от друга, а полный набор сочетаний МДС представлять в виде декартова про сочетаний значений измерений всех слоев.

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

Действия по выявлению х этгирупп значений можно производить путем выполнения несколько шаго Шаг 1. Разбиение полного набора измерений на слои измерений.

Разбиение должно быть произведено таким образом, чтобы сочетаемость значений измерений одного слоя в МДС не зависелзаначбеынийотизмерений из другого слоя.

В рассматриваемом иллюстративном примере имеется два слоя Итоговое полное описание МДС быть получено декартовым произведением описания для сочетаний из слоя 2 и группы з {«Ярославская область», «Тверскаяласотбь»} из слоя 1. Слой 1 содержит одно измерение и и вырожденное описание. Дальнейшее изложение алгоритма будем производить для слоя 2. Шаг 2. Получение начального множества описаний.

На втором шаге для слоя 2 каждый объект (строка) предситдаевляектосняъюнвкцивй пар ИмяИзмерения.Значение. При этом получаем следующие логические выражения, описывающие объект ВидКредита.Потребительский & Заемщик.ФизЛицо & Пол.Мужской & ВидДеятельности.НеИспользуется;

ВидКредита.Потребительский & Заемщик.ФизЛицо &.ЖеПнослкий & ВидДеятельности.НеИспользуется; ВидКредита.Ипотечный & Заемщик.ФизЛицо & Пол.Мужской & ВидДеятельности.НеИспользуется; ВидКредита.Ипотечный & Заемщик.ФизЛицо & Пол.Женский & ВидДеятельности.НеИспользуется; ВидКредита.НаПополнение & Заемщик.ЮрЛоиц& Пол.НеИспользуется & ВидДеятельности.РознТорговля;

ВидКредита.НаПопокупкуОборудоапния & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.РознТорговля;

ВидКредита.НаПополнениеОС & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.ПроизводствоОдежды;

ВидКредита.НаПопокупкуОборудования & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.ПроизводствоОдежды;

ВидКредита.Межбанковский & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.БанковскаяДеятельность.

Шаг 3. Индуктивное обобщение ьнаочгаол множества сочетаний.

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

ВидКредита.{Потребительский | Ипотечный} & Заемщик.ФизЛицо & Пол.{Мужской | Женский} & ВидДеятельности.НеИспользуется; ВидКредита.{НаПополнениеОС | НаПопокупкуОборудования} & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.{РознТорговля | ПроизводствоОдежды};

ВидКредита.Межбанковский & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.БанковскаяДеятельность.

Полученные выражения описывают множества связанных значений измерений в слое 2 в совместной встречаемости этих значений.

Шаг 4. Формирование групп знйачеинзимерений.

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

В рассматриваемом иллюстративном примере выявлены группы значений, которые приведены н (если в выражение включенызнавчсеения некоторого измерения, соответствующую группу мы будем обозначать «Все»):

Группы для измерения «Вид кредита»: КрФЛ={Потребительский + Ипотечный}, КрПредпр={НаПополнениеОС + НаПопокупкуОборудования}, {Межбанковский}.

Группы для измерения «Заемщ{иФки»з:Лицо}, {ЮрЛицо}. Группы для измерения «Пол»: {Мужской + Женский = Все}, {НеИспользуется}.

Группы для измерения «Вид деятельности»: ВДПредпр={РознТорговля + ПроизводствоОдежды}, {БанковскаяДеятельность}, {НеИспользуется}.

Шаг 5. Получение логическпоигосаноия МДС по слоям.

После того, как группы получили наименование, выражения, сформированные на шаге 2, прив к итоговому выражению для сочетаний слоя 2 в виде, содержащем описание кластеров сочетани МДС(Слой_2)=(ВидКредита.КрФЛ & Заемщик.ФизЛицоПол&.Все & Вид деятельности НеИспользуется) | (ВидКредита.КрПредпр & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.ВДПредпр) | ( кредита.Межбанковский & Заемщик.ЮрЛицо & Пол.НеИспользуется & ВидДеятельности.Банковская).

Первый слой содержит сетдвиеннное измерение «Регион». МДС для этого слоя описывается единственной группой значений измерений: МДС(Слой_1){«Ярославская область» + «Тверская область» Шаг 6. Получение логического описания множества СДЗ.

Результирующее МДС может быть получено енсиоемдин описаний сочетаний по слоям: МДС = МДС(Слой_1) | МДС(Слой_2). Полученные результаты Предложен алгоритм анализа структуры разреженного многомерного куба данных. Выявлены элементы структуры разреженного многомерного куба данных (слой измерений, гру значений измерений, кластер сочетаний значений измерений), которые могут быть использованы описании метаданных многомерной информационной системы.

Рассмотренный иллюстративный пример показывает, что логический вариант метода Data Mi может быть илспьозован при построении описания МДС по имеющемуся списку сочетаний. Однако разработки алгоритма в случае куба большой размерности со сложным вариантом сочетае значений измерений при описании структуры многомерного куба данных путем выеярволвения клас сочетаний может потребоваться дополнительное разбиение МДС на компоненты. Такая ситуация м возникнуть, если в описании наблюдаемого явления можно выделить несколько семантическ компонент и список сочетаний значений измерений разбиваетсяожнесатвап,одвмн каждом из которых существует свой вариант разделения измерений на слои. В этой ситуации полное множество со должно быть разбито на подмножества, соответствующие компонентам наблюдаемого явления, и каждого подмножества применен опиысайннвыше алгоритм.

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

 кластеры сочетаний значений измерений, объединяющие сочетания по критерию схожего поведения по отношению к связям между измерениями;

 слои измерений, разделяющие все имеющиеся в кубе измерения на непересекающиеся на Сочетаемость значений в каждом из слоеевляеотпсяредтолько связями между измерениями внутри этого слоя и не зависит от того, какие значения в сочетаниях принимают измерения, лежащие Приведенные особенности задачи перехода от задания структуры многомерного куба данных спи Заключение

Данные многомерной информационной системы, использующей большой набор характеристик наблюдаемого явления, имеют структуру разреженного и неравномерно заполонгеонмнеоргноогомн куба. Анализ структуры многомерного куба, описывающего факты, полученные в результате данных или преобразования информации других фактов, является сложной задачей. Для её ре можно использовать логические методы интеллектуальногоза.анаПлриедлагаемый алгоритм анализа структуры разреженного многомерного куба позволяет выявить элементы структуры куба данных измерений, группы значений измерений) и представить совокупность ячеек куба в виде набора к ячеек, обладающих сходнымсивойствами. Каждый кластер задается набором сочетаний значений измерений, которые могут быть получены декартовым произведением групп значений измере Выявленные элементы структуры многомерного куба можно использовать при описании метадан многомерной информационной системы. Такой способ описания метаданных хорошо отражает семанти наблюдаемого явления, для описания которого разработана информационная система. Благодарности

Работа выполнена при финансовой поддержке Министерства образования ипо нПауркоиграРмФме повышения конкурентоспособности РУДН-10«05» среди ведущих мировых н-оабурчанзоовательных центров на 20-210620 гг.

Литература

References Об авторах: Фомин Максим Борисович, кандидат информационных технологи,й [e-mail] Смирнов Иван Валентинович, физи-мкаотематических наук, Российский университет доцент, дружбы доцент

кафедры народов, кандидат физи-мкаотематических наук, доцент,

заведующий лабораторией «Компьютерная лингвистика и интеллектуальный анализ информации» Института системного анал,изФаедеральный исследовательский центр «Информатика и управление» Российскйо академии наудко;цент кафедры информационных технол,огий Российский университедтружбы народовiv,[e-mail] Note on the authors: Fomin Maxim B., Candidate of Physico-Mathematical Sciences, Associate Professor, Associate Professor of the Department of Information Technology, Peoples’ Friendship University of [e-mail] Smirnov Ivan V., Candidate of Physico-Mathematical Sciences, Associate Professor, head of the laboratory for Сomputational Linguistics and Intelligent Data Analysis, The Institute for S,yFsteedmersal Analysis Research Center Computer Science and Control of the Russian Academy of Sciences; Associate Professor of the Department of Information Technologies, Peoples’ Friensdisthyiopf RUusnsiviae,[e-mail] Russi

References

1. Thomsen E. OLAP Solution: Building Multidimensional Information System . - NY: Willey Computer Publishing, 2002 . - 688p .

3. Висков А.В. , Фомин М .Б. Методы описания допустимых сочевтиазниитйов-преикзнаков при использовании многомерных моделей в инфокоммуникационных систем -аCхom/m/. -TТелекоммуникации и Транспо-рт. 2012 . - № 7. - С . 45 - 47 .

4. Fayyad U. , Piatetsky-Shapiro G. , Smyth P. From data mining to knowledge discovery: an overview // Advances in knowledge discovery and data mining . - Menlo Park: AAAI press, 1996 . - P. 1 - 34 .

6. Michalski R.S. Attributional calculus: a logic and representation language for natural induction // Reports of the Machine Learning and Inference Laboratory, MLI 04-2 , George Mason University, Fairfax, 2004 [электронныйресурс] // URL: http://mars.gmu.edu/handle/1920/1487/ (датаобращения 04.09. 2017 )

8. Панов А .И. Выявление прич-иснлнеодственных связей в данных психологического тестирования логическими методами // Искусственный интеллект и принятие -реш20е1н3и . й -. № 1 -. C. 24 - 32 .

1. Thomsen E. OLAP Solution: Building Multidimensional Information System . - NY: Willey Computer Publishing, 2002 . - 688p .

2. Viskov A.V. , Fomin M.B. Analytical dimensions modeling in multidimensional databases // Vestnik IrGTU [Proceedings of Irkutsk State Technical University]. - 2012 . - Т . 63 , № 4 .- 19S . 15

3. Viskov A.V. , Fomin M.B. Methods of a description of the permissible combination of detail-attributes when using multidimensional models in infocommunication systems // T-Comm: Telecommunications and Transport. - 2012 . - № 7 -. S. 45 - 47 .

4. Fayyad U. , Piatetsky-Shapiro G. , Smyth P. From data mining to knowledge discovery: an overview // Advances in knowledge discovery and data mining . - Menlo Park: AAAI press, 1996 . - P. 1 - 34 .

5. Vapnik V . Vosstanovlenie zavisimostei ot empiricheskikh dannyh // M.: Nauka , 1979 . - 448 s.

6. Michalski R.S. Attributional calculus: a logic and representation language for natural induction // Reports of the Machine Learning and Inference Laboratory, MLI 04-2 , George Mason University, Fairfax, 2004 [электронныйресурс] // URL: http://mars.gmu.edu/handle/1920/1487/ (датаобращения 04.09. 2017 )

7. Avtomaticheskoe porozhdenie gipotez v intellektuaknykh sistemakh .Editors Pankratova E.S., Finn V.K. - M.: Librocom , 2009 . - 528 s.

8. Panov A.I. Extraction of cause-effect relationships from psychological test data using logical methods // Scientific and Technical Information Processing- 2014 . - T. 41 , № 5 -. S. 275 - 282 .