（计算机应用技术专业论文）基于数据挖掘的olap智能查询推荐技术研究.pdf

浙江大学硕士学位论文摘要 摘要 随着数据库技术的发展以及联机分析处理( o n l i n ea n a l y s i sp r o c e s s i n g ，简 称o l a p ) 多维分析查询方法的普及，与其相关的服务和产品成为了业界关注的 焦点。而o l a p 查询分析操作复杂，一般用户在短时间内难以熟练掌握，进而影 响其发挥应有作用。如何在分析过程中帮助普通用户进行高效查询，已成为o l a p 应用中亟待解决的问题。 针对o l a p 操作复杂导致的用户使用效率低下问题，本文提出基于操作序列 挖掘的o l a p 查询推荐方法，并开发了一整套挖掘o l a p 多维分析查询序列模式， 以此预测用户未来查询操作，并将之推荐给用户的实用系统。 首先从多维表达式( m u l t i d i m e n s i o n a le x p r e s s i o n ，m d x ) 查询语句记录中提 取整数数列形式的查询序列，再利用序列模式挖掘方法对查询序列进行频繁序列 模式挖掘，并在挖掘出的模式及其子模式的基础上建立概率矩阵，最后通过搜索 与用户当前查询操作或查询序列匹配的候选模式对其下一步查询操作进行预测， 并将预测结果按概率大小分级推荐。总的来说，本文的主要研究工作和贡献如下： ( 1 ) 本文提出了一种解析现行m d x 多维查询语言的方法，在给定多维数据 集的条件下，从连续的每条m d x 查询语句中提取维度层次及操作类型信息，将 之抽象转化成数字，由此将连续查询序列转化为一维数组。它支持跨维度跨层次 的查询，支持现行的o l a p 查询操作种类，如钻取、切片、旋转等。 ( 2 ) 根据所转化的抽象查询序列自身特点，研究并提出了基于p r e f i x s p a n 的查询序列模式挖掘改进算法。研究了基于概率的查询预测问题，阐述了建立概 率矩阵计算未来查询操作的方法，并与查询推荐相结合，将结果显示给用户。 ( 3 ) 在7 位o l a p 专业分析人员的查询分析日志数据集上对本文提出的查 询推荐方法进行性能评价，实验结果表明使用用户相关模型前五推荐内容的平均 正确率为9 2 2 0 ，其中第一推荐的平均正确率为7 7 0 6 ；使用公共模型前五推 荐内容的平均正确率为8 1 8 9 ，其中第一推荐的平均正确率为6 0 8 5 。通过实 浙江大学硕士学位论文摘要 验论证了本文提出的o l a p 查询推荐技术适用于用户相关和用户无关两个方向的 预测及推荐。 关键词：联机分析处理，数据挖掘，查询推荐 浙江大学硕士学位论文a b s t r a c t a b s t r a c t r e c e n t l y , w i t ht h ed e v e l o p m e n to fd a t a b a s ea n do n - l i n ea n a l y s i sp r o c e s s i n g ( o l a p ) ， i t sr e l a t e ds e r v i c e sa n dp r o d u c t sb e c a m et h ef o c u so fi n d u s t r y b u to l a pq u e r y a n a l y s i si sc o m p l e x ，w h i c hc a n n o tb ee x p e r t l ym a s t e r e di nas h o r tt i m eb yo r d i n a r y u s e r s h o wt oh e l po r d i n a r yu s e r st oi n c r e a s et h ee f f i c i e n c yo fq u e r yd u r i n gt h ep r o c e s s o fa n a l y s i si st h ei m p e r a t i v ep r o b l e mo f u s i n go l a p a no p e r a t i o ns e q u e n c em i n i n gb a s e do l a pq u e r yr e c o m m e n d a t i o nm e t h o di s p r o p o s e dt oc o u n t e rt h el o we f f i c i e n c yp r o b l e mc a u s e db yt h ec o m p l e x i t yo fo l a p q u e r yo p e r a t i o n s ，a n da ne n t i r es y s t e mf o ro l a pq u e r ys e q u e n c e sm i n i n gi sa l s o p r o p o s e dt op r e d i c tu s e r sf u t u r eq u e r y f i r s t ，a b s t r a c tq u e r ys e q u e n c e s ，i nt h ef o r mo fn u m e r i c a la r r a y , a r ee x t r a c t e df r o m c o n t i n u o u sm d x ( m u l t i d i m e n s i o n a le x p r e s s i o n ) q u e r yo p e r a t i o n s t h e n ，aq u e r y s e q u e n c e sm i n i n ga l g o r i t h mi se x p l o i t e dt oo b t a i nt h ef r e q u e n ts e q u e n t i a lp a t t e r n sf r o m q u e r ys e q u e n c e s ，a n dam a t r i xo fp r o b a b i l i t i e si se s t a b l i s h e du p o nm i n e dp a t t e r n sa n d t h e i rs u b - p a t t e r n s f i n a l l y , t h en e x to p e r a t i o no fc u r r e n tu s e ri sp r e d i c t e db ys e a r c h i n g c a n d i d a t ep a t t e r n sm a t c h e d 、 r i t ht h eu s e r sq u e r yo p e r a t i o no rq u e r ys e q u e n c e ，a n dt h e p r e d i c t i o nr e s u l t sa ler a n k e da c c o r d i n gt ot h em a g n i t u d eo fp r o b a b i l i t i e s t os u mu p ， t h ek e yc o n t r i b u t i o n sa n dm a i nc o n t e n t si nt h i sp a p e ra r ea sf o l l o w s ： ( 1 ) t h i sp a p e rp r o v i d e sam e t h o do fa n a l y z i n gm d xm u l t i d i m e n s i o n a lq u e r y l a n g u a g ei no p e r a t i n g o nc o n d i t i o no ft h eg i v e nm u l t i d i m e n s i o n a ld a t a b a s e ，i tp i c k s u pi n f o r m a t i o no fd i m e n s i o n a l i t yl e v e la n dt y p eo fo p e r a t i n gf r o ms e q u e n t i a lm d x q u e r ys e n t e n c e s ，a b s t r a c t sa n dt r a n s f o r m st h ei n f o r m a t i o nt on u m b e r si no r d e rt o c h a n g e t h e s e q u e n t i a lq u e r ys e q u e n c e t o s i n g l e d i m e n s i o na r r a y i ts u p p o r t s c r o s s - d i m e n s i o na n dc r o s s - l e v e lq u e r y , a sw e l la st h et y p e so fo l a p q u e r yo p e r a t i n g i no p e r a t i n g ( e g d r i l l ，s l i c ea n d p i v o t ) ( 2 ) a c c o r d i n gt ot h ec h a r a c t e ro fa b s t r a c t l yt r a n s f e r r e dq u e r ys e q u e n c e s ，t h et h e s i s p r o v i d e saq u e r ys e q u e n c e sm i n i n ga l g o r i t h mb a s e do np r e f i x s p a n i ts t u d i e st h eq u e r y p r e d i c t e dp r o b l e mb a s e do np r o b a b i l i t y , a n de x p a t i a t et h em e t h o do fs e t t i n gu pa 浙江大学硕士学位论文a b s t r a c t p r o b a b i l i t ym a t r i xt o c a l c u l a t ef u t u r eq u e r yo p e r a t i n g ，a sw e l la sp r e s e n t i n gt h e r e c o m m e n d a t i o nq u e r ya n dr e s u l tt ou s e r s ( 3 ) t h ep e r f o r m a n c eo ft h ep r o p o s e dq u e r yr e c o m m e n d a t i o nm e t h o dw a s e v a l u a t e dw i t ha no l a pq u e r yo p e r a t i o nd a t a s e tr e c o r d e df o r ms e v e np r o f e s s i o n a l o l a pu s e r s t h er e s u l t ss h o wt h a tw i t hu s e r - s p e c i f i cr e c o m m e n d a t i o nm o d e l s ，t h e a v e r a g ea c c u r a c yr a t e so ft h et o pf i v er e c o m m e n d a t i o n sa n dt h ef i r s tr e c o m m e n d a t i o n a r e9 2 2 0 a n d7 7 0 6 r e s p e c t i v e l y , w i t hac o m m o nr e c o m m e n d a t i o nm o d e l ，t h e a v e r a g ea c c u r a c yr a t e so ft h et o pf i v er e c o m m e n d a t i o n sa n dt h ef i r s tr e c o m m e n d a t i o n a r e81 8 9 a n d6 0 8 5 r e s p e c t i v e l y t h ee x p e r i m e n td e m o n s t r a t e st h a tt h eo l a p q u e r yr e c o m m e n d a t i o nt e c h n o l o g ya d v a n c e db yt h i sp a p e ri sa d a p tt ot h ep r e d i c a t i o n a n dr e c o m m e n d a t i o nb o t hi nt h ea r e ao fr e la t e da n du n r e l a t e du s e r s k e y w o r d s ：o l a p , d a t am i n i n g ，q u e r i e sr e c o m m e n d a t i o n 浙江大学硕士学位论文图目录 图目录 图1 1w 曲搜索领域查询推荐技术应用3 图1 2 个人连续路径预测系统截图3 图1 3w e b 使用记录挖掘系统4 图1 4 机器学习o l a p 查询推荐系统界面6 图1 5 基于马尔科夫模型的o l a p 预测系统示意图7 图2 1m o n d f i a n 图形化多维数据展示界面1 0 图2 2 多维数据集f o o d m a r t 维度信息1 1 图2 3o l a p 服务器日志文件1 2 图3 1 基本m d x 查询语句1 5 图3 2m d x 查询语句示例1 6 图3 3 钻取示意图。17 图3 4 日志中的查询序列举例1 9 图5 1 用户相关模型实验结果3 6 图5 2 公共模型第一类实验结果3 7 图5 3 公共模型第二类实验结果3 8 图6 1 系统结构层次示意图4l 图6 2 原型系统用户界面截图4 3 图6 3 原型系统操作界面截图4 4 i i i 浙江大学硕士学位论文 表目录 表目录 表2 1o l a p 分析目标12 表2 27 位人员数据采集所得日志文件信息13 表3 1 抽象查询序列构造算法伪代码一1 8 表3 27 个日志文件中含有的抽象查询序列数量2 1 表3 3 抽象查询序列生成结果2 l 表4 1g s p 算法伪代码2 4 表4 2p r e f i x s p a n 算法伪代码2 7 表4 3 查询序列模式挖掘算法伪代码2 8 表4 4 第一组算法参数为0 1 0 挖掘结果2 9 表4 5 第二组算法参数为o 2 0 挖掘结果3 0 表5 1 两种模型三组实验的平均正确率一3 8 表6 1 数据采集及抽象转化模块主要实现的类4 2 表6 2 序列模式挖掘及预测模块主要实现的类4 2 i v 浙江大学硕士学位论文第l 章绪论 第1 章绪论 1 1 课题背景与意义 随着数据库技术的飞速发展，大型用户在日常应用中产生了海量的数据，对 于这些大型用户的决策管理人员，面临着如何从海量数据中提取对决策分析有用 信息的难题。传统的联机事务处理系统( o n l i n et r a n s a c t i o np r o c e s s i n g ，简称 o l t p ) 作为数据管理手段，主要用于处理事务，但其对分析处理的支持一直无法 满足大多数用户的需求。研究者逐渐尝试对o l t p 系统中的功能进行加工完善， 形成一个更好的支持决策制定的、面向分析的、综合的决策支持系统( d e c i s i o n s u p p o r ts y s t e m ，简称d s s ) 。但是目前大型用户的信息系统数据一般由d b m s 管 理，决策支持系统和运行操作数据库在数据来源、数据内容、数据模式、服务对 象、事务管理、访问方式等很多方面都有不同的特点和需求，所以直接在运行操 作的数据库上建立d s s 是不合适的。 由此关系数据库之父e ec o d d 在1 9 9 3 年提出了联机分析处理( o n l i n e a n a l y s i sp r o c e s s i n g ，简称o l a p ) 的概念。c o d d 认为联机事务处理( o l t p ) 已 无法满足终端用户日益提高的对数据库查询功能的需求，s q l 对数据库的简单查 询也无法满足用户对海量数据分析的需求。用户进行决策分析需要对关系数据库 中的大量数据进行多次计算才能得到结果，而显然的是通过简单查询得到的结果 并不能满足决策分析者提出的查询分析需求。因此，c o d d 提出了多维数据库以及 相对应的多维分析的概念，即o l a p 。其对联机分析处理的定义为：使分析人员、 管理人员或执行人员能够从多种角度对从原始数据中转化出来的、能够真正为用 户所理解的、并真实反映企业维特性的信息进行快速、一致、交互地存取，从而 获得对数据的更深入了解的一类软件技术。 o l a p 系统按照其存储器的数据存储格式可以分为关系o l a p ( r e l a t i o n a l o l a p ，简称r o l a p ) 、多维o l a p ( m u l t i d i m e n s i o n a lo l a p ，简称m o l a p ) 和 混合型o l a p ( h y b r i do l a p ，简称h o l a p ) 三种类型。 浙江大学硕士学位论文第l 章绪论 r o l a p 将分析用的多维数据存储在关系数据库中，不必将每一个s q l 查询 都作为实视图保存，只定义某些应用频率较高、计算量较大的查询作为实视图， 优先使用它们来生成查询结果以提高查询效率。同时用作r o l a p 存储器的 r d b m s 也针对o l a p 作相应的优化，比如并行存储、并行查询、并行数据管理、 s q l 的o l a p 扩展、位图索引、基于成本的查询优化等等。 m o l a p 将o l a p 分析所用到的多维数据在物理上存储为多维数组的形式， 形成“立方体”的结构。维的属性值被映射成多维数组的下标值或下标的范围， 而度量值作为多维数组的值存储在数组的单元中。 由于m o l a p 和r o l a p 有着各自的优点和缺点，因此一个新的o l a p 结构 混合型o l a p ( h o l a p ) 被提出，它能把m o l a p 和r o l a p 两种结构的优点结 合起来。迄今为止，对h o l a p 还没有一个正式的定义。但很明显，h o l a p 结构 不应该是m o l a p 与r o l a p 结构的简单组合，而是这两种结构技术优点的有机 结合，能满足用户各种复杂的分析请求。 发展至今，各大数据库软件提供商均研发出了各自的o l a p 分析软件，但大 多操作复杂，需专业o l a p 分析人员经过一定时间的学习培训才能对其进行熟练 的查询操作，对于大多数普通用户，在短时间内难以熟练掌握，进而影响其发挥 应有作用。如何在分析过程中帮助普通用户进行高效查询，已成为o l a p 应用中 亟待解决的问题。查询推荐技术【l j 通过数据挖掘等手段获取用户历史操作记录中 的模式信息，并以此为基础向用户推荐合适的操作，其在w e b 搜索【2 】、信息检索 【3 】【4 】及数据库查询5 恫等领域中已有广泛应用，表明一个合理设计的查询推荐模块 能大大提高用户的操作效率。 例如在w e b 搜索领域，成熟的搜索引擎都会提供查询推荐服务，见图1 1 。 在搜索框下拉菜单中显示与用户输入搜索词相近的推荐结果，方便用户查询，提 高搜索引擎的用户体验性，并使得w e b 搜索对于新用户来说易于上手。 2 m 江人学砸学位论文第1 章绪论 g o l j 臻 “ m u u 埘 i 一 置妻嘲 髓城 自 * 、 t # t t 一 囤iiw e b 搜索领域赢询推荐技术应h j 文献【7 1 针对个人路径与车辆的路径模式挖掘及预测的不同之处，研究并开发 了一套挖掘个人连续路径模式并以此预测个人路径的实用系统。分为三部分实 现：个人真实路径采集和数据处理部分、个人连续路径模式挖掘部分、以及个人 路径预测部分。其系统推荐路径显示见图12 。 魅豳 图i2 个人连续路径预测系统截幽 文献嘲研究并开发了一个称为w e b s i f t 的w e b 使用记录挖掘系统，其架构见 图i3 ，对不同来源的w e b 使用记录进行预处理、模式发现和模式分析三个步骤， 获得用户“偏好”的规则从而进一步的向用户提供推荐、预测等一系列功能，满足 用户需求。 浙江 学域学位论立第1 章绪论 图13 w e b 使用记录挖掘系统 鉴于查询推荐技术在各领域的蓬勃发展并形成了一套成熟的技术体系，将之 运用于o l a p 联机分析处理上，可提高其使用效率，为新用户、初级用户及大多 数普通用户提供有效帮助，降低查询操作复杂性。 1 2 研究现状及存在问题 o l a p 领域内的查询推荐研究目前处于起步阶段。研究人员利用不同的信息 获取渠道，采用不同的解决问题的思路，但基本包含有三部分的研究内容。首先， 研究人员利用不同的方法对真实的o l a p 查询操作进行抽象化处理，主要目的足 提取查询之间的相似特性，简化后续的工作。第二部分，研究人员从抽象化的真 实查询中抽取模式( 模型) ，方法包括聚类、经! | i 熟悉模型( 如马尔科夫模型) 等等，目的是为进步的预测推荐提供依据。第三部分，即查询推荐部分，主要 是根据前一步抽墩的模式( 模型) ，并结合定的实时信息，来预测将会进行的 查询操作，并将其作为结果推荐。以f 列举目前o l a p 领域内典型的查询推荐研 究工作。 文献p l 【l o l 构建了一个基于聚类的o l a p 查询推荐框架。研究人员提出o l 。a p 浙江大学硕上学位论文第l 章绪论 服务器上的日志记录了用户所有多维分析查询语句，将此渠道作为获取o l a p 查 询操作的信息来源。之后采用经典的k 中心点算法将日志文件上的历史查询语句 进行聚类，使查询语句的序列转化抽象为相应的类别序列。采用计算历史查询记 录间的h a u s d o r f f 距离作为查询语句的相似度进行聚类。h a u s d o r f f 距离可以计算 两个集合之间的距离，但需确定两个集合中对应元素的距离，文献中采用经典的 h a m m i n g 距离来计算： ( 1 ) d h ( ， ) = n i i c o m p a r e ( a i ，b i ) ( 经典h a m m i n g 距离公式) ( 2 ) d n ( q l ，q 2 ) = m a x m a x r l e q l m i n r 2 e q 2 d h ( r l ，r 2 ) ，m a x r 2 e q 2 m i n r l e q i d h ( r l ，r 2 ) ) ( 两个 查询问的h a u s d o r f f 距离公式) 将日志上的每一条查询语句记录抽象为相应的类别序列号，同时也把当前用 户所做的查询操作语句转化为类别序列号，将当前类别序列号与同志历史类别序 列号做近似串匹配，匹配到的历史序列的后一位类别序列号作为预测结果，并把 k 中心点聚类算法中计算得到的“中心点”查询语句作为该预测类别的代表查询， 将其推荐给当前用户，达到查询推荐的目的。 该文献的研究工作的贡献是率先将查询推荐技术运用于o l a p 领域，并建立 了推荐框架，为后续的研究提供了良好的开端，但其工作具有很大的局限性。其 设计框架为使用聚类算法，只能支持简单的分析查询，即对单一维度的查询操作 语句，不支持常见的o l a p 操作如钻取、切片等等，因为只有单一维度的查询语 句能够运用h a m m i n g 距离公式和h a u s d o r f f 足1 1 离公式计算相似度；此外，其预测 部分只是采用简单的近似串匹配算法对类别序列进行匹配，若在海量日志记录的 情况下，势必匹配次数将会大大增加，从而降低查询推荐的效率及可靠性。 文献l 】【1 2 1 将研究工作的重点放在了使用机器学习的方法，对用户相关信息进 行训练，达到预测特定用户查询行为的目的。首先研究人员根据用户查询的维度 层次度量信息定义了o l a p 分析上下文( o l a pa n a l y s i sc o n t e x t ) 和首选项 ( p r e f e r e n c e ) 的概念： ( 1 ) c f = f gp 孵( m i ) v a l m ) ) + 为一个事实上下文( f a c tc o n t e x t ) ，其中产g r e g ( a v gs u m ) 是一个聚合函数( a g g r e g a t ef u n c t i o n ) ，而m i m ，v a l m d o m ( m i ) ； 5 江 学魄学论文 第1 绪论 ( 2 ) 维度d 中的首选项表示为p “k ，可定义成( 。c 9 ) 的形式，其中 。是 在a ”c a o 之上的j ，”格偏序，a ”为维度d 下的层次h 中包含的参数集台，并且 。暑a 。xa “：c 9 为首选项上下文。 在对用户查询的维度层次度景信息建立首选项( p r e f e r e n c e ) 参数之后t 以此 为越硎；进行上下文首选项模型( c o n t e x t u a lp | i e f c r c n c em o d e l i n g ) 训练，艟后推荐 给用户的足若干个卤进项参数，以易于理解的语句砬示在儿用户界俩之上，并提 供查询链接，见圈l4 。其不足之处在于，住提供查咖推荐功能之前，需e 1 时用 户的蠢询操作进行洲练，训练所需数据文献中没有提及，并且需对每一个用户分 别训练，没有建讧用广无关的公共模型，其查询推荐的可用性令人担忧。且缺少 必要的实验结粜支持，无法体现其可行性。 ，m 日h sc b ) p r o t o t y p e s ( c ) 陶i4 机器学习o l a p 卉询推荐系统界面 浙江大学硕士学位论文第l 章绪论 在o l a p 领域其它的相关研究工作中，例如o l a p 性能优化研究，文献【1 3 1 0 4 】 率先为用户查询行为建模，其目的是通过预测用户下一步查询操作来改进o l a p 系统缓存算法，从而提高o l a p 系统性能。其研究工作一部分为改进缓存算法， 在此不做介绍，只对其建模和预测部分进行阐述。 在建模部分采用m 阶马尔科夫模型( o r d e r - mm a r k o vm o d e l ) ，是一种时间 无关的马尔科夫模型( d i s c r e t et i m em a r k o vm o d e l ，简称d t m m ) ，其概率变迁 只依赖于一个固定的状态数量m ( 称为d t m m 阶) ，表示在时间点t 之前被直接 访问的状态数量( 如状态s 卜1 ，s 卜z ，s t - m ) 。预测部分则是基于m 阶马尔科夫模型， 计算状态变迁间的概率大小，将最可能的下一个状态作为预测结果。此两部分内 容见图1 5 。 其不足之处在于其研究目的并非查询推荐，所以没有将真实查询操作很好的 抽象化，致使马尔科夫模型建立过程较为复杂；另外在当时多维表达式 ( m u l t i d i m e n s i o n a le x p r e s s i o n ，m d x ) 语句并未设计完善，故其研究成果无法支 持现行o l a p 分析所采用的m d x 查询语言标准。 m u n i c h e d a n g e n p a s s a u l o c a t i o nv e h i c l ep a r t 1 0 ；0 9 8 ；o ；0 ；0 6 ) 图1 5 基于马尔科夫模型的o l a p 预测系统示意图 1 3 本文主要研究内容 综合上一节的论述，目前o l a p 领域内的查询推荐研究，根据关注的查询推 荐对象不同，分为两个研究方向：用户相关和用户无关。用户相关即对特定用户 的查询操作进行查询推荐，用户无关即采用公共查询操作数据作为依据对任意用 7 浙江大学硕士学位论文第l 章绪论 户进行查询推荐。其中存在的问题主要有：抽取查询模式( 模型) 之前将真实查 询抽象化的工作尚有欠缺，导致后续建模工作繁琐；采用聚类算法进行抽象化工 作导致所含信息损失较大，且后续预测工作无法进行精确计算。 针对现有研究存在的不足，本文提出基于数据挖掘的o l a p 智能查询推荐技 术，从o l a p 用户历史操作记录中挖掘查询操作的频繁序列模式，并根据o l a p 用户实时的查询序列，匹配序列模式及其子模式，通过建立概率矩阵对其下一步 查询操作进行预测，并将结果推荐给用户。该方法支持多用户多维度o l a p 操作 推荐，支持o l a p 常见钻取、切片、旋转等操作，基于概率矩阵的序列模式匹配 大大增加了推荐结果的正确率和可靠性。 主要内容有：研究了如何将用户相关和用户无关两个方向的查询推荐统一于 同一方法中；研究了如何将真实查询操作序列转化成可供挖掘( 抽取模式) 的抽 象查询序列，为后续工作减轻复杂度；研究了如何将实时查询和查询模式相结合， 进行精确概率计算，预测用户下一步查询操作，并分级推荐预测结果。 1 4 本文结构 本文共分七章，按以下结构进行组织： 第一章绪论，介绍了o l a p 的发展背景及本课题的研究意义，将现有的o l a p 查询推荐研究进行了分析论述，并根据其不足之处提出了本文相应的研究内容及 方法，描述了大体研究框架。 第二章详细描述了o l a p 查询操作数据采集的环境建设及工作流程。该采集 方法可以有效的记录分析人员的真实查询操作记录，并按要求格式生成日志文 件，为后续的抽象序列生成及挖掘工作提供合理的训练数据。 第三章介绍了m d x 查询语言规范及o l a p 常见查询操作的概念，着重阐述 了在按位置钻取的条件下，将真实o l a p 查询操作转化为抽象查询序列的过程， 其中分三种情况对转化方法进行了讨论，并通过实验论证了其可行性。 第四章介绍了两种常用的序列模式挖掘算法，并分析了其优缺点，通过抽象 查询序列集合自身特点，选择并研究了基于p r e f i x s p a n 的查询序列模式挖掘算法， 8 浙江大学硕士学位论文第l 章绪论 给出了其描述及算法结构，最后用两组不同参数的实验对该算法进行了验证。 第五章对查询预测基于概率的计算做了详细阐述，介绍了查询预测的工作原 理，同时对查询推荐的工作原理进行了描述。通过实验论证了查询预测与查询推 荐相结合的可靠性。 第六章简要的叙述了本文提出的o l a p 查询推荐系统的原型实现及相关模块 的类。 第七章总结本文完成的主要工作及成果，阐述了本文的主要贡献和创新点， 最后指出在此基础上需要进行的下一步研究工作。 9 * 大 学r t 女 第2 章o l a p 矗询操作数据采集 第2 章o l a p 查询操作数据采集 在介绍研究内容之前，首先将本文提出方法及原型系统所用数据基础的采集 环境、采集流程描述如下。由7 位实验参与人员使用o l a p 多维分析查询软件， 同志系统记录所有多维分析查询语句，并按要求格式生成日志文件，为后续研究 工作提供合理的训练数据。 2 1 查询数据采集 根据第1 章中的分析，无论何种查询推荐方法，都需要获得历史查询记录作 为抽取模式或模型的数据基础。本文的数掘采集环境采用o l a p 服务器为开源 项目m o n d r i a n 3 12 ，部署在t o m c a t 5 e 。其具备图形化查询分析展示界面，用 户进行o l a p 查询操作如钻取、切片、旋转等均可在图形界面上点击标签直接操 作，后台将会自动生成相应m d x 蠢询语句，亦可手动输入m d x 查询语言直接 进行查询。其界面见图2l 。 型型一j u dj 7 j d 面圣jd t i ， i 一 b f 刊 c h 一【 y 一 m n h m n ， 圈2im o n d r i a n 图形北多维教据展示界面 町晰m吼mm悱撕冉m狲啡m晰 浙江大学硕士学位论文 第2 章o l a p 查询操作数据采集 多维数据集为m o n d r i 强, 自带的演示数据集f o o d m a r t ，共1 2 个维度( 包括 t i m e ，s t o r e ，c u s t o m e r s 等多层次维度及g e n d e r ，s t o r et y p e 等单层次维度) ，3 个度量值( 包括u 衄s a l e s ，s t o r e c o s t ，s t o r es a l e s ) ，见图22 。 面到刿剧剧剧到 日月 。 镕# i b i 8 77 幽t l h i i m d 7 * 海i 日口c u s t c , m 2r s b 日纠皿啦n 垃叫 日口6 e n d e r 日0 1 翌自l 塾i t m 日口1 t 蛆i 日i t i 监 日i k j t n j 皿 日口塾i 蛆! 日d i m t y e or = 1 9 9 7 日m j j i 1e * 图2 2 多维数据集f o e , # a m 维度信息 该o l a p 服务器所采用日志系统为开源项目l o 窖q ，日志格式可由用户自行 定义，为方便数据采集，将日志输出格式设置为m a m n ”，即输出用户进行查询 的每条m d x 语句，真实o l a p 查询序列记录即日志文件见图2 3 。 浙江大学顶士学位论文第2 章o l a p 查询撵作数据采集 国箍” 图2 3o l a p 服务器日志文什 查询操作数据采集的参加人员为7 位o l a p 专业分析人员，来自与本实验室 有合作项目的企业，该企业在商业智能领域有着丰富的研发经验，7 位受邀专业 人员均能熟练使用m o n d t i a n 引擎及其图形化展示界面。实验过程采用人为设定的 2 0 个o l a p 分析目标，每个分析目标内含有三项查询目标( 部分分析目标见表 2 1 ) ，7 位实验人员根据分析目标，分别在f 0 0 d m a r t 数据集上进行分析及查询， 由l o g 卅同志系统记录所有分析查询语句形成e l 志文件。 表2 lo l a p 分析目标 n u m b e r q u e s t i o n a l u w e l , 查出在2 0 0 7 年度电视( t v ) 促销中，美国加州( c a ) l o s a n g e l e s 市第7 超市( s u p e l m a r k e t ) 分店的销售额 查出美国华州( w a ) t a c o m a 市第1 7 分店在该年邮件( b u l k 浙江大学硕士学位论文第2 章o l a p 查询操作数据采集 m a i l ) 促销中获得的销售额 查出美国俄州( o r ) s a l e m 市所有类型分店在该年日报( d a i l y p a p e r ) 促销中获得的销售额 2 查出在2 0 0 7 年度日报、广播、电视( d a i l yp a p e r , r a d i o ，t v ) 联合促销中，美国俄州( o r ) s a l e m 市第1 3 豪华型超市( d e l u x e s u p e r m a r k e t ) 分店的销售额 查出加拿大b c 省v a n c o u v e r 第1 9 分店在该年同报、广播、 电视( d a i l yp a p e r ，r a d i o ，t v ) 联合促销中获得的销售额 查出美国加，、i 1 ( c a ) s a nf r a n c i s c o 市第1 4 分店在该年周末报、 广播、电视( s u n d a yp a p e r , r a d i o ，t v ) 联合促销中获得的销 售额 3 查出美国华州( w a ) s e a t t l e 市第1 5 超市( s u p e r m a r k e t ) 分 店在2 0 0 7 年的销售额 2 2 实验结果 参加数据采集的7 位人员，分别根据其不同的查询习惯及偏好，完成2 0 项 o l a p 分析目标，可得7 个日志文件，其中含有查询记录条数见表2 2 。 表2 27 位人员数据采集所得日志文件信息 i d 含有查询记录数量 人员1 人员2 人员3 人员4 人员5 人员6 人员7 3 0 1 3 7 4 4 0 2 2 7 2 3 6 0 3 4 7 2 8 3 浙江大学硕士学位论文第2 章o l a p 查询操作数据采集 2 3 本章小结 本章介绍了o l a p 查询操作数据采集的环境建设及工作流程。根据7 位o l a p 专业分析人员的实验数据，该采集方法可以有效的记录分析人员的真实查询操作 记录，并按要求格式生成日志文件，为后续的抽象序列生成及挖掘工作提供合理 的训练数据。 1 4 浙江大学硕士学位论文第3 章抽象查询序列生成 第3 章抽象查询序列生成 o l a p 服务器日志文件中记录的是用户每个查询操作生成的多维表达式 ( m u l t i d i m e n s i o n a le x p r e s s i o n ，m d x ) 语句，其在很多方面与结构化查询语言 ( s q l ) 语法相似，但它不是s q l 语言的扩展，其自身有一套固定的语法。要对 其采用数据挖掘算法，找出历史查询语句间的规律，则必须对多维表达式语句语 法进行解析，将若干查询语句组成的查询序列提取成可供挖掘的抽象化查询序 列。 本章接下来将介绍一种解析方法，是本文提出的一种适用于解析m d x 语句 所查询的多维数据的维度及层次信息的方法。从语法结构角度先进行分析，找出 其表示查询维度层次信息的语法规范，对其在不同查询情况下的唯一性进行讨 论，最后确定根据此规范将真实的m d x 查询序列转化成整数数列形式的抽象查 询序列，作为数据挖掘的数据基础。 3 1m d x 查询语言及o l a p 查询操作 o l a p 分析采用多维表达式( m d x ) 语句i l 副，其支持多维对象和数据的定义 及操作。见图3 1 ，每个m d x 查询语句包含数据请求( s e l e c t ) 子句，起始点 ( f r o m ) 子句及可选的筛选( w h e i 砸) 子句。s e l e c t 子句决定该条m d x 语 句查询的维度轴；f r o m 子句决定当执行该条m d x 语句时该从哪个多维数据源 提取数据；w h e r e 子句作为可选子句，决定选用哪一维度或层次进行切片。 s e l e c l m e a s u r e s u n i ts a l e s ，【m e a s u r e s s t o r es a l e s 】) o nc o l u m n s ， t i m e 2 0 0 7 ，【t i m e 2 0 0 8 】) o nr o w s f r o ms a l e s w h e r e ( s t o r e u s a 【c a 】) 图3 1 基本m d x 查询语句 浙江大学硕士学位论文第3 章抽象查询序列生成 m d x 查询语言中对多维数据集的维度和层次定义有特定语法结构：对多维 数据集中的维度x 下的第i 层次钻取，所使用的m d x 查询语句遵循“【维度x 】【层 次l 】【层次2 】【层次i c h i l d r e n ”的规范。例如有以下m d x 查询语句，见图3 2 ， 其中含有“c h i l d r e n ”的关键串共三个，分别是：【p r o m o t i o nm e d i a a l l m e d i a c h i l