2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf)

Лекция 11. ВВЕДЕНИЕВразличныхобластяхчеловеческойдеятельности(экономике,финансах, медицине, бизнесе, геологии, химии, и др.) повседневно возникаетнеобходимость решения задач анализа, прогноза и диагностики, выявленияскрытых зависимостей и поддержки принятия оптимальных решений. Внастоящее время вследствие бурного роста объема информации, развитиятехнологий ее сбора, хранения и организации в базах и хранилищах данных(в том числе Интернет-технологий), точные методы их анализа имоделирования зачастую отстают от потребностей реальной жизни.

Здесьтребуются универсальные, простые и надежные подходы, пригодные дляобработки информации из различных областей, в том числе для решенияпроблем, которые могут возникнуть в ближайшем будущем. В качествеподобного базиса могут быть использованы технологии и подходыматематической теории распознавания и классификации [1, 2, 8].Действительно, данные подходы в качестве исходной информациииспользуют лишь выборки описаний-наблюдений объектов, предметов,ситуаций или процессов (выборки прецедентов), при этом каждое отдельноенаблюдение-прецедент записывается в виде вектора числовых значенийотдельных его свойств-признаков. Выборки признаковых описаний являютсяобычно первичными исходными данными, которые повседневно возникают вразличных предметных областях, и которые могут быть использованы длярешения следующих задач:- распознавание (классификация, диагностика) ситуаций, явлений, объектовили процессов с обоснованием решений;- прогнозирование ситуаций, явлений, процессов и состояний по выборкамдинамических данных;- кластерный анализ и исследование структуры данных;- выявление существенных признаков и минимизация описаний объектов;- нахождение эмпирических закономерностей различного вида;1- нахождение нестандартных или критических случаев;- формирование эталонных описаний образов.Данные задачи возникают в различных предметных областях.Приведем некоторые примеры подобных приложений:- обработка данных социологических опросов;- прогнозирование тенденций изменения макроэкономических показателей;- анализ финансовых данных и прогноз финансовых показателей;- оценка экономического состояния предприятий и перспектив ихинвестирования;- проблемы прогнозирования экологических последствий по малымвыборкам прецедентов;- широкий круг задач медицины, связанных с созданием систем поддержкипринятия диагностических решений, обработкой медицинской статистики,анализа эффективности лекарств и прогноза последствий лечения;- задачи геологического прогнозирования;- задачи экспериментальной физики, связанные с анализом накопленногоэкспериментального материала на этапах выявления качественныхвзаимосвязей между физическими параметрами и созданиемприближенных математических моделей;- задачи прогнозирования свойств новых органических соединений в химиина основе имеющегося банка исследованных органических соединений;- обработка и анализ данных в биологии, с целью оптимизацииселекционных и генетических исследований;- обширный круг задач распознавания изображений.1.

Основные задачи анализа данных, распознавания,классификации и прогноза по прецедентам.Исходной информацией являются описания объектов (ситуаций ,предметов, явлений или процессов) S в виде векторов значений признаковS = ( x1 ( S ), x 2 ( S ),..., x n ( S )) , где признаки xi , i = 1,2,..., n , характеризуют различные2стороны-свойства S. Одно из «свойств» y(S) объектов S (не входящее всостав признаков) считается «основным». Свойство y(S) принимает конечноечисло значений и для некоторых объектов S1 , S 2 ,..., S m считается известным.Предполагается, что существует прямая связь между признаками и основнымсвойством (неизвестная пользователю).Задачараспознавания(прогноза,идентификации,«классификации с учителем») по прецедентам состоит в определениизначениясвойстваy(S)объектаSпоинформацииS1 , S 2 ,..., S m , y ( S1 ), y ( S 2 ),..., y ( S m ) (обучающей или эталонной выборке).

Обычновместо термина «основное свойство объекта» используют термин «классобъекта».Объекты,имеющиеравныезначенияосновногосвойствасчитаются принадлежащими одному множеству (образу, классу объектов), изадача распознавания по прецедентам формулируется как задача отнесенияобъекта к одному из классов.Задачу распознавания далее мы будем рассматривать далее какзадачу классификации с учителем, и использовать следующую постановку иобозначения.1.

Пусть некоторое множество объектов является объединениемконечного числа непересекающихся подмножеств, именуемых классами:lM = ∪ K i , K i ∩ K j = ∅, i ≠ j . Данное разбиение известно лишь частично вi =1виде выборки объектов S1, S2 ,..., Sm из данного множества, содержащейпредставителей всех классов. Для определенности будем считать, чтоS mi−1 , Smi−1 +1,..., Smi ∈ Ki ,m0 = 0, ml = m, i = 1,2,..., l .2. Описание произвольного объектаSизMзадается в видесовокупности из n значений признаков X1, X 2 ,..., X n : x1 ( S ), x2 ( S ),..., xn ( S ), гдеxi ( S ) ∈ M i - значение признака X i на объектеS.Здесь множества M iзадают область допустимых значений признака.

Признак, как некоторое3свойство объекта, может быть произвольной природы (некоторая числоваяхарактеристика, наличие или отсутствие какого-то свойства, изображение,функция, и т.д.). Мы будем рассматривать случаи числовых признаков, аименно:а)M i = {0,1}- признак бинарный, обозначает отсутствие или наличиекакого-либо свойства;M i = {0,1,..., k − 1}б)- признак k – значный, выражает степеньвыраженности некоторого свойства с конечным числом значений;в)M i = [ai , bi ] ,Числовыегдеai , bi − числа,признакилибо символыявляются± ∞.наиболеепростымиираспространенными. Признаки номинальные (при сравнении которых нельзяиспользоватьотношения«больше»,«меньше»,например«цвет»,«социальное положение», «пол»), порядковые (где существенны илиизвестны лишь отношения <, >, но не сама величина различия междузначениямипризнаков),идругиеболее«сложные»признакирассматриваться не будут.

На практике, данные признаки сводятся кчисловым, или для задач со сложными признаками создаются специальныеметоды.Вкачествеподобныхпримеровможнопривестизадачираспознавания зрительных и слуховых образов. Далее, для простоты записи,мы будем отождествлять объект с его описанием:S = ( x1 ( S ), x2 ( S ),..., xn ( S )) .Обучающая выборка будет задаваться таблицей обучения T nml из mстрок и n столбцов, в которой строками являются признаковые описанияобъектов, причем первые m1 объектов из первого класса, следующие (m2 − m1 )- из второго, и т.д. Т.е. класс K j представлен (m j − m j −1 ) эталонами,m0 = 0, ml = m . Строка ( x1 ( S j ), x2 ( S j ),..., xn ( S j )) таблицы являетсяпризнаковымописанием эталонного объекта S j , а столбец ( xi ( S1 ), xi ( S2 ),..., xi ( S m ))t содержитзначения признака xi на эталонной выборке.Примерами подобных задач являются:4-задачи медицинской диагностики, в которых по совокупностисимптомов, данных лабораторных обследований и т.п.

требуется поставитьдиагноз при заданном конечном наборе возможных их вариантов (здесь«основное свойство» есть наличие/отсутствие определенного заболевания);- задачи технической диагностики, когда по набору значенийкосвенных технических параметров, показаниям датчиков и приборовтребуется определить наличие или вид неисправности;- прогноз эффективности инвестирования предприятия по егофинансово-экономическим показателям (здесь «основное свойство» естьоценка эффективности инвестирования, качественная или в баллах);- прогноз тенденций в политике, финансах и экономике, выявлениеи оценивание скрытых факторов;-прогнозсвойстворганических/неорганическиххимическихсоединений и сплавов по составляющим компонентам и технологиипроизводства;- прогноз урожайности (интервала сбора культуры с единицыплощади) сельскохозяйственных культур по описанию их состояния наразличных стадиях роста и климатических условий;- распознавание изображений, рукописных и других символов,подписей.Задача распознавания объекта S состоит в определении классаK j , j = 1,2,..., l , которому( x1 ( S ), x2 ( S ),..., xn ( S ))принадлежит объект, на основе описания объектаи таблице обучения T nml .

Данная задача обычно решается вдва этапа. Сначала по таблице обучения подбирается алгоритм, которыйнаилучшим образом соответствует в каком-либо смысле таблице обучения.Данный этап называют этапом обучения распознаванию. На втором этапе,подобранный алгоритм непосредственно применяется для классификациинового объекта.Данная постановка задачи распознавания имеет простуюгеометрическую интерпретацию. Множеству M (соответственно классам)5соответствуют область (подобласти) n-мерного векторного пространствапризнаковых описаний. Исходная информация об областях представлена ввиде отдельных их точек. По данной исходной информации требуетсяопределять принадлежность новых точек к одной из подобластей.В практическом распознавании, в качестве допустимых решений,принимаются «отказы от распознавания», когда распознаваемый объект непохож на все предыдущие прецеденты, или когда он похож приблизительно вравной степени на объекты двух и более классов.Задача автоматической классификации (классификации безучителя, кластерного анализа, таксономии) состоит в автоматическомразбиении заданной выборки объектов на классы (группировки) так, чтобыпо совокупности значений признаков объекты одной группировки былиблизки друг другу, а объекты разных группировок – далеки.

Полученныегруппировки являются приближенным макроописанием исходной выборки.Для простоты изложения, чтобы не возникало разночтений и путаницымеждузадачамиклассификациисучителем(распознавания)иклассификации без учителя, для последней далее будут использоваться какправило термины «кластерный анализ», «кластеризация», и вместо терминов«классы» - термин «кластеры».Задача оценки информативности признаков и объектовсостоит в вычислении относительного вклада признака (объекта) в процессраспознавания.Задача минимизации признакового пространства состоит внахожденииминимальногонаборапризнаков,обеспечивающегонезначительное ухудшение качества (точности) распознавания относительноисходного набора признаков.Задачапоискалогическихзакономерностей(логическихзависимостей, извлечения знаний, data mining) состоит в нахождениитаких значений (интервалов значений) признаков, которые свойственны6многим объектам одного класса (с одинаковым значением свойства y).

Этовыражается в правилах следующего вида:1. «для 80% эталонных объектов S = ( x1 ( S ), x 2 ( S ),..., x n ( S )) второгокласса (y(S)=2) выполнены условия: (1.3 ≤ x 2 ( S ) ≤ 5.2) & (6.7 < x5 ( S ) ≤ 22.2) &( x 6 ( S ) = 1) & ( x9 ( S ) < 11) ».2. «если (3 ≤ x1 ( S ) ≤ 7.2) & (1.9 ≤ x 4 ( S ) ≤ 2.2) & (5 < x6 ( S )) & ( x11 ( S ) = 1) , то свероятностью 0.9 выполнено y(S)=1 (объект S принадлежит первомуклассу)».Существуют и другие функции, параметры, величины, которыемогут быть вычислены (хотя бы приближенно) по эталонным выборкам, икоторые имеют интерпретацию и практическую ценность для пользователя(логические описания классов, логические корреляции, и др.).Лекция 22. Алгоритмы распознавания, основанные на принципечастичной прецедентностиПринципиальнаяидеяалгоритмовчастичнойпрецедентностисостоит в отнесении распознаваемого объекта в тот класс, в котором имеетсябольшеечислопрецедентов),«информативных»приблизительнофрагментовравныхэталонов(частичныхсоответствующимфрагментамобъекта S [1, 2].