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

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


Смотрите также:
Контрольная работа по дисциплине «Анализ данных и прогнозирование» Тема 15: Кластерный анализ...
Задачи классификации объектов: кластерный анализ. Дискриминантный анализ...
Анализ понятие о кластерном анализе...
Модели и алгоритмы обработки информации в автоматизированных системах...
Реферат Дипломный проект 127  л., 16  рисунков, 27  таблиц, 36  источников, 2 приложения...
Лекция Кластерный анализ...
Проект по гидроэкологии «Исследование состояния водных объектов г...
Система дистанционного обучения в рамках концепции развития современной организации: кластерный...
Система есть комплекс элементов находящийся во взаимодействии...
Кластерный анализ режимов систем тягового электроснабжения для целей ситуационного управления...
Сохранение объектов культурно-исторического...
Кластерный генетический алгоритм синтеза оптимальных решений задачи инвестиционного планирования...



Загрузка...
скачать
УДК 510.22

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


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

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

Введение

Широко применяемым инструментом для исследования структуры большого числа объектов и связей между ними в различных теоретических и практических проблемах искусственного интеллекта, принятия решений, распознавания образов, обработки разнородной информации и других областей является кластерный анализ. В результате кластеризации заданная совокупность объектов A1,...,An агрегируется в небольшое количество групп – кластеров X1,...,XR. В кластерном анализе объединение объектов в группы производится, исходя из их сходства или различия, которое оценивается степенью близости объектов, выражаемой некоторой метрикой в признаковом пространстве.

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

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

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

Многопризнаковые объекты Ai, i=1,…,n обычно принято представлять как векторы или кортежи qi=(qi1e1,…, qimem) в пространстве Q=Q1…Qm, где Qs={qses} – непрерывная или дискретная шкала s-го признака, es=1hs, s=1,…,m. Ситуация существенным образом усложняется, если одному и тому же объекту Ai может соответствовать не один, а несколько m-мерных векторов с различающимися значениями признаков. Подобные ситуации возникают, например, когда объект Ai оценивается k независимыми экспертами по m критериям, или когда необходимо одновременно учесть m параметров объекта Ai, измеренных k различными способами. В таких случаях объект Ai представляется в m-мерном пространстве Q уже не одним вектором qi, а группой, состоящей из k векторов {qi(1),…,qi(k)} вида qi(j)=(qi1e1(j),…, qimem(j)), j=1,…,k, которая должна рассматриваться как единое целое. При этом, очевидно, измеренные разными способами значения параметров, как и индивидуальные оценки, данные экспертами, могут быть похожими, различающимися и даже противоречивыми, что в свою очередь может приводить к несравнимости m-мерных векторов qi(j), характеризующих один и тот же объект Ai.

Совокупность таких «составных» объектов может иметь в пространстве Q сложную структуру, достаточно трудную для анализа. Непросто ввести в этом пространстве и метрику для измерения расстояний между объектами. Указанные трудности можно преодолеть, если воспользоваться иным способом представления многопризнаковых объектов, основанным на формализме мультимножеств [Петровский, 2003], который позволяет одновременно учесть различные комбинации значений количественных и качественных признаков, а также их многозначность.

Введем вместо прямого произведения m шкал признаков Q=Q1…Qm обобщенную шкалу признаков – множество G=Q1...Qm, состоящее из m групп признаков, и представим объект Ai в таком символическом виде:

Ai = {kAi(q11)◦q11,…,kAi(q1h1)◦q1h1,…,kAi(qm1)◦qm1,…, kAi(qmhm)◦qmhm}. (1)

где число kAi(qses) указывает, сколько раз признак qsesQs встречается в описании объекта Ai, знак ◦ обозначает кратность вхождения признака qses. Например, при многокритериальной оценке объекта Ai несколькими экспертами число kAi(qses) равно числу экспертов, давших объекту Ai оценку qses по критерию Qs. Множество G характеризует свойства совокупности объектов A={A1,...,An}. Объект Ai можно записать и более компактно как Ai={kAi(x1)◦x1,…,kAi(xh)◦xh}, определив элементы множества G={x1,...,xh} следующим образом:

x1=q11, x2=q12,…,=q1h1, =q21,…,=q2h2,…, =qm1,…,=qmhm,

где h=h1+...+hm. Такая запись объекта Ai представляет его как множество с повторяющимися элементами xjG или мультимножество. Функция числа экземпляров мультимножества kA:GZ+={0,1,2,…} определяет кратность вхождения элемента xiG в мультимножество А.

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

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

объединение AB = {kAB (x)◦x | kAB (x)=max(kA(x), kB(x))};

пересечение AB = {kAB (x)◦x | kAB (x)=min(kA(x), kB(x))};

сложение A+B = {kA+B(x)◦x kA+B(x)=kA(x)+kB(x)};

вычитание AB = {kAB(x)◦x kAB(x)=kA(x)kA∩B (x)};

симметрическая разность AB = {kAB(x)◦x kAB(x)=|kA(x)kB(x)|};

дополнение = ZA = {x |=kZ(x)–kA(x)};

умножение на число tA = {ktA(x)◦x ktA(x)=tkA(x), tZ+};

умножение АВ = {kАВ(x)◦x kАВ(x) = kA(x)kB(x)};

п-ая степень Ап = {kАn(x)◦x kАn(x) = (kA(x))п};

прямое произведение AB = {kAB◦xi, xj | kAB=kA(xi)kB(xj), xiA,xjB};

прямая п-ая степень (A)n ={k(А)n◦x1,…,xп | k(А)n=kA(x1)… kA(xn), xiA},

где x1,…,xn – кортеж n элементов.

Мультимножество называется пустым , если k(x)=0, и максимальным Z, если kZ(х)=maxAAkA(х), xG. При переходе от мультимножеств к множествам и замене kA(x) на A(x) многие из выше определенных операций с мультимножествами останутся справедливыми и для множеств, но некоторые из них могут изменить или потерять смысл. Например, операции арифметического сложения и умножения на число для множеств неопределимы, вычитание множеств определяется иначе, а арифметическое умножение множеств будет совпадать с их пересечением.

Различные классы метрических пространств мультимножеств (A,d) задаются следующими метриками (псевдометриками):

d1p(A,B) = [m(AΔB)]1/p; d2p(A,B) = [m(AΔB)m(Z)]1/p;

d3p(A,B) = [m(AΔB)m(AB)]1/p, (2)

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

Алгеброй мультимножеств называется семейство мультимножеств L(Z), замкнутое относительно операций объединения, пересечения, сложения, вычитания и дополнения. Максимальное мультимножество Z является единицей алгебры, а пустое мультимножество  – нулем. Мера мультимножества m обладает свойствами: m()=0; сильная аддитивность m(iAi)=im(Ai); слабая аддитивность m(iAi)=im(Ai) для AiAj=; монотонность m(A)m(B)AB; симметричность m(A)+m()=m(Z); непрерывность m(Ai)=m(Ai); эластичность m(tA)=tm(A).

Меру мультимножества можно ввести различными способами, например, как мощность мультимножества m(A)=A=ikA(xi) или как линейную комбинацию функций кратности m(A)=iwikA(xi), wi>0. В этом случае метрики приобретают вид:

d1р(A,B) =;

d2p(A,B) =, w'i=wi/kZ(xj);

d3p(A,B) =.

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

При замене kA на A метрические пространства измеримых мультимножеств превращаются в соответствующие метрические пространства измеримых множеств, которые будут обладать многими аналогичными свойствами. Так, основная метрика вида d11(A,B)=m(AB) или d11(A,B)=|AB| приведена во многих монографиях по теории множеств и называется расстоянием Фреше-Никодима-Ароншаяна или метрикой меры. Локально усредненная метрика d31(A,B)=m(AB)/m(AB) называется расстоянием Штейнхауса, а d31(A,B)=|AB|/|AB| – биотопическим расстоянием [Деза, Лоран, 2001]. Расстояние между множествами вида d12(A,B)=[m(AB)]1/2 упомянуто в книге [Орлов, 1979]. Семейства метрик общего вида d1p(A,B)=[m(AB)]1/р, d2p(A,B)=[m(AB)/m(Z)]1/р и d3p(A,B)= =[m(AB)/m(AB)]1/р в пространствах измеримых множеств и измеримых мультимножеств введены впервые автором [Петровский, 2003].

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

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

Кластер традиционно формируется как теоретико-множественное объединение наиболее близких объектов [Anderberg, 1973]. Новые типы операций над мультимножествами открывают новые возможности для группирования многопризнаковых объектов. Например, кластер Xt объектов может быть получен как сумма Xt=iAi, объединение Xt=iAi или пересечение Xt=iAi мультимножеств Ai, описывающих объекты Ai, либо как линейная комбинация различных мультимножеств вида Xt=itiAi, Xt=itiAi или Xt=itiAi, ti>0. Когда кластер Xt образуется в результате объединения или пересечения объектов Ai, происходит усиление лучших свойств (максимальных значений признаков xj) или соответственно худших свойств (минимальных значений признаков xj), присутствующих у отдельных членов группы. При сложении объектов агрегируются все свойства xj всех членов кластера Xt.

Для генерации группы объектов в алгоритмах кластерного анализа обычно используются следующие подходы: минимизировать различие (максимизировать сходство) между объектами внутри группы; максимизировать различие (минимизировать сходство) между группами объектов. Далее будем считать для простоты, что различие между объектами Ai внутри кластера Xt, между некоторым объектом Ai и кластером Xt, между кластерами Xt, представленными как точки или группы точек в пространстве мультимножеств, определяется одинаковым образом и задается одним из вышеприведенных расстояний d11, d21, d31.

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

s1(A,B)=1m(AΔB)m(Z); s2(A,B)=m(AB)m(Z);

s3(A,B)=m(AB)m(AB). (3)

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

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

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

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

Шаг 2. Вычислить расстояния d(Xa,Xb) между всеми возможными парами кластеров Xa и Xb, 1a,bR, ab, используя одну метрик d11, d21, d31 метрического пространства мультимножеств.

Шаг 3. Найти пару наиболее близких кластеров Xu,Xv таких, что

d(Xu,Xv) =d(Xa,Xb), (4)

и сформировать новый кластер путем сложения Xr=Xu+Xv, объединения Xr=XuXv или пересечения Xr=XuXv мультимножеств, или путем линейной комбинации одной из этих операций.

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

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

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

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

Отметим, что процедура иерархической кластеризации, начиная с 3 шага, может сильно ветвиться из-за большого числа эквивалентных пар кластеров Xu, Xv, находящихся в признаковом пространстве на одинаковом минимальном расстоянии. Поэтому появляется много вариантов для дальнейшего слияния кластеров. И, как следствие, в итоге могут сформироваться несовпадающие конечные группы объектов даже при использовании одной и той же метрики. Наименьшее число таких конечных групп возникает, если агрегирование объектов осуществляется путем сложения мультимножеств, наибольшее – при пересечении мультимножеств. Использование локально усредненной метрики d31 порождает меньшее число точек ветвления алгоритма по сравнению с основной метрикой d11 и полностью усредненной метрикой d21.

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

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

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

K(Xr#) =/Nrl,

где Nrl равно числу объектов Ai в кластере Xrl. Перейти к шагу 4.

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

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

J(At,Xt) =. (5)

Функционал J(At,Xt) по своему содержанию близок критерию K(Xr#) компактности кластера и характеризует своего рода «кучность» распределения объектов в признаковом пространстве. Заметим, что в нашем случае центр At кластера Xt может совпадать с одним из реально имеющихся объектов Ai из совокупности A, или быть так называемым «фантомным» объектом, сконструированным из признаков xj в виде (1), но реально отсутствующим в исходной совокупности объектов A.

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

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

Шаг 2. Распределить все объекты Ai по кластерам Xt (t=1,...,R) в соответствии с некоторым правилом. Например, вычислить расстояния d(Ai,Xt) между каждым объектом Ai и кластерами Xt, и поместить объект Ai в ближайший из кластеров Xr, который определяется условием d(Ai,Xr)= =d(Ai,Xt). Или определить центр At для каждого кластера Xt, решив уравнение (5), и поместить каждый объект Ai в кластер с ближайшим центром As, задаваемый условием d(Ai,As) =d(Ai, At).

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

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

H(Xopt) = min, (6)

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

Заключение

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

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

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

В ряде случаев возникает необходимость решить обратную задачу кластерного анализа, например, построить классификацию множества G={x1,...,xh} свойств объектов, используя совокупность объектов A={A1,...,An}. Или требуется одновременно расклассифицировать и объекты, и их свойства. В последнем случае применяются методы двойной классификации, и строятся две последовательности: группы объектов {X1,...,XR} и группы свойств {G1,...,GL}. Содержательную интерпретацию полученных группировок можно дать, например, с помощью многомерного шкалирования [Айвазян и др., 1989]. При этом, однако, могут возникнуть ситуации, особенно если множество G свойств объектов состоит из элементов разного «качества», когда содержательная интерпретация отдельных кластеров свойств Gw окажется затруднительной.

Литература

[Айвазян и др., 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.

* Работа поддержана программами фундаментальных исследований президиума РАН «Фундаментальные проблемы информатики и информационных технологий» и ОИТВС РАН «Фундаментальные основы информационных технологий и систем», Российским фондом фундаментальных исследований (проекты 04-01-00290, 05-01-00666, 06-07-89352)

1 117312, Москва, проспект 60-летия Октября, 9, ИСА РАН, pab@isa.ru




Скачать 198.55 Kb.
оставить комментарий
Дата20.04.2012
Размер198.55 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх