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

实验题目： 直方图进行数据离散化 1 实验目的直方图使用分箱来近似数据分布，是数据规约的一种形式。通过本实验，需要掌握不同直方图的数学原理和构造方法。同时，掌握使用不同直方图对数据进行离散化的原理和方法。最后，利用实验数据实现一种直方图并进行评估。2 实验步骤2.1 算法原理首先，假设有N个自然数的集合U=x | xN，其中最大值为。（1）等宽度直方图对数据进行分箱。假设按等宽度的方法进行分箱（宽度w=1），则对于N个数据，按其值分别放入到相应的箱中，箱子的数目。设每个箱中的统计数据为，按照坐标值/频率对（）表示在二维坐标上，则可以得到该组数据的单桶直方图。其中，。一般情况下，为了进一步压缩数据，通常进行数据分箱时，每一个桶代表的是连续的属性值，即取宽度。在这种分箱方法下，分箱数目。则按照公式，其中，令所得到的值/频率对，的宽度为q的直方图，即为常见的等宽度直方图。（2）等深度直方图与等宽度直方图相比，等深度直方图仅仅是在创建数据桶时与其不同。等深度直方图的数据桶的创建思想是：使得每个桶的频率粗略的为常数，即每个桶中包含大致相当的样本数据数目。设分箱的数目为K，则对于每一个桶，有，其中。只有在这种情况下，才满足大致相当。所要求的是每一个桶的边界，。求边界的过程：首先对该集合U进行排序（由小到大），由于每桶的数目相等，所以每间隔c个数据，取一次数据值，即为一个有效的边界值。对于排序后的序列，有。所得到的二维值对，即是等深度直方图。2.2 算法步骤用户输入数据分桶的数目K，然后按如下步骤计算：（1）对样本数据进行排序（2）计算宽度w和c（2）对数据进行扫描和计算等宽度直方图的数目值和等深度直方图的边界2.3 程序流程图开始获取分桶数目k读入文件数据计算桶宽度w逐个扫描数据，统计数目结束图1 等宽度直方图流程图在图1中，数据的分桶数目是用户输入的数据，预先由用户设定。样本数据存放在文本文件eggs.txt中，由程序运行时读入。在实验中，通过对样本数据的考察，计算桶宽度w的方法是。统计结果存放在数组中，返回统计结果。获取分桶数目k读入文件数据数据顺序排序计算桶的深度p，每个桶的数目c开始结束间隔c个数目在数据中一个值，作为边界值图2 等深度直方图流程图在图2中，数据的分桶数目是用户输入的数据，预先由用户设定。样本数据存放在文本文件eggs.txt中，由程序运行时读入。每个桶的数据量c的计算公式，N表示原始数据的数据个数。边界计算结果存放在数组e中，返回边界数组，计算过程结束。3 实验结果分析图3 等宽度直方图（K=10）统计结果图4 等宽度直方图（K=20）统计结果图5 等深度直方图（K=10）统计结果图6 等深度直方图（K=20）统计结果上面的图分别表示K=10和K=20的情况下eggs.txt中数据的等宽度和等深度直方图的统计结果。直方图的使用是为了离散化数据。在实验中，使用每个桶的中值来代表该桶中数据的离散结果。在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定义如下：，其中，和分别表示第i个值的离散值和真实值，N表示数据总量。最大相对误差M定义如下：，其中，N的定义和平均相对误差中的相同。对于K=10，根据等宽度和等深度的方法，可以得到两组不同的离散值T1和T2。对于这两组离散值，通过计算，得到平均相对误差E1=8.538418，E2=0.399769，最大相对误差M1=549.00，M2=2.00。由上述两组比较可得，在对该样本数据进行离散化时，采用等宽度直方图的方法，效果更好。对于等宽度直方图，当K=10和K=20的情况下，可得到两组不同的离散值T1和T2。通过上述方法计算可得，平均相对误差E1=8.538418，E2=4.261210，最大相对误差M1=549.00，M2=274.00。对于上述两组数据，对于采用直方图进行数据离散化，在桶数目多的情况下，误差较小。当K=N时，数据即为原始数据，此时，误差E和M都为0。但是这样的数据离散化时无意义的，在比较K不同时，还需要考虑另一项指标：数据压缩比率。在实验中，对于每个桶中的数据，取离散值的方法是取中值。如果改变取值方法，比如用桶内样本的平均值来表示离散值，则会得到不同的E和M，但是结论不会改变。5 实验心得体会1、使用程序读入文本数据方法读入数据问题，使用的数据是从dat文件转换过来的txt文件，每行的数据都是换行后的，所以可以直接通过getline函数获取每行值，然后使用atoi函数转换为整型数据。2、为何在实验结论中的评价标准不使用绝对误差？绝对误差对于离群点敏感，不能代表整体逼近效果。3、对于一簇样本数据，应采用何种直方图划分更为合理？对于数据的划分，在实验中是采用用户的一个预设值，可以通过数学的方法获取一个较为良好的K值吗？ 参考文献 1 数据挖掘：概念与技术/（加）韩家炜，（加）坎伯（Kamber,M.）著；范明等译.-北京：机械工业出版社，2001.8附录（源代码）/读入数据BOOL CDrawHistogramDoc:ReadFile(CString filePath)fstream infile(eggs.txt);if(!infile)return FALSE;char ch_num10;/int i=0;/infile.seekgwhile(!infile.eof() )infile.getline(ch_num,sizeof(ch_num);vt_data_org.push_back(atoi(ch_num);infile.close();return TRUE;/等宽度直方图统计void CDrawHistogramDoc:WidthEqualCate(vector vt,int min,int max,int num)if(max=0 | num=0)return;int interval=max/(int)num;/申请数组，初始化为0int * array=new intnum;for(int pos=0;posnum;pos+)arraypos=0;for(int i=0;i(int)vt.size();i+)if(vti/interval vt_data_width.assign(array,array+num);delete array;/等深度直方图计算边界void CDrawHistogramDoc:DepthEqualCate(vector vt,int min,int max,int num)if(max=0 | num=0)return;/首先排序，然后查找值，默认升序sort(vt.begin(),vt.end();int size=(int)vt.size();int interval=(int)vt.size()/num;int i=interval;for(int j=0;jvt_data_depth.push_back(vti);i += interval;this-vt_data_depth.push_back(vtsize-1);/直方图绘制void CDrawHistogramView:DrawEqualWidthHistogram(int x_size)/this-OnInitialUpdate();/this-Invalidate();CDrawHistogramDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);CClientDC dc(this);vector:iterator ptr;int i=0;for(ptr=pDoc-vt_data_width.begin();ptr!=pDoc-vt_data_width.end();ptr+)/计算矩形区域CRect rect(this-orgPoint.x + i*x_size,this-orgPoint.y-(pDoc-vt_data_widthi)/this-y_ratio,this-orgPoint.x+ (i+1)*x_size ,this-orgPoint.y);CBrush * myBrush=new CBrush;myBrush-CreateSolidBrush(RGB(i*45%255,i*75%255,i*5);/填充区域dc.FillRect(&rect,myBrush);i+;/显示统计值CString str;for(int j=0;jvt_data_width.size();j+)str.Format(%d,pDoc-vt_data_widthj);dc.TextOut(orgPoint.x+X_LENGTH,orgPoint.y-Y_LENGTH+20*j,str);void CDrawHistogramView:DrawEqualDepthHistogram()/this-OnInitialUpdate();CDrawHistogramDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);CClientDC dc(this);vector:iterator ptr;int i=0;if(pDoc-vt_data_depthpDoc-vt_data_depth.size()-1/this-x_ratioX_LENGTH)this-Invalidate();MessageBox(坐标和数据不符合！,错误,MB_OK | MB_ICONERROR);return;/最后一个数是终点边界for(ptr=pDoc-vt_data_depth.begin();ptr!=pDoc-vt_data_depth.end();ptr+)/绘制0-vt_data_depth0if(i=0)CRect rect(this-orgPoint.x,this-orgPoint.y-200,this-orgPoint.x + pDoc-vt_data_depth0/this-x_ratio,this-orgPoint.y);CBrush * myBrush=new CBrush;myBrush-CreateSolidBrush(RGB(i*25,i*75,i*5);dc.FillRect(&rect,myBrush);else/计算矩形区域CRect rect(this-orgPoint.x + pDoc-vt_data_depthi-1/this-x_ratio,this-orgPoint.y-200,this-orgPoint.x + pDoc-vt_data_depthi/this-x_ratio,this-orgPoint.y);CBrush * myBrush=new CBrush;