Проектирование классификаторов

«Проектирование классификаторов»

1. Методы классификации.
2. Методы кодирования.
3. Виды классификаторов.
4. Требования, учитываемые при проектировании.
5. Последовательность проектирования.
6. Необходимость классификации и кодирования.

1.1. Методы классификации

Классификация – это разделение множества объектов на подмножества по их сходству или различию в соответствии с принятыми методами. Классификация фиксирует закономерные связи между классами объектов.

Объект классификации – элемент множества, используемый при классификации.

Признак классификации – признак, по которому производится деление заданного множества на подмножества.

Классификационная группировка – подмножества, которые получаются в результате деления заданного множества.

Глубина классификации – число ступеней классификации.

Применяется три метода классификации: элементарный, иерархический и фасетный.

Существуют следующие требования для выбранной системы классификации:

 достаточная емкость и необходимая полнота, которые гарантируют охват всех объектов классификации в заданных границах;

 оправданная глубина;

 обеспечение возможности решения  задач управления объектом;

 возможность расширения множества классифицируемых объектов и внесения необходимых изменений в структуры классификации;

 обеспечение возможности сопряжения с другими классификациями однородных объектов;

 обеспечение простоты ведения классификатора.

Каждая система классификации характеризуется следующими свойствами:

 гибкостью системы;

 емкостью системы;

 степенью заполненности системы.

Гибкость системы — это способность допускать включение новых признаков, объектов без разрушения структуры классификатора. Необходимая гибкость определяется временем жизни системы.

Емкость системы — это наибольшее количество классификационных группировок, допускаемое в данной системе классификации.

Степень заполненности системы определяется как частное от деления фактического количества группировок на величину емкости системы.

Элементарный метод

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

Пример. Множество районов Н.Новгорода

Согласно генеральному плану развития города часть Борского района должна войти в состав Н.Новгорода. Предположим, что будет выделен Борский район города. Тогда классификация нарушится в первом случае. Или ее нужно будет выполнить заново.

Иерархический метод

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

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

Характерными особенностями иерархической системы являются:

        возможность использования неограниченного количества признаков классификации;

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

Требования к классификатору, построенному на иерархическом методе классификации:

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

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

Значительным недостатком иерархической классификации является жесткость классификационной схемы. Она обусловлена заранее установленным выбором признаков классификации и порядком их использования по ступеням классификации. Это ведет к тому, что при изменении состава объектов классификации, их характеристик или характера решаемых при помощи классификатора задач требуется коренная переработка классификационной схемы. Гибкость этой системы обеспечивается только за счет ввода большой избыточности в ветвях, что приводит к слабой заполненности структуры классификатора. Поэтому при разработке классификаторов следует учитывать, что иерархический метод классификации более предпочтителен для объектов с относительно стабильными признаками и для решения стабильного комплекса задач.

Обобщенное представление иерархической классификации приведено на рисунке.

Пример. Выполним иерархическую классификацию групп студентов на дневном отделении экономического факультета. В качестве классификационных признаков выберем: специальность, курс, способ финансирования. На рисунке приведен фрагмент классификационного дерева.

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

Группы студентов дневного отделения  экономического факультета

              Группы специальности экономическая теория

                            1 курс

                                          Бюджетные

                                                        …

                                          Вне бюджетные

                                                        …

                                          Смешанные

                                                        1 группа

                            2 курс

                                          Бюджетные

                                                        …

                                          Вне бюджетные

                                                        …

                                          Смешанные

                                                        1 группа

                                                                      ….

              Группы специальности прикладная информатика

                            1 курс

                                          ...

Фасетный (многоаспектный) метод

Аспект — точка зрения на объект классификации, который характеризуется одним или несколькими признаками.

Многоаспектная система — это система классификации, которая использует параллельно несколько независимых признаков (аспектов) в качестве основания классификации. Существуют два типа многоаспектных систем: фасетная и дескрипторная.

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

Дескриптор — ключевое слово, определяющее некоторое понятие, которое формирует описание объекта и дает принадлежность этого объекта к классу, группе.

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

К классификатору, построенному на основе фасетного метода классификации, предъявляются следующие требования:

1. Должен соблюдаться принцип не пересекаемости фасета, т. е. состав признаков одного фасета не должен повторяться в других фасетах этого же класса;
2. В состав классификатора должны быть включены только такие фасеты и признаки, которые необходимы для решения конкретных задач.

Общий вид фасетной классификационной схемы:

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

Пример.  Снова выполним классификацию групп студентов дневного отделения экономического факультета, но с использованием фасетного метода. Выберем в качестве фасетов: специальность, курс, способ финансирования.

В результате классификации мы имеем списки групп. Например, по специальности прикладная информатика или на 3 курсе, или бюджетные. Состав фасетной формулы: специальность, курс, способ финансирования. Каждая группа характеризуется одним из значений в фасете. Так группа 735: прикладная информатика, 3 курс, смешанная.

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

Недостатками фасетного метода классификации являются неполное использование емкости, не традиционность и иногда сложность применения.

В современных классификационных схемах часто одновременно используются оба метода классификации. Это снижает влияние недостатков методов классификации и расширяет возможность использования классификаторов в информационном обеспечении управления.

1.2. Методы кодирования

Для полной формализации информации недостаточно простой классификации, поэтому проводят следующую процедуру — кодирование.

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

Система кодирования — это совокупность правил обозначения объектов и группировок с использованием кодов.

Код — это условное обозначение объектов или группировок в виде знака или группы знаков в соответствии с принятой системой. Код базируется на определенном алфавите (некоторое множество знаков). Число знаков этого множества называется основанием кода.

Код характеризуется следующими параметрами:

        длиной;

        основанием кодирования;

        структурой кода, под которой понимают распределение знаков по признакам и объектам классификации;

        степенью информативности, рассчитываемой как частное от деления общего количества признаков на длину кода;

        коэффициентом избыточности, который определяется как отношение максимального количества объектов к фактическому количеству объектов.

К методам кодирования предъявляются определенные требования:

        код должен осуществлять идентификацию объекта в пределах заданного множества объектов классификации;

        желательно предусматривать использование в качестве алфавита кода десятичных цифр и букв;

        необходимо обеспечивать по возможности минимальную длину кода и достаточный резерв незанятых позиций для кодирования новых объектов без нарушения структуры классификатора.

Методы кодирования могут носить самостоятельный характер – регистрационные методы кодирования, или быть основанными на предварительной классификации объектов – классификационные методы кодирования.

Регистрационные методы кодирования бывают двух видов: порядковый и серийно-порядковый.

Порядковый метод — каждый из объектов множества кодируется с помощью чисел натурального ряда.

Пример. Числа месяца, годы. Если присвоить коды районам Н.Новгорода при их классификации по алфавиту

Описание классификатора:

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

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

Пример. Рассмотрим международный классификатор видов транспорта и транспортировки товаров.

Посмотрите, выделены серии номеров по видам транспорта.

10 - 19 – морской транспорт.

20 – 29  – железнодорожный транспорт.

30 – 39  – автодорожный транспорт.

40 – 49  – воздушный транспорт.

50 - 59 - почтовые отправления (активный вид транспорта неизвестен).

60 - 69 – смешанные перевозки (активный вид транспорта неизвестен).

70 - 79 – фиксированные транспортные установки (стационарный транспорт)

80 - 89 – внутренний водный транспорт. Этот код используется только в тех случаях, когда этот вид водного транспорта учитывается отдельно.

90 - 99 – вид транспорта неизвестен.

Кодовые обозначения подвидам транспорта присваиваются внутри серии. Оформим таблицу в соответствии с правилами.