2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 7

< d i 2 < d i1 < ati < d i1 < d i 2 < ... < d iv = ∞ .Для простоты записи, мы рассмотрим случай, когда значения u и v равны длявсех признаков i , а также будем считать, что первые по порядку объектыобучающейвыборкиипринадлежатрассматриваемомуклассуK λ = {S1 , S 2 ,...S mλ } . B11B12 B12 B 22 ...B1n B 2n  ,Построим числовую матрицу M =  1 2 1 21 2CCCC...CCn n  m× N 1 1 2 2N = n × (u + v) ,j = 1,2,..., u ,B i2 = (bij2 q ) m ×v , q = 1,2,..., mλ , i = 1,2,..., n , j = 1,2,..., v ,C1i = (cij1q ) ( m−m )×u , q = 1,2,..., m − mλ , i = 1,2,..., n , j = 1,2,..., u ,Ci2 = (cij2 q ) ( m−m )×v , q = 1,2,..., m − mλ , i = 1,2,..., n , j = 1,2,..., v , whereB1i = (bij1q ) mλ ×u , q = 1,2,..., mλ , i = 1,2,..., n ,λλλ1, xi ( S q ) ≤ d ij2 ,1, xi ( S q ) ≥ d ij1 ,2qb =bij = 0,иначе,иначе,0,1, xi ( S mλ + q ) < d ij1 ,1, xi ( S mλ + q ) > d ij2 ,1q2qcij = cij = иначе.иначе,0,0,1qij(2)(3)Как следует из (2), (3), выполняются следующие ограничения дляэлементов M :bij1q ≤ bi1,qj +1 , bij2 q ≤ bi2, qj+1 ,(4)cij1q ≥ ci1,qj +1 , cij2 q ≥ ci2, qj+1 .(5)Таким образом, матрица M имеет структуру, как показано в Таблице 1.Таблица 1.Иллюстрацияструктурыкоэффициентовi=1i=2i=3 матрицы …i=nПроблемы0000011 1111111 0111111 11111111111111Z0000001 … 0000001 11111110011111 1111111 1111111 0001111 0000001 1111111…0011111 11111111111111 0001111 0000001 1111111 0001111 1111111…1111111 00001111111111 0000011 1111111 0000011 0011111 1111111…1111111 0011111.........1110000 0000000 0000000 1111100 1100000 0000000 … 0000000 10000001000000 0000000 1110000 0000000 1110000 0000000 … 1000000 00000001111000 0000000 1000000 0000000 1111000 0000000 … 1100000 00000000000000 1100000 0000000 1100000 0000000 1100000 … 0000000 111100039.........Di1 , Di2находится во взаимнооднозначном соответствии с множеством векторов {< xij1 , xij2 > },Множество всех предикатов (1) с возможными границами< xij1 , xij2 > =1122< x11, x12,..., x11u , x112 , x122 ,..., x12v , x121 , x122 ,..., x12u , x21, x22,..., x22v ,..., x1n1 , x1n 2 ,..., x1nu , xn21 , xn22 ,..., xnv2 >при ограничениях x , x ∈ {0,1},1ij2iju∑xj =11ijv= 1,∑ xij2 = 1, i=1,2,…,n.j =1В виду данного соответствия, мы будем использовать также запись< xij1 , xij2 > ) для стандартного критерия оптимальности.Единицы в12{ < xij , xij > }ϕ(соответствуют выбору значений параметровc1j , c 2j , j = 1,2,..., n .Для выполнения условия 2) должны выполняться неравенства (6).nuvf (< x , x >) = ∑ (∑ c x + ∑ cij2 q xij2 ) ≥ 1, q = 1,2,..., m − mλcq1ij2iji =1j =11q 1ij ij(6)j =1Наконец, стандартный критерий оптимальности предиката ϕ( < xij , xij > )равен числу выполненных равенств в системе (7) (при соответствующих1значениях параметровnui =1j =1c1j , c 2j , j = 1,2,..., n ).vf (< x , x >) = ∑ (∑ (b − 1) x + ∑ (bij2 q − 1) xij2 ) = 0, q = 1,2,..., m.bq1ij2ij21qij1ij(7)j =1Таким образом, проблема поиска оптимального предиката (1) может бытьсформулирована как специальная дискретная оптимизационная задача.:Задача Z:12ϕ( < xij , xij > )=<число выполненных уравнений в (7)> → max,при ограничениях (8-9)nu∑ (∑ ci =1j =1vx + ∑ cij2 q xij2 ) ≥ 1, q = 1,2,..., m − mλ .1q 1ij ijj =1uvx , x ∈{0,1}, ∑ x = 1,∑ xij2 = 1, i=1,2,…,n,1ij2ij(8)j =11ij(9)j =1Поставим в соответствие задаче (7-9) аналогичную задачу (10-13)относительно вещественных переменных.Задача ZC:<число выполненных неравенств в (10)> → max,40при ограничениях (11-13)nui =1j =1nui =1j =1∑ (∑ (b1qij∑ (∑ cv− 1) x + ∑ (bij2 q − 1) xij2 ) ≥ 0, q = 1,2,..., m, .1ij(10)j =1vx + ∑ cij2 q xij2 ) ≥ 1, q = 1,2,..., m − mλ .1q 1ij ij(11)j =1xij1 ≥ 0 , i=1,2,…,n, j=1,2,…,u,(12)xij2 ≥ 0 , i=1,2,…,n, j=1,2,…,v.(13)Пусть Q = {q :, гдеui =1j =1∑ (∑ (b< xij1 , xij2 >Пустьn1qijv− 1) x + ∑ (bij2 q − 1) xij2 ) = 0, q = 1,2,..., m}1ijj =1является некоторым решением задачи (10-13).номерi=1,2,…,nпризнакаp (i ) = min{ j : bij1q = 1, ∀q ∈ Q} ,xir∗2 = 1, xij∗2 = 0, j ≠ r.выполнения аналогичных операций длявекториr (i ) = min{ j : bij2 q = 1, ∀q ∈ Q} .xip∗1 = 1, xij∗1 = 0, j ≠ p,Пустьфиксирован,i=1,2,…,n,Послебудет определен< xij∗1 , xij*2 > .ЛЕКЦИЯ № 10Теорема.

Вектор <xij∗1 , xij*2 >является решением Задачи Z.Доказательство.∗1а вектор < xij , xij > удовлетворяетограничениям (9) по построению. Покажем справедливость (11) для*1*2о1о2ϕ( < xij , xij > )=ϕ( < xij , xij > ),*2< xij∗1 , xij*2 > .При любом1i , xij =0приДействительно, если ∃j < p (i ) :j<p(i).xij1 >0, тогда ∃q ∈ Q : bij1q =0 и f qb (< xijo1 , xijo 2 >) < 0 , что противоречитусловиюq ∈ Q . Аналогично, xij2 =0 при j<r(i).uТогда∑cj =1vx + ∑c x1q o1ij ijj =12q o2ijij=u∑cj = p (i )x +1q o1ij ijv∑cj =r (i )2q o2ijijx(p,r зависятот i).41В силу (5),∀q = 1,2,..., m − mλ , ∃i, т.ч.cip1q(i ) ∨ cir2 q(i ) = 1 .Окончательно,nuvi =1j =1j =1f qc (< xij*1 , xij*2 >) = ∑ (∑ cij1q xij*1 + ∑ cij2 q xij*2 ) ≥ cip1q( i ) xip*1(i ) + cir2 q( i ) xir*2( i ) ≥ 1, q = 1,2,..., m − mλ, т.е.

(11) выполнено.Данная теорема дает основу для создания алгоритма поиска предикатов(1) для каждого класса:1. Вычисление опорного объекта.2.Вычисление множествD1 , D 2.∗1Решение Проблемы ZC, и нахождение решения {Q, < xij , xij > }проблемы Z.Замечания.1.Длянахождениямножествалогическихзакономерностейнекоторого класса выбирается произвольный эталон класса в качествеопорногоэталонов.Находятсялогическиезакономерности,соответствующие локально-оптимальным решениям Проблемы Z,связанной с конкретным опорным элементом.Объединение всехполученных логических закономерностей образует конечное множествологических закономерностей класса. Далее выбирается новый опорныйэлемент класса из эталонов, оставшихся «непокрытыми» найденнымиранее предикатами класса.

Для нового опорного элемента аналогичнонаходится множество связанных с ним логических закономерностей,которые пополняют множество найденных ранее логическихзакономерностей класса. Процесс продолжается до «покрытия»найденными закономерностями всех эталонов класса.2.Возможно вычисление “полных множеств” D1 , D 2 , которыевключают значения параметров оптимальных предикатов (1).Доказательство аналогично рассмотренному в [5] для некоторогоэвристического критерия оптимальности логических закономерностей. В3.случае практически больших размерностей множеств*2D1 , D 2 , некоторыеприближения могут быть использованы для сокращения размерностей.3.Для нахождения максимальной совместной подсистемы системылинейных неравенств практически успешно использовался итеративныйпрактический алгоритм [6].Рассмотренный алгоритм является вполне универсальным нотрудоемким в случаях «плохой отделимости» класса.

Под плохойотделимостью класса здесь будем понимать наличие значительногочисла объектов данного класса, находящихся в окружении объектовдругих классов (хотя доля данных объектов класса относительно общегочисла объектов класса может быть мала). В данном случае приходитсярешать большое число задач Z, но результаты, полученные при42использовании в качестве опорных элементов объектов-выбросов, будутотрицательны. Полученные закономерности будут иметь низкоезначение критерия качества. Сложность основной задачи существенновозрастает с ростом длины обучающей выборки.

Эффективное решениедля выборок большой длины возможно при следующей модификациизадачи Z .Поставим задачу поиска логической закономерности P (S ) класса, длякоторойϕ (P) ≥ h , где h >0 – некоторый параметр (качество предикатабудем оценивать долей объектов своего класса, на которых он равен 1). Т.е.априори предполагается, что логические закономерности данного качествасуществуют.

Пусть g – параметр (0<g<1).Опишем алгоритм поиска логических закономерностей класса, результаткоторого формулируется следующим образом: «В вычисленномPj ={ P (S ) } класса K j смножестве логических закономерностейвероятностью не менее g имеется логическая закономерностьP (S ) , длякоторой ϕ (P ) ≥ h».Пусть задача поиска логических закономерностей класса решаетсяотносительно k случайно выбранных «опорных» эталонов классаK j , а всенайденные логические закономерности объединяются в одно множество Pj .Тогда вероятность того, что искомый предикат не будет найден оцениваетсясверху как (1 − h) k . Тогда значение параметра k определяется изсоотношения(1 − h) k ≤ (1 − g ) .(14)Значение параметра k является важным фактором эффективностиалгоритма.

Например, при g=0.9 и h=0.1 из (14) следует k≥ 22. Значениеk=22 вполне приемлемо для задач большой размерности.43В заключение, рассмотрим вопрос выбора значения параметра h.Как его оценить для заданной конкретной задачи, какое его значениеявляется обоснованным с каких-либо позиций?Найденные логические закономерности класса K j могут быть«статистически значимыми» или нет.

Для этого используется подход,именуемый «перестановочный тест». Выполняется серия из следующих tоднотипных расчетов (t – параметр «количество случайных перестановок»).Осуществляется случайная перестановка строк таблицы обучения, при этом ,как и ранее, первыеm1~строк новой таблицы Tnml считаются эталонамипервого класса, следующие по порядку ( m2 − m1 ) строк - эталонами второгокласса, и т.д. (т.е. проводится случайное изменение номеров классовэталонных объектов с сохранением общего числа эталонов класса). Для~~класса K j таблицы Tnml~находится наилучшая закономерность Pj с~качеством ϕ ( Pj ) .

Тогда логическая закономерность Pq из множества Pj ={~P (S ) } считается статистически значимой, если неравенства ϕ ( Pq ) ≥ ϕ ( Pj )выполнены не менее чем 100*q%, (0<q<1 – уровень значимости) в серии из tиспытаний. Таким образом, значения величин ϕ ( Pj ) , полученных врезультате перестановочных тестов, являются естественным вариантомвыбора нижней границы для параметра h.6. Нахождение логических закономерностей, оптимальных постандартному критерию качества (генетический алгоритм).Внастоящемразделерассматриваетсяследующийподход.Определяется некоторое множество предикатов вида (1), на которомсуществует наилучшая логическая закономерность рассматриваемого класса.Каждому предикату взаимнооднозначно соответствует бинарный вектор,длина которого равна числу эталонов класса.

Поскольку допустимость44предикатов и значения их критерия качества вычисляются просто, задачанахождения наилучшей закономерности эффективно решается с помощьюгенетического (эволюционного) подхода для заданного критерия качествазакономерностей относительно введенного множества бинарных кодов.6.1.Основныеэлементыэволюционных методов поиска.генетическихалгоритмов–Основной задачей является нахождение оптимального по заданномукритерию объекта в некотором, вообще говоря бесконечном, множествеобъектов.