Диссертация (1137055), страница 7
Текст из файла (страница 7)
Данные для примера, иллюстрирующего работу алгоритмаЛинСтратКритерий 1 Критерий2 Взвешенный критерийСтратаШаг010.83100.23121.82211.22232.81322.211.Произведеминициализациювесовицентров.Допустим,сгенерированные начальные значения равны = (0.2,0.8) . Тогда диапазонсвертки критериев от 0.2 до 0.8. Внутри него генерируем три числа, упорядочиваяих в порядке убывания с1 = 2.4, с2 = 1.9, с3 = 0.3.Шаг 2. Вычисляем свертку критериев с весами. Получаем значения длякаждого объекта соответственно 0.8, 0.2, 1.8, 1.2, 2.8, 2.2. Далее для первогообъекта вычисляем квадрат разности значения свертки и значения центра каждойстраты (с − 1 )2 , = 1, … ,3. Минимальным является квадрат разности длятретьей страты ( с3 − 1 )2 = (0.3 − 0.8)2 = 0.25 , следовательно, назначаемпервый объект на страту с номером 3.
Аналогично производим назначения для41остальных объектов. Получаем, что объекты принадлежат соответственно стратамс номерами 3, 3, 2, 2, 1, 1.Шаг 3. Матрица S будет иметь следующий вид:000=01(1001100110000)Вычислив матрицу ( − ( )−1 ) и обозначив ее получим:−2−1−5=−4−8(−7−1−2−4,−5−7−8)Получается следующая квадратичная программ для весов: → = 1{ ≥ 0Где :159 156 = ()156 159Решение задачи квадратичного программирования дает веса = (0.5,0.5).Шаг 4. Теперь для каждой из страт вычисляем центры как средние значениявзвешенных критериев объектов, принадлежащих заданной страте.
Таким111222образом, с3 = ∙ (0.8 + 0.2) = 0.5, с2 = ∙ (1.8 + 1.2) = 1.5, с1 = ∙ (2.8 + 2.2) =2.5.2.1.3. Свойства алгоритма ЛинСтратАлгоритм ЛинСтрат сходится к локальному оптимуму за конченое числошагов. Как видно из (15) минимизация фактически происходит только по двумпеременным w и S. При фиксированных весах и центрах каждый объект на страту42с ближайшим центром вдоль оси взвешенного критерия. Для фиксированногоразбиения оптимизационная задача (15) имеет глобальное решение относительновесов. Таким образом последовательность значений целевой функции убывает.Поскольку число всевозможных разбиений конечно, рано или поздно мы получимразбиение, которое появлялось ранее, а значит и значение весов.
Следовательно,получим значение целевой функции равное значению на предыдущем шаге иначеполучим противоречие. Доказательства сходимости к локальному минимумуподобных алгоритмов можно найти в [54, 55].Сложность алгоритма в худшем случае равна числу упорядоченныхразбиений S. Однако, на практике, для решения таких задач, обычноограничивают число шагов алгоритма некоторым конечным числом. Рассмотримвычислительную сложность для каждого шага алгоритма отдельно.На шаге 2 для каждого из N объектов производится свертка с весами по Мкритериям и вычисляется наименьшая из K квадратов разностей, значит оценкасложности этого шага в худшем случае O(NMK).На шаге 3 требуется O(NM) операций для вычисления матрицы . Матрица это ничто иное как , каждый элемент, которой приведен к следующему виду:1ℎ = − ∑∈ .Произведение требует (2 ) операции. Обозначим O(f(M)) оценкусложности решения задачи квадратичного программирования (14), где f зависитот выбранного алгоритма оптимизации.На шаге 4 вычисляются средние значения взвешенных критериев внутристрат.
Сложность этого шага O(N).Вопрос об инициализации алгоритмов, строящих разбиения, является однимиз ключевых в кластерном анализе [56]. В зависимости от начальных значенийвесов w и центров c могут получаться различные разбиения. Будемпридерживаться традиционного эвристического подхода – задать начальныепараметры случайно, найти решение для каждой такой инициализации, а затемвыбрать решение, для которого значение целевой функции будет минимально.432.2.
Организация вычислительных экспериментов по сравнению алгоритмовстратификации и ранжирования2.2.1. Методы стратификации, используемые в экспериментахДля верификации предлагаемого алгоритма и его сравнения с другимиметодами стратификации мы решили использовать как искусственные, так иреальные данные.Ниже, в таблице 2.2, приводятся два разработанных нами алгоритмастратификации, а также методы, рассмотренные в главе 1 и отобранные дляэкспериментального сравнения.Таблица 2.2.
Список методов стратификации и их обозначений, используемых вэтой главеМетод стратификацииАббревиатура Раздел диссертацииМетод линейной стратификации ЛинСтратсиспользованиемквадратичногоLSQ2.1.2программированияМетод линейной стратификации ЛинСтратLS2.1.1на основе эволюционной минимизацииСтратификация с помощью правила БордаBC1.1.3(Borda count)Метод ABC- классификации на основелинейной оптимизации весов (LinearLWO1.1.6weights optimization)Ранжирование по влиянию (AuthorityAR1.1.1ranking)Стратификация объединением границPS1.1.2Парето (Paretostrat)Все методы были имплементированы в среде Matlab. Более подробновопросы программной реализации будут рассматриваться в главе 4.
Для BC,LWO,ARпослеполученияодномерногоранжированиястратификацияпроизводилась по численным значениям агрегированного критерия применением44к его значениям алгоритма к-средних. Аналогично получаем стратификацию поотдельно взятому критерию. Случайная инициализация для LS, LSQ а также ксредних для BC, LWO, AR выполнялась 100 раз, после чего выдавался результат,дающий наименьшее значение целевой функции.2.2.2. Генерация синтетических данныхДля конструирования генератора синтетических данных мы используемподходы,аналогичныетем,которыеразработаныдлясравнительныхисследований алгоритмов кластер-анализа.
Традиционно, в кластер анализеиспользуютсяразличныеалгоритмыгенерациисинтетическихданных,позволяющие контролировать геометрические свойства кластеров и шума, ипроводить всестороннюю экспериментальную оценку алгоритмов. Обычно втаких экспериментах оценивается, насколько хорошо те или иные алгоритмымогут восстановить принадлежность объектов заданным кластерам в зависимостиот геометрических свойств данных.
Применим такой же подход для оценкиалгоритмов стратификации и ранжирования. Несмотря на обилие генераторовкластерных структур для верификации и сравнения алгоритмов кластер-анализа[55, 56, 57], почему-то до сих пор в литературе отсутствуют подобные генераторыструктур ранжирования. Возможно, это связано со слабой разработанностьюпроблематикимеханизмавтоматизациипорождениястратификации.синтетическихданныхТаким образом,длязадачимодельныйранжированияиспользуется впервые. Нами разработан алгоритм генерации искусственныхстратифицированныхданных,позволяющийвсестороннеконтролироватьконфигурацию страт. Наша схема генерации страт позволяет гибко моделироватьихпараметрыишумовыеэффекты:ориентацию,толщину,размахиинтенсивность (определение этих понятий будет дано ниже).Для того чтобы обеспечить возможность проведения контролируемыхэкспериментов по сравнению алгоритмов, предлагается алгоритм генерациистратифицированных данных, позволяющий разносторонне контролировать45геометрическую конфигурацию страт.
Алгоритм генерирует страты в видепараллельных гиперплоскостей. Более точно, геометрия стратифицированныхданных определяется различными параметрами, к которым относятся: весовыекоэффициенты w, уровни страт c, интенсивности страт θ, размах страт φ итолщина страт σ. Дадим описание этих понятий.Весаwзадаюториентациюстрат.Нарисунке2.1(a,б,в)проиллюстрированы три варианта весовых коэффициентов: w=(0.5, 0.5), w=(0.4,0.6) и w=(0.2, 0.8).
Толщина σ задает диапазон возможных отклонений объектовперпендикулярно плоскости их страт. Далее, на рисунке 2.1 (г, д, е) показаныстраты при увеличении их толщины для значений σ={0.03, 0.05, 0.10}. Принебольших значениях σ все объекты находятся в плоскости своей страты, сувеличением начинают отклоняться, утолщая страту, и в конечно итоге стратыначинают перекрываться. Параметр интенсивность θ=(θ1, θ2,…, θK) задаетотносительную численность объектов в каждой страте. Иными словами θkпоказывает вероятность того, что наугад взятый объект окажется из страты сномером k.
На рисунке 2.1(ж, з, и) продемонстрированы три различных вариантаинтенсивностей: θ =(0.2, 0.3, 0.5), θ=(0.1, 0.2, 0.7) и θ=(0.05, 0.15, 0.8). Сначала, кавидно на рисунке 2.1(ж), диспропорция в численности объектов не столь заметна,но на рисунке 2.1(и) и уже видно, что объектов в первой страте стало заметноменьше, в то время как большая часть объектов сосредоточилась во второй итретьей стратах. Последний параметр – размах страты φ, то есть разброс объектовв плоскости своей страты.
По умолчанию мы будем генерировать объекты,расположенные равномерно в плоскости страты. Также интересен случай, когдаобъекты сосредоточены в некоторой ограниченной области в плоскости страты.Как будет показано далее, этот параметр существенно влияет на качество работынекоторых алгоритмов. На рисунке 2.1(к, л, м) можно видеть, как меняется формастраты при увеличении размаха φ={0.3, 0.2, 0.1}.46Рисунок 2.1. Линейные страты для различных комбинаций параметров генерациив двумерном случае M=2.
(1) страты в зависимости от ориентации w (a) w = (0.5,0.5), (б) w = (0.8, 0.2), (в) w = (0.2 ,0.8); (2) страты в зависимости от толщины (г)σ=0.05,(д), σ=0.1 (е), σ=0.2; (3) страты в зависимости от интенсивности (ж)θ=(0.5, 0.3, 0.2) (з) θ=(0.7, 0.2, 0.1) (и) θ=(0.8, 0.15, 0.05); (4) страты в зависимостиот размаха (к) φ=0.05,(л) φ=0. 1,(м) φ=0.5В диссертационной работе экспериментально изучается влияние описанныхвышепараметровиихразличныхкомбинацийнакачествоработырассматриваемых методов многокритериальной стратификации (см. таблицу 2.2).47Все синтетические данные, на которых проводятся эксперименты, получены спомощью следующего алгоритма:На входе:- Число объектов N, размерность пространства критериев M и число страт K;- Уровни страт c;- Весовые коэффициенты (ориентация страт) w;- Толщина страт σ;- Интенсивности страт θ;- Размах страт φ.На выходе:- Значения критериев для каждого объекта;- Индексы страт для каждого объекта.Алгоритм генерации линейных страт:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
