Software & Systems

В последнее время интенсивно развивается группа методов под общим названием Data Mining, ориентированных прежде всего на обработку массивов данных значительного размера, содержащих информацию об интересующих объектах, с целью извлечения из них сведений требуемого вида [1, 2]. Как правило, на первом этапе исследования выделяемых объектов решается задача классификации, в которой каждый такой экземпляр должен быть отнесен к какому-либо из уже известных непересекающихся классов объектов Ai из общей совокупности {A} = {A1, A2, …, Ak}. Обычно индивидуальные свойства исследуемых объектов выражают через значения их существенных характерных числовых признаков:  = {х1, х2, …, хn}. При этом каждому исследуемому объекту с номером s взаимно-однозначно соответствует своя точка  = = {a1s, a2s, …, ans} в n-мерном пространстве значений признаков U, на котором введена некоторая мера r. Такой подход позволяет геометрически иллюстрировать методы классификации в n-мерных метрических пространствах. В частности, в работах [3, 4] для построения классификатора предложено использовать специальное бинарное дерево решений, у которого в качестве узловых правил используются гиперплоскости в U, нормальные к межцентровым векторам разделяемых множеств.

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

Обработка зашумленных данных является многогранной проблемой, решаемой как в статисти- ческих методах, так и в задачах искусственного интеллекта. Предварительный анализ экспериментальных данных, имеющих вид случайной величины, сделан в [5, 6]. В работе [7] рассматриваются вопросы моделирования рассуждений на основе прецедентов и классификации в условиях таких данных в интеллектуальных системах поддержки принятия решений. В работах [8, 9] представлено несколько расчетных схем, позволяющих выделять детерминированные компоненты из временных рядов с аддитивной хаотической погрешностью.

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

В задаче классификации объект должен быть отнесен к какому-либо из уже известных непересекающихся классов объектов, входящих в их совокупность {A} = {A1, A2, …, Ak}. Смысловой вариант определения задачи классификации нового, ранее неизвестного объекта ÎU относительно выделенной на U совокупности классов {A} заключается в выяснении включения  в один из классов данной совокупности:

ÎAi, где Ai  Ì{A}.                                               (1)

Ответом в задаче является номер i класса Ai, в который включается объект . Математическую модель µ (формульную, алгоритмическую и др.), решающую задачу (1) для любой заданной точки ÎU, называют классификатором либо решающей функцией.  Он задает отображение вида

µ :  ® {A}.                                                       (2)

В реальных задачах для заданной совокупности классов {A} решающая функция m формируется на основе обучения – обработки набора прецедентов (обучающей выборки) [7, 10] – совокупности пар вида Р = {рs} = {( cls)}, где  = (a1s, a2s, …, ans). В них не только заданы координаты некоторой задающей объект точки ÎU, но и явно при помощи методов из предметной области указано, в какой из классов {A} входит данная точка (и соответствующий ей объект): ÎAcls. Обозначим общий объем обучающей выборки через NN, а число объектов в классах из {A} – через N1, …, Nk, (N1 +…+Nk = NN).

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

Допустим, требуется разработать автоматический классификатор µ, решающий задачу (2) на основании обучающей выборки Р, представляющей собой набор проб, образцов с определенной ка- кими-либо методами из предметной области их принадлежностью к классам {А}. Ошибки в выде- лении набора числовых признаков , шумы в ис- ходных данных приводят к тому, что в прецедентах нарушается правильность отображения µ в задаче (2), то есть точке  может быть сопоставлен неверный класс cls. Назовем такую ситуацию выбросом. Наличие выбросов в обучающей выборке Р дает существенное нарушение гипотезы компактности и значительно затрудняет как построение решающей функции µ, так и последующее решение задачи классификации.

Вспомогательные обозначения. Постановка задачи

Для численного учета общей доли выбросов в выборке Р предложено использовать две пороговые величины:

d0 – предельно допустимая доля удаляемых выбросов, при которой можно без ущерба для общей информативности выборки Р удалить из нее все выбросы;

d1 – предельно допустимая доля корректируемых выбросов, при превышении которой выборку Р уже нельзя считать достаточно информативной для решения задачи (1)–(2).

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

Например, при NN » n×102¸ n×103 (1 £ n £ 9) в задачах дефектоскопии, обработки кадастровых и геологических данных предельно допустимое число отбрасываемых прецедентов можно принять равным n ¸ 10n, d0 = 0,01, а предельно допустимую долю ошибок d1 = (20¸30)d0 = 0,2¸0,3.

При NN » n×105¸n×106 в задачах классификации компонентов тканей организмов (биотехнология, медицина) d0 = 0,001, d1 = (30¸50)d0 = 0,03¸0,05.

При наличии выбросов в Р, помимо неадекватного отображения реальной картины, построение классификатора приводит к следующим негативным последствиям:

-      практическая невозможность полного разделения набора прецедентов по заданной совокупности классов {A}, что характерно для нейросетевых методов классификации;

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

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

Рассмотрим один из возможных путей практической реализации автоматической препроцессорной обработки обучающей выборки.

Анализ прецедентов

Допустим, некий объект из обучающей выборки Р задан точкой , которая изначально включена в класс Af Ì {A}. Требуется проверить правомерность включения точки  в класс Af  (с использованием пространства U и его меры r), а не в какой-либо другой класс из совокупности {A}, то есть проверить, не будет ли точка выбросом.

Для этого предложено использовать специальную меру R(, Aq) близости объекта  к произвольному классу Aq. Ее наиболее удобной функциональной реализацией представляется мера близости точки  и множества точек Aq, аналогичная методу ближайшего соседа с той разницей, что соседство определяется не по одной ближайшей точке, а по нескольким (s) ближайшим:  

R(, Aq) = min{r(, ) + r(, ) +…

+ r(, )},                                                    (3)

где 1£ j1< j2< … < js £ Nq;   ¹   (r = 1, …, s).

С целью сокращения общего числа операций при расчете минимума в расстоянии R(, Aq) для сортировки расстояний предложено использовать дискретизацию значений расстояний r( ) с точностью до 0,05 % с кодированием их целыми числами от 0 до 1 000, которые используются в качестве индексов вспомогательного линейного массива V(1001). Для быстрого выполнения такого упорядочения надо использовать блочную (карманную, корзинную) сортировку.

В том случае, когда точка  пространства U геометрически наиболее близка к точкам из множества {Af \}, теоретически должно выполняться следующее идеальное соотношение:

R(, Af) = min{R(, A1), R(, A2), …,

R(, Ak)}.                                                               (4)

При этом для всех Aq ¹ Af  

R(, Aq) > R( Af).                                     (5)

В практических расчетах минимум (или очень близкая к нему величина) в формуле (4) может достигаться не на одном классе: наряду с классом Af такая же степень близости R может достигаться и на другом классе из совокупности {A}. При этом в зависимости от последовательности анализа, а также погрешности вычислений возможно приня- тие другого класса, отличного от Af, в качестве бли- жайшего к . Для устранения влияния неедин- ственности решения (4) и погрешности расчетов в качестве проверочного условия включения  в Af предложена следующая формула, использующая явно выделенный минимум степеней близости Мk:

Mk = min{R(, A1), R(, A2), …, R(, Ak)};

R(, Af) < (1+e)×Mk,                                       (6)

где ε – достаточно малое вещественное число. При таком определении все классы равноправны при определении их близости к точке

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

-      квадрат евклидова расстояния e=(0,05¸0,1)n;

-      евклидово расстояние e=(0,2¸0,3)n;

-      манхэттенское расстояние e=(0,3¸0,5)n. (7)

При выполнении условий (6)–(7) начальный вариант включения Î{a}f  принимается, иначе – нет. При невыполнении условий в качестве корректирующего класса принимается тот класс Ar, на котором достигается явно выделенный минимум Мk.

Соотношения (6)–(7) позволяют разработать на их основе алгоритм анализа обучающей выборки для последующего построения классификатора для совокупности классов {A}={A1, A2, …, Ak}. Он заключается в последовательном переборе всех прецедентов рs = ( cls), для каждого из которых вначале рассчитываются все расстояния {R( A1), R( A2), …, R( Ak)}, затем определяется их минимум Мk и проверяется условие (6). Если оно выполнено, то начальное приписывание точке класса cls подтверждается. В противном случае прецедент рs считается выбросом из обучающей выборки, в качестве корректирующего класса принимается тот класс, на котором достигается явно выделенный минимум Мk.

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

Выяснение принципиальной возможности кор- рекции выборки P производится путем проверки условия

d £ d1,                                                                 (8)

где d1 – введенная выше предельно допустимая доля корректируемых выбросов.

Приведем алгоритм анализа обучающей выборки, в котором применяется матрица расстояний между точками М(NN ´ NN).

Исходные данные алгоритма:

-      число k выделенных классов в пространстве значений признаков;

-      массив N(k) чисел объектов в классах {N1, N2, …, Nk};

-      количество s ближайших точек в классе Ak к точке  по которым вычисляется R( Ak);

-      NN – общий объем обучающей выборки P;

-      n – число характерных признаков объектов;

-      массив Pr(NN´n) координат точек  = (a1i, a2i, …, ani) (1£i£NN), объектов из P, упорядоченных по принадлежности к классам A1, A2, …, Ak;

-      массив Ncl(NN) классов объектов из P;

-      e – коэффициент запаса при проверке расстояний;

-      d1 (delta1) – предельно допустимая доля корректируемых выбросов.

Решаемая задача: анализ выбросов в обучающей выборке.

Выходные данные:

-      COR – логическая переменная, равная true, если коррекция P возможна, и false – иначе;

-      общее число Nв выбросов в обучающей выборке;

-      доля d (delta) выбросов в обучающей выборке;

-      массив NV (Nв) номеров выбросов в обучающей выборке;

-      массив NCOR(Nв) номеров корректирующих классов для выбросов в обучающей выборке.

В описании алгоритма номера прецедентов обозначены через No, классов – через Nc.

Описание алгоритма анализа обучающей выборки

Начальные присваивания.

Nв := 0; //Начальное значение числа выбросов

 Для No от 1 до NN {    // Расчет элементов матрицы расстояний М

    М[No][No]:=0;

   для  i от 1 до n { PR_No[i]:= Pr[No][i];};

   для  j от No+1 до NN{

      для  i от 1 до n { PR_j[i]:= Pr[j][i];};

      М[No][ j]:= RO(n, PR_No, PR_j)М[i][No];}};

      М[j][No] :=М[No][ j];

    };

 };

  first[1]:=1; last[1]:=N[1];// Формирование массивов границ классов

  для  Nc от 2 до k {first[Nc]:=last[Nc -1]+1; last[Nc]:= = last[Nc -1]+N[Nc];}

Шаг 1. Проход по прецедентам, определение выбросов.

  Для No от 1 до NN {

    для  Nc от 1 до k {//1.1.Проход по классам, расчет расстояний R(`aNo, ANc)

      {min:= М[No][first[Nc]];max:=min;//1.1.1.Расчет min и max расстояний

         для  i от (first[Nc] +1)  до last[Nc]

             {el:=М[No][i];если (elmax){max:= el;}};  

      };

     L:=(max - min); del:=0,001*L;//1.1.2.Инициализация и расчет элементов V

    для  i от 1 до 1000 { V[i] :=0;};

    для  i от first[Nc] до last[Nc] {num:=1000*( М[No][i] - min)/L;

если (М[No][i] – min - del*num>0.5){num:=num+1;};V[num]:=V[num]+1;

      };

RO[Nc] :=0; def_s:=s;       //1.1.3.Инициализация и расчет расстояния RO[Nc]

   для  ind от 1 до 1000 { если (V[ind]>0)

     {val:= min + del×ind;

       если (def_s ³ V[ind]){num:= V[ind]; def_s:= def_s - V[ind];}

  иначе {num:= def_s; def_s:=0;} ;

       RO[Nc] := RO[Nc] + num*val; если (def_s =0){ break;};

     };

   };

 };//Завершение прохода по классам, расчет всех расстояний до них RO[Nc]

  Mk:=RO[1];Nmin:=1;//1.2.Проход по классам, расчет минимума Mk и Nmin

  для  Nc от 2 до k {  если (Mk < RO[Nc]) { Mk:= RO[Nc]; Nmin:= Nc;};   };

  Est:=(1+e)* Mk;//1.3.Проверка выброса, заполнение массивов NV, NCOR

  если (RO[Ncl[Nо]] < Est) {continue;}

  иначе { Nв:= Nв +1;  NV[Nв]:= Nо;  NCOR[Nв]:= Nmin;};

};  //Завершение Шага 1

Шаг 2. Расчет коэффициента delta: 

delta:= Nв / NN.

Шаг 3. Определение возможности коррекции выборки:

  COR:=true; если (delta > delta1){COR:=false;}.

Завершение работы алгоритма.

Если в результате анализа выборки получено значение COR = false, необходима коррекция набора признаков , а возможно, и аппаратных средств исследования. 

Если же выполнено условие COR=true, можно считать, что в этом случае числовые признаки  адекватно отражают свойства разделяемых классов объектов и Р задает удовлетворительный по качеству массив данных. Затем выполняется переход ко второму этапу, на котором учитывается влияние погрешностей при формировании Р.

Оценим сложность алгоритма анализа обучающей выборки. Сложность расчета расстояний r( ) определяется метрикой на пространстве значений признаков U. Общее количество данных расчетов в алгоритме равно 0,5*NN*(NN–1). В алгоритме используются следующие элементарные операции: присваивание, проверка простых условий, сложение и вычитание (в процессорах с плавающей запятой выполняются сходно), умножение, деление. Поскольку алгоритм адаптивный, действительное число операций определяется соста- вом конкретной анализируемой выборки. Результаты моделирования показывают, что при k<

Коррекция обучающей выборки

Предложен алгоритм коррекции обучающей выборки, учитывающий результаты анализа – долю выбросов d в Р, массивы NV и NCOR. Предварительно производится проверка условия

d < d0.                                                                       (9)

Если оно выполнено, можно считать, что выбросы оставляют малую долю от общего числа прецедентов. В простейшем случае выбросы просто удаляются из обучающей выборки Р. Учитывая их малое число, возможен также их индивидуальный человеко-машинный анализ. Если условие (9) не выполнено, доля выбросов достаточно велика. При их отбрасывании будет потеряна значительная часть исходной информации. Вручную проанализировать их также затруднительно из-за большого объема. Поэтому в качестве реального выхода предлагается автоматизированная коррекция выбросов, отмеченных в массиве NV. Для каждого выброса ошибочный прецедент (, cls) заменяется прецедентом (, clr), в котором номер r  принимается из массива NCOR. При этом условие (6) корректности прецедента будет выполнено и выброс устранен.

Приведем алгоритм коррекции обучающей выборки.

Исходные данные алгоритма:

-      n – число характерных признаков объектов;

-      число классов k;

-      NN – общий объем обучающей выборки P;

-      массив Pr(NN´n) координат точек = (a1i, a2i, …, ani) (1£i£NN), объектов из P, упорядоченных по принадлежности к классам A1, A2, …, Ak;

-      массив Ncl(NN) классов объектов из P;

-      d0 (delta0) – предельно допустимая доля удаляемых выбросов;

-      общее число Nв выбросов в обучающей выборке;

-      доля d (delta) выбросов в обучающей выборке;

-      массив NV размерности Nв номеров выбросов в обучающей выборке;

-      массив NCOR размерности Nв номеров корректирующих классов для выбросов в обучающей выборке.

Решаемая задача: коррекция выбросов в обучающей выборке.

Выходные данные:

-      NNN – общий объем новой скорректированной обучающей выборки;

-      новый массив PrN (NNN´n) координат точек = (a1i, a2i, …, ani) (1£i£NNN);

-      новый массив NclN(NNN) классов объектов из скорректированной обучающей выборки.

В описании алгоритма номера прецедентов обозначены через No, классов – через Nc.

Начальные присваивания. NNN:=0.

Шаг 1. Удаление выбросов.

  Если (delta £ delta0) {NoN:=1; для No от 1 до NN

      {Если (Ncl[No]¹NV[NоN]) {NNN:=NNN +1; NclN(NNN):=Ncl[No];

       для  i от 1 до n {PrN [NNN][i]:= Pr [N][i] ;}

        }  иначе{NоN:=NоN +1;}

     }

 }; return;

Шаг 2. Коррекция выбросов.

  NoN:=1; для No от 1 до NN {

      для  i от 1 до n {PrN [No][i]:= Pr [No][i]; }

      если (Ncl[No]¹NV[NоN]) {NclN(No):=Ncl[No];}

      иначе{NоN:=NоN +1; NclN(No):=NCOR[No];};

 }; NNN:=NN;  return;

Завершение работы алгоритма.

Сложность алгоритма коррекции обучающих выборок оценивается величиной О(NN).

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

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

Необходимая дополнительная настройка алгоритмов путем задания в них оптимального числа s ближайших точек при расчете расстояния от объекта до класса, а также величин коэффициентов e, d0, d1 должна учитывать метрику пространства значений признаков U и специфику класса решаемых задач. Изменение этих величин позволяет с использованием предлагаемых алгоритмов автоматически получать различные варианты обучающих выборок и соответствующих классификаторов. Из них можно выбирать оптимальные по тем или иным критериям. Выполненные на конкретных выборках расчеты позволили эффективно устранить в них выбросы и значительно упростить построение классификаторов в виде бинарных деревьев с разделяющими гиперплоскостями.

Массовое практическое применение предлагаемого подхода в конкретных предметных областях (психология и социология, медицина и биотехнология, экология, материаловедение и др.) поможет не только выработать соответствующие рекомендации по выбору величин {s, e, d0, d1}, обеспечивающих построение оптимальных классификаторов, но и, возможно, создать его специализированные модификации.

Литература

1.     Барсегян А., Куприянов М., Холод И., Тесс М., Елизаров С. Анализ данных и процессов. СПб: БХВ-Петербург, 2009. 512 с.

2.     Witten I.H., Frank E. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publ., 2005, 524 p.

3.     Гданский Н.И., Крашенинников А.М., Рысин М.Л. Построение сложных классификаторов для объектов в многомерных пространствах // Инженерный вестник Дона, 2013. № 2; URL: http://ivdon.ru/ru/magazine/archive/n2y2013/1611 (дата обращения: 08.09.2015).

4.     Гданский Н.И., Крашенинников А.М. Общий метод построения кусочно-линейной разделяющей поверхности для множеств объектов, заданных точками в пространстве // Изв. МГТУ МАМИ. 2013. Т. 4. № 1 (15). С. 165–171.

5.     Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988. 176 с.

6.     Hastie T., Tibshirani R., Friedman J.H. The elements of statistical learning: Data mining, inference, and prediction. NY: Springer Verlag, 2001, 738 p.

7.     Варшавский П.Р., Еремеев А.П. Моделирование рассуждений на основе прецедентов в интеллектуальных системах поддержки принятия решений // Искусственный интеллект и принятие решений. 2009. № 2. С. 45–57.

8.     Крянев А.В., Лукин Г.В. Математические методы обработки неопределенных данных. М.: Наука, 2006. 308 с.

9.     Выделение детерминированных компонент из зашумленных данных. URL: http://do.gendocs.ru/docs/index-241588.html (дата обращения: 08.09.2015).

10.  Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.