Вариационные алгоритмы автоматической классификации объектов

В работе разработан и программно реализован алгоритм автоматической классификации объектов. Работа защищена с оценкой отлично. ...

ВВЕДЕНИЕ 3
ГЛАВА 1. Методы и алгоритмы используемые в задачах автоматической классификации объектов.. 6
1.1. Иерархическая классификация 7
1.2. Алгоритм СПЕКТР 8
1.3. Алгоритм КРАБ 11
ГЛАВА 2. Вариационные алгоритмы автоматической классификации объектов на основе информационной меры однородности 15
2.1. Информационная мера однородности на основе энтропии 16
2.2. Функционал качества разбиения учитывающий равномерности основных параметров характеризующих разбиение 18
2.3. Функционал качества разбиения учитывающий однородность внутриклассовых расстояний. 29
ГЛАВА 3. Программная поддержка вариационного алгоритма автоматической классификации объектов и алгоритма распознавания образов на основе информационной меры однородности 31
3.1. Обоснование выбора аппаратно – программной 31
платформы дляпрототипа системы классификации 31
объектов и распознавания образов 31
3.2. Основные функции прототипа системы и их использование 33
3.3. Описание структуры данных прототипа системы 35
3.4. Описание пользовательского интерфейса прототипа системы 40
3.5. Вычислительные эксперименты 54
ЗАКЛЮЧЕНИЕ 58
ЛИТЕРАТУРА 61
Приложение №1 Программный код модуля классификации и распознания 6

Известно, что одно из центральных мест в прикладном анализе эмпирических данных занимает задача автоматического агрегирования элементов различной природы. Данная задача имеет достаточно большую область применений, например: в кибернетике, управлении, принятии решений, экономике, социологии, медицине, геологии, астрономии, биологии и т. п. Решением задачи автоматической классификации объектов является такое разбиение исходного множества анализируемых объектов без участия человека на непересекающиеся подмножества, в которых содержатся только сходные, близкие друг к другу в заданном признаковом пространстве, в некотором, возможно неизвестном, но объективно существующем отношении [1].
Современные методы решения задач классификации объектов базируются на двух основных подходах: эвристическом и вариационном. Вариационный подход наиболее приемлем для решения задачи автоматического агрегирования элементов, хотя и в данном подходе присутствует эвристическая составляющая при построении функционала качества разбиения, экстремальное значение которого соответствует наилучшему разделению в интуитивном понимании исследователя. В некоторых работах обращается внимание на степень однородности (похожести) объектов внутри каждого класса, которая должна быть учтена в функционале качества разбиения. В данной работе предложен критерий однородности, основанный на информационной мере в виде аналога энтропии по Шеннону, который может быть использован при конструировании функционалов, учитывающих степень однородности (похожести) объектов внутри каждого класса [6].
В настоящее время существует множество методов автоматической классификации объектов, в том числе и вариационных. Каждый из них обладает своими преимуществами и недостатками, оптимального метода пока не найдено. Из этого можно сделать вывод, что задача классификации не является решенной в достаточной степени хорошо. В связи с острой необходимостью решения подобных задач и постоянным увеличением вычислительных мощностей ЭВМ попытка использования вариационных алгоритмов для их решения становится весьма актуальной.
В данной работе предлагается использовать меру информационной однородности, разработанную в последние годы на факультете, для конструирования функционалов. Принцип максимальной однородности разбиения был предложен в работах Загоруйко, как модель действия человека при неавтоматической классификации. Существенным отличием предлагаемого подхода является использование в качестве общей меры однородности функционала, который построен на основе комбинации информационных мер однородностей отдельных характеристик (классов, размеров классов, расстояний между классами, количеств элементов в классе). Таким образом реализуемый подход будет обладать существенной новизной по сравнению с используемыми методами. На этой основе нами было сконструировано два функционала, подлежащих исследованию в данной работе. Первый уже некоторое время исследуется, второй был сконструирован недавно и предлагается как альтернатива первому.

Цель:
Исследование ранее созданного вариационного функционала на основе информационной меры однородности и разработка нового алгоритма автоматической классификации объектов на основе функционала, подлежащего максимизации.

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

16. Маматов Е.М. Оценка информативности признаков при решении задач классификации объектов. // Потребительская кооперация России на пороге третьего тысячелетия: Сборник научных трудов участников научно-практической конференции профессорско-преподавательского состава. Ч.2 – Белгород: Изд-во БУПК, 1999, с.165-175.
Приложение №1
Программный код модуля классификации и распознания
//---------------------------------------------------------------------------
#ifndef DinamicH
#define DinamicH
//---------------------------------------------------------------------------
#include "system.hpp"
typedef double** DoublePointer;
struct TTreeObject
{
int Id1, Id2;
double Metrix;
int Class;
};
enum MetrixMode
{mEuclid, mManhattan, mChebishev, mMinkovsky};
enum UniformityMode
{umNegEntropia,umRepresentativeness};
class ClassGroupData
{
public:
double **MetrixMatrix;//Матрица расстояний
TTreeObject *TreeMatrix; //Матрица деерва
//Визуализаци работы функционала (статистика)
//Массивы значений
double *Fs;
double *Ds;
double *Hs;
double *Rs;
double *Gs;
//________________
//Предельные значения
double DMax;
double HMax;
double GMax;
double RMax;
double FuncMax;
double DMin;
double HMin;
double GMin;
double RMin;
double FuncMin;
//_____________________
bool *GraphCuts; //Номера разрезанных ребер
/////////////////////////////////////////////
double **ClassInform; //Информация о классах
double **ClassMatrix; //Информация об объектах
double *ObjectParams; //Параметры объекта передаваемого для распознания
int ProstrSize; //Размерность пространства
int NumberOfObjects; //Общее количество объектов набора
int NumberOfClasses; //Общее количество классов набора
int ClassInformSize; //Количество столбцов матрицы классов
int ClassMatrixSize; //Количество столбцов матрицы объектов
String ClassGroupId; //Название класса
void InitClassMatrix(int ObjNum); //Инициализация матрицы классов и массивов значений
void InitMetrixMatrix(void); //Выделение памяти под матрицу расстояний
void InitTreeMatrix(void); //Выделение памяти под матрицу дерева
ClassGroupData(String CGID, int PrSize, int ClassNum,int ObjNum); //Конструктор c количеством объектов
ClassGroupData(String CGID, int PrSize, int ClassNum); //Конструктор
~ClassGroupData(void); //Деструктор
int GetNumberOfObjectsFromClassInform(void); //Получение количества классов из марицы
void EvMetrixCalc(void); //Вычисление расстояний в матрицу расстояний MetrixMatrix (предварительно ее надо инициализировать)
double GetMetrix(int a,int b); //Получение расстояния между объектами(нумерация с ноля)
double GetMetrix(int a,int b,double **Matrix); //Получение расстояния между объектами(нумерация с ноля) в некоторой матрице
double CalcMu(int,int,int, double **);
double CalcRo (int, int, double);
void Classificate (void);
void GenerateSourceData(int MaxClassObjNum);
void GenerateObjectData(void);
void DoUseWeights(bool mode); //0- Не использ 1-Использ
int Recognize(bool mode, double D, double Rk);//mode=true: 1 объект, предварительно задаваемый
//mode=false: генерация множества объектов и оценка работы метода
void SortTreeMatrix(void); //Сортировка ребер по возрастанию
void QuickSortTreeMatrix(void); //Нахождение max ребра и установка его на первую позиция
void CutTree(int PointA,int PointB,int ClassToCut, int ClassToSet); //Разрезание дерева
void SetNonClass(int PointA,int PointB);
void BackUpClasses(int *, int *);
void RestoreClasses(int *, int *);
double GetRibMetrixByNum(int ClassNum, int RibNumInClass);
int GetRibNo (int PointA, int PointB);
int B_Sk ( double **CenterMassMatrix, double *epsilan, int No);
void SetObjectToRecognize (double *params);
void SetMetrixMode(MetrixMode mModeToSet);
void SetUniformityMode(UniformityMode uModeToSet);
void SetMinkovskyStepen (int stepen);
void UndoClassificationResults(void);
int Classifired;
private:
double ** GetMemory(int, int); //Выделение памяти
void FreeMemory(DoublePointer &,int); //Очистка памяти
double ** GetMetrixMemory(int); //Выделение памяти треугольником
void BuildTree(void); //Построение дерева
double Absolute(double);
bool UseWeight;
MetrixMode mMode; //Режим расчета расстояний (Евклидово, Манхеттенское)
UniformityMode uMode; //Используемый функционал
int MinkovskyStepen; //Степень расстояния минковского
double *global_weight_vector; //Вектор весов признаков
};
extern ClassGroupData *TempClassGroup;
#endif
//---------------------------------------------------------------------------
#pragma hdrstop
#include "Dinamic.h"
#include "system.hpp"
#include <Math.h>
#include <values.h>
#include <vcl.h>
#include <stdio.h>
//---------------------------------------------------------------------------
#pragma package(smart_init)
ClassGroupData *TempClassGroup=0;
//++++++++++++++++++++++++ClassGroupData+++++++++++++++++++++++++++
void ClassGroupData::CutTree(int PointA,int PointB,int ClassToCut, int ClassToSet)
{
int tempId,i,j;
for (i=0; i<NumberOfObjects-1;i++)
{
if ((TreeMatrix[i].Id1==PointA)&&
(TreeMatrix[i].Id2!=PointB)&&
((ClassMatrix[TreeMatrix[i].Id1][1]==ClassToCut)||
(ClassMatrix[TreeMatrix[i].Id1][1]==ClassToSet)))
{
TreeMatrix[i].Class=ClassToSet;
ClassMatrix[PointA][1]=ClassToSet;
CutTree(TreeMatrix[i].Id2,TreeMatrix[i].Id1,ClassToCut, ClassToSet);
};
if ((TreeMatrix[i].Id2==PointA)&&
(TreeMatrix[i].Id1!=PointB)&&
((ClassMatrix[TreeMatrix[i].Id1][1]==ClassToCut)||
(ClassMatrix[TreeMatrix[i].Id1][1]==ClassToSet)))
{
ClassMatrix[PointA][1]=ClassToSet;
TreeMatrix[i].Class=ClassToSet;
CutTree(TreeMatrix[i].Id1,TreeMatrix[i].Id2,ClassToCut, ClassToSet);
}
};
if ((ClassMatrix[PointA][1]==ClassToCut)||
(ClassMatrix[PointA][1]==ClassToSet))
ClassMatrix[PointA][1]=ClassToSet;
/*Данная функция разрезает КМП по заданному ребру (ребро задается
как две точки PointA и PointB). Класс определяется в сторону
ветвления дерева от точки PointA. Переменная ClassToCut показывает
какой из уже существующих классов необходимо порезать. ClassToSet
определяет, какой номер присвоить только что получившемуся классу*/
}
//_____________________Выделение памяти____________________________
double ** ClassGroupData::GetMemory(int rowsNo, int colsNo)
{
double **getting;
getting=new double *[rowsNo];
for (int i=0; i<rowsNo;i++) getting[i]=new double [colsNo*2+3];
return getting;
}
//_________________________________________________________________
//___________________________Очистка памяти________________________
void ClassGroupData::FreeMemory(DoublePointer &destroing,int rowsNo)
{
for (int i=0;i<rowsNo;i++)
{
delete[] destroing[i];
};
delete[] destroing;
destroing=NULL;
}
//__________________________________________________________________
//________________________Консчтрукторы_________________________________________
//1.
ClassGroupData::ClassGroupData(String CGID, int PrSize, int ClassNum,int ObjNum)
{
int i;
MetrixMatrix=0;
ObjectParams=0;
TreeMatrix=0;
ClassInform=0;
ClassMatrix=0;
ProstrSize=PrSize;
ClassInformSize=3+PrSize*2;
ClassMatrixSize=PrSize+2;
ClassGroupId=CGID;
NumberOfObjects=ObjNum;
NumberOfClasses=ClassNum;
ClassInform=GetMemory(NumberOfClasses, ClassInformSize);
for (i=0;i<NumberOfClasses;i++) ClassInform[i][0]=i+1;
ClassMatrix=GetMemory(NumberOfObjects, ClassMatrixSize);
for (i=0;i<NumberOfObjects;i++) ClassMatrix[i][0]=i+1;
Classifired=0;
mMode=0;
uMode=0;
UseWeight=false;
global_weight_vector=new double [ProstrSize];
for (i=0;i<ProstrSize;i++)
{
global_weight_vector[i]=1;
};
GraphCuts=new bool [NumberOfObjects-1];
Fs=new double [NumberOfObjects-1];
Ds=new double [NumberOfObjects-1];
Hs=new double [NumberOfObjects-1];
Gs=new double [NumberOfObjects-1];
Rs=new double [NumberOfObjects-1];
DMax=0;
HMax=0;
GMax=0;
RMax=0;
FuncMax=0;
DMin=1;
HMin=1;
GMin=1;
RMin=1;
FuncMin=MAXDOUBLE;
}
//2.
ClassGroupData::ClassGroupData(String CGID, int PrSize, int ClassNum)
{
int i;
MetrixMatrix=0;
TreeMatrix=0;
ClassInform=0;
ClassMatrix=0;
ObjectParams=0;
ProstrSize=PrSize;
ClassInformSize=3+PrSize*2;
ClassMatrixSize=PrSize+2;
ClassGroupId=CGID;
NumberOfClasses=ClassNum;
ClassInform=GetMemory(NumberOfClasses, ClassInformSize);
for (i=0;i<NumberOfClasses;i++) ClassInform[i][0]=i+1;
ClassMatrix=0;
Classifired=0;
mMode=0;
uMode=0;
UseWeight=false;
global_weight_vector=new double [ProstrSize];
for (i=0;i<ProstrSize;i++)
{
global_weight_vector[i]=1;
};
DMax=0;
HMax=0;
GMax=0;
RMax=0;
FuncMax=0;
DMin=1;
HMin=1;
GMin=1;
RMin=1;
FuncMin=MAXDOUBLE;
}
//________________________________________________________________________________
//_________________________Деструктор_____________________________________________
ClassGroupData::~ClassGroupData(void)
{
FreeMemory(ClassInform, NumberOfClasses);
if (ClassMatrix!=0)FreeMemory(ClassMatrix, NumberOfObjects);
if (MetrixMatrix!=0)FreeMemory(MetrixMatrix, NumberOfObjects);
if (TreeMatrix!=0) delete[] TreeMatrix;
if (ObjectParams!=0) delete[] ObjectParams;
Classifired=0;
delete[] global_weight_vector;
delete[] Fs;
delete[] Ds;
delete[] Hs;
delete[] Gs;
delete[] Rs;
delete[] GraphCuts;
}
//_________________________________________________________________________________
void ClassGroupData::DoUseWeights(bool mode)
{
int i,j,n;
double *sigma;
double ** ClassMatrixForWeight;
double temp;
if (mode)
{
ClassMatrixForWeight=GetMemory(NumberOfObjects, ProstrSize);
sigma=new double [NumberOfObjects-1];
temp=MAXDOUBLE;
for (i=0;i<ProstrSize;i++) global_weight_vector[i]=0;
for (n=0;n<ProstrSize;n++)//Копирование матрицы
{
for (i=0;i<NumberOfObjects;i++)
{
ClassMatrixForWeight[i][n]=ClassMatrix[i][n+2];
};
};
for (n=0;n<ProstrSize;n++)//Упорядочивание матрицы повозрастанию по признакам
{
for (i=0;i<NumberOfObjects;i++)
{
for (j=i;j<NumberOfObjects;j++)
{
if (ClassMatrixForWeight[i][n]>ClassMatrixForWeight[j][n])
{
temp=ClassMatrixForWeight[j][n];
ClassMatrixForWeight[j][n]=ClassMatrixForWeight[i][n];
ClassMatrixForWeight[i][n]=temp;
};
};
};
};
for (n=0;n<ProstrSize; n++)//Непосредственный расчет весов
{
for (i=0;i<NumberOfObjects-1;i++)
{
sigma[i]=ClassMatrixForWeight[i+1][n]-ClassMatrixForWeight[i][n];
};
temp=0;
for (i=0;i<NumberOfObjects-1;i++)
{
temp+=sigma[i];
};
for (i=0;i<NumberOfObjects-1;i++)
{
sigma[i]/=temp;
};
for (i=0;i<NumberOfObjects-1;i++)
{
if (sigma[i]==0) sigma[i]=0.00000000000000001;
global_weight_vector[n]+=sigma[i]*log(sigma[i])/log(NumberOfObjects-1);
};
global_weight_vector[n]=-global_weight_vector[n];
};
FreeMemory (ClassMatrixForWeight, NumberOfObjects);
delete[] sigma;
} else
{
for (i=0;i<ProstrSize;i++) global_weight_vector[i]=1;
};
};
//________________Инициация ClassMatrix____________________________________________
void ClassGroupData::InitClassMatrix(int ObjNum)
{
int i;
if (ClassMatrix==0)
{
NumberOfObjects=ObjNum;
ClassMatrix=GetMemory(NumberOfObjects,ClassMatrixSize);
for (i=0;i<ObjNum;i++) ClassMatrix[i][0]=i+1;
};
GraphCuts=new bool [NumberOfObjects-1];
Fs=new double [NumberOfObjects-1];
Ds=new double [NumberOfObjects-1];
Hs=new double [NumberOfObjects-1];
Gs=new double [NumberOfObjects-1];
Rs=new double [NumberOfObjects-1];
}
//_________________________________________________________________________________
//_________________Получение количества объектов из матрицы ClassInform____________
int ClassGroupData::GetNumberOfObjectsFromClassInform(void)
{
int i, NumberOfObjects=0;
for (i=0;i<NumberOfClasses;i++) NumberOfObjects+=ClassInform[i][1];
return NumberOfObjects;
}
//_________________________________________________________________________________
//_______________________________Выделение памяти треугольником____________________
double **ClassGroupData::GetMetrixMemory(int n)
{
double **getting;
int k=0;
getting=new double *[n];
for (int i=0; i<n;i++) getting[i]=new double [++k];
return getting;
}
//__________________________________________________________________________________
void ClassGroupData::SetMetrixMode(MetrixMode mModeToSet)
{
mMode=mModeToSet;
};
//_________________________Выделение памяти под матрицу расстояний__________________
void ClassGroupData::InitMetrixMatrix(void)
{
MetrixMatrix=GetMetrixMemory(NumberOfObjects);
}
//__________________________________________________________________________________
//_________________________Выделение памяти под матрицу дерева______________________
void ClassGroupData::InitTreeMatrix(void)
{
int i;
TreeMatrix=new TTreeObject [NumberOfObjects-1];
for (i=0;i<NumberOfObjects-1;i++) TreeMatrix[i].Class=0;
}
//__________________________________________________________________________________
//____________________________Расчет расстояний_____________________________________
void ClassGroupData::EvMetrixCalc(void)
{
int i,j,n;
double sum=0;
for (i=0;i<NumberOfObjects;i++)
{ for (j=0;j<=i;j++)
{
for (n=2;n<=ProstrSize+1;n++) sum+=pow((ClassMatrix[i][n]-ClassMatrix[j][n]),2);
MetrixMatrix[i][j]=sqrt(sum);
sum=0;
};
};
};
//___________________________________________________________________________________
double ClassGroupData::Absolute(double Arg) //Модуль
{
if (Arg<0) Arg*=-1;
return Arg;
};
//__________________Получение расстояния между объектами_____________________________
double ClassGroupData::GetMetrix(int a, int b)
{
int n;
double sum=0;
if (mMode==mEuclid)
{
for (n=2;n<=ProstrSize+1;n++) sum+=pow((ClassMatrix[a][n]-ClassMatrix[b][n])* global_weight_vector[n-2],2);
sum=sqrt(sum);
return sum;
};
if (mMode==mManhattan)
{
for (n=2;n<=ProstrSize+1;n++) sum+=Absolute(ClassMatrix[a][n]-ClassMatrix[b][n])* global_weight_vector[n-2];
return sum;
};
if (mMode==mChebishev)
{
double temp=0;
for (n=2;n<=ProstrSize+1;n++)
{
temp=Absolute(ClassMatrix[a][n]-ClassMatrix[b][n])* global_weight_vector[n-2];
if (temp>sum) sum=temp;
};
return(sum);
};
if (mMode==mMinkovsky)
{
for (n=2;n<=ProstrSize+1;n++) sum+=pow(Absolute(ClassMatrix[a][n]-ClassMatrix[b][n])* global_weight_vector[n-2],MinkovskyStepen);
sum=pow(sum, 1/float(MinkovskyStepen));
return sum;
};
}
//_____________________________________________________________________________________
//__________________Получение расстояния между объектами_____________________________
double ClassGroupData::GetMetrix(int a, int b, double **Matrix)
{
int n;
double sum=0;
if (mMode==mEuclid)
{
for (n=0;n<ProstrSize;n++) sum+=pow((Matrix[a][n]-Matrix[b][n])* global_weight_vector[n],2);
sum=sqrt(sum);
return sum;
};
if (mMode==mManhattan)
{
for (n=0;n<ProstrSize;n++) sum+=Absolute(Matrix[a][n]-Matrix[b][n])* global_weight_vector[n];
return sum;
};
if (mMode==mChebishev)
{
double temp=0;
for (n=0;n<ProstrSize;n++)
{
temp=Absolute(Matrix[a][n]-Matrix[b][n])* global_weight_vector[n];
if (temp>sum) sum=temp;
};
return(sum);
};
if (mMode==mMinkovsky)
{
for (n=0;n<ProstrSize+1;n++)
sum+=pow(Absolute(ClassMatrix[a][n]-ClassMatrix[b][n])* global_weight_vector[n],MinkovskyStepen);
sum=pow(sum, 1/float (MinkovskyStepen));
return sum;
};
}
//_____________________________________________________________________________________
void ClassGroupData::SetMinkovskyStepen (int stepen)
{
MinkovskyStepen=stepen;
};
void ClassGroupData::BuildTree(void)
{
int k ,i,j,i1,j1, n=NumberOfObjects,m;
int *Col;
double dmin;
Col=new int [NumberOfObjects];
for (k=0;k<n;k++) Col[k]=k;
k=0;
while (k<(n-1))