Глава 16 Методы анализа структурных объектов

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

Анализ структурированных объектов включает в себя аппарат для описания информативных особенностей структур в виде их метрических и топологических свойств: диаметр графа, число вершин, наличие специфичных связей, клик, колец. Использование этого аппарата позволяет решать задачи нахождения изоморфных графов и определения наибольших общих частей двух графов, измерять расстояния между графами. На этой базе делается классификация молекул (таксономия графов), решаются, например, задачи обнаружения закономерных связей между структурными свойствами и биологической активностью веществ (задача распознавания), поиска структурных фрагментов, наиболее сильно влияющих на заданное свойство веществ (задача выбора информативных характеристик), предсказания свойств синтезируемых соединений (задача прогнозирования). Для решения этих задач разработаны эффективные алгоритмы, реализованные в программной системе СИСТРАН [92,117].

Имеются объекты, важным свойством которых является не пространственная, а временная организация их составных частей. Это, например, тексты — литературные, генетические или музыкальные. Для их анализа разрабатываются меры близости между символьными последовательностями [131], что позволяет делать классификацию текстов, находить межтекстовые или межъязыковые аналогии. Решаются задачи обнаружения повторов, выявления структурных единиц из слитного текста, видов вариативности, иерархической организации текстов и пр. [10,11,44].

При распознавании речевых сигналов мы тоже сталкиваемся с проблемами анализа объектов, имеющих временную структуру. Близкие особенности имеют объекты, представляющие собой динамические траектории развития процессов. При сравнении двух структурных объектов или динамических траекторий возникает проблема выравнивания их протяженности по оси времени. Простая схема линейного сжатия или растяжения обычно не дает хороших результатов. Например, одно и то же слово, состоящее из двух слогов, один диктор может произнести, растягивая первый слог, а другой — растягивая второй слог. Чтобы наилучшим образом совместить друг с другом одинаковые фонемы этих слов, необходимо для одного из них сделать нелинейное преобразование оси времени: одни его участки растянуть, а другие участки сжать. И только после такого наилучшего совмещения похожих частей друг с другом можно определить степень похожести этих слов. Описанная здесь нелинейная нормализация объектов по времени и определение расстояния между сравниваемыми объектами делается одним из двух методов: методом динамического программирования (ДП) или методом скрытых марковских процессов (СМП). Опишем суть этих методов.