Кластерный анализ объектов с противоречивыми свойствами

Размещено на http://www.allbest.ru/

УДК 510.22

КЛАСТЕРНЫЙ АНАЛИЗ ОБЪЕКТОВ С ПРОТИВОРЕЧИВЫМИ СВОЙСТВАМИ

А.Б. Петровский

Введение

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

Широко применяемым инструментом для исследования структуры большого числа объектов и связей между ними в различных теоретических и практических проблемах искусственного интеллекта, принятия решений, распознавания образов, обработки разнородной информации и других областей является кластерный анализ. В результате кластеризации заданная совокупность объектов A₁,...,A_n агрегируется в небольшое количество групп - кластеров X₁,...,X_R. В кластерном анализе объединение объектов в группы производится, исходя из их сходства или различия, которое оценивается степенью близости объектов, выражаемой некоторой метрикой в признаковом пространстве.

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

1. Представление многопризнаковых объектов

Многопризнаковые объекты A_i, i=1,…,n обычно принято представлять как векторы или кортежи q_i=(q_i1^e1,…, q_im^em) в пространстве

Q=Q₁…Q_m,

где Q_s={q_s^es} - непрерывная или дискретная шкала s-го признака, e_s=1h_s, s=1,…,m. Ситуация существенным образом усложняется, если одному и тому же объекту A_i может соответствовать не один, а несколько m-мерных векторов с различающимися значениями признаков. Подобные ситуации возникают, например, когда объект A_i оценивается k независимыми экспертами по m критериям, или когда необходимо одновременно учесть m параметров объекта A_i, измеренных k различными способами. В таких случаях объект A_i представляется в m-мерном пространстве Q уже не одним вектором q_i, а группой, состоящей из k векторов {q_i⁽¹⁾,…,q_i^(k)} вида q_i^(j)=(q_i1^e1(j),…, q_im^em(j)), j=1,…,k, которая должна рассматриваться как единое целое. При этом, очевидно, измеренные разными способами значения параметров, как и индивидуальные оценки, данные экспертами, могут быть похожими, различающимися и даже противоречивыми, что в свою очередь может приводить к несравнимости m-мерных векторов q_i^(j), характеризующих один и тот же объект A_i.

Совокупность таких «составных» объектов может иметь в пространстве Q сложную структуру, достаточно трудную для анализа. Непросто ввести в этом пространстве и метрику для измерения расстояний между объектами. Указанные трудности можно преодолеть, если воспользоваться иным способом представления многопризнаковых объектов, основанным на формализме мультимножеств [Петровский, 2003], который позволяет одновременно учесть различные комбинации значений количественных и качественных признаков, а также их многозначность. Введем вместо прямого произведения m шкал признаков Q=Q₁…Q_m обобщенную шкалу признаков - множество G=Q₁...Q_m, состоящее из m групп признаков, и представим объект A_i в таком символическом виде:

A_i = {k_Ai(q₁¹)?q₁¹,…,k_Ai(q₁^h1)?q₁^h1,…,k_Ai(q_m¹)?q_m¹,…, k_Ai(q_m^hm)?q_m^hm}. (1)

где число k_Ai(q_s^es) указывает, сколько раз признак q_s^esQ_s встречается в описании объекта A_i, знак ? обозначает кратность вхождения признака q_s^es. Например, при многокритериальной оценке объекта A_i несколькими экспертами число k_Ai(q_s^es) равно числу экспертов, давших объекту A_i оценку q_s^es по критерию Q_s. Множество G характеризует свойства совокупности объектов A={A₁,...,A_n}. Объект A_i можно записать и более компактно как A_i={k_Ai(x₁)?x₁,…,k_Ai(x_h)?x_h}, определив элементы множества G={x₁,...,x_h} следующим образом:

x₁=q₁¹, x₂=q₁²,…,=q₁^h1,

=q₂¹,…,=q₂^h2,…,

=q_m¹,…,=q_m^hm,

где h=h₁+...+h_m. Такая запись объекта A_i представляет его как множество с повторяющимися элементами x_jG или мультимножество. Функция числа экземпляров мультимножества k_A:GZ₊={0,1,2,…} определяет кратность вхождения элемента x_iG в мультимножество А.

2. Метрические пространства мультимножеств

Метрические пространства мультимножеств были введены в работах [Петровский, 1995, 2003]. Определяются следующие операции над мультимножествами:

объединение AB = {k_AB (x)?x | k_AB (x)=max(k_A(x), k_B(x))};

пересечение AB = {k_AB (x)?x | k_AB (x)=min(k_A(x), k_B(x))};

сложение A+B = {k_A+B(x)?x k_A+B(x)=k_A(x)+k_B(x)};

вычитание AB = {k_AB(x)?x k_AB(x)=k_A(x)k_A?B (x)};

симметрическая разность AB = {k_AB(x)?x k_AB(x)=|k_A(x)k_B(x)|};

дополнение = ZA = ?x =k_Z(x)k_A(x);

умножение на число t*A = {k_t*A(x)?x k_t*A(x)=tk_A(x), tZ₊};

умножение А*В = {k_А*В(x)?x k_А*В(x) = k_A(x)k_B(x)};

п-ая степень А^п = {k_Аn(x)?x k_Аn(x) = (k_A(x))^п};

прямое произведение AB = {k_AB?x_i, x_j k_AB=k_A(x_i)k_B(x_j), x_iA,x_jB};

прямая п-ая степень (A)ⁿ ={k_(А)n?x₁,…,x_п | k_(А)n=k_A(x₁)… k_A(x_n), x_iA},

где x₁,…,x_n - кортеж n элементов.

Мультимножество называется пустым , если k(x)=0, и максимальным Z, если k_Z(х)=max_AAk_A(х), xG. При переходе от мультимножеств к множествам и замене k_A(x) на _A(x) многие из выше определенных операций с мультимножествами останутся справедливыми и для множеств, но некоторые из них могут изменить или потерять смысл. Например, операции арифметического сложения и умножения на число для множеств неопределимы, вычитание множеств определяется иначе, а арифметическое умножение множеств будет совпадать с их пересечением. Различные классы метрических пространств мультимножеств (A,d) задаются следующими метриками (псевдометриками):

d_1p(A,B) = [m(AДB)]^1/p; d_2p(A,B) = [m(AДB)m(Z)]^1/p;

d_3p(A,B) = [m(AДB)m(AB)]^1/p, (2)

где p - целое число, m - мера мультимножества, действительная неотрицательная функция, заданная на алгебре мультимножеств L(Z).

Алгеброй мультимножеств называется семейство мультимножеств L(Z), замкнутое относительно операций объединения, пересечения, сложения, вычитания и дополнения. Максимальное мультимножество Z является единицей алгебры, а пустое мультимножество - нулем. Мера мультимножества m обладает свойствами: m()=0; сильная аддитивность m(_iA_i)=_im(A_i); слабая аддитивность m(_iA_i)=_im(A_i) для A_iA_j=; монотонность m(A)m(B)AB; симметричность m(A)+m()=m(Z); непрерывность m(A_i)=m(A_i); эластичность m(t*A)=tm(A).

Меру мультимножества можно ввести различными способами, например, как мощность мультимножества m(A)=A=_ik_A(x_i) или как линейную комбинацию функций кратности m(A)=_iw_ik_A(x_i), w_i>0. В этом случае метрики приобретают вид:

d_1р(A,B) =;

d_2p(A,B) =, w'_i=w_i/k_Z(x_j);

d_3p(A,B) =.

Назовем соответствующие метрики основной, полностью усредненной и локально усредненной. Основная метрика d_1p(A,B) является метрикой типа Хемминга, традиционно используемой во многих приложениях. Полностью усредненная метрика d_2p(A,B) характеризует различие между двумя мультимножествами A и B, отнесенное к расстоянию, максимально возможному в исходном пространстве. Локально усредненная метрика d_3p(A,B) задает различие, отнесенное к максимально возможной «общей части» AB только этих двух мультимножеств в исходном пространстве. Функции d_2p(A,B) и d_3p(A,B) удовлетворяют условию нормировки 0d(A,B)1. Функция d_3p(A,B) не определена для A=B=, поэтому по определению принимается d_3p(,)=0.

При замене k_A на _A метрические пространства измеримых мультимножеств превращаются в соответствующие метрические пространства измеримых множеств, которые будут обладать многими аналогичными свойствами. Так, основная метрика вида d₁₁(A,B)=m(AB) или d₁₁(A,B)=|AB| приведена во многих монографиях по теории множеств и называется расстоянием Фреше-Никодима-Ароншаяна или метрикой меры. Локально усредненная метрика d₃₁(A,B)=m(AB)/m(AB) называется расстоянием Штейнхауса, а d₃₁(A,B)=|AB|/|AB| - биотопическим расстоянием [Деза, Лоран, 2001]. Расстояние между множествами вида d₁₂(A,B)=[m(AB)]^1/2 упомянуто в книге [Орлов, 1979]. Семейства метрик общего вида d_1p(A,B)=[m(AB)]^1/р, d_2p(A,B)=[m(AB)/m(Z)]^1/р и d_3p(A,B)= =[m(AB)/m(AB)]^1/р в пространствах измеримых множеств и измеримых мультимножеств введены впервые автором [Петровский, 2003].

3. Агрегирование многопризнаковых объектов

Принципиальными моментами кластерного анализа являются: выбор выражения, определяющего расстояние между объектами в признаковом пространстве; выбор алгоритма группирования объектов; разумная интерпретация сформированных групп. Выбор вида пространства и типа метрики зависит от свойств анализируемых объектов. Для рассмотренных выше многопризнаковых объектов наиболее адекватно метрическое пространство измеримых мультимножеств (A,d) с основным, полностью или локально усредненным расстоянием, например, d₁₁, d₂₁, d₃₁.

Кластер традиционно формируется как теоретико-множественное объединение наиболее близких объектов [Anderberg, 1973]. Новые типы операций над мультимножествами открывают новые возможности для группирования многопризнаковых объектов. Например, кластер X_t объектов может быть получен как сумма X_t=_iA_i, объединение X_t=_iA_i или пересечение X_t=_iA_i мультимножеств A_i, описывающих объекты A_i, либо как линейная комбинация различных мультимножеств вида X_t=_it_i*A_i, X_t=_it_i*A_i или X_t=_it_i*A_i, t_i>0. Когда кластер X_t образуется в результате объединения или пересечения объектов A_i, происходит усиление лучших свойств (максимальных значений признаков x_j) или соответственно худших свойств (минимальных значений признаков x_j), присутствующих у отдельных членов группы. При сложении объектов агрегируются все свойства x_j всех членов кластера X_t.

Для генерации группы объектов в алгоритмах кластерного анализа обычно используются следующие подходы: минимизировать различие (максимизировать сходство) между объектами внутри группы; максимизировать различие (минимизировать сходство) между группами объектов. Далее будем считать для простоты, что различие между объектами A_i внутри кластера X_t, между некоторым объектом A_i и кластером X_t, между кластерами X_t, представленными как точки или группы точек в пространстве мультимножеств, определяется одинаковым образом и задается одним из вышеприведенных расстояний d₁₁, d₂₁, d₃₁.

Сходство объектов, описываемых как мультимножества, можно характеризовать следующими показателями (индексами):

s₁(A,B)=1m(AДB)m(Z); s₂(A,B)=m(AB)m(Z);

s₃(A,B)=m(AB)m(AB). (3)

Функции s₁, s₂, s₃ обобщают на случай мультимножеств известные индексы сходства объектов, такие соответственно как коэффициент простой согласованности, мера сходства Рассела-Рао, коэффициент Жаккара или мера Роджерса-Танимото [Anderberg, 1973]. Заметим, что коэффициент простой согласованности s₁ и мера сходства Рассела-Рао s₂ связаны соотношением s₁(A,B)=s₂(A,B)+s₂(,), которое представляет собой одно из возможных бинарных разложений максимального мультимножества Z на блоки из покрытий и перекрытий мультимножеств [Петровский, 2000].

4. Иерархический кластерный анализ

Рассмотрим общую схему процедуры иерархической кластеризации совокупности объектов A, представленных мультимножествами A₁,...,A_n, когда число R генерируемых кластеров X₁,...,X_R заранее не определено.

Шаг1. Положить R=n, где R - число кластеров, n - число объектов A_i. Тогда каждый кластер X_i совпадает с некоторым объектом A_i, i=1,...,R.

Шаг 2. Вычислить расстояния d(X_a,X_b) между всеми возможными парами кластеров X_a и X_b, 1a,bR, ab, используя одну метрик d₁₁, d₂₁, d₃₁ метрического пространства мультимножеств. Шаг 3. Найти пару наиболее близких кластеров X_u,X_v таких, что и сформировать новый кластер путем сложения X_r=X_u+X_v, объединения X_r=X_uX_v или пересечения X_r=X_uX_v мультимножеств, или путем линейной комбинации одной из этих операций.

d(X_u,X_v) =d(X_a,X_b), (4)

Шаг 4. Уменьшить число кластеров на единицу: R=n1. Если R=1, то остановиться и вывести результат, например, в виде дендрограммы. Если R1, перейти к следующему шагу.

Шаг 5. Вычислить расстояния d(X_a,X_b) между новыми парами кластеров для всех 1a,bR, abr. Вернуться к шагу 3.

Процесс иерархической кластеризации заканчивается, когда все объекты будут объединены в несколько классов или в один единственный класс. Процедура может быть также прервана на некотором шаге, когда индекс различия превысит некоторый пороговый уровень. Методы оптимизации дендрограмм, основанные на поиске удовлетворительного порогового уровня d_opt(X_u,X_v) для расстояния [Miyamoto, 1987], позволяют дать разумную интерпретацию сформированным группам объектов.

Характер образования кластеров и результаты процесса кластеризации в значительной мере определяется видом используемой метрики d. Основная метрика d₁₁ и полностью усредненная метрика d₂₁ дают практически одинаковые результаты. При кластеризации сначала происходит слияние «небольших» (имеющих небольшое число признаков) объектов, мало различающихся между собой, а затем начинается агрегирование более «крупных» объектов. Получающиеся в итоге группы более или менее сопоставимы по числу входящих в них объектов, но сильно отличаются друг от друга наборами характеризующих их признаков. Процесс кластеризации с локально усредненной метрикой d₃₁ начинается с группирования похожих объектов «среднего» и «большого» размеров, имеющих существенные «общие» наборы признаков, к которым далее присоединяются все более и более отличающиеся «небольшие» объекты. Итоговые группировки объектов, полученные в первом и во втором случаях, могут различаться достаточно сильно.

Отметим, что процедура иерархической кластеризации, начиная с 3 шага, может сильно ветвиться из-за большого числа эквивалентных пар кластеров X_u, X_v, находящихся в признаковом пространстве на одинаковом минимальном расстоянии. Поэтому появляется много вариантов для дальнейшего слияния кластеров. И, как следствие, в итоге могут сформироваться несовпадающие конечные группы объектов даже при использовании одной и той же метрики. Наименьшее число таких конечных групп возникает, если агрегирование объектов осуществляется путем сложения мультимножеств, наибольшее - при пересечении мультимножеств. Использование локально усредненной метрики d₃₁ порождает меньшее число точек ветвления алгоритма по сравнению с основной метрикой d₁₁ и полностью усредненной метрикой d₂₁.

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

Шаг 3.1. Найти все эквивалентные пары наиболее близких кластеров X_u, X_v, соответствующих условию (4), и с помощью одной из операций (суммирования, объединения или пересечения) сформировать новые кластеры X_rl, l=1,…,g для всех g эквивалентных пар кластеров.

Шаг 3.2. Найти кластер X_r^#, минимизирующий некоторый дополнительный критерий, например, компактность кластера, выражаемую функционалом

K(X_r^#) =/N_rl,

где N_rl равно числу объектов A_i в кластере X_rl. Перейти к шагу 4.

5. Неиерархический кластерный анализ

В методах неиерархического кластерного анализа число кластеров R считается фиксированным и заданным заранее. В алгоритмах кластеризации часто используется понятие центра A_t кластера X_t, t=1,...,R, который находится как решение задачи минимизации некоторого функционала от расстояния, например, следующего вида:

J(A_t,X_t) =.(5)

Функционал J(A_t,X_t) по своему содержанию близок критерию K(X_r^#) компактности кластера и характеризует своего рода «кучность» распределения объектов в признаковом пространстве. Заметим, что в нашем случае центр A_t кластера X_t может совпадать с одним из реально имеющихся объектов A_i из совокупности A, или быть так называемым «фантомным» объектом, сконструированным из признаков x_j в виде (1), но реально отсутствующим в исходной совокупности объектов A.

Обобщенная схема неиерархической кластеризации совокупности объектов A={A₁,...,A_n}, представленных мультимножествами, включает следующие основные этапы.

Шаг 1. Выбрать некоторое начальное разбиение совокупности объектов A на R кластеров A ={X₁,...,X_R}.

Шаг 2. Распределить все объекты A_i по кластерам X_t (t=1,...,R) в соответствии с некоторым правилом. Например, вычислить расстояния d(A_i,X_t) между каждым объектом A_i и кластерами X_t, и поместить объект A_i в ближайший из кластеров X_r, который определяется условием d(A_i,X_r)= =d(A_i,X_t). Или определить центр A_t для каждого кластера X_t, решив уравнение (5), и поместить каждый объект A_i в кластер с ближайшим центром A_s, задаваемый условием d(A_i,A_s) =d(A_i, A_t).

Шаг 3. Если после распределения всех объектов A_i по кластерам X_t объекты не изменят своей кластерной принадлежности, заданной первоначальным разбиением, то остановиться и вывести результат. В противоположном случае вернуться к шагу 2.

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

H(X_opt) = min, (6)

где функционал J(A_i, X_t) определяется, например, выражением (5). В общем случае решение задачи (6) неоднозначно, поскольку функционал H(X_opt) качества разбиения является функцией, имеющей много локальных экстремумов. Конечный результат зависит и от первоначального (близко или далеко от оптимального) распределения объектов по классам.

Заключение

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

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

При решении практических задач с помощью кластерного анализа может оказаться полезным следующий прием.

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

Эти разбиения затем анализируются неиерархическими методами, и находится наилучшее или наиболее приемлемое из разбиений.

Часто в процедурах кластеризации вместо минимизации расстояния d между объектами, характеризующего их различия, используется максимизация разнообразных показателей сходства объектов s (3).

В ряде случаев возникает необходимость решить обратную задачу кластерного анализа, например, построить классификацию множества G={x₁,...,x_h} свойств объектов, используя совокупность объектов A={A₁,...,A_n}.

Или требуется одновременно расклассифицировать и объекты, и их свойства.

В последнем случае применяются методы двойной классификации, и строятся две последовательности: группы объектов {X₁,...,X_R} и группы свойств {G₁,...,G_L}. Содержательную интерпретацию полученных группировок можно дать, например, с помощью многомерного шкалирования [Айвазян и др., 1989]. При этом, однако, могут возникнуть ситуации, особенно если множество G свойств объектов состоит из элементов разного «качества», когда содержательная интерпретация отдельных кластеров свойств G_w окажется затруднительной.

кластер метрический пространственный мультимножество

Литература

[Айвазян и др., 1989] Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерности. - М.: Финансы и статистика, 1989.

[Деза, Лоран, 2001] Деза М.М., Лоран М. Геометрия разрезов и метрик./Пер. с англ. - М.: МЦНМО, 2001.

[Орлов, 1979] Орлов А.И. Устойчивость в социально-экономических моделях. - М.: Наука, 1979.

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

[Петровский, 2000] Петровский А.Б. Комбинаторика мультимножеств. // Доклады Академии наук. 2000, Т.370, №6, С.750-753.

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

[Петровский, 2004] Петровский А.Б. Многокритериальное принятие решений по противоречивыми данным: подход теории мультимножеств. // Информационные технологии и вычислительные системы. 2004, №2, С.56-66.

[Anderberg, 1973] Anderberg M.R. Cluster Analysis for Applications. - New York, Academic Press, 1973.

[Miyamoto, 1987] Miyamoto S. Cluster analysis as a tool of interpretation of complex systems.//Working paper WP-87-41. - Laxenburg, Austria, IIASA, 1987.

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