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

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

Введение. Можно выделить несколько способов хранения информации (рис.1):

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

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

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

Пусть даны два класса A и B, связанных друг с другом отношением «многие ко многим», причем каждой паре объектов (a,b), для которых установлено это отношение, поставлено в соответствие значение некоторой функции w(a,b) (рис.2). Примерами таких классов могут служить товары и клиенты, покупающие эти товары, где значением w(a,b) является количество данного товара, покупаемого клиентом, к примеру, за месяц.

Предположим также, что объекты класса A могут быть классифицированы путем отнесения каждого a e A к некоторой категории c e C по определенным признакам. Ставится задача: на основе анализа имеющейся информации классифицировать объекты класса B, т.е. распределить их по группам d e D. В дальнейшем, термин «объект» будем применять только к объектам класса A, а элементы класса B назовем «субъектами».

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

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

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

Рассмотрим произвольное конечное множество A = {ai|i = 1..n} . Будем называть множество A – множеством объектов или классом A, элементы этого множества – объектами или экземплярами класса, а номера i элементов – идентификаторами объектов.

Предположим, что у каждого объекта существует ряд характеристик, которые мы назовем его признаками. Некоторые признаки могут быть общими для всех элементов множества A, другие – только для определенного подмножества элементов A. Множество всех признаков обозначим Q, его элементы – qj (рис.3). Будем считать, что между множествами A и Q установлено отношение u, т.е. каждому элементу множества A соответствует некоторое количество признаков – элементов множества Q. Если признак q e Q соответствует элементу a e A, то u(a,q)=1, в противном случае u(a,q)=0.

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

Существует некоторое множество , которое мы назовем множеством субъектов. На произведении множеств определена функция веса , которая каждой паре ставит в соответствие некоторое значение веса объекта для субъекта.

Рассмотрим некоторое множество . Каждому субъекту поставим в соответствие вес множества для этого субъекта:

по всем . Необходимо:

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

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

Алгоритм классификации объектов по категориям

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

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

Каждое ребро такого графа соединяет вершины двух типов: признак и значение признака (Рис.4). Для каждого признака можно ввести понятие уровня в иерархии . На самом верхнем уровне иерархии () содержатся корневые признаки, т.е. признаки, присутствующие у всех элементов множества . Каждый из этих признаков соединен со своими значениями. В свою очередь, какое-либо значение корневого признака может породить один или несколько других признаков следующего уровня, что соответствующим образом отображается на графе. Все сказанное распространяется и на нижестоящие уровни. При порождении значением признака некоторого набора признаков должно выполняться условие:

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

Дерево признаков можно описать двумя функциями и . Аргументами функции является значение некоторого, результатом – множество признаков, порождаемых :

При этом множество может быть пустым либо состоять лишь из одного признака. Функция определена на множестве признаков и выдает множество значений признака: . Причем должно состоять как минимум из двух элементов (признак должен иметь как минимум два значения).

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

Рассмотрим комбинацию значений набора признаков . Здесь – номер набора признаков, – номер комбинации их значений. Возможность такой комбинации набора признаков и их значений определяется по дереву признаков. Если комбинация возможна, обозначим ее . Множество таких возможных комбинаций . Каждой возможной комбинации значений признаков соответствует некоторое множество , элементы которого имеют признаки и значения, совпадающие со значениями признаков комбинации. Каждое такое множество соответствует категории объектов. Назовем все признаки из набора – признаками категории . Всевозможные категории образуют множество .

Между элементами множеств и ставится взаимнооднозначное соответствие. Таким образом, категорию можно определить либо как совокупность значений некоторого набора признаков (категория на множестве значений признаков), либо как совокупность элементов множества , обладающих этими значениями признаков (категория на множестве объектов).

В дальнейшем категорию будем обозначать как , где – набор признаков категории, а – их значения. При этом будем говорить, что категория вложена в категорию и обозначать , если (все признаки, определяющие категорию , являются признаками категории и значения этих признаков одинаковы для обеих категорий). Другими словами, каждый объект, входящий в категорию , входит также и в категорию . В качестве примера можно привести категорию «фотопленка 36 кадров чувствительностью 400», вложенную в категорию «фотопленка 36 кадров».

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

Непересекающимся категориям соответствуют непересекающиеся множества объектов.

Каждое значение произвольно выбранного признака категории порождает некоторое множество признаков следующего уровня . Объединение таких множеств для данной категории будем называть множеством доступных признаков. Все объекты, принадлежащие категории помимо признаков категории обладают доступными признаками. К примеру, у всех объектов категории «фотопленка фирмы «Konica» в ценовом диапазоне от 1 до 3 долларов» есть также доступные признаки «чувствительность», «количество кадров», «ширина», «вес» и т.п. В отличие от признаков категории, доступные признаки могут принимать разные значения для разных элементов категории (Рис.5).

Попытаемся множество разбить некоторым образом на категории. Множество само соответствует категории , у которой нет ни одного признака категории, а множество доступных признаков образуют все корневые признаки (для которых ). Для того, чтобы разбить эту категорию на дочерние, необходимо выбрать один из доступных признаков. Назовем его порождающим признаком и обозначим . Каждому значению порождающего признака может соответствовать одна дочерняя категория (Рис.6). Порожденные категории в свою очередь также могут разбиваться на дочерние по произвольно выбранному для каждой категории доступному признаку. Порождающий признак становится признаком категории для дочерних категорий.

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

где – набор признаков родительской категории; – набор их значений; – набор признаков дочерней категории; – набор их значений.

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

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

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

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

Категории нижнего уровня представляют собой непересекающиеся множества объектов, сумма которых представляет собой все пространство объектов или некоторое его подмножество (если разбиение в каких-либо местах было неполным). Назовем эти категории базисными категориями объектов.

Варьируя последовательность выбора порождающих признаков и этапы, на которых мы завершаем построение иерархии категорий, получим всевозможные разбиения пространства объектов или некоторого его подмножества на базисные категории (Рис.8). Набором базисных категорий будем называть любую совокупность непересекающихся категорий. Набор назовем полным, если базисные категории покрывают все пространство объектов и неполным – в противном случае. Любой неполный набор можно сделать полным посредством введения категории «Остальные объекты».

Назовем набор базисных категорий , вложенным в набор , (), если выполнено . Таким образом, набор базисных категорий можно получить некоторым разбиением категорий набора .

Разделение субъектов на группы

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

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

Субъектам соответствуют точки , где – количество категорий, – вес -ай категории для -га субъекта. Далее для выделения групп субъектов применяется один из алгоритмов кластеризации [1], при котором в пространстве категорий выделяются

кластера – множества точек близких друг к другу по расстоянию.

2-й способ. Группу субъектов будем описывать некоторым вектором значений . Каждую компоненту такого вектора назовем типом субъекта, а ее значение – значением типа.

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

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

В каждом из пространств типа субъекта выделяем

кластера субъектов, которым приписываем некоторое значение данного типа.

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

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

Понятие «видимости» можно задать с помощью иерархического описания типов. Для этого выбранные наборы категорий должны удовлетворять некоторым свойствам. Эти свойства можно описать посредством построения дерева типов субъекта (рис.11).

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

Для каждого типа-родителя можно ввести понятие «видимости» дочерних типов. Будем считать, что субъект «видит» дочерний тип при определенных значениях типа-родителя и «не видит» при других. В случае если субъект не видит некоторый тип, он не видит и все его дочерние типы. Таким образом, для каждой группы субъектов область видимости представляет собой часть дерева типов.

Итак, классификация субъектов имеет цель:

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

2. Последовательное разбиение субъектов на группы по значениям каждого из типов. Изначально всем субъектам приписывается максимально возможная область видимости. На каждом шаге выбирается некоторый тип. В его пространстве откладываются все субъекты, для которых этот тип виден. Далее выделяются кластера, которым ставятся в соответствие значения данного типа. Для каждого субъекта корректируется его область видимости по значению типа. На последовательность выбора типов накладывается единственное условие: дочерний тип должен следовать за типом-родителем (поскольку его видимость для субъекта определяется значением типа-родителя). Следовательно, на первом шаге выбирается тип верхнего уровня.

Информационная модель

Основным способом хранения информации в современных системах является реляционная модель Кодда (Codd) [2], реализованная во всех современных промышленных базах данных (ORACLE, Informix, DB2 и др.). Построим реляционную модель, реализующую приведенные выше подходы к классификации объектов и субъектов. Для удобства представления нотацией Мартина (Martin), методика которой изложена в работах [3,4] и реализована CASE-средством S-Designer DataArchitect компании Sybase.

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

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

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

* один к одному * один ко многим * многие ко многим

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

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

* «Объекты классификации», соответствующий пространству объектов ; * «Признаки», соответствующий пространству признаков ;

* «Значения признаков», соответствующий пространству значений признаков ;

* «Категории», соответствующий множеству категорий ; * «Субъекты», соответствующий множеству субъектов .

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

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

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

Заключение

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

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

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

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

Литература.

1. Гонзалес Р., Ту Дж. Принципы распознавания образов. Пер. с англ., М., Мир. 1978.

2. Codd E.F. A Relational Model of Data for Large Shared Data Banks. Communications of ACM. 1970.

3. DeMarco Tom. Structured Analysis and System Specification. Yourdon Press, New York. 1978.

4. Smith M., Tockey S. An Integrated Approch to Software Requirements Definition Using Objects. 1988.

Признаки категории и их значения: Тип продукции фотопленка Фирма-производитель Konica Цена 1 - 3 $ Доступные признаки: Ширина фотопленки Кол-во кадров фотопленки Чувствительность фотопленки Вес ... Рис.5. Категория объектов