开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 人工智能/神经网络 > 查看源码
面向对象的模拟退火编程技术.cpp
资源名称：K－均值聚类算法C++编程.rar　[点击查看]
上传用户：bonzan
上传日期：2007-04-15
资源大小：4k
文件大小：13k
源码类别：

人工智能/神经网络

开发平台：

Visual C++

面向对象的模拟退火编程技术.cpp：源码内容
  1. //***********引入库函数
  3. #include "iostream.h"
  4. #include "math.h"
  5. #include "stdlib.h"
  6. #include "iomanip.h"
  7. #include "time.h"
  8. #include "fstream.h"
  10. //*************定义常量
  11. const int TRUE=1;
  12. const int FALSE=0;
  13. const int MarkovLengh=10000;
  14. const int MaxInnerLoop=10000;
  15. const int MaxOuterLoop=60;
  16. const double CO=0.1;
  17. const double DeclineRate=0.95;
  18. const long MAX=100000;
  19. const int AcceptRate=1;
  20. const double ForceDecline=0.9;
  23. //************定义全局变量
  25. int DataNum;               //聚类样本数目
  26. int Dimension;             //样本维数
  27. int K;                     //分类数
  28. double *DataSet;            //指向浮点型的指针
  29. int HALT=0;
  30. int Row=3;
  34. //***************************************************************
  35. //  类 GETDATA： 设定全局变量，维数，样本数，和类别数等         ***  
  36. //               随机生成样本或手工输入样本的类               ***
  37. //***************************************************************
  40. class GETDATA{
  42. public:
  43. GETDATA();
  44. void Display();
  45. void Initial();
  46. void Input();
  47. double FRand(double,double);
  48.     double rand1,rand2;          //随机数的高低值
  50. };
  52. GETDATA::GETDATA()
  53. {
  54. int i,j;
  55. Dimension=2;
  56. DataNum=50;
  57. K=4;
  58. DataSet=new double[Dimension*DataNum];
  59. for(i=0;i<DataNum;i++)
  60. {
  61. for(j=0;j<Dimension;j++)
  62. DataSet[i*Dimension+j]=(((double)rand()/(double)RAND_MAX)*100);
  63. }
  64. } 
  66. //*****************显示当前待聚类的样本(维数，个数，类别数等)
  68. void GETDATA::Display()
  69. {
  70. int i,j;
  71. cout<<" 当前样本集如下:"<<endl<<" {"<<endl;
  72. for(i=0;i<DataNum;i++)
  73. {
  74. cout<<" [";
  75. for(j=0;j<Dimension;j++)
  76. {
  77.     cout<<" "<<setw(8)<<DataSet[i*Dimension+j];
  78. }
  79. cout<<" ]  ";
  80. if((i+1)%Row==0)
  81. cout<<endl;
  82. }
  83.     cout<<endl<<" }"<<endl;
  85. cout<<endl<<" 以上实数样本集由计算机在1---100之间随机产，其中："<<endl;
  87. cout<<endl<<" 样本维数 Dimension= "<<Dimension<<endl;
  88. cout<<" 样本数   DataNum= "<<DataNum<<endl;
  89. cout<<" 类别数   K= "<<K<<endl;
  90. }
  93. //****************输入待聚类样本，包括维数，个数，类别数等
  95. void GETDATA::Input()
  96. {
  97. char flag;
  98. int i,j;
  99. double s=0;
  100. cout<<endl<<" 请依次输入: 维数  样本数目  类别数"<<endl;
  101. cout<<endl<<" 维数 Dimension: ";
  102. cin>>Dimension;
  103. cout<<endl<<" 样本数目 DataNum: ";
  104. cin>>DataNum;
  105. cout<<endl<<" 类别数 K：";
  106. cin>>K;
  107. cout<<endl<<" 随机生成数据输入R  人工输入按B: "<<endl; delete[]DataSet;
  108. DataSet=new double[Dimension*DataNum];
  109. cin>>flag;
  110. if(flag=='R'||flag=='r')
  111. {
  112. cout<<" 输入随机数生成范围(最小值和最大值):"
  113. <<endl<<" 最小值：";
  114. cin>>rand1;
  115. cout<<endl<<" 最大值：";
  116. cin>>rand2;
  117. for(i=0;i<DataNum;i++)
  118. {
  119. for(j=0;j<Dimension;j++)
  120. DataSet[i*Dimension+j]=FRand(rand1,rand2);
  121. }
  123. }
  124. else
  125. if(flag=='H'||flag=='h')
  126. {
  127. for(i=0;i<DataNum;i++)
  128. {
  129. cout<<endl<<" 请输入第"<<i+1<<" 个样本的"<<Dimension<<" 个分量";
  130. for(j=0;j<Dimension;j++)
  131. cin>>DataSet[i*Dimension+j];
  132. }
  133. }
  134. else 
  135. cout<<endl<<" 非法数据！ ";
  136. }
  138. //****************初始化聚类样本
  140. void GETDATA::Initial()
  141. {
  142. char ch;
  143. GETDATA::Display();
  144. cout<<endl<<" 重新录入样本输入A  开始聚类B: ";
  145. cin>>ch;
  146. while(!(ch=='A'||ch=='a')&&!(ch=='B'||ch=='b'))
  147. {
  148. cout<<endl<<" 重新录入样本输入A  开始聚类B: ";
  149. cin>>ch;
  150. }
  152. if(ch=='A'||ch=='a')  
  153. GETDATA::Input();
  154. }
  156. double GETDATA::FRand(double rand1,double rand2)
  157. {
  158. return rand1+(double)(((double)rand()/(double)RAND_MAX)*(rand2-rand1));
  159. }
  164. //***********************************************************
  165. // 类SSA:    K-均值算法的实现                           ***  
  166. //           功能：根据设定的K,DataNum,Dimension等聚类    ***
  167. //***********************************************************
  169. class SAA
  170. {
  171. public:
  172. struct DataType
  173. {
  174. double *data;
  175. int father;
  176. double *uncle;
  177. };
  179. struct ClusterType
  180. {
  181. double *center;
  182. int sonnum;
  184. };
  186. SAA();
  187. void Initialize();
  188. void KMeans();
  189. void SA( );
  190. void DisPlay();
  193. void GetDataset(DataType *p1,double *p2,int datanum,int dim);
  194. void GetValue(double *str1,double *str2,int dim);
  195. int  FindFather(double *p,int k);
  196. double SquareDistance(double *str1,double *str2,int dim);
  197. int Compare(double *p1,double *p2,int dim);
  198. void NewCenterPlus(ClusterType *p1,int t,double *p2,int dim);
  199. void NewCenterReduce(ClusterType *p1,int t,double *p2,int dim);
  200. double MaxFunc();
  201. void Generate(DataType *p1,ClusterType *c1);
  202. double Compare(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
  203. void CopyStatus(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
  204. int  SecondFather(DataType *p,int t,int k);
  205. double AimFunction(DataType *q,ClusterType *c);
  206. double FRand(double ,double);
  207. void KMeans1();
  209. protected:
  211. double Temp;
  212. //double CO;
  213. //double DeclineRate;
  214. //int MarkovLengh;
  215. //int MaxInnerLoop;
  216. //int MaxOuterLoop;
  217. double AimFunc;
  219. DataType *DataMember, *KResult,*CurrentStatus,*NewStatus;
  220. ClusterType * ClusterMember,*NewCluster,*CurrentCluster;
  221.  
  222. }; //end of class SAA
  226. //************建立构造函数，初始化保护成员
  227. SAA::SAA()
  228. {
  229. int i;
  230. // DeclineRate=(double)0.9;
  231. // MarkovLengh=1000;
  232. // MaxInnerLoop=200;
  233. // MaxOuterLoop=10;
  234. // CO=1;
  237. DataMember=new DataType[DataNum];
  238. ClusterMember=new ClusterType[K];
  240. for(i=0;i<DataNum;i++)
  241. {
  242. DataMember[i].data=new double[Dimension];
  244. DataMember[i].uncle=new double[K];
  245. }
  246. for(i=0;i<K;i++)
  247. ClusterMember[i].center=new double[Dimension];
  249. GetDataset(DataMember,DataSet,DataNum,Dimension);
  252. }//endSAA
  255. //****************初始化参数，及开始搜索状态
  257. void SAA::Initialize( )
  258. {
  260. //K-均值聚类法建立退火聚类的初始状态
  261. // KMeans();
  263.  
  264. }
  266. //*******************k-均值法进行聚类
  267. //************接口：数据，数量，维数，类别
  268. //逐点聚类方式
  270. void SAA::KMeans()
  271. {
  273. int i,j,M=1;
  274. int pa,pb,fa;
  275. ClusterType *OldCluster;
  277. //初始化聚类中心
  279. OldCluster=new ClusterType[K];
  280. for(i=0;i<K;i++)
  281. {
  282. // cout<<endl<<i+1<<"中心：";
  283. GetValue(ClusterMember[i].center,DataMember[i].data,Dimension);
  284. ClusterMember[i].sonnum=1;
  286. OldCluster[i].center=new double[Dimension];
  287. GetValue(OldCluster[i].center,ClusterMember[i].center,Dimension);
  288. }
  291. for(i=0;i<DataNum;i++)  
  292. {
  293. // cout<<endl<<i+1<<": "<<ClusterMember[0].center[0]<<" "<<ClusterMember[1].center[0]<<" son: "<<ClusterMember[0].sonnum;
  294. for(j=0;j<K;j++)
  295. {
  296. DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
  297. // cout<<"   "<<i+1<<"->"<<j+1<<": "<<DataMember[i].uncle[j];   //"类中心 "<<ClusterMember[j].center[0]<<": "<<DataMember[i].uncle[j]<<"  ";
  298. }
  299. pa=DataMember[i].father=FindFather(DataMember[i].uncle,K);
  300. if(i>=K)
  301. {
  302. // cout<<endl<<pa<<" 类样本数："<<ClusterMember[pa].sonnum;
  303. ClusterMember[pa].sonnum+=1;
  304. // cout<<endl<<pa<<" 类样本数："<<ClusterMember[pa].sonnum;
  305. NewCenterPlus(ClusterMember,pa,DataMember[i].data,Dimension);
  306. // cout<<endl<<i+1<<"->"<<pa+1<<"类  :"<<ClusterMember[pa].center[0];
  307. GetValue(OldCluster[pa].center,ClusterMember[pa].center,Dimension);
  308. } 
  309. }
  311. //开始聚类，直到聚类中心不再发生变化。××逐个修改法××
  312. while(!HALT)
  313. {
  314. //一次聚类循环：1.重新归类；2.修改类中心
  315. for(i=0;i<DataNum;i++)  
  316. {
  317. // cout<<endl;
  318. for(j=0;j<K;j++)
  319. {
  320. // cout<<"  D "<<DataMember[i].data[0]<<"  "<<ClusterMember[j].center[0]<<"  ";
  321. DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
  322. //              cout<<DataMember[i].data[0]<<"->"<<ClusterMember[0l].center[0]<<" : "<<DataMember[i].uncle[0]<<endl;
  323. // cout<<i+1<<"->"<<j+1<<" "<<DataMember[i].uncle[j];
  324. }
  326. fa=DataMember[i].father;
  328.     if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
  329. {
  331. pa=DataMember[i].father;
  332. ClusterMember[pa].sonnum-=1;
  334. pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
  335. ClusterMember[pb].sonnum+=1;
  337. NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
  338. NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);
  341. /* cout<<endl<<"*********************"<<M<<" 次聚类：*****************";  //聚一次类输出一次结果
  342. cout<<endl<<DataMember[i].data[0]<<" in "<<pa+1<<"类 -> "<<pb+1<<"类: ";
  344. for(t=0;t<K;t++)
  345. {
  346. cout<<endl<<" 第 "<<t+1 <<"类中心: "<<ClusterMember[t].center[0]<<"  样本个数："<<ClusterMember[t].sonnum;
  347. }
  349. DisPlay();
  350. M=M+1;
  351. */
  352. }
  354. }//endfor 
  357. //判断聚类是否完成，HALT=1,停止聚类
  358. HALT=0;
  359. for(j=0;j<K;j++)
  360. if(Compare(OldCluster[j].center,ClusterMember[j].center,Dimension))
  361. break;
  362. if(j==K)
  363. HALT=1;
  366. for(j=0;j<K;j++)
  367. GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
  369. }//endwhile
  371. }//end of KMeans
  373. //批聚类方式
  375. void SAA::KMeans1()
  376. {
  377. int i,j,M=1;
  378. int pa,pb,fa;
  379. ClusterType *OldCluster;
  381. //初始化聚类中心
  383. OldCluster=new ClusterType[K];
  384. for(i=0;i<K;i++)
  385. OldCluster[i].center=new double[Dimension];
  387. for(j=0;j<K;j++)
  388. GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
  390. //开始聚类，直到聚类中心不再发生变化。××逐个修改法××
  391. while(!HALT)
  392. {
  393. //一次聚类循环：1.重新归类；2.修改类中心
  394. for(i=0;i<DataNum;i++)  
  395. {
  396. for(j=0;j<K;j++)
  397. DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
  398. fa=DataMember[i].father;
  400.     if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
  401. {
  403. pa=DataMember[i].father;
  404. ClusterMember[pa].sonnum-=1;
  406. pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
  407. ClusterMember[pb].sonnum+=1;
  409. NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
  410. NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);
  411. }
  413. }//endfor 
  416. //判断聚类是否完成，HALT=1,停止聚类
  417. HALT=0;
  418. for(j=0;j<K;j++)
  419. if(Compare(OldCluster[j].center,ClusterMember[j].center,Dimension))
  420. break;
  421. if(j==K)
  422. HALT=1;
  425. for(j=0;j<K;j++)
  426. GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
  428. }//endwhile
  430. }
  432. //几个经常需要调用的小函数
  434. void SAA::NewCenterPlus(ClusterType *p1,int t,double *p2,int dim)
  435. {
  436. int i;
  437. for(i=0;i<dim;i++)
  438. p1[t].center[i]=p1[t].center[i]+(p2[i]-p1[t].center[i])/(p1[t].sonnum);
  439. }
  442. void SAA::NewCenterReduce(ClusterType *p1,int t,double *p2,int dim)
  443. {
  444. int i;
  445. for(i=0;i<dim;i++)
  446. p1[t].center[i]=p1[t].center[i]+(p1[t].center[i]-p2[i])/(p1[t].sonnum);
  447. }
  450. void SAA::GetDataset(DataType *p1,double *p2,int datanum,int dim)
  451. {
  452. int i,j;
  453. for(i=0;i<datanum;i++)
  454. {
  456. for(j=0;j<dim;j++)
  457. p1[i].data[j]=p2[i*dim+j];
  458. }
  459. }
  461. void SAA::GetValue(double *str1,double *str2,int dim)
  462. {
  463. int i;
  464. for(i=0;i<dim;i++)
  465. str1[i]=str2[i];
  466. }
  468. int  SAA::FindFather(double *p,int k)
  469. {
  470. int i,N=0;
  471. double min=30000;
  473. for(i=0;i<k;i++)
  474. if(p[i]<min)
  475. {
  476. min=p[i];
  477. N=i;
  478. }
  479. return N;
  480. }
  482. double SAA::SquareDistance(double *str1,double *str2,int dim)
  483. {
  484. double dis=0;
  485. int i;
  486. for(i=0;i<dim;i++)
  487. dis=dis+(double)(str1[i]-str2[i])*(str1[i]-str2[i]);
  488. return dis;
  489. }
  491. int SAA::Compare(double *p1,double *p2,int dim)
  492. {
  493. int i;
  494. for(i=0;i<dim;i++)
  495. if(p1[i]!=p2[i])
  496. return 1;
  497. return 0;
  498. }
  501. double SAA::FRand(double a,double b)
  502. {
  503. return a+(double)(((double)rand()/(double)RAND_MAX)*(b-a));
  505. }
  508. void SAA::DisPlay()
  509. {
  510. int i,N,j,t;
  511. ofstream  result("聚类过程结果显示.txt",ios::ate);
  512. for(i=0;i<K;i++)
  513. {
  514. N=0;
  515. cout<<endl<<endl<<"******************** 第 "<<i+1<<" 类样本:*******************"<<endl;
  516. result<<endl<<endl<<"******************** 第 "<<i+1<<" 类样本:*******************"<<endl;
  517. for(j=0;j<DataNum;j++)
  518. if(DataMember[j].father==i)
  519. {
  520. cout<<" [";
  521. for(t=0;t<Dimension;t++)
  522. cout<<" "<<setw(5)<<DataMember[j].data[t];
  523. cout<<" ]  ";
  524. if((N+1)%Row==0)
  525. cout<<endl;
  527. result<<" [";
  528. for(t=0;t<Dimension;t++)
  529. result<<" "<<setw(5)<<DataMember[j].data[t];
  530. result<<" ]  ";
  531. if((N+1)%Row==0)
  532. result<<endl;
  534. N=N+1;
  535. }
  536. }//end for
  538. cout<<endl<<endl<<"  聚类结果，总体误差准则函数："<<AimFunction(DataMember,ClusterMember)<<endl;
  539. result<<endl<<"  聚类结果，总体误差准则函数："<<AimFunction(DataMember,ClusterMember)<<endl;
  540.   
  541. result.close();
  543. }//end of Display
  545. double SAA::AimFunction(DataType *q,ClusterType *c)
  546. {
  547. int i,j;
  548. double *p;
  549. p=new double[K];
  550. for(i=0;i<K;i++)
  551. p[i]=0;
  552. for(i=0;i<K;i++)
  553. {
  554. for(j=0;j<DataNum;j++)
  555. if(q[j].father==i)
  556. {
  557. p[i]=p[i]+SquareDistance(c[i].center,q[j].data,Dimension);
  558. }
  559. }
  562. AimFunc=0;
  563. for(i=0;i<K;i++)
  564. AimFunc=AimFunc+p[i];
  565. return AimFunc;
  567. }
  571. //************************************
  572. //            主函数入口          ****   
  573. //************************************
  576. void main()
  577. {
  578. //用户输入数据
  579. srand((unsigned)time(NULL));
  580. GETDATA getdata;
  581. getdata.Initial();
  582. ofstream file("聚类过程结果显示.txt",ios::trunc);   //聚类结果存入“聚类结果显示.txt”文件中
  584. //k-均值聚类方法聚类
  585. SAA saa;    //****此行不可与上行互换。
  587. saa.KMeans();    //逐个样本聚类
  588. // saa.KMeans1();   //批处理方式聚类，可以比较saa.KMeans()的区别
  589. cout<<endl<<"***********************K-均值聚类结果：**********************";
  590. file<<endl<<"***********************K-均值聚类结果：**********************"<<endl;
  592. file.close();
  593. saa.DisPlay(); 
  595. cout<<endl<<"  程序运行结束！"<<endl;
  597. }