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

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

Свойство сходства и различимости объектов, относящихся к одному и тому же классу, широко используется при построении различных методов классификации. Так, например, в ряде методов сортировки объектов, основанных на теориях нечетких [16], [17] и грубых [18] множеств, допускается неоднозначность классификации объектов, связанная с разной степенью принадлежности объекта к классу, то есть объекты, которые «несомненно» и «возможно» принадлежат к некоторому классу, считаются различающимися.

Процедура классификации объектов в рамках формальной логики может быть описана как совокупность (последовательность) решающих правил, которые представляются выражениями вида:

ЕСЛИ условия, ТО решение. (10)

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

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

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

Аппроксимация индивидуальных правил сортировки. Перейдем к формальной постановке задачи аппроксимации большого числа правил сортировки многопризнаковых объектов компактным набором простых решающих правил. Пусть A ={A₁,...,A_k} - совокупность объектов, которые описываются m дискретными признаками Q₁,…,Q_m, имеющими качественные значения. Каждая группа признаков Q_s={}, e_s=1,…,h_s, s=1,…,m отражает содержательное качество объектов, например, может быть значением показателя, характеризующего какое-либо свойство объекта, или оценкой объекта по критерию, и тому подобное. Объекты A_i, i=1,…,k предварительно рассортированы по нескольким классам X_t, t=1,…,f путем прямой классификации. Принадлежность объекта A_i к некоторому классу X_t выражается правилом сортировки R, которое может считаться еще одним качественным признаком со шкалой значений R={r_t}. Любой объект A_i может существовать в n экземплярах, которые отличаются наборами признаков, его характеризующих. Однако в описании каждого экземпляра объекта присутствует только одно какое-то значение признака из каждой группы Q₁,…,Q_m,R. Других дополнительных предположений об особенностях классов, признаков объектов и их значений (важности, предпочтительности, характерности, упорядоченности и прочее) не делается. Требуется построить одно или несколько решающих правил, составленных из небольшого числа значений признаков, которые относили бы объекты к заданным классам наилучшим (в смысле близости к предварительной сортировке) образом. Само понятие близости также должно быть определено.

Сопоставим каждый многопризнаковый объект с мультимножеством вида, аналогичного выражению (1)

A_i = {(k_Ai()*), (k_Ai(r_t)*r_t)} (11)

над доменом G={Q₁,…,Q_m,R}. Запись объекта A_i в таком виде может трактоваться как еще один способ выражения индивидуальных правил сортировки (10). А именно: терм условия ассоциируется тогда с различными комбинациями значений признаков , описывающими свойства объекта A_i, а терм решение - с принадлежностью объекта A_i к классу X_t. В терм решение входит также некоторое правило, позволяющее говорить о принадлежности объекта A_i к какому-то определенному классу X_t. Это может быть, например, правило простого большинства голосов, в соответствии с которым объект A_i будет считаться принадлежащим к классу X_t, если k_Ai(r_t)k_Ai(r_p) для всех pt, или правило квалифицированного большинства голосов, по которому должно выполняться условие k_Ai(r_t)_pt k_Ai(r_p), или любое другое правило. При этом предполагается, что каждый объект оценивается всеми n экспертами.

Вся совокупность объектов A ={A₁,...,A_k}, представленных мультимножествами (11), порождает семейство первичных решающих правил сортировки. Правила совпадают или являются похожими, когда различные объекты с идентичными или схожими (близкими) значениями признаков включаются в один класс. Противоречивые правила относят слабо различимые объекты в разные классы.

Для простоты будем считать, что результатом классификации должно быть разложение совокупности объектов A только на два класса X_a и X_b. Требование бинарной декомпозиции A ={X_a, X_b} не является принципиальным ограничением. Если необходимо рассортировать объекты на большее число классов, можно сначала разбить совокупность объектов на две группы, затем одну из них или обе группы - на подгруппы, и так далее. Например, заявки можно разделить на принятые и отклоненные, отклоненные заявки - на отложенные для дальнейшей доработки и окончательно не принятые, и так далее.

Рассмотрим наиболее простой и типичный случай, когда все группы объектов формируются как суммы соответствующих им мультимножеств. Тогда каждое из мультимножеств X_t, t=a,b, представляющее свой класс объектов, можно записать в виде следующего разложения на мультимножества по группам признаков:

X_t = (12)

где каждое слагаемое есть в свою очередь разложение

подмножества индексов =I_t и I_rt=I_rI_t; I_t - подмножество индексов i для объектов A_i, имеющих функции кратности k_Ai(r_t)_ptk_Ai(r_p) или k_Ai(r_t)k_Ai(r_p),pt; - подмножество индексов i для объектов A_i, имеющих k_Ai()0, k_Ai()=0, vs, k_Ai(r_t)=0; I_r - подмножество индексов i для объектов A_i, имеющих k_Ai(r_t)0, k_Ai()=0. Так как каждый экземпляр объекта A_i может обладать только единственными значениями k_Ai() и k_Ai(r_t) из каждой группы признаков Q_s и R, то выполняются следующие условия для мощностей мультимножеств:

|Q_sa| + |Q_sb| = k, |R_a| + |R_b| = k, |X_a| + |X_b| = k(m+1)

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

Очевидно, что объекты A_i, которые попали в разложение {R_a, R_b}, сделанное только по правилам сортировки, образуют наилучшую из всех возможных декомпозиций рассматриваемой совокупности объектов A ={A₁,...,A_k} на два класса для имеющегося набора первичных правил сортировки. Обозначим через d*=d(R_a, R_b) расстояние между мультимножествами R_a и R_b в метрическом пространстве мультимножеств (A, d) с метрикой d, определяемой одним из выражений (2) или (5). В каждой конкретной задаче классификации расстояние d* является предельно возможным расстоянием между объектами, входящими в разные классы. При идеальной предварительной сортировке объектов противоречия в индивидуальных правилах отсутствуют. В этом случае максимально возможное расстояние в метрическом пространстве мультимножеств (A , d), на котором могут находиться объекты, принадлежащие разным классам, будет равно соответственно d₁*=kn, d₂*=1/h, d₃*=1. Здесь n есть число индивидуальных правил сортировки, приходящихся на один объект, совпадающее, в частности, с числом экспертов, h - общее число значений всех признаков, описывающих объекты, равное для задачи классификации h=h₁+...+h_m+f.

Сформулируем теперь основную идею нахождения обобщенного решающего правила, аппроксимирующего большое семейство противоречивых правил сортировки многопризнаковых объектов. Для каждой группы признаков Q_s нужно сгенерировать пары новых мультимножеств таким образом, чтобы мультимножества внутри каждой пары были удалены друг от друга в метрическом пространстве (A , d) как можно больше и с достаточной точностью совпадали с первоначальной сортировкой объектов по классам X_a и X_b, заданной разложением {R_a, R_b}. Разные комбинации признаков, определяющих границы между сгенерированными мультимножествами внутри каждой пары, дадут желаемые обобщенные решающие правила для классификации объектов.

Решение задачи аппроксимации решающих правил для классификации многопризнаковых объектов сводится, таким образом, к решению m оптимизационных задач вида

d(Q_sa, Q_sb) max d(Q_sa, Q_sb) = d(Q_sa*, Q_sb*) (13)

где мультимножества Q_sa* и Q_sb* принадлежат к разным классам и находятся на максимально возможном расстоянии в метрическом пространстве мультимножеств (A , d). Решение каждой из задач (13) является наилучшей бинарной декомпозиций {Q_sa*, Q_sb*} имеющейся совокупности многопризнаковых объектов A ={A₁,...,A_k} по s-ой группе признаков. Когда число h_s значений каждого из признаков невелико (h_s=25), решение задачи (13) не вызывает существенных трудностей и может быть получено даже путем простого перебора.

Каждое мультимножество Q_st* (t=a,b), относящееся к одному и тому же классу, представляет собой сумму двух подмультимножеств Q_st* = Q_st*¹ + Q_st*². Значение признака q_s*, которое определяет границу между слагаемыми Q_st*¹ и Q_st*², назовем аппроксимирующим признаком. Комбинации аппроксимирующих признаков {q_s*} для разных номеров s групп признаков Q_s задают условия отнесения объекта A_i к соответствующему классу X_t и образуют в совокупности искомые обобщенные правила классификации объектов вида (11).

Аппроксимирующие признаки q_s* для различных групп признаков можно упорядочить по величине расстояния d(Q_sa*, Q_sb*). Для построения обобщенных правил классификации следует использовать признаки q_s*, занимающие первые места в такой ранжировке. Чем ближе значения расстояний d(Q_sa*, Q_sb*) к расстоянию d*=d(R_a, R_b), тем более точной будет аппроксимация первоначальной индивидуальной сортировки объектов. Оценить точность аппроксимации по s-ой группе признаков можно, например, выражением

_s = d(Q_sa*, Q_sb*)d(R_a, R_b) (14)

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

Конкурсный отбор проектов. Соотношения между совокупностью объектов A ={A₁,...,A_k} и множеством их признаков G={x₁,...,x_h} удобно выражать с помощью матрицы C=||c_ij||_kh, которая часто используется в анализе данных, теории принятия решений, распознавании образов, других приложениях и называется таблицей «объекты-признаки», информационной таблицей или таблицей решений [2], [18]. Строки этой матрицы соответствуют объектам, столбцы - признакам, а элементы матрицы являются значениями признаков. Таким образом, каждая строка матрицы C характеризует свойства рассматриваемого объекта, а каждый столбец дает информацию об объектах, обладающих данным свойством. Свойства совокупности A ={A₁,...,A_k} многопризнаковых объектов A_i, представленных мультимножествами, и их принадлежность к некоторому классу решений X_t также можно описать с помощью таблиц решений. В исходной таблице решений C=||c_ij||_kh, элементы которой задаются как c_ij =k_Ai(x_j), x_j=,r_t, каждая строка является аргументом выражения (11). Разложению совокупности объектов A на два класса X_a и X_b, которые задаются формулой (12), соответствует преобразованная таблица решений C'=||k_Xt'(x_j)||_2h, состоящая из двух строк k_Xa'(x_j) и k_Xb'(x_j). Матрицы C и C' состоят из 2(m+1) блоков, которые соответствуют мультимножествам признаков Q_sa, Q_sb и решений R_a, R_b.

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

Шаг 1. Построить таблицу решений C=||k_Ai(x_j)||_kh для рассматриваемой совокупности многопризнаковых объектов A ={A₁,...,A_k}, строки которой соответствуют мультимножествам A_i вида (11).

Шаг 2. Объединить объекты A_i, относящиеся к заданным классам X_a и X_b, воспользовавшись формулами (12). Получить преобразованную таблицу решений C'=||k_Xt'(x_j)||_2h, строки которой соответствуют мультимножествам X_a и X_b.

Шаг 3. Решить задачу оптимизации (13) для каждого бинарного разложения {Q_sa*, Q_sb*} по s-ой группе признаков Q_s и найти аппроксимирующий признак q_s* в каждом s-ом блоке преобразованной матрицы C'.

Шаг 4. Проранжировать аппроксимирующие признаки q_s* по убыванию величины расстояния d*=d(R_a, R_b) или показателя точности _s (14).

Шаг 5. Выбрать аппроксимирующие признаки q_s*, которые обеспечивают необходимую точность аппроксимации _s0, и сформировать из них обобщенное решающее правило для классификации многопризнаковых объектов. _

Проиллюстрируем предложенный подход к построению обобщенного решающего правила для классификации многопризнаковых объектов, которое аппроксимирует большое число противоречивых правил сортировки, на примере конкурсного отбора проектов для формирования государственной научно-технической программы по высокотемпературной сверхпроводимости [14]. Каждая представленная на конкурс заявка независимо оценивалась 3 экспертами по 6 качественным критериям, которые давали также свое заключение по принятию или отклонению заявки. Всего было подано более 250 заявок и около 170 из них было отобрано для включения в программу.

Приведем некоторые данные, иллюстрирующие рассматриваемый пример: часть решающей таблицы C=||k_Ai(x_j)||_kh, характеризующей поданные на конкурс проекты A_i; преобразованная решающая таблица C'=||k_Xt'(x_j)||_2h, соответствующая классам принятых X_a и отклоненных X_b проектов; значения расстояний между бинарными разложениями d₁(Q_sa*,Q_sb*) и d₁(R_a,R_b) в пространстве мультимножеств (A , d₁) с метрикой (5) при w_s=1; значения показателей точности _s для аппроксимирующих признаков q_s* по каждому s-ому блоку матрицы.

Объекты / Признаки

Классы / Признаки

Принятые проекты A₁-A_i входят в класс X_a, отклоненные проекты A_i+1-A_k относятся к классу X_b. Обратим внимание читателя, что хотя проекты A_i и A_i+1 имеют одинаковые значения оценок {q_s} по всем признакам, но наборы их индивидуальных правил сортировки не совпадают, и поэтому A_iX_a, а A_i+1X_b. Множество аппроксимирующих признаков q_s*, упорядоченное по величине расстояния d₁(Q_sa*,Q_sb*), выглядит следующим образом:

{q_s*} = {q₄¹, q₄²; q₁¹, q₁²; q₅¹, q₅²; q₃¹, q₃²; q₂¹, q₂²} (15)

Заметим, что задача (13) не имеет оптимального решения по критерию Q₆, то есть любое значение признака q₆ является неаппроксимирующим. Выбрав некоторое желаемое значение точности аппроксимации ₀, получим следующие обобщенные решающие правила для отбора проектов.

«Исполнители проекта должны быть одними из лучших или обладать опытом и квалификацией, достаточными для проведения работ» (оценки q₄¹ или q₄²; точность аппроксимации _s0,66).

«Проект должен быть крайне важным или важным для достижения одной из основных целей программы; исполнители проекта должны быть одними из лучших или обладать опытом, квалификацией и материально-техническими ресурсами, достаточными для проведения работ» (оценки q₄¹ или q₄²; и q₁¹ или q₁²; и q₅¹ или q₅²; точность аппроксимации _s0,55).

Отметим, что последнее правило полностью совпадает с решающим правилом для отбора проектов, приведенным ранее в работе [14]. Обобщенное решающее правило классификации объектов позволяет также выявить расхождения в индивидуальных правилах сортировки, применявшихся экспертами, и при необходимости скорректировать их. Ранжирование (15) аппроксимирующих признаков по величине расстояния d₁ показывает, что наиболее важным для отбора проектов оказывается критерий Q₄, характеризующий опыт и квалификацию исполнителей, а следующими по важности - критерии Q₁, оценивающий важность проекта для достижения целей программы, и Q₅, отражающий ресурсное обеспечение работ.

Заключение

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

Литература

[1]. О.И.Ларичев, Е.М.Мошкович. Качественные методы принятия решений. Вербальный анализ решений. - М.: Наука, Физматлит, 1996.

[2]. Б.Г.Миркин. Анализ качественных признаков и структур. - М.: Статистика, 1980.

[3] Л.Г.Евланов. Теория и практика принятия решений. - М.: Экономика, 1984.

[4]. В.Д.Ногин. Принятие решений в многокритериальной среде: количественный подход. - М.: Физматлит, 2002.

[5]. А.Б.Петровский. Метрические пространства мультимножеств.//Доклады Академии наук, 1995, Т.344, №2, 175-177.

[6]. А.Б.Петровский. Основные понятия теории мультимножеств. - М.: Едиториал УРСС, 2002.

[7]. Ю.И.Журавлев. Корректные алгебры над множествами некорректных (эвристических) алгоритмов.I,II,III.//Кибернетика, 1977, №4, 14-21; 1977, №6, 21-27; 1978, №2, 35-43.

[8]. Ю.Н.Тюрин. Экспертная классификация.//Экспертные методы в современных исследованиях. Сборник трудов. - М.: ВНИИСИ, 1979, 5-15.

[9]. J.G.Kemeni, J.L.Snell. Mathematical models in the social sciences. - Ginn, Boston, 1962. (Дж.Кемени, Дж.Снелл. Кибернетическое моделирование./Пер. с англ. - М.: Советское радио, 1972).

[10]. Б.Г.Литвак. Экспертная информация: методы получения и анализа. - М.: Радио и связь, 1982.

[11]. B.Roy. Multicriteria methodology for decision aiding. - Kluwer Academic Publishers, Dordrecht, 1996.

[12]. А.В.Литвинова. Упорядочивание многопризнаковых объектов на основе теории мультимножеств.//Дипломная работа на соискание степени магистра. Московский физико-технический институт (государственный университет), М., 2002.

[13]. Кто в России самый интеллектуальный? Рейтинг ведущих российских разработчиков высоких технологий.//Компания, 2000, №47(143), 38-39.

[14]. О.И.Ларичев, А.С.Прохоров, А.Б.Петровский, М.Ю.Стернин, Г.И.Шепелев. Опыт планирования фундаментальных исследований на конкурсной основе.//Вестник АН СССР, 1989, №7, 51-61.

[15]. А.А.Дорофеюк. Алгоритмы автоматической классификации.//Автоматика и телемеханика, 1971, №12, 78-113.

[16]. С.А.Орловский. Проблемы принятия решений при нечеткой исходной информации. - М.: Наука, 1981.

[17]. H.J.Zimmerman, L.A.Zadeh, B.R.Gaines. Fuzzy sets and decision analysis. - North-Holland, Amsterdam, 1984.

[18]. Z.Pawlak, R.Slowinsky. Rough set approach to multi-attribute decision analysis.//European Journal of Operational Research, 1994, №72, 443-459.

Размещено на Allbest.ru