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