计算机应用
COMPUTER APPLICATIONS
1999年 第19卷 第9期 Vol.19 No.9 1999



时间序列数据立方的存储与聚集计算
唐常杰　杨　峰　于中华　相利民　左
　　摘　要　本文讨论了从时序数建造、存储数据立方，以及聚集计算的算法，其中N23算法和扩展的EN23算法可以方便地将一个N（N>3）维数据立方转换为三维数据立方，大大降低了I/O次数，极大地提高了运行效率。
　　关键词　数据采掘，数据立方，聚集计算，时态数据
THE STORAGE AND AGGREGATION ON THE DATA
CUBE FOR TIME SERIES
Tang Changjie　Yang Feng　Yu Zhonghua　Xiang Limin　Zuo Jie
Computer Department,Sichuan University　Sichuan.Chengdu 610064
　　Abstract　This paper proposes the algorithms to build, storage and aggregate the data cube for temporal data. Among them the algorithm N23 and EN23 can convert the N dimensional data cube into a 3 dimensional data cube with low I/O cost and high performance.
　　Keywords　Data mining, Data cube, Aggregation, Temporal data
　　　　在现实生活中，有大量与时间有关的数据,称为时序数据(或时态数据)。从时序数据中发现指示(例如周期模式)具有广泛的应用前景。
1　对时序数据采掘的意义及难点
　　决策者在决策之前，常常需要从历史性数据(即时态数据)了解相关对象的规律和趋势，对未来进行预测。例如，对消费者进行分析，发现哪些人更加可能会对邮件宣传作出反应； 预测消费贷款的可能结果,预测呆帐，坏帐；预测电视台在各种节目方案下的收视率，以更好地编排节目，增加广告收入等等。
　　从时序数据中发现规律，至少有两个困难∶数据量大；发现模式(例如周期)的算法。先驱者经过探索，指出多维数据立方是解决这些困难的基本数据结构之一。
　　作为OLAP(联机事务分析)的工具，多维数据立方在实现时有两种方案，即基于关系数据库的ROLAP和基于多维数据库的MOLAP。ROLAP中数据单元为元组，适合于大型的数据集，其优势在于稀疏数据在关系数据库中比在数组中存贮得更加紧密。MOLAP直接使用特殊的数据结构（如稀疏数组）来实现多维数据立方，数组的维作为坐标轴。根据一个数据单元在稀疏数组中的位置，可以推导出它在多维数据立方中的准确位置。但是，当数据比较稀疏的时候，这种方法存贮效率低。压缩技术成为需要解决的关键问题。

图1　三维数据立方
2　多维空间位置矢量与一维数组互换
　　设被处理数据对象有N维，分别记为D0,D1,……,DN-1。对每一维增加个值Sum，对象在Di 维上的值为 (di0,di1,……，diSUM)。为了方便，diSUM 表示为Di｜Di｜ 。每一个维Di 都有｜Di｜+1 个值。用矢量V（v0,v1,……，vN-1 来表明数据立方单元多维空间中的位置。一个数据立方单元的地址中至少有一个vj 等于｜Dj｜ ，其中j≥0，并且jN 。用矢量V(｜D0｜,……，｜DN-1｜） 表示的数据立方单元对应于分组Sum。
　　例1：从图1中，三维数据立方的维D0,D1,D2的大小为：｜D0｜=5,｜D1｜=4,｜D2｜=3 。di0是0，di1 是1，依次类推。i=0,1,2。数据立方单元V(5,4,3)就代表着单元V(Sum,Sum,Sum)。 地址是V(5,0,0)的数据单元保存着以下内部数据单元的和{ V(0,0,0), V(1,0,0), V(2,0,0), V(3,0,0), V(4,0,0) }。数据单元V(5,4,2)也存放着其它一些内部数据单元的和：S1={V(5,0,0), V(5,1,0), V(5,2,0), V(5,3,0)} S2={V(0,4,0), V(1,4,0), V(2,4,0), V(3,4,0), V(4,4,0)}。外部数据单元V(5,4,0)的值要由内部数据单元集合S1或者S2中的值来决定。
　　数据立方是面向查询驱动而设置的，所以维的数目直到建立数据立方的要求发出之前是未知的。多维立方是用一维数组来实现的。 例如，上面图中的数据立方的单元就是这样排列的：V(0,0,0)和V(0,1,0)分别排在一维数组中的第0个和第1个位置。而最后一个数据单元V(5,4,3,)处于第119个位置，因为数据立方中一共有(5+1)*(4+1)*(3+1)=120个数据单元。
　　下面的算法1将数组位置转化为多维空间位置矢量，其逆向算法思路类似，限于篇幅这里略去细节，参见http//:202.115.48.10 。
　　算法1：　数组位置转为多维空间位置矢量
　　Procedure Vector2Index(Vector V(v0,……vN-1))
{ index = 0; //N是数据立方的维数
for (i=0; i<N-1; i++)
{
index += vi; 
index *= (｜DI+1｜+1);
} //end for
index += vN-1;
return index;
}
3　数据立方的存储方案
　　当数据立方的维数增加时，查询代价迅速增加。为了探索比较不同方法的效果我们集成了下列的方法，由用户在使用时选配。
3．1　将数据立方压缩在一维数组中
　　通常，OLAP数据立方中20%的数据非零。排除这些空单元是简单有效的方法，只需记录非空单元的数据及偏移量。由于稀疏矩阵必须在压缩之前就产生并且填充，所以压缩后的数组将是根据单元偏移量排序的。否则须重新排序，或消除重复单元。这是时间换空间的方法。
3.2　利用B+-树压缩数据立方
　　不需分配大量内存，使用以单元偏移量作为键值,将数据单元插入B+-树，花费较小，但是叶节点指针所指的数据单元总是按照偏移量的升序排列的。根据键值就可以访问多维数组中的任何一个非空单元。
3.3　分块存储
　　将数组分块，每块是一个稀疏数组,可放入内存中。分块中只有外部单元或只有内部单元。通常，外部单元远远小于内部单元，并且会比内部单元更频繁被访问。给定一个N维数据立方，分块存储的方法将它分解为比较小的块，并且将每一个块作为一个对象存储在外存中。多数分块在各个维上面有相同的大小。将每一个分块都作为数据单元来处理。
3．4　仿ROLAP存储方法
　　将压缩后的数组放在关系数据库的表中，表中包含下列字段，数据单元的偏移量，该单元在多维空间中的各个维上面的度量，第一维，第二维，…等等。每一元组是一个压缩过的数据单元。当所有的数据单元都插入到这个表中之后，它们会被建立索引，可快速地查找到指定单元。
4　聚集计算
　　聚集计算（包括总和，均值，最大值，最小值）是传统的分析工具。进行聚集计算是对一个数据仓库建造数据立方的主要目的。我们希望进行聚集计算的时候消耗最少，一般要选择最小的维进行计算。例如在图1中，为了计算外部数据单元（Sum），我们首先选择沿着D2进行计算。
4.1　朴质聚集算法
　　输入：　n维数组A［D0,D1,…Dn-1］，｜Di｜为第i维的长度(1<=i<=n)。G为一聚集函数。{Di0, Di1, ……,Din-2}为{D0, D1,……,Dn-1}的真子集，且{D0, D1,……,Dn-1}-{Di0,Di1,……,Dik}= {Dj}(0<=j<n)。
　　输出：　{Di0,Di1,……,Din-2}对应的n-1维数组B。
　　步骤：　分配D［0］*D［1］*……*D［j-1］的数组空间M；
//外层循环
for (d［n-1］=0; d［n-1］<D［n-1］; d［n-1］+　+)
　for (d［n-2］=0; d［n-2］<D［n-2］; d［n-2］+　+)
　　……
　　　for (d［j+1］=0; d［j+1］<D［j+1］; d［j+1］+　+)
　　　{ 
　　　　for (d［j-1］=0; d［j-1］<D［j-1］; d［j-1］+　+)
　　　　　……
　　　　　for (d［1］=0; d［1］<D［1］; d［1］+　+)
　　　　　　for (d［0］=0; d［0］<D［0］; d［0］+　+)
　　{依key从小到大的顺序从B-树中读入下一个元组，并加到M［ d［0］］［d［1］］…［d［j-1］］单元中。
}
　　//保存计算结果到表示B的B-树中。
　　for (d［j-1］=0; d［j-1］<D［j-1］; d［j-1］++)
　　　or (d［1］=0; d［1］<D［1］; d［1］++)
　　　for (d［0］=0; d［0］<D［0］; d［0］++)
　　　　{根据key的定义在B中计算新的key;
　　　　将{key，M［d［0］］［d［1］］…［d［j-1］］}二元组
　　　　插入到表示B的B-树中。
　　}}
　　本算法将N维数据立方聚集为N-1维数据立方。反复调用，可将N维数据立方聚集到一个数据单元上面。实用中，人们往往需要将N维数据立方（N3 ）聚集为三维数据立方，以便观察数据。因此，我们提出了如下的改进算法。
4.2　数据立方聚集改进算法(N23算法)
　　输入：n (n>3)维数组A［D0,D1,…Dn-1］，｜Di｜为第i维的长度(1<=i<=n)。G为一聚集函数。{Di0,Di1,Di2}为{D0,D1,…,Dn-1}的真子集，0 ≤i0,i1,i2≤n-1，并且 i0≠i1,i1≠i2,i0≠i2。
　　输出：{Di0,Di1,Di2 }所对应的3维数组B。
　　步骤：　For (I=1; I<｜Di0｜; I++)
　　　　　　　　For (J=0; J<｜Di1｜; J++)
　　　　　　　　　　For (K=0; K<｜Di2｜; K++)
　　　　　　　　　　{ B［I］［J］［K］ =
　　A［d0］…［I］…［J］…［K］…［dn-1］ ,
　　　　　　　　　　其中dp≠I,dp≠J,dp≠K
　　　　　　　　　　} 
　　本算法可改进为下面的N2M算法，将N维数据立方一次性转换为M维数据立方（M<N）。
4.3　数据立方聚集推广算法(N2M算法)
　　输入：　n维数组A［D0,D1,…Dn-1］，｜Di｜为第i维的长度(1<=i<=n)。G为一聚集函数。{Di0,Di1,…,Dim-1}为{D0,D1,…,Dn-1}的真子集，0≤i0,i1,i2,…im-1 ≤ n-1，并且i0≠i1≠im-1。
　　输出：　计算{Di0,Di1,…,Dim-1}所对应的m（m<n）维数组B
　　步骤：　
　　For (I=1; I<｜Di0｜; I++)
　　　For (J=0; J<｜Di1｜; J++)
　　　　For (K=0; K<｜Di2｜; K++)
　　　　　{ B［I］［J］［K］ =
　　　　　A［d0］…［I］…［J］…［K］…［dn-1］，
　　　　　其中dp≠I,dp≠J,dp≠K 
　　　　　}
4.4　N23的扩展算法(EN23算法)
　　N23算法计算量较大，I/O次数较多，利用外部数据单元的暂时存放聚集计算的中间值，可以把效率提高一个数量级。算法要点如下∶
步骤：① 分配(｜D［0］｜+1)*(｜D［1］｜+1)*…*(｜D［n-1］｜+1)的数组空间；
　　② 从数组A中取出一个数据单元a［j0］［j1］…［j(n-1)］；
　　③ 让a［j0］［j1］…［j(n-1)］分别在各个维相应的Sum单元中投影，A［Sum］［j1］…［j(n-1)］，A［j0］［Sum］…［j(n-1)］, ……, A［j0］［j1］…［Sum］；
　　④ 从A中取出下一个数据单元，执行③；如果没有更多数据单元，跳转⑤；
　　⑤ 计算三维数据立方
For (I=1; I<｜Di0｜; I++)
　For (J=0; J<｜Di1｜; J++)
　　For (K=0; K<｜Di2｜; K++)
　　{B［I］［J］［K］=A［Sum］…［I］…［J］…［K］…A［dp］ ,
其中dp≠I,dp≠J,dp≠K
　　}
5　测试
　　测试数据 　采用了加拿大Simon Fraser大学开发的商品化数据采掘系统DBMiner所带的演示数据。数据存储为Microsoft Access的MDB文件。包括Category, Detailed-category, name, region, country, city, cost, revenue, quantity，time等10个字段，一共有1000条记录。
　　软硬件环境　Win95 +Pentium 200 CPU，32M内存。
　　测试内容　建立数据立方，作聚集计算、使用采掘周期规律。
　　主要测试结果　任意选择三个维（字段）来建立数据立方，如果使用N23算法建造数据立方大约需要14分钟的时间；而使用EN23算法，大约只需要1分钟的时间。可见EN23算法比N23算法提高效率一个数量级。还能给出出拟周期值(关于采掘周期规律的算法另文叙述)。
注：本文研究得到国家自然科学基金(69773051号)和教育部留学回国人员启动基金资助。
作者简介：唐常杰　教授。
杨峰　硕士。
于中华　相利民　副教授。
左　硕士研究生。研究方向均为数据库、知识工程。
作者单位：四川大学计算机系　四川.成都（610064）
参考文献
［1］　W.H.Inmon. Building the Data Warehouse. Q.E.D Technical Publishing Group, Wellesley, Massachusetts,1992
［2］　R.Kimball. The Data Warehouse Toolkit. John Wiley & Sons, New York, 1996
［3］　S.Chaudhuri, U.Dayal. An overview of data warehousing and OLAP technology. ACM SIGMOD Record, 1997;26:65-74
［4］　R.Agrawal, R.Srikant. Mining sequential patterns. In Proc. 1995 Int. Conf. Data Engineering, March,1995; 3-14
［5］　唐常杰,等.从Web数据中采掘逆周期规律.数据库研究进展98——第十五届全国数据库学术会议论文集，成都：1998
［6］　Hongjun Lu, Jiawei Han. Stock Movement Prediction And N-Dimensional Inter-Transaction Association Rules. Simon Fraser University,1998
收稿日期:1999-06-28
