3. Объединение

Сначала каждый объект исходной выборки данных выделяется в отдельный кластер. Далее отыскивается пара кластеров с наименьшим межкластерным расстоянием и объединяется в один кластер большего размера. Этот процесс продолжают до тех пор, пока не будет выполняться некоторое условие оптимальности или все объекты не окажутся в одном кластере. Для больших выборок, включающих более 1000 элементов, этот алгоритм неэкономичен, и определение оптимальных условий требует привлечения некоторых аппроксимаций.

4. Разбиение

Алгоритмы разбиения полностью противоположны алгоритмам объединения. В этих алгоритмах исходная выборка данных последовательно разбивается на все более мелкие кластеры в соответствии с некоторыми правилами (минимальный или максимальный размер, стандартное отклонение и т. д.). Трудности, возникающие при реализации этих алгоритмов, обычно связаны с выбором формы функций разбиения.

5. Добавление

Эти алгоритмы работают путем добавления элементов выборки в уже существующие кластеры. Ограниченность этих алгоритмов очевидна.

6. Поиск

Алгоритмы поиска обычно применяются к тем системам, для которых в результате математического анализа исключены многие из возможных способов разбиения на кластеры. С помощью этих алгоритмов производится такая оптимальная кластеризация системы, которая приводит к минимуму функции ошибок.

Существует много различных алгоритмов, однако ни один из них не приспособлен для решения любой из возникающих задач. Некоторые алгоритмы, например алгоритм ISODATA Болла и Холла [19,20] может осуществлять процедуры добавления, поиска, объединения и разбиения. Такие алгоритмы имеют более широкую область применения, однако ни один из них не является универсальным. К тому же многие алгоритмы являются эвристическими по своей природе, и поэтому успех их реализации, в конечном счете, зависит от мастерства исследователя. И наконец, последний недостаток методов кластеризации заключается в том, что иногда возникают трудности с отнесением неизвестного объекта к одному из уже имеющихся классов.

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

1.2.4 Программа PASS C&T

Знание известных биологически активных соединений и аналитические возможности даже самого лучшего из химиков - ограничены, и поэтому помощь специальной компьютерной системы в получении оценок по возможным видам биологической активности для различных классов соединений была бы полезной. Идея создания компьютерной системы прогноза биологической активности, на первый взгляд, выглядит достаточно просто: нужно собрать всю известную информацию о биологически активных соединениях, создать на этой основе обучающую выборку, провести анализ связей "структура-активность" для веществ из обучающей выборки и построить соответствующие зависимости. "Подставив" в эти зависимости данные о структуре нового вещества, можно получить в результате оценку его биологической активности.

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

Предложение предсказывать подобным образом спектр биологической активности вещества было впервые высказано в начале 70-х годов к.х.н. В.В. Авидоном c сотрудниками, работавшими тогда в НИИ по биологическим испытаниям химических соединений. В.В. Авидоном, совместно с к.х.н. В.Г. Блиновой, к.м.н. Е.М. Михайловским, Р.К. Казарян, к.ф.-м.н. В.С. Ароловичем и др., были разработаны оригинальные языки описания химической структуры, Тезаурус (структурированный словник) по биологической активности химических соединений, математические методы установления зависимостей "структура-активность" и прогноза свойств новых веществ; создан банк данных по биологически активным соединениям (обучающая выборка). На этой основе были осуществлены первые эксперименты по прогнозированию спектра биологической активности по структурной формуле вещества.

За истекшее двадцатилетие методы, первоначально предложенные для прогноза спектра биологической активности, претерпели существенные изменения. Эти изменения базируются как на теоретическом анализе методики прогнозирования, так и на имеющемся опыте ее применения для поиска веществ с требуемыми свойствами.

Современная версия компьютерной системы предсказания спектра биологической активности PASS C&T (Prediction of Activity Spectra for Substances: Complex & Training) реализована в 1998 году. Она включает в себя обучающую выборку, содержащую более 30000 биологически активных веществ с известной биологической активностью, и охватывает более 400 фармакологических эффектов, механизмов действия, а также мутагенность, канцерогенность, тератогенность и эмбриотоксичность.

Математический подход, используемый в PASS C&T, выбран Д.А. Филимоновым в результате сравнительного анализа 300 различных методов. Показано, что средняя точность прогноза с помощью PASS C&T при скользящем контроле с поочередным исключением по одному соединению из обучающей выборки составляет около 84%.

Результаты прогноза выдаются либо в виде текстового файла, который может в дальнейшем обрабатываться с помощью различных текстовых процессоров, либо в виде SDF файла, который может импортироваться в ISIS/Base и добавляться к имеющейся в базе данных информации о веществах. Далее обработка результатов прогноза осуществляется стандартными программными средствами, имеющимися в ISIS/Base.

Биологическая активность описывается в PASS C&T качественным образом ("да"/"нет"). Выдаваемые результаты прогноза помимо названий активности включают в себя оценки вероятностей наличия (Pa) и отсутствия каждой активности (Pi), имеющие значения от 0 до 1. Поскольку эти вероятности рассчитываются независимо, их сумма не равна единице.

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