直方图进行数据离散化实验52574.docx

实验题目： 直方图进行数据离散化 1 实验目的直方图使用分箱来近似数据分布，是数据规约的一种形式。通过本实验，需要掌握不同直方图的数学原理和构造方法。同时，掌握使用不同直方图对数据进行离散化的原理和方法。最后，利用实验数据实现一种直方图并进行评估。2 实验步骤2.1 算法原原理首先，假设有NN个自然数的的集合U=x | xxN，其中最最大值为。（1）等宽度直直方图对数据进行分分箱。假设按按等宽度的方方法进行分箱箱（宽度w=1），则对对于N个数据据，按其值分别放放入到相应的的箱中，箱子子的数目。设每个箱中中的统计数据据为，按照坐坐标值/频率率对（）表示在二维维坐标上，则则可以得到该该组数据的单单桶直方图。其中，。一般情况下，为为了进一步压压缩数据，通通常进行数据据分箱时，每每一个桶代表表的是连续的的属性值，即即取宽度。在在这种分箱方方法下，分箱箱数目。则按照公式式，其中，令所得到的值/频频率对，的宽度为qq的直方图，即即为常见的等等宽度直方图图。（2）等深度直直方图与等宽度直方方图相比，等等深度直方图图仅仅是在创创建数据桶时时与其不同。等等深度直方图图的数据桶的的创建思想是是：使得每个个桶的频率粗粗略的为常数数，即每个桶桶中包含大致致相当的样本本数据数目。设分箱的数目目为K，则对对于每一个桶桶，有，其中中。只有在这种种情况下，才才满足大致相相当。所要求求的是每一个个桶的边界，。求边界的过程程：首先对该该集合U进行行排序（由小小到大），由由于每桶的数数目相等，所所以每间隔cc个数据，取取一次数据值值，即为一个个有效的边界界值。对于排排序后的序列列，有。所得到的二二维值对，即即是等深度直直方图。2.2 算法步步骤用户输入数据分分桶的数目KK，然后按如如下步骤计算算：（1）对样本数数据进行排序序（2）计算宽度度w和c（2）对数据进进行扫描和计计算等宽度直直方图的数目目值和等深度度直方图的边边界2.3 程序流流程图开始获取分桶数目k读入文件数据计算桶宽度w逐个扫描数据，统计数目结束图1 等宽度直直方图流程图图在图1中，数数据的分桶数数目是用户输输入的数据，预预先由用户设设定。样本数数据存放在文文本文件egggs.txxt中，由程程序运行时读读入。在实验验中，通过对对样本数据的的考察，计算算桶宽度w的的方法是。统计结果存存放在数组中中，返回统计计结果。获取分桶数目k读入文件数据数据顺序排序计算桶的深度p，每个桶的数目c开始结束间隔c个数目在数据中一个值，作为边界值图2 等深度直直方图流程图图在图2中，数据据的分桶数目目是用户输入入的数据，预预先由用户设设定。样本数数据存放在文文本文件egggs.txxt中，由程程序运行时读读入。每个桶的数据量c的计算公公式，N表示示原始数据的的数据个数。边界计算结结果存放在数数组e中，返回边界界数组，计算算过程结束。3 实验结果分分析图3 等宽度直直方图（K=10）统计计结果图4 等宽度直直方图（K=20）统计计结果图5 等深度直直方图（K=10）统计计结果图6 等深度直直方图（K=20）统计计结果上面的图分别别表示K=110和K=20的情情况下egggs.txtt中数据的等等宽度和等深深度直方图的的统计结果。直方图的使用是为了离散化数据。在实验中，使用每个桶的中值来代表该桶中数据的离散结果。在K=10的情况下：使用等宽度直方图，样本数据离散值为550，1650，2750，3850，4950，6050，7150，8250，9350，10450；使用等深度直方图，样本数据的离散值为3，43，182，403，643，981，1378，1803，2365，6770。在K=20的情况下，使用等宽度直方图，样本数据离散值为275，825，1375，1650，1925，2475，3025，3575，4125，4675，5225，5775，6325，6875，7425，7975，8525，9075，9625，10175，10725；使用等深度直方图，样本数据的离散值为0，2，17，50，108，199，308，412，539，683，842，1051，1221，1368，1552，1776，2035，2338，2742，6915。实验表明：对于采用不同的直方图和不同的桶数目K，得到不同的离散化结果。4 实验结论对于上述的四四种离散化结结果，如何来来判定哪种离离散化数据的的效果更好呢呢？一般的，离散散后的数据越越接近样本原原始数据，则则效果越好。数据离散化后，与原始数据肯定存在差异，一般用误差度量这种差异大小。在这里，定义平均相对误差和最大相对误差来表示离散数据逼近原始样本数据的程度，作为离散化的评判标准。平均相对误差差E定义如下：，其中，和分分别表示第ii个值的离散散值和真实值值，N表示数数据总量。最大相对误差差M定义如下：，其中，NN的定义和平平均相对误差差中的相同。对于K=100，根据等宽宽度和等深度度的方法，可可以得到两组组不同的离散散值T1和TT2。对于这这两组离散值值，通过计算算，得到平均均相对误差EE1=8.55384188，E2=0.3997669，最大相相对误差M11=549.00，M22=2.000。由上述两组组比较可得，在在对该样本数数据进行离散散化时，采用用等宽度直方方图的方法，效效果更好。对于等宽度直直方图，当KK=10和KK=20的情情况下，可得得到两组不同同的离散值TT1和T2。通通过上述方法法计算可得，平均相对误误差E1=88.5384418，E22=4.2661210，最最大相对误差差M1=5449.00，MM2=2744.00。对于上述两两组数据，对对于采用直方方图进行数据据离散化，在在桶数目多的的情况下，误误差较小。当当K=N时，数数据即为原始始数据，此时时，误差E和和M都为0。但但是这样的数数据离散化时时无意义的，在在比较K不同同时，还需要要考虑另一项项指标：数据据压缩比率。在实验中，对对于每个桶中中的数据，取取离散值的方方法是取中值值。如果改变变取值方法，比比如用桶内样样本的平均值值来表示离散散值，则会得得到不同的EE和M，但是是结论不会改改变。5 实验心得体体会1、使用程序读读入文本数据据方法读入数据问题题，使用的数数据是从daat文件转换换过来的txxt文件，每每行的数据都都是换行后的的，所以可以以直接通过ggetlinne函数获取取每行值，然然后使用attoi函数转转换为整型数数据。2、为何在实验验结论中的评评价标准不使使用绝对误差差？绝对误差对于于离群点敏感感，不能代表表整体逼近效效果。3、对于一簇样样本数据，应应采用何种直直方图划分更更为合理？对对于数据的划划分，在实验验中是采用用用户的一个预预设值，可以以通过数学的的方法获取一一个较为良好好的K值吗？ 参考文献 1 数据据挖掘：概念念与技术/（加加）韩家炜，（加加）坎伯（KKamberr,M.）著；范明等等译.-北京京：机械工业业出版社，22001.88附录（源代码）/读入数据BOOL CDDrawHiistogrramDocc:ReaadFilee(CStrring ffilePaath)fstreaam inffile(""eggs.txt");if(!innfile)returrn FALLSE;char cch_numm10;/int i=0;/infiile.seeekgwhile(!infiile.eoof() )infille.gettline(ch_nuum,sizzeof(cch_numm);vt_daata_orrg.pussh_bacck(atooi(ch_num);infilee.closse();returnn TRUEE;/等宽度直方方图统计void CDDrawHiistogrramDocc:WiddthEquualCatte(vecctor<iint> vvt,intt min,int mmax,innt numm)if(maxx<=0 | numm=0)returrn;int inntervaal=maxx/(intt)num;/申请数组组，初始化为为0int * arrayy=new intnnum;for(innt poss=0;poos<numm;pos+)arrayypos=0;for(innt i=00;i<(iint)vtt.sizee();i+)if(vtti/iintervval < num)arraayvti/inntervaal+;this->>vt_daata_wiidth.aassignn(arraay,arrray+nuum);deletee aarray;/等深度直方方图计算边界界void CDDrawHiistogrramDocc:DeppthEquualCatte(vecctor<iint> vvt,intt min,int mmax,innt numm)if(maxx<=0 | numm=0)returrn;/首先排序序，然后查找找值，默认升升序sort(vvt.beggin(),vt.ennd();int siize=(iint)vtt.sizee();int inntervaal=(innt)vt.size()/numm;int i=interrval;for(innt j=00;j<nuum;j+)this->vt_ddata_ddepth.push_back(vti);i += interrval;this->>vt_daata_deepth.ppush_bback(vvtsizze-1);/直方图绘制制void CDDrawHiistogrramVieew:DrrawEquualWiddthHisstograam(intt x_siize)/thiss->OnIInitiaalUpdaate();/thiss->Invvalidaate();CDrawHHistoggramDooc* pDDoc = GetDoocumennt();ASSERTT_VALIID(pDooc);CClienntDC ddc(thiis);vectorr<int>>:iteeratorr ptr;int i=0;for(pttr=pDooc->vtt_dataa_widtth.beggin();ptr!=pDoc->vt_ddata_wwidth.end();ptr+)/计算矩矩形区域CRectt rectt(thiss->orggPointt.x + i*x_ssize,tthis->>orgPooint.yy-(pDooc->vtt_dataa_widtthi)/thiss->y_rratio,this->orgPPoint.x+ (ii+1)*xx_sizee ,thiis->orrgPoinnt.y);CBrussh * mmyBrussh=neww CBruush;myBruush->CCreateeSoliddBrushh(RGB(i*45%255,ii*75%2255,i*5);/填充区区域dc.FiillRecct(&reect,myyBrushh);i+;/显示统计计值CStrinng strr;for(innt j=00;j<pDDoc->vvt_datta_widdth.siize();j+)str.FFormatt("%d"",pDocc->vt_data_widthhj);dc.TeextOutt(orgPPoint.x+X_LLENGTHH,orgPPoint.y-Y_LLENGTHH+20*jj,str);void CDDrawHiistogrramVieew:DrrawEquualDeppthHisstograam()/thiss->OnIInitiaalUpdaate();CDrawHHistoggramDooc* pDDoc = GetDoocumennt();ASSERTT_VALIID(pDooc);CClienntDC ddc(thiis);vectorr<int>>:iteeratorr ptr;int i=0;if(pDooc->vtt_dataa_deptthpDooc->vtt_dataa_deptth.sizze()-11/thiis->x_ratioo>X_LEENGTH)this->Invaalidatte();MessaageBoxx("坐标和和数据不符合合！","错错误",MBB_OK | MB_IICONERRROR);returrn;/最后一个个数是终点边边界for(pttr=pDooc->vtt_dataa_deptth.beggin();ptr!=pDoc->vt_ddata_ddepth.end();ptr+)/绘制00-vt_ddata_ddepth0if(i=0)CRecct recct(thiis->orrgPoinnt.x,tthis->>orgPooint.yy-200,this->orgPPoint.x + ppDoc->>vt_daata_deepth00/thiis->x_ratioo,thiss->orggPointt.y);CBruush * myBruush=neew CBrrush;myBrrush->>CreatteSoliidBrussh(RGBB(i*255,i*755,i*5);dc.FFillReect(&rrect,mmyBrussh);else/计计算矩形区域域CRecct recct(thiis->orrgPoinnt.x + pDocc->vt_data_depthhi-1/thiss->x_rratio,this->orgPPoint.y-2000,thiss->orggPointt.x + pDoc->vt_ddata_ddepthi/thhis->xx_ratiio,thiis->orrgPoinnt.y);CBruush * myBruush=neew CBrrush;myBrrush->>CreatteSoliidBrussh(RGBB(i*455%255,i*75%255,ii*5);/MeessageeBox(""aaa");/填充充区域dc.FFillReect(&rrect,mmyBrussh);i+;/显示统计计值CStrinng strr;for(innt j=00;j<pDDoc->vvt_datta_deppth.siize();j+)str.FFormatt("%d"",pDocc->vt_data_depthhj);dc.TeextOutt(orgPPoint.x+X_LLENGTHH,orgPPoint.y-Y_LLENGTHH+20*jj,str);