Диссертация (1137117), страница 8
Текст из файла (страница 8)
Объект, в этом случае, принадлежит обоим паттерн-кластерам. Однако, в силу свойства 1, различные порядково-инвариантныепаттерн-кластеры не пересекаются. Поэтому, предположение о различныхпаттерн-кластерах следует отвергнуть, и сделать вывод, что все три строкипринадлежат одному порядково-инвариантному паттерн-кластеру.3.Предположим, что свойство выполняется для m объектов (т.е.
всепринадлежат одному порядково-инвариантному паттерн-кластеру). Покажем, чтов этом случае, оно выполняется и для (m+1) объектов. Действительно,рассматривая два объектаи, найдем, что они принадлежат одномупорядково-инвариантному паттерн-кластеру. Повторяя, далее рассуждения п. 2,найдем, что все строки принадлежат одному порядково-инвариантному паттернкластеру.Таким образом, опираясь на метод математической индукции, можноутверждать, что свойство верно для случая произвольного числа объекта.Теорема 1 доказана.Рассмотрим вопрос существования обратного утверждения к теореме 1. Вобщем случае, обратная теорема – неверна.
Однако, справедливо следующее(близкое к нему) утверждение.Теорема 2. (Свойство 3) Если объектыпринадлежат одномупорядково-инвариантному паттерн-кластеру, то существует такой порядок Pрасположения анализируемых показателей А, В, С, …, L, при котором их значениядля всех объектов образуют монотонную неубывающую (невозрастающую)последовательность.56Доказательство. Рассмотрим произвольный объект (например, первый –) рассматриваемого паттерн-кластера и расположим значения показателей так,чтобы они образовали неубывающую (невозрастающую) последовательность:,Такому расположению значений показателей соответствует паттерн, графическипредставляющий собой кусочно-линейную неубывающую функцию в системепараллельных координат, а само расположение значений показателей А, В, С, …,L задает определѐнную последовательность P A, B, C, , L .
В силу порядковой~инвариантности кластера и все его остальные объекты будут соответствоватьэтому паттерну для данной последовательности.Теорема 2 доказана.Определим вычислительную сложность порядково-инвариантной паттернкластеризации. Всего исследуются k объектов, описанных m показателями.Для составления десятичной кодировки каждого объекта требуется m(m-1)/2сравнений. Для сравнения кодировок всех объектов и разделения на порядковоинвариантные паттерн-кластеры требуется k(k-1)/2 сравнений. Таким образом,вычислительная сложность предложенного метода составляет2.4 Диффузионно-инвариантная паттерн-кластеризацияВ данном подразделе рассматривается третий метод, входящий вординальную парно-сопоставительную модель выявления паттернов. Подробноеописание данного метода приведено в [10].Существеннойособенностьюпорядково-инвариантнойпаттерн-кластеризации является наглядность результатов, основанная на визуальномпредставлении паттернов с использованием параллельных координат, что57позволяет геометрически отобразить схожесть структуры данных в рамкахвыделяемых кластеров.Однако, для задач обработки информации часто оказывается важнымвыделять в отдельные кластеры объекты, обладающие не только схожейструктурой, но и близостью значений определяющих их показателей.
С этойцелью рассмотрим модификацию этого метода, которую будем называть«диффузионно-инвариантной паттерн-кластеризацей». В ее основе лежит идеяпоиска (и объединения в единые кластеры) объектов, настолько близких поструктуре и значениям своих показателей, что взаимный обмен значениямиотдельных из них не сказывается существенным образом на их схожести (всмысле принадлежности к единому кластеру). Фактически это означает, чтовозможно заменять значения показателя одного из объектов другим.
Самиобъекты при этом, хотя и могут менять формы кусочно-линейных функций, нетеряют схожести по отношению друг к другу.Приведем общее описание метода. Как и ранее, исследуется множество X,содержащее k объектов, каждый из которых описывается m показателями. Данноемножество разделено напорядково-инвариантных паттерн-кластера. Внутрикаждого паттерн-кластера сравнивается каждая возможная пара исследуемыхобъектов (для определѐнности, обозначими). Поскольку проведенапроцедура порядково-инвариантной паттерн-кластеризации, объектамсоответствуют определѐнные кодировкиии, а такжеииуже. Объектамтакже однозначно соответствуют вектораи. Поскольку данные объекты принадлежат одномупорядково-инвариантному паттерн-кластеру, сравнение двух любых показателейобъектаисоответствующихпоказателейобъекта(подразумевается сравнение «больше», «равно», «меньше»)аналогично.Далее, последовательно обменяем каждый из показателей объектасоответствующий показатель объекта1-огопоказателяна. На первом шаге обмениваются значения(получими58), на втором шаге – значения 2-ого показателя(получимзначенияиj-ого), на j-ом –показателя (получим).иНаконечномшагеиполучим).При каждом обмене показателей двух объектов повторяем порядковоинвариантную паттерн-кластеризацию, т.е.
формируем кодировки объектов исравниваем расстояние Хемминга. Как и при порядково-фиксированной ипорядково-инваринатной паттерн-кластеризациях, возможны 2 случая:объединяем1.соответствующиеобъектыводиндиффузионно-инвариантный паттерн-кластер19;относим соответствующие объекты в разные диффузионно-2.инвариантные паттерн-кластеры.Разберем предложенный выше метод на примере данных, представленных втаблице 6.Таблица 6. Значения показателей шести объектовОбъект 1Объект 2Объект 3Объект 4Объект 5Объект 6Показатель А354015707510В данном примере множествоПоказатель В101565455060Показатель С253020606515состоит из шести объектов, описанныхследующими векторами: x1 35, 10, 25 , x2 40, 15, 30 , x3 15, 65, 20 , x4 70, 45, 60 ,x4 75, 50, 65 иx6 10, 60, 15соответственно. Построимкусочно-линейныефункции, описывающие данные объекты.19Кластеры,образованныеприиспользованиидиффузионно-инвариантнойкластеризации, будем называть диффузионно-инвариантными паттерн-кластерами.59паттерн-807060Объект 150Объект 240Объект 330Объект 420Объект 510Объект 60Показатель АПоказатель ВПоказатель СРисунок 12.
Кусочно-линейные функции объектов 1-6.Поскольку одной из особенностей порядково-инвариантной паттернкластеризации является выделение объектов со схожей структурой паттернов,результатом его применения ко множеству {} будет разбиениена два порядково-инвариантных паттерн-кластера:и(см. Рисунок 13).Рисунок 13. Результат разбиения исходного множества.Идею,лежащуювосноведиффузионно-инвариантнойпаттерн-кластеризации, продемонстрируем на порядково-инвариантных паттерн-кластерахиСначала рассмотрим.. Объекты, принадлежащие к данному порядково-инвариантному паттерн-кластеру, имеют схожую структуру показателей: вчисловом выражении преобладает показатель «А», следующим по величинеявляется показатель «С» (отличается от показателя «А» незначительно),наименьшее значение у показателя «В».60При дальнейшем анализе можно отметить, что хотя все объекты порядковоинвариантного паттерн-кластераи обладают схожей внутренней структурой,однако показатели первого и второго объектов существенно ниже аналогичныхпоказателей четвертого и пятого объектов.
В некоторых задачах данный фактможет иметь существенное значение. В связи с этим, выше описан алгоритм,позволяющий выделять группы объектов не только схожих поструктуреисследуемых показателей, но и по близости их значений.Для решения подобной задачи возможно использовать метрическиесоотношения. В работе предложен альтернативный подход: общности структурыобъектов определяются с целью выделения «функционально близких».
В связи сэтим, в работе предлагается использование весьма распространенного втехнических системах понятия «функциональной взаимозаменяемости» [59],определяемой как «связь в определенных пределах между функциональнымипараметрами деталей и узлов (блоков) и их экономическими оптимальнымиэксплуатационными показателями».Применительнокрешаемойврамкахданнойработызадаче,функциональную взаимозаменяемость будем определять как способность двух иболее объектов оставаться в рамках одного кластера при взаимном обменезначениями соответствующих показателей.Продолжим рассмотрение порядково-инвариантного паттерн-кластера.Последовательно обменяем значения показателей A, B и С объектов 4 и 5 (см.Рисунок 14), и рассмотрим, как меняются соответствующие объектам кусочнолинейные функции.
На первом шаге имеемна втором –ии, на третьем –.61,иРисунок 14. Кусочно-линейные функции объектовипри взаимном обмене показателей.На рисунке выше наглядно видно, что, несмотря на взаимный обменсоответствующих показателей объектови, все кусочно-линейные функциипо-прежнему остаются весьма схожими. Доминирующее в количественномзначении положение занимает показатель «А», затем – показатель «С».Наименьшее значение у показателя «В».Проведем аналогичный обмен показателей объектов 1 и 2.
На первом шагеполучаеми, на втором –, на третьем –ии. Кусочно-линейные функции объектов изображены на рисунке 15.Рисунок 15. Кусочно-линейные функции объектовипри взаимном обмене показателей.При взаимном обмене данных показателей по-прежнему наблюдается схожеесоотношение показателей исследуемых объектов: наибольшее значение упоказателя «А», затем следуют показатели «С» и «В».
Таким образом, взаимныйобмен значениями показателей объектови, а такжеобъектовисущественным образом не влияет на характер кусочно-линейных функций.Однако, ситуация кардинальным образом изменится при взаимном обменепоказателей второго (или первого) объекта с показателями пятого (иличетвѐртого) объектов. Для наглядности, изобразим на рисунке 16 подобный обмен62показателей объектовиНа первом шаге получаем, на втором –иии, на третьем –.Рисунок 16. Кусочно-линейные функции объектовипри взаимном обмене показателей.Для первого и четвертого объектов при взаимном обмене соответствующихпоказателей ситуация является аналогичной.Такимобразом,впорядково-инвариантномпаттерн-кластереможно выделить два подкластера:и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
