Диссертация (1137055), страница 6
Текст из файла (страница 6)
Случай (а) отличается от случая (б) тем, что в выборке (б)отсутствует объект I. Речь идет о случае, когда добавление или удаление данныхприводит к изменению направления главной компоненты, но направления стратпри этом остаются неизменными. Таким образом метод линейной стратификации33демонстрирует устойчивость рангов, а метод главных компонент, при переходе от(а) к (б), меняет ранжирование. В обоих случаях линейная стратификацияприводит к весам = (0.5, 0.5) и страты, а соответственно и ранги объектовостаются неизменными. При определении весов по методу главных компонент вслучае (а) получаем веса (веса нормированы таким образом, чтобы в сумме даватьединицу) = (0.5, 0.5), в случае (б) = (0.26, 0.74), при этом объекты D и Нзначительно меняют ранги.
Так происходит, поскольку при изъятии одногообъекта меняется направление, в проекции на которое выборочная дисперсиямаксимальна.3.53.5332.52.5221.51.5110.50.500-0.5-0.500.511.522.533.5-0.5-0.500.511.522.533.5Рисунок 1.4. Пример различных решений по методу главных компонент илинейной стратификации. В обоих случаях линейная стратификация приводит кодинаковым весам = (.
, . ), а по методу главных компонент в случае (а)веса = (. , . ), в случае (б) = (. , . )34Таблица 1.5. Множество объектов для примера сравнения ЛинСтрат и МГКОбъектК1К2Ранг ЛинСтрат(а,б) Ранг МГК(а)Ранг МГК(б)A100.710.710.26B0.50.50.710.710.50C010.710.710.74D201.411.410.51E111.411.411.00F021.411.411.49G302.122.122.23H1.51.52.122.121.50I032.122.12-Выводы по главе 1Впервойглавеописаныосновныеподходыкавтоматизациимногокритериальной стратификации.
Рассмотренные подходы условно поделенына три группы исходя из лежащих в их основе методов ранжирования: на основелинейнойсверткойкритериев,использующиеотношениемногомерногоупорядочения и все остальные, использующие нелинейную комбинациюкритериев. Предложена модель линейных страт и метод стратификации,относящийся к первой группе и основанный на оптимизации параметров моделилинейных страт. Рассмотрены некоторые вырожденные случаи применениямодели линейной стратификации. Проанализированы сходства и различия методалинейной стратификации и метода главных компонент.35Глава 2. Разработка и экспериментальная верификация алгоритмовлинейной стратификацииВ этой главе предлагается алгоритм оптимизации целевой функциимногокритериальной линейной стратификации на основе решения задачиквадратичного программирования (10), сформулированной в главе 1. Дляпроведениявычислительныхэкспериментовповерификацииалгоритмаразработана схема генерации искусственных стратифицированных данных.Предлагаемый нами алгоритм ЛинCтрат экспериментально сравнивается ссуществующими методами стратификации на сгенерированных данных приразличных сочетаниях параметров.
При этом ЛинCтрат оказался лучше всех сточкизренияблизостирешенияктому,котороеподразумеваетсявсгенерированных данных, за исключением случаев, когда данные подверглисьоченьвысокомууровнюзашумления.Такжевэтойглавепроведеныэксперименты и на реальных данных, относящихся к библиометрическимпоказателям.
Мы рассматриваем два вида таких данных – когда единицаминаблюдения выступают научные журналы в области искусственного интеллекта иотдельные страны (по публикационной активности). На этих данных алгоритмЛинCтрат приводит к хорошо интерпретируемым и адекватным результатам. Приэтом алгоритм строит упорядоченное разбиение, наиболее согласованное сразбиениями, построенными по отдельно взятым критериям.2.1. Разработка алгоритмов решения задачи линейной стратификацииВ первой главе была сформулирована задача построения линейнойстратификации,аппроксимирующейданныеобъектызначениями критериев , = 1, … , и j = 1, … , M:охарактеризованные362∑ ∑ (∑ − ) →=1 –веса=1(13)∑ = 1, ≥ 0{где,,=1критериев,ci ∈ {с1 , с2 , … , сK }–центрыстрат,−разбиение на К непересекающихся подмножетсв {1 , 2 , … , }.К сожалению, решение задачи (13) получить в замкнутой форме не удается,поскольку оптимизация производится по дискретному множеству страт.
Крометого, в задаче фигурируют ограничения в виде неравенств. Эта задача напоминаетзадачу к-средних, только разбиение производится по агрегированному критерию.Поэтомупредлагаетсяискатьрешениезадачиметодомчередующейсяминимизации, имея в виду, что критерий в (13) зависит от трех групппеременных: веса критериев , страты , и их центры сk . Согласно этомуметоду, вычисления проводятся итерациями, каждая из которых включаетпоследовательную минимизацию (13) по весам, стратам и центрам в отдельности.На таком принципе основаны оба предложенных алгоритма. Различаются онитолько лишь способом определения оптимальных весов – в одном случаем весаищутся на основе популярного подхода, моделирующего эволюцию сообществадопустимых решений, а в другом с помощью «честного» решения возникающейзадачи квадратичного программирования.2.1.1.
Решение задачи линейной стратификации на основе эволюционногоподходаПервоначально мы решали сформулированную задачу, используя подходэволюционной минимизации. По сутиречь идет ослучайном поискеоптимального решения относительно весов w [47, 48]. На каждой итерации для37фиксированных значений w применяется одномерная процедура к-средних длянахождения оптимального разбиения и уровней страт. Ниже алгоритм описанболее подробно.Эволюционный алгоритм:На входе: объекты = (1 , 2 , … , )На выходе: страты S, уровни страт c и веса w.1.Сгенерировать популяцию векторов весовых коэффициентов такую, что веса удовлетворяют ограничениям ∑=1 = 1, ≥ 0, = 1, … , .2.уровниДля каждого члена популяции найти оптимальное разбиение S иc применением одномернойпроцедурык-средних кзначениямагрегированного критерия на объектах = ∑=1 , = 1 … .3.Найти «наилучший» элемент популяции, доставляющий минимумцелевой функции (12), и заменить им наихудший из элементов популяции.4.Сдвинуть популяцию весов случайным образом: = + , где =1 … , ~(0, ), – параметр алгоритма.5.Привести веса в соответствие с ограничениями неотрицательности исуммирования к единице следующим образом.
Веса, значения которыхполучились отрицательными, заменить нулевыми и нормировать каждыйполученный набор из популяции весов на его сумму.6.Перейти к пункту 1 и повторить заданное число итераций.Описанный выше алгоритм требует задания трех параметров: численностьпопуляции L, число итераций T и параметр α. Во всех экспериментах, которыепроводились с данным алгоритмом, использовались следующие значенияпараметров: L=300, T=100 и α=0.01.Этот алгоритм имеет ряд недостатков, присущих методам случайногопоиска. Так, например, как будет показано в экспериментах на синтетическихданных, этот подход плохо работает при увеличении размерности данных,поскольку случайный поиск при высокой размерности не эффективен. Более того,38этот алгоритм в наших экспериментах далеко не всегда работал лучше другихрассматриваемых алгоритмов.2.1.2. Решение задачи линейной стратификации на основе квадратичнойоптимизации: алгоритм ЛинСтратПредлагаемый алгоритм ЛинСтрат решает задачу (13), используя подходчередующейся минимизации, который основан на поиске оптимального решенияпо одной группе переменных при фиксированных других [49, 50].
Тот жепринцип заложен в алгоритм кластеризации к-средних [51, 52]. Решение задачи(12) ищется чередованием двух последовательных шагов:1) При фиксированном разбиении найти оптимальные веса и центры.2) При фиксированных весах и центрах найти оптимальное разбиение.Введем обозначение для матрицы разбиения , элементы которой =1, при ∈ , причем = 0, ≠ . Перепишем теперь (13) в матричном виде:‖ − ‖2 → { = 1 ≥ 0(14)Решая оптимизационную задачу относительно переменной , получаем =( )−1 .
Далее подставим значение в выражение − . Получим: − ( )−1 = ( − ( )−1 ). Перепишем задачу (14):‖( − ( )−1 )‖2 → { = 1 ≥ 0(15)Задача (15) является задачей выпуклой оптимизации относительно прификсированном разбиении. Для решения задачи (15) можно воспользоватьсяодним из известных алгоритмов квадратичного программирования, например,39методом активного множества (active-set algorithm) [53], реализованным в пакетеMatlab. Метод активного множества – это итеративная процедура, включающаядва чередующихся шага.
Из текущего решения определяются активныеограничения-неравенства, т.е. те, которые обращаются в равенства. Остальныеограничения опускаются. Затем решается полученная оптимизационная задача сограничениями-равенствами.Наконец,решениенаследующейитерациизаписывается как, удовлетворяющая исходным ограничениям комбинациярешения предыдущей итерации и полученного решения задачи с ограничениямиравенствами.Сформулируем теперь алгоритм линейной стратификаци ЛинСтрат.На входе:- Объекты , = 1 … ;- Число страт ;На выходе:- Веса ;- Центры страт ;- Разбиение .Алгоритм:1. Инициализировать веса w и центры страт .
Cгенерировать веса w случайнотакие, что ≥ 0, = 1 … и ∑=1 = 1 . Вычислить свертку критериев свесами. Центры страт сгенерировать случайно равномерно из диапазона отминимального значения свертки критериев до максимального.2. По заданным весам и центрам найти оптимальное разбиение:2 ∈ , где = (∑ − ) , = 1 … , = 1. . =13. При заданном разбиении решить оптимизационную задачу относительновесов :40‖( − ( )−1 )‖2 → { = 1 ≥ 04. Вычислить центры страт = ( )−1 .5. Сравнить новое значение целевой функции со значением полученным напредыдущем шаге. Завершить, когда значение перестанет меняться.Продемонстрируем работу алгоритма по шагам на простом примере.Рассмотрим шесть объектов записанных в таблице 2.1.Таблица 2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
