?? covernn.cpp
字號:
// CoverNN.cpp: implementation of the CoverNN class.
//
//////////////////////////////////////////////////////////////////////
#include "CoverNN.h"
#include <math.h>
#include <fstream.h>
#include <time.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CoverNN::CoverNN()
{
InnPro = false;//采用內積
Covers = new CovCell;//建立一個頭結點，便于連接鏈表
}
CoverNN::~CoverNN()
{
CovCell * p ;
p = Covers;
while(p!=NULL)
{
Covers = Covers->next;
delete[] p->center;
delete p;
p = Covers;
}
}
////////////////////////////////////////////////////////////
// 學習樣本數據的格式：
// LINE1：訓練樣本總數 樣本輸入維數
// LINEi：樣本值 類別
////////////////////////////////////////////////////////////
//////////////根據文件名載入學習數據或測試數據/////////////////
int CoverNN::LoadData( const char * fn_dat, const bool train)
{
int i,j;
ifstream inf( fn_dat );
inf>>Num>>Dim_in;
Data = new double*[Num];
Target = new int[Num];
for(i=0;i<Num;i++)
{
Data[i] = new double[Dim_in+1];
for(j=0;j<Dim_in;j++)
{
inf>>Data[i][j];
}
inf>>Target[i];
}
inf.close();
if(train)
{
NoCov = new bool[Num];
for(i=0;i<Num;i++)
{
NoCov[i] = true;
}
}
return 0;
}
/////////訓練網絡////////////////
void CoverNN::Train()
{
int i,j;
R = 0;
for(i=0;i<Num;i++)
{
Data[i][Dim_in] = 0;
for(j=0;j<Dim_in;j++)
{
Data[i][Dim_in] += Data[i][j] * Data[i][j];
}
if(R < Data[i][Dim_in])
{
R = Data[i][Dim_in];
}
}
R = sqrt(R) * 1.5;
//將樣本數據進行投影
for(i=0;i<Num;i++)
{
Data[i][Dim_in] = sqrt(R*R - Data[i][Dim_in]);
}
//------------開始循環求覆蓋------------------
Num_C = 0;
CovCell * p;
p = Covers;
CovCell * pcell;
int kind = -1;
while( !IsFinished( kind ) )
{
//----------------跳過已經被覆蓋的樣本---------------
i = 0 ;
while(!NoCov[i] && i<Num)
{
i++;
}
//----------------初始化覆蓋的中心------------------
pcell = new CovCell;
pcell->center = new double[Dim_in+1];
for(j=0;j<=Dim_in;j++)
{
pcell->center[j] = Data[i][j];
}
pcell->kind = Target[i];
//
GetCovCell(*pcell);//得到一個覆蓋
p->next = pcell;
p = p->next;
Num_C++;//覆蓋數加1
kind = -1;
}
//--------------對最后一個覆蓋的處理------------
pcell = new CovCell;
pcell->center = new double[Dim_in+1];
for(i=0;i<Dim_in;i++)
{
pcell->center[i] = 0;
}
pcell->center[Dim_in] = R;//覆蓋中心在半球面的最頂端
pcell->kind = kind;//覆蓋類別為剩余的樣本點的類別
if(InnPro)//覆蓋閾值分情況取值
{
pcell->threshold = 0;
}
else
{
pcell->threshold = R;
}
p->next = pcell;
Num_C++;
//----------學習完畢后，清理學習數據所占的內存------------
delete[] NoCov;
delete[] Data;
delete[] Target;
}
/////判斷訓練是否可以結束///////////
bool CoverNN::IsFinished(int &kind)
{
bool yes = true;
for(int i=0;i<Num;i++)//遍歷所有樣本點
{
if(NoCov[i])//尋找未被覆蓋的樣本
{
if(kind == -1)
{
kind = Target[i];
}
else if(kind != Target[i])//如果還有不同類的樣本，則不能結束
{
yes = false;
break;
}
}
}
return yes;
}
///////判斷樣本是否被覆蓋/////////
bool CoverNN::IsCovered( const CovCell &cell, double * dat)
{
double tmp = 0;
int i;
if(InnPro)//------采用內積-------
{
for(i=0;i<=Dim_in;i++)
{
tmp += cell.center[i] * dat[i];
}
return (tmp > cell.threshold);
}
else///--------采用距離---------
{
for(i=0;i<=Dim_in;i++)
{
tmp += pow( (cell.center[i] - dat[i]) , 2);
}
tmp = sqrt( tmp );
return (tmp < cell.threshold);
}
}
////////判斷前一個集合是否為后一個的真子集///////////
bool CoverNN::IsRealSubset(const bool * subset, const bool * superset)
{
bool yes = true;
int i,k = 0;
for(i=0;i<Num;i++)
{
if(subset[i] && !superset[i])
{
yes = false;
break;
}
else if(superset[i] && !subset[i])
{
k++;
}
}
return (yes && k>0);
}
//////求一個覆蓋//////////////////
int CoverNN::GetCovCell(CovCell &cell)
{
CovCell cell_old;
cell_old.center = new double[Dim_in+1];
cell_old.kind = cell.kind;
double temp;
double farthest,nearest;//farthest代表本類樣本，nearest代表非本類樣本
int covd_num[] = { 0 , 0 };
double * cen_tmp = new double[Dim_in];//求覆蓋的樣本個數,同時保存得到覆蓋的臨時中心(只需要前Dim_in維)
int i;
bool * sfx[2];
sfx[0] = new bool[Num];//用來保存sfx[1]
sfx[1] = new bool[Num];//用來標記本次被覆蓋的點的下標，被覆蓋標記為true
for(i=0;i<Num;i++)
{
sfx[0][i] = sfx[1][i] = false;
}
bool isrealsub;
bool end_tag = true;
bool needtrans = true;
while(end_tag)
{
nearest = Nearest_non(cell);
farthest = Farthest_kin(cell,nearest);
cell.threshold = (nearest + farthest)/2;//原算法的閾值求法
// cell.threshold = nearest - 3.1415926535*7/19.0;//修改算法
covd_num[1] = GetDomain( cell, cen_tmp, sfx[1]);
isrealsub = IsRealSubset(sfx[0],sfx[1]);//前一次覆蓋的點是后一次的真子集也就代表點數增多
if(covd_num[1]<covd_num[0])
{
if(needtrans)//如果還沒有平移過
{
GetTranslationpoint(cell);
needtrans = false;
}
}
if(isrealsub)
{
//------------保存本次的數據,同時求得重心---------------
temp = 0;
for(i=0;i<Dim_in;i++)
{
cell_old.center[i] = cell.center[i];
cell.center[i] = cen_tmp[i];
temp += cen_tmp[i] * cen_tmp[i];
}
cell_old.center[Dim_in] = cell.center[Dim_in];//保存本次的覆蓋中心
cell.center[Dim_in] = sqrt( R*R - temp);//投影后得到完整的新的覆蓋中心（重心）
cell_old.threshold = cell.threshold;//保存本次的閾值
covd_num[0] = covd_num[1];//保存本次的覆蓋樣本數
for(i=0;i<Num;i++)
{
sfx[0][i] = false;//先要將原來的全部清零，再重新賦值
if(sfx[1][i])
{
sfx[0][i] = true;
sfx[1][i] = false;
}
}
needtrans = true;//置標志位：可平移
//--------不求重心，而改求中心------
GetMidpoint(cell.center,sfx[0]);//結果：原始算法得到10個覆蓋
}
else if(needtrans)
{
//------------先保存本次的數據---------------
for(i=0;i<Dim_in;i++)
{
cell_old.center[i] = cell.center[i];
}
cell_old.center[Dim_in] = cell.center[Dim_in];//保存本次的覆蓋中心
cell_old.threshold = cell.threshold;//保存本次的閾值
covd_num[0] = covd_num[1];//保存本次的覆蓋樣本數
for(i=0;i<Num;i++)
{
sfx[0][i] = false;//先要將原來的全部清零，再重新賦值
if(sfx[1][i])
{
sfx[0][i] = true;
sfx[1][i] = false;
}
}
//-------------再進行平移----------------
GetTranslationpoint(cell);
needtrans = false;//置標志位：下次不可平移
}
else
{
end_tag = false;
}
}
//-----------得到一個覆蓋--------------
for(i=0;i<=Dim_in;i++)
{
cell.center[i] = cell_old.center[i];//保存當前覆蓋的中心（權值）
}
cell.threshold = cell_old.threshold;//保存當前覆蓋的閾值
for(i=0;i<Num;i++)
{
if(sfx[0][i])
{
NoCov[i] = false;//標記已覆蓋樣本
}
}
delete[] sfx[0];
delete[] sfx[1];
delete[] cen_tmp;
delete[] cell_old.center;
return 0;
}
///////求本次覆蓋蓋住的樣本數，并附帶求中心（即新的覆蓋中心）/////////////
int CoverNN::GetDomain(const CovCell &cell, double * cen, bool * sfx)
{
int result = 0;
int i,j;
for(i=0;i<Dim_in;i++)
{
cen[i] = 0;
}
for(i=0;i<Num;i++)
{
if(NoCov[i] && Target[i]==cell.kind)//屬于本類且未被覆蓋
{
if( IsCovered(cell, Data[i]) )
{
result++;
sfx[i] = true;
for(j=0;j<Dim_in;j++)
{
cen[j] += Data[i][j];
}
}
}
}
for(i=0;i<Dim_in;i++)//加和平均求得重心，只求得前Dim_in維的值，最后一維需投影
{
cen[i] = cen[i] / result;
}
return result;
}
////////////求非本類的距cen最近的樣本與cen的內積（或距離）////////////
double CoverNN::Nearest_non(const CovCell &cen)
{
double result , temp;
int i;
if(InnPro)//------采用內積-----
{
result = 0;
for(i=0;i<Num;i++)
{
if( NoCov[i] && Target[i]!=cen.kind )//未被覆蓋 且 非本類
{
temp = GetInnerProduct(cen.center,Data[i],Dim_in+1);
if(result < temp)
{
result = temp;
}
}
}
}
else//-------采用距離-------
{
result = 2*R;
for(i=0;i<Num;i++)
{
if( NoCov[i] && Target[i]!=cen.kind )//未被覆蓋 且 非本類
{
temp = GetDistance(cen.center,Data[i],Dim_in+1);
if(result > temp)
{
result = temp;
}
}
}
}
return result;
}
///////////求本類的距cen最遠的樣本與cen的內積（或距離）////////////
double CoverNN::Farthest_kin(const CovCell &cen, const double max)
{
double result , temp;
int i;
if(InnPro)//------采用內積-----
{
result = R * R;
for(i=0;i<Num;i++)
{
if( NoCov[i] && Target[i]==cen.kind )//本類 且 未被覆蓋
{
temp = GetInnerProduct(cen.center,Data[i],Dim_in+1);
if(temp > max && result > temp)
{
result = temp;
}
}
}
if(result == R*R)//如果未找到同類的其他樣本點，則設max=R*R*cos(2a)，result取R*R*cos(a)
{
result = result * sqrt( (result+max) / (2*result) );
}
}
else//-------采用距離-------
{
result = 0;
for(i=0;i<Num;i++)
{
if( NoCov[i] && Target[i]==cen.kind )//本類 且 未被覆蓋
{
temp = GetDistance(cen.center,Data[i],Dim_in+1);
if( temp < max && result < temp )
{
result = temp;
}
}
}
if(result==0)//如果未找到同類的其他樣本點，則取距離max的一半
{
result = max / 2;
}
}
return result;
}
//////////////求內積的內聯函數///////////////////////////////
inline double CoverNN::GetInnerProduct(const double* a, const double* b, const int dim)
{
double result = 0;
for(int i=0; i<dim; i++)
{
result += a[i]*b[i];
}
return result;
}
/////////////求距離的內聯函數/////////////////////////////////
inline double CoverNN::GetDistance(const double* a, const double* b, const int dim)
{
double result = 0;
for(int i=0; i<dim; i++)
{
result += pow( (a[i]-b[i]) , 2);
}
return sqrt(result);
}
//////////求平移點//////////////
int CoverNN::GetTranslationpoint( CovCell &cen )
{
int i,j,k = 0;
int * P_B = new int[Dim_in+1];
int allpt = 0, times = 0;
double d;
double * pt_proj = new double[Dim_in+1];//投影點（垂足）
double * temp = new double[Dim_in+1];
double ** Ei = new double*[Dim_in+1];
for(i=0;i<=Dim_in;i++)//Ei[0]并未使用
{
Ei[i] = new double[Dim_in+1];
}
k = GetSet_minDist(cen, P_B);//求與oldPt距離最近的非本類的樣本點集，返回值為樣本點的個數
if(k==0)//如果k==0則平移出錯，函數返回
return 1;
for(i=0;i<Num;i++)//-----------如果無法找到足夠的點，將終止循環--------------
{
if(NoCov[i] && Target[i] != cen.kind)
{
allpt++;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -