Диссертация (1137117), страница 7
Текст из файла (страница 7)
Несмотря на простоту реализации предложенного метода,результаты получаются относительно «грубыми», в связи с чем предполагаетсяего развитие в подразделах 2.3 и 2.4. Порядково-фиксированную паттернкластеризацию можно использовать для получения предварительных результатов,а также на данных, не требующих большой точности.2.3 Порядково-инвариантная паттерн-кластеризацияВ данном подразделе предлагается к рассмотрению второй оригинальныйметоданализапаттернов,накоторомбазируетсяординальнаяпарно-сопоставительная модель.
Данный метод также основан на парном сравненииисследуемых показателей. Как было показано выше, метод анализа паттерновявляется эффективным инструментарием анализа информации. Вместе с тем, рядисследований указывают на необходимость «крайне осторожного выборапоследовательности анализируемых показателей» при его использовании,поскольку она влияет на форму образуемых паттернов [31]. Потому, актуальнойявляется задача развития данного метода с целью устранения указаннойособенности. В работе предложена модификация метода анализа паттернов,позволяющая формировать паттерны объектов вне зависимости от порядкаанализируемых показателей.
Модификация получила название «порядковоинвариантной паттерн-кластеризации». Разработан алгоритм ее компьютернойреализации, проведена апробация метода с использованием известных наборовданных. Подробное описание предложенного метода приведено в [11].Опишем основную идею, на которой базируется предложенный метод. Дляэтого рассмотрим множество из 3 объектов, исследуемое по 3 показателям,значения которых приведены в таблице 5. Данные значения, как и в примере сданными таблицы 3, не требуют нормировки, т.к. их сравнение и визуализация непредставляет собой особых трудностей.47Таблица 5.
Гипотетический пример.АBCОбъект 1703070Объект 2702090Объект 3704050Используя значения приведѐнной выше таблицы, построим кусочнолинейые функции (см. Рисунок 5).10090807060Объект 150Объект 240Объект 33020100АBCРисунок 5. Кусочно-линейные функции объектов.На рисунке 5 наглядно видно, что объекты 1-3 имеют схожие внутренниеструктуры (согласно рассматриваемым показателям).
Используем порядковофиксированную паттерн-кластеризацию для объединения объектов в единыйкластер:Объект 1:;Объект 2:;Объект 3:.∑∑∑48Таким образом, объекты 1-3 образуют единый порядково-фиксированныйпаттерн-кластер.Далее, проверим возможность соотнесения объектов 1-3 в единый кластерпри рассмотрении других возможных последовательностей показателей A,B,C (нарисунке 6 приведены последовательности A,C,B и B,C,A).Рисунок 6.
Построение кусочно-линейных функций объектов 1-3 при различныхпоследовательностей исследуемых объектов.На рисунке 6 наглядно видно, что, в общем случае, кусочно-линейныефункции теряют схожесть при изменении последовательности исследуемыхпоказателей.Прииспользованиипорядково-фиксированнойпаттерн-кластеризации, получим аналогичный вывод.Порядково-инвариантнаяпаттерн-кластеризациибазируетсянаидеиобъединения объектов, не меняющих свою принадлежность к определѐнномукластеру при изменении последовательности исследуемых показателей.
Следуетотметить, что существование подобных кластеров не является очевидным.Подобную возможность продемонстрируем на примере данных таблицы 1.49Рисунок 7. Кусочно-линейные функции последовательностей «депозиты, кредиты, валютныеоперации» и «валютные операции, кредиты, депозиты».Рисунок 8. Кусочно-линейные функции последовательностей «кредиты, депозиты, валютныеоперации» и «валютные операции, депозиты, кредиты».Рисунок 9. Кусочно-линейные функции последовательностей «валютные операции, депозиты,кредиты» и «кредиты, депозиты, валютные операции».На рисунках 7-9 видно, что, несмотря на различные последовательностианализируемых показателей, банки 1 и 2 показывают схожие внутренние50структуры, тогда как структура банка 3 – отличается.
Далее, опишем процедурукластеризации, не зависящую от перестановок показателей.Определение 2. Кластеризацию, результат которой не зависит отпоследовательностипоказателейисследуемыхобъектов,будемназывать«порядково-инвариантной паттерн-кластеризацией», а кластеры, полученные врезультаты ее применения, соответственно,порядко-инвариантными паттерн-кластерами.Для использования всех возможных перестановок потребуется исследоватьm! перестановок, что потребует значительных временных затрат. Поэтомупредлагается альтернативный метод.Для начала, проводится порядково-фиксированная паттерн-кластеризация,разделяющая множество X напорядково-фиксированных паттерн-кластеров.Это позволяет уменьшить необходимое в дальнейшем количество операций.Далее,каждомуобъектуставимсоответствие полный взвешенный орграфзначениям показателейвовзаимнооднозначное, вершины которого соответствуют, а вес рѐберопределяетсясоотношениями соответствующих вершин.
Количество необходимых парныхсравненийпоказателейопределяетсяобщимколичестворѐберсоответствующего графа (учитывая что 2 показателя соединяются единственнымребром) по формулеВеса рѐбер определяются как51Такимобразом,аналогично(4),формируем∑∑новыйдесятичныйпозиционный кодАналогично (5), рассматриваем расстояние Хемминга dH между объектами,которые ранее были объединены в один порядково-фиксированный паттернкластер. Возможны 2 случая:объединяем соответствующие объекты в один порядково-1.инвариантный паттерн-кластер;относим соответствующие объекты в разные порядково-2.инвариантные паттерн-кластеры.Опишем некоторые свойства порядково-инвариантных паттерн-кластеров.Утверждение 1.
(Cвойство 1) Порядково-инвариантные паттерн-кластерыне пересекаются.Инымисловами,одинобъект,описанныйвектором, не может принадлежать двум различным порядковоинвариантным паттерн-кластерам.Доказательство. Пусть имеется два различных порядково-инвариантныхпаттерн-кластераи), содержащие совокупность a и b(объектов, соответственно. Запишем утверждение о не пересечении порядковоинвариантных паттерн-кластерови:Доказательство проведем от противного.
Предположим, что эти кластерыпересекаются, т.е.Обозначим.. Согласно предположению,Выберем объектмножеств (паттерн-кластеров). Посколькуи.образовано пересечением, можно сделать вывод, что:52{.С другой стороны, согласно условию, паттерн-кластерыиразличны. Это означает, что существует такая последовательность показателей P,при котором кусочно-линейные функции паттерн-кластеровинесовпадают (графически, это выражается в их различном кусочно-линейномпредставлениидляданнойпоследовательности).Обозначимданнуюкусочно-линейныефункциипоследовательность через ̃ .Всилуинвариантностии,произвольного объекта каждого паттерн-кластера должны совпадать с кусочнолинейными функциями других объектов кластера для любой последовательностианализируемых показателей Р, в том числе и для последовательности ̃ .
Такимобразом, введенное предположениепривело к противоречию,выражающемуся в том, что произвольная последовательность ̃ кусочнолинейной функции объектадолжна одновременно совпадать с двумяразличными кусочно-линейными функциями кластерови(которые иобусловили различие кластеров). В силу этого, данное предположениенеобходимо отвергнуть, что и приводит к:.Утверждение 1 доказано.Замечание.Утверждениепорядково-инвариантной1фактическипаттерн-кластеризации,определяетапотомуоднозначностьимеетважноеприложение как для построения алгоритма ее реализации, так и длядоказательства других свойств.В качестве иллюстрации приведем следующий пример.
Пусть имеетсянесколько различных порядково-инвариантных паттерн-кластеров. Перемешаемобъекты этих паттерн-кластеров, поместив их в одно множество. Выберемпроизвольный порядок рассматриваемых показателей объекта и воспользуемсяпорядково-инвариантной паттерн-кластеризацией. Тогда все объекты вновь53окажутсяраспределеннымипосвоимпорядково-инвариантнымпаттерн-кластерам.Теорема 1. (Свойство 2) Если существует такая последовательность Ррасположения показателей А, В, С, …, L, при котором их значения для всехобъектовобразуютстрогомонотоннуювозрастающую(убывающую)последовательность, то эти объекты образуют порядково-инвариантный паттернкластер.Доказательство. Доказательство проведем для случая возрастающейпоследовательности (поскольку эта же последовательность, рассматриваемая вобратном порядке, образует убывающую последовательность).Воспользуемсяметодомматематическойиндукции:докажемсправедливость свойства для случая двух и трех объектов, расширив затем дляслучая произвольного числа объектов.1.
Пусть имеются два объекта:,,содержащие возрастающую последовательность значений показателей А, В, С, …,L. Воспользуемся представлением объектов в виде направленного графа, гдевершины графа характеризуют значения показателей А, В, С, …, L, а ребра –отношения между соседними значениями (см. Рисунок 10).Рисунок 10. Представление объектов54ив форме графов.Покажем, что условие возрастания значений показателей полностьюопределяет также и ребра полного взвешенного орграфа, характеризующиеотношения между значениями узлов, которые они соединяют (см. Рисунок 11).При этом характер этого отношения будет одинаков для объектовРисунок 11.
Представление объектовии.в форме полных взвешенных орграфовДействительно, из условия:следует, что длялюбых значений k и m, выполняются неравенства:припри;и.Аналогичный вывод можно сделать и для строки е2: из условияследует, чтоприпри;и.Таким образом, значения соответственных ребер полных взвешенныхорграфов(определяющиххарактеротношениймеждуисследуемымипоказателями) одинаков для обоих объектов.
Следовательно, объектыпринадлежат одному порядково-инвариантному паттерн-кластеру.2. Покажем справедливость свойства для случая трех объектов:,,.55иДействительно, анализируя объектыи, можно сделать вывод, что онипринадлежат одному порядково-инвариантному паттерн-кластеру (см. выше).Аналогичный вывод можно сделать и для других двух объектови: онипринадлежат одному (предположим – другому) порядково-инвариантномупаттерн-кластеру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
