Диссертация (1137117), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Объектыкаждого из подкластеров обладают не только схожей структурой показателей, нои весьма близкими количественными значениями, поскольку взаимный обменсоответствующих показателей не приводит к существенному изменению кусочнолинейных функций. Данные подкластеры предлагается называть «диффузионноинвариантными паттерн-кластерами», а общее их количество обозначать. Нарисунке 17 изображено разбиение порядково-инвариантного паттерн-кластерана 2 диффузионно-инвариантных паттерн-кластера:Рисунок 17. Слева направо:,ии..Далее, рассмотрим порядково-инвариантный паттерн-кластерНа шаге 1 получими63={ ,; на шаге 2 –}.и; на шаге 3 –и.Кусочно-линейные функции изображены на рисунке 18.Рисунок 18. Кусочно-линейные функции объектовипри взаимном обмене показателей.Исходя из формы кусочно-линейных функций, изображенных на рисунке18, объектыине теряют своей схожести при взаимном обмене показателей.При использовании порядково-инвариантной паттерн-кластеризации на каждомописанном выше шаге исследуемые объекты остаются в едином кластере.

Такимобразом, данные объекты образуют диффузионно-инвариантный паттерн-кластер.Рассмотрим следующую теорему [10].Теорема 3. Пусть два объекта x1  x11, x12 , , x1m  и x2  x21, x22 , , x2m принадлежат одному кластеру v, построенному с использованием евклидоварасстояния – d e xi , z   RV между объектами и центром кластера z  z1 , z2 , , zm  ,где RV– радиус кластера. Образуем новые объекты x1* и x2* , обменявсоответствующие значения одной из координат исходных объектов x1 и x2 . Тогда1) Евклидовы расстояния между исходными объектами de x1 , x2  и между вновьобразованными объектами de x1* , x2*  равны, т.е.

de x1 , x2   de x1* , x2* .2) По меньшей мере один из вновь образованных объектов принадлежитданному кластеру v.Доказательство.Евклидово расстояние1.Приведемдоказательствомежду объектамиd e x1 , x2 ипервогоравноmx11  x21 2   x1i  x2i 2i 264.утверждения.Евклидово расстояние между объектамииравно:mx21  x11 2   x1i  x2i 2d e x1* , x2* i 2.Таким образом, получаем de x1 , x2   de x1* , x2* .2. Далее, докажем второе утверждение. Поскольку объектыпринадлежать одному кластеру, тоm xd e x1 , z i 1m xd e x2 , z i 1 zi   RV ,21i zi   RV ,22iгде RV – радиус кластера v .Таким образом,md e2 x1 , z   x1i  zi   RV2 ,2i 1d e2 x2 , z    x2i  zi   RV2 .m2i 1Евклидово расстояние между объектоми центром кластера равно:mx21  z1 2   x1i  zi 2d e x1* , z i 2.Аналогично, xd e x2* , z m11  z1     x 2 i  z i 22i 2.Таким образом,md e2 x1* , z  x21  z1    x1i  zi  ,22i 2md e2 x2* , z  x11  z1    x2i  zi  .22i2m m22222d e2 x1* , z  x21  z1    x1i  zi   x21  z1     x1i  zi   x11  z1   i 2 i1 m22222 d e2 x1* , z  x21  z1     x1i  zi   x11  z1    x21  z1   RV2  x11  z1  i165иПолучаем22d e2 x1* , z  x21  z1   RV2  x11  z1 2.Аналогично, дляd e2 x2* , z  x11  z1   RV2  x21  z1 2.При сложении правых и левых частей неравенств, получимde2 x1* , z  de2 x2* , zИзслагаемых меньшеи 2RV2 .следует, что либо по крайней мере одно из,de2 x1* , z RV2 de x1* , z RV x1*  v RV2 de x2* , z RV x2*  vилиde2 x2* , zлибо оба неравенства верны (в таком случаеВычислительнаясложность.

Теорема 3 доказана.диффузионно-инвариантнойпаттерн-кластеризации оценивается следующим образом:2.5 Применение новых методов анализа паттернов на классическихтестовых данных «Anderson-Fisher Iris Data»Поскольку в работе предложены новые методы анализа паттернов,предлагается использовать некоторые классические тестовые данные дляопределения их эффективности.Результаты применения новых методов анализа паттернов к набору данных«Ирисы Андерсона - Фишера» [32] опубликованы [42]. Приведем описаниеполученных результатов.Поскольку данный набор тестовых данных широко используется припроверке эффективности различных методов кластеризации, его применениевозможно не только для проверки новых, разрабатываемых методов, но и для66сопоставления вновь полученных результатов с работой иных, известныхалгоритмов. В частности, в работе [2] демонстрируются различные возможностиметода анализа паттернов, в том числе, и для тестовых данных «Anderson-FisherIris Data».Исследуем эффективность порядково-инвариантной паттерн-кластеризациина указанном наборе данных.

Исследуется множество. При этом,заранее известно, что исходное множество объектов можно разделить на 3подмножества:- Iris Setosa (Ирис щетинистый);- Iris Versicolor (Ирис разноцветный);- Iris Virginica (Касатик виргинский),каждое из которых содержит по 50 объектов.

При этом, каждому объектупоставлено во взаимно однозначное соответствие вектора-, гдехарактеризует длину чашелистика исследуемого объекта (sepal length);-характеризует ширину чашелистика исследуемого объекта (sepal width);-характеризует длину лепестка исследуемого объекта (petal length);-характеризует ширину лепестка исследуемого объекта (petal width).Постановка задачи: используя данные измерений приведенных ирисов,разбить множествона 3 непересекающиеся подмножества, каждое из которыхбудет содержать цветы только одного вида.Поставленную задачу будем решать в 2 этапа.Этап I.

Непосредственное применение порядково-инвариантной паттернкластеризации к исследуемому набору тестовых данных.Припорядково-инвариантнойпаттерн-кластеризацияполучим два порядково-инвариантных паттерн-кластера:= {Iris Setosa} (всего50 цветов) ииспользовании= {Iris Versicolor и Iris Virginica} (100 цветов).Подобный результат не является чем-то новым и характерен для многихизвестных методов. К примеру, одним из возможных способов выделения IrisSetosa является пороговое значение длины лепестка (24,5мм). В связи с этим,67результаты этапа I показывают, что полученное при помощи порядковоинвариантной паттерн-кластеризации разбиение является не хуже других.

Попрежнему остается вопрос о разбиении 2-ого порядково-инвариантного паттернкластера.Весьма важным является информационное содержаниеи. Прииспользовании порогового значения 24,5 мм возможно получения 2 подмножествобъектов: к первому относятся цветы с длинной лепестка меньше 24,5 мм, ковторому – больше.

Несмотря на тот факт, что количество подмножеств в данномслучае также будет равно 2, дополнительного информационного содержания мыне получим. Если мы добавим к исходному множеству объектов дополнительныеобъекты, к примеру, розы, то в результате использования приведенного вышепорога (24,5 мм) по-прежнему получим разделение на 2 подмножества.С другой стороны, при использовании порядково-инвариантной паттернкластеризации мы получаем дополнительную информацию об отличительныхформах цветков {Setosa} и {Versicolor + Virginica}, что определяется различнымисоотношениями ширины чашелистика и длины лепестка.

Наглядно, данноесоотношение продемонстрируем на рисунке 19.Также можно заметить, что, в общем случае, значения ширины чашелистикау всех исследуемых цветков весьма схожи, а значения длины чашелистикаотносительно сильно превоходит значения ширины лепестка.Рисунок 19. Кусочно-линейные функции {Setosa} и {Versicolor + Virginica}.Отличия кусочно-линейных функций, приведенных на рисунке выше,наиболее ярко видны для соотношения показателей68и. Для {Setosa} кусочно-линейная функция на данном отрезке убывает, а для {Versicolor + Virginica} –возрастает, т.е.образом,для {Setosa} иосновываясьнадля {Versicolor + Virginica}.

Такимпорядково-инвариантнойпаттерн-кластеризации,выявлен весьма наглядный критерий, который позволяет разбить исходноемножество объектов на непересекающиеся подмножества. Критерий опирается насоотношения размеров лепестков, составляющих форму цветка.Этап II. Применение порядково-инвариантной паттерн-кластеризации длязначений разностей.При решении поставленной задачи возникают определѐнные трудности,связанные с весьма схожими, в некоторых случаях, структурами показателей IrisVersicolor и Iris Virginica.

Поскольку метод анализа паттернов предполагаетобъединение схожих показателей, получение 100-процентного результата наклассических тестовых данных представляет собой очень трудную задачу.Продемонстрируем наглядно на данных таблицы 7.Таблица 7. Iris Versicolor и Iris VirginicaВидИрисаДлинаШиринаДлинаШириначашелистика чашелистика лепестка лепесткаVersicolor62,75,11,6Virginica62,251,5По данным таблицы 7 построим кусочно-линейные функции (см. рисунокниже).7654Versicolor3Virginica2101234Рисунок 20. Кусочно-линейные функции цветков Iris Versicolor и Iris Virginica.

Характеристики

Список файлов диссертации