Отображение структуры данных в память эвм

Рассмотрим вопросы, возникающие при анализе СД при помощи ЭВМ. Каждый объект множества Е является конструктивным, поскольку их описания могут быть представлены конечными конфигурациями знаков (в данном случае — набором признаков). Известно, что любой конструктивный объект можно закоди­ровать словом в подходящем алфавите. Дальнейшая редукция связана с перенумерацией слов алфавита, например, путем лексикографического упорядочения. Таким образом, в принципе достаточно рассматривать отображение объектов множества Е на натуральные (в общем случае рациональные) числа, адекватно представляющие адреса ячеек памяти ЭВМ. Однако любая ап­паратура и средства обработки и хранения данных обладают не­которой собственной структурой, поэтому на информацию, по­мещенную в память ЭВМ, будут наложены некоторые дополнитель­ные отношения, и вопрос состоит в том, чтобы при этом не оказа­лась нарушенной собственно СД.

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

2. Второй существенный вопрос состоит в том, каким образом хранить данные в ЭВМ и как способ хранения описаний объектом и отношений между ними влияет на возможность и скорость полу­чения решения поставленной задачи. Например, отношение между объектами может задаваться: перечислением всех своих возможных значений (хранение матрицы непарных расстояний в задаче авто­матической классификации); списком отношений, реализованных для каждого объекта (цепи, инвертированные списки при хране­нии информационных массивов); непосредственным вычислением требуемого отношения путем перебора всех объектов (поиск «бли­жайшего соседа» для принятия решения по прецеденту). Отсюда возникает задача нахождения такого отображения множества описаний объектов Х в память ЭВМ, чтобы обеспечивалось бы­строе вычисление (или поиск значений) требуемых отношений для любых объектов. Выигрыш при этом может быть достигнут, как за счет сокращения объема требуемой памяти, так и за счет уско­рения обработки вследствие уменьшения числа переборных опе­раций. «В идеале структура машины должна соответствовать естественной структуре задачи». Выполнение этого требования в случае задач обработки данных означало бы такое размещение информации в памяти, что все отношения между описаниями объектов множества Е следовали бы не из содержания описаний, а непосредственно из их положения в запоминающем устройстве. Таким образом, была бы обеспечена изоморфность структуры представления данных в памяти и структуры, задавае­мой на множестве объектов исследуемыми отношениями. В этом случае описания объектов определяют не содержание информации в памяти, а лишь ее расположение, поэтому смысловую нагрузку, соответствующую описанию каждого объекта, несет собственно место хранения информации об объекте, а значит, эта информация может быть минимальной — в пределе это есть лишь номер (имя) объекта, служащий для его идентификации.

3. Следствием наложения структуры хранения информации в памяти ЭВМ на СД является возможность до­ступа к данным лишь через вычисление адреса (координаты) еди­ницы памяти, в которой хранится требуемая информация. Таким образом, можно говорить об одномерности представления в ЭВМ любой СД и, следовательно, о необходимости построения отобра­жения СД в одномерную шкалу, являющуюся моделью памяти ЭВМ.

Такое отображение, во-первых, задает на множестве Е отноше­ние линейного порядка, что дает возможность организовывать быстрый поиск и обработку данных в ЭВМ, а, во-вторых, позволяет визуализировать СД для человека с тем, чтобы использовать его возможности в процессе решения задачи для проведения сопоста­вительного анализа.

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

Можно предложить общую схему анализа данных в рамках структурного метода (рис.6.5).

1. Формирование ТЭД—составление описаний исследуемых объектов Х={xi(j)}.

2. Формулировка знаний исследователя о СД на текущий мо­мент в виде задания образов А_iили использование этих знаний при выборе математического метода и алгоритма обработки Н.

3. Применение алгоритмов анализа СД, в том числе: отображе­ние данных в пространства низшей размерности (R^p, р==1, 2, 3) с целью визуального анализа структуры V или ее эффективного представления в ЭВМ; получение различных вариантов разбиения множества Е на однородные классы (S_k), отбрасывание неинфор­мативных признаков.

4. Сопоставительный анализ (A_i, и S_k) и уточнение знаний ис­следователя о СД, и если требуется, то переход к очередному циклу анализа СД (п. 2).

5. Окончательное описание СД {V), в том числе: выбор мини­мального числа признаков и (или) объектов, дающих возможность получить ту же структуру* V* на Е, что и исходное описание X', описание элементов S_kполученной СД при помощи вероятностных или детерминистских законов F;, выбор минимального числа объ­ектов и (или) признаков, позволяющих получить то же описание F* каждого элемента СД (S_k, k=1,…,n), что и все объекты (признаки) S_i

Кроме рассмотренных задач распознавания, классификации, из приведенной схемы легко понять пути решения с помощью структурного метода таких задач, как про­гнозирование и принятие решения методом «прецедента», когда, определив местоположение объекта исследования в структуре V, ему приписывают (присваивают) известные свойства «ближайшего» по структуре объекта. Решается также задача создания избира­тельного банка данных с ассоциативным доступом, когда ТЭД пополняется только за счет объектов исследования, не укладывающихся в найденную структуру V, а в качестве ответа на запрос выдается не только описание одного объекта, но и ассоциирован­ные с ними в структуре объекты с «похожими» описаниями.

Решение еще одной возможной задачи — восстановление не­известных значений признаков в ТЭД. Ее общая схема такова (рис. 6.6):

1. определение структуры решения V по всем объектам ТЭД без учета не полностью имеющихся признаков;

2. присваивание от­сутствующим значениям признаков i-го объекта (X_m) известных зна­чений признаков ближайшего в структуреj-го объекта (X_k);

3. снова опре­деление структуры решения V₂по всем объектам с учетом всех признаков;

4. определение структуры решения V₃по тем объектам, которые имели значения всех признаков;

5. если структура V₃вкладывается в структуру V₂, т. е. взаимное расположение объек­тов в V₃совпадает с их расположением в V₂, то восстановление пропусков в ТЭД окончено (путь 1), в противном случае возможно исполь­зование итерационной процедуры, определяемой всеми этими пунктами (путь 2).

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

На экспериментальные данные накладывается одна из моделей описания данных. В рамках геометрической модели M_гсовокупность вторичных оценок {A_o()}, описывающих исследуемое множество данных F={f_i}₁^N, представляется совокупностью векторов-оъектов {X_i}₁^N, заданных своими параметрами ({X_i}₁^N=(x_i1,x_i2,...,x_iL). Вектора {X_i}₁^Nалгоритмами {Q_m} разбиваются, согласно заданных критериев разбиения {^t}_m, на совокупности однородных классов {S_q}_m. Наличие петли в схеме по параметру (t) подчеркивает факт, что при формировании однородных классов существует необходимость использования, наряду с различными алгоритмами группирования Q_m, и разных критериев оценки качества разбиения {^t} для каждого m‑го алгоритма. Полученные в системе классы {S_q}_mпредъявляются исследователю Исс, который на основе своих суждений {}_mи собственных представлений M_ио разбиении совокупностей вторичных оценок {A_o(w)} на группы {W_p}_mпринимает решение {W}_Обо правильности разбиения {S_q}_mили об использовании нового алгоритма Q_m (петля по параметру m).

В случае если число классов для объектов известно, то схема выделения однородных классов незначительно отличается от рассмотренной ранее (рис.6.7,б). Здесь исследователь задает число классов С, тем самым перенастраивает программно-алгоритмическое обеспечение подсистемы формирования эталонов классов.

При классификации объектов можно предложить следующую схему выбора алгоритмов:

1. Оценить начальные условия;

2. Если выборка данных и количество параметров относительно не велико – применить алгоритмы параллельной группировки;

   1. Число классов не известно и не может быть определено — использовать алгоритмы иерархической группировки;

      1. Структура данных представляет собой сложную структуру — выбрать алгоритм «ближний сосед»;

      2. Структура данных представляет собой сферообразную структуру — выбрать алгоритм «дальний сосед»;

      3. Структура данных сложно отнести к первому или второму типу — выбирать алгоритмы «средней связи» или «центр тяжести», возможно, требуются дополнительные данные;

   2. Число классов известно — использовать алгоритм «k– внутригрупповых средних». Возможно, необходимо изменять начальные центры классов;

   3. Число классов неизвестно — использовать алгоритм «максиминного расстояния». Возможно, необходимо изменения первого центра класса и/или коэффициента ;

3. Выборка данных велико и реализация процедуры обработки затруднительна — применить алгоритмы последовательной группировки.