分布式环境下全局序列模式挖掘技术研究
分布式环境下全局序列模式挖掘技术研究
胡孔法1,2，张长海2，达庆利1，陈崚2
（1. 东南大学经济管理学院，江苏 南京 210096；
2. 扬州大学计算机科学与工程系，江苏扬州 225009）
摘要：由于分布式环境下挖掘全局序列模式常常产生过多候选序列,加大了网络通信代价。为此提出一种基于分布式环境下的挖掘全局序列模式算法-FMGSP(Fast Mining of Global Sequential Pattern)。
FMGSP算法将各站点得到的局部序列模式压缩到一种语法序列树上，避免了重复的序列前缀传输；
基于合并树中结点序列规则、简单的特点，提出一种I/S-E(Item Extension and Sequence Extension)剪枝策略，有效地约减了候选序列，减少了网络传输量，从而快速生成全局序列模式。理论和实验表明，在大数据集环境下的FMGSP算法性能优越，能够有效地挖掘全局序列模式。
关键字：数据挖掘；全局序列模式；语法序列树；I/S-E剪枝
中图分类号：TP311文献标识码：A
Research on mining global sequential pattern on distributed system
HU Kong-fa1，2 , ZHANG Chang-hai2 , DA Qing-li1 , CHEN Ling2
(1. School of Economics & Management ， Southeast University， Nanjing 210096，China；
2. Department of Computer Science and Engineering，Yangzhou University， Yangzhou 225009，China)
Abstract：Now some distributed sequential pattern mining algorithms generate too much candidate sequences, increase communication overhead. In this paper, a new algorithm – FMGSP (Fast Mining of Global Sequential Pattern) on distributed system is proposed. The idea of this algorithm is to compress local frequent sequential patterns into the corresponding lexicographic sequence tree, avoid transmission of repeated prefixes. Basing on the regular and simple sequences of merged trees, a new pruning method that I/S-E (Item Extension and Sequence Extension) pruning is presented to prune candidate sequences effectually. Therefore, communication overhead is reduced greatly, and generate global sequential patterns effectively. The theories and experiments show that the performance of FMGSP is predominant, and it is more effectual when mine global sequential patterns for huge amount of data.
Key words：data mining；global sequential pattern；lexicographic sequence tree；Item Extension and Sequence Extension pruning
0引言
序列模式挖掘在数据挖掘中占有很重要的地位，而且有着广泛的应用前景，如顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列模式的分析等等。从数据库中挖掘序列模式这类问题首先由AGRAWAL R和SRIKANT R两人提出，并总结了序列模式的定义，提出了一种基于Apriori的改进算法GSP（Generalized Sequential Patterns）算法[1]。后来，MANNILA H提出了挖掘频繁序列片段[2]的问题，GAROFALAKIS M提出了基于规则表达式约束[3]的挖掘，ZAKI M提出了一种基于垂直格式存储的序列模式挖掘算法-SPADE算法[4]，近来HAN J又提出了一种基于投影的模式增长的算法-Freespan算法[5]，以及后来基于Freespan的改进算法Prefixspan[6]。
但是在目前的信息主导时代，海量数据存储在数据库或者数据仓库中，这样序列模式挖掘在单机系统中就不能很好地实现，尤其是在功能和性能上已不能够满足数据处理能力的需求。在实际应用的很多大型数据库也是分布存在的，如跨地区的大型购物中心数据存储等。为此，人们提出了分布式序列模式挖掘来解决这一问题。不过分布式序列模式挖掘有着它自身的挑战性，因为在各站点很容易挖掘局部序列模式，但是这些局部序列模式并不一定是决策者想要的全局序列模式，并且序列元素是有序的，由此产生的候选序列数目也是惊人的。目前与分布式序列模式挖掘相关的研究也不少，GURALNIK V 在树投影基础上提出了几种新的基于分布存储的并行挖掘序列模式算法：STPF 算法和DTPF 算法[7]。PARK J S 提出了PDM 算法[8]，以及AGRAWAL R 提出的CD 算法[9]，该算法实质是对Apriori 算法的并行化来挖掘关联规则。为了避免过多的冗余信息，LU Jieping 等人提出了全局最大项目集的挖掘[10]，该算法在不丢失信息的情况下减少了数据量。
CHEUNG D W 又提出了FDM(Fast Distributed of Mining Association Rules)算法[11]，用来解决分布式环境下关联规则挖掘的问题。后来，YANG Ming 等人提出了FMAGF 算法[12]，它采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集，有效地减小了网络通信量。近来人们又提出了FDMSP(Fast Distributed Mining of Sequential Patterns)算法[13]，该算法吸取FDM 算法的精华，采用序列模式前缀指定选举站点来统计全局计数，从而获得全局序列模式。但是该算法在各分站点的序列被分配到选举站点时需要传输的数据量相当大，而且合并子树后经过全局约减的候选序列数量也是相当大。为此本文提出基于分布式环境下的快速全局序列模式挖掘算法FMGSP(Fast Mining of Global Sequential Pattern)，将得到的局部序列模式压缩到一种语法序列树上，避免了前缀的重复出现，有效地减少了数据量；而且基于合并树提出了I/S-E pruning 剪枝策略。实验证明，随着模式的增长，该剪枝操作越来越有效。
1 相关概念
分布式环境下挖掘序列模式，假设分布式环境下有n 个站点S 1，S 2，…，S n ，并且数据库DB 分别被划到n 个站点上，对应的数据库分别为DB 1，DB 2，…，DB n ，各个站点被认为是独立的计算机，且可以互相通信。这样各个站点上的数据序列定义则类似于单机下的定义：设I ={i 1，i 2，…，i n }是一个项目集合，项目集或者项
集(items)就是各种项目组成的集合，也就是I 的所有子集。序列就是若干项集的有序列表，可表示为
s 2，…，s n >，其中s j 为项集，也称作元素。对于序列s 1=和s 2=，当且仅当1≤j 1＜j 2＜…＜j n ≤m ， a 1?b j1，a 2?b j2，…，a n ?b jn 时，称s 2为s 1的超序列， s 1为s 2的子序列，记作：s 1?s 2。
定义1 在分布式系统下，给定模式为
)(。如果count(T)大于全局最小支持计数minCount=|DB|*minSup=(|DB 1|+|DB 2|+…+|DB n |)*minSup ，那么序列T 为全局序列模式
=|DB i|* minSup，那么序列T为局部序列模式(Local Sequential Pattern)。
定义2 站点S i (i=1，2，…，n)上所有局部序列模式可以构成一棵全模式序列树，树根对应空序列，第一层用L1局部序列模式表示，第二层用L2局部序列模式表示，……，第k层用L k局部序列模式表示，而且父节点是子节点的前缀。全模式序列树上对应的L k局部序列模式所生成的子树为L k全模式子树。(L k 序列模式长度) 通常，给定一个序列s=
例1假设s=
性质1 如果存在一个全局序列模式s，那么至少存在一个站点S i (i=1，2，…，n)使得在该站点上序列s及其所有子序列都是全局-本地序列模式。
证明：反证法：假设序列s在任何站点都不是局部序列模式，也就是每个站点上s序列满足count i(s) ＜minCount i (i=1，2，…，n)，因此count(s)= count1(s)+ count2(s)+…+ count n(s) ＜minCount1 + minCount2 +…+ minCount n=(|DB1|+|DB2|+…+|DB n|)* minSup=|DB|*minSup，这表明序列s不是全局序列模式，和前提存在一个全局序列模式s矛盾，得证。
定理1 所有全局序列模式集合F G是所有语法序列树集合的子集。
证明：某站点的语法序列树集合就是该站点对应的所有局部序列模式，根据性质1可知，对于任意一个全局序列模式，必定存在一个站点使得该序列是局部序列模式，所以把各站点对应的所有局部序列模式进行累加，可得：所有的全局序列模式集合是所有语法序列树集合的子集。
2分布式环境下全局序列模式挖掘算法
分布式环境下挖掘序列模式，减少网络传输量是我们的主要目标。因为全局序列模式由局部序列模式产生，所以我们把重点放在对局部序列模式研究上，从而来降低网络传输量。本文在子树被分配到选举站点前所做的工作就是把局部序列模式压缩到语法序列树上，这样能够在不丢失信息的情况下减少传输量，且便于后面合并子树后处理节点时操作方便、快捷；在子树合并后所做的工作就是进行更加有效的I/S-E pruning剪枝操作，从而大大减少全局候选序列，这样在收发请求计数时就节省了很大的代价。
2.1 全局序列模式挖掘技术
首先利用Prefixspan算法[6]在各站点挖掘局部序列模式，然后压缩到相应的语法序列树上(压缩规则见算法解释 (2))。然后算法FMGSP采用算法FDMSP[13]中的选举站点(Polling Site)方法来优化网络通信，把各站点具
有相同根节点的L2子树集中到一个选举站点，最后合并子树，对合并树采取剪枝操作，详细算法见2.2节。
性质2 如果一个序列s的支持度小于minSup，即非频繁序列，那么序列s的任何超序列都是不频繁的序列。
推论1如果序列s不是局部序列模式，那么序列s的超序列一定不是局部序列模式。如果序列s不是全局序列模式，那么序列s的超序列一定不是全局序列模式。
性质2多数用在单机环境下挖掘序列模式，可以有效地剪掉候选序列，而本文则是基于性质2及相关推论提出一种剪枝策略I/E-S pruning，能够有效地剪掉那些局部频繁但不满足全局序列模式的候选序列。
例2序列s作扩展后为s◇s p、s◇s q、s◇i p和s◇i q，如果s◇s p频繁，s◇s q非频繁，根据性质2可知：s◇s p ◇s q、s◇s p◇i q非频繁，同样，s◇i p◇s q、s◇i q◇s q非频繁；如果s◇i p频繁，而s◇i q非频繁，那么s◇i p◇i q非频繁。
基于性质2和相关推论提出下面剪枝策略如下：
⑴ SS剪枝：已知序列s◇sα1◇α2◇…◇αm和s◇sβ，m≥1，如果s◇sβ非全局序列模式，那么序列s◇s α1◇α2◇…◇αm◇sβ非全局序列模式。既可以将序列s作SE扩展生成的孩子节点(s◇sα1)经过若干扩展后可能作SE扩展(扩展项为β)的候选序列去掉。(联结符号◇表示不限扩展类别)
⑵ SI剪枝：已知序列s◇sα1◇α2◇…◇αm和s◇sβ，如果s◇sβ非全局序列模式，那么序列s◇sα1◇α2◇…◇αm◇iβ非全局序列模式。既可以将序列s作SE扩展生成的孩子节点(s◇sα1)经过若干扩展后可能作IE 扩展的候选序列去掉。
⑶ IS剪枝：已知序列s◇sα1◇α2◇…◇αm和s◇sβ，如果s◇sβ非全局序列模式，那么序列s◇iα1◇α2◇…◇αm◇sβ非全局序列模式。既可以将序列s作IE扩展生成的孩子节点(s◇iα1)经过若干扩展后可能作SE 扩展的候选序列去掉。
⑷ II剪枝：已知序列s◇iα1◇iα2◇i…◇iαm和s◇iβ，如果s◇iβ非全局序列模式，那么序列s◇iα1◇i α2◇i…◇iαm◇iβ非全局序列模式。既可以将序列s作IE扩展生成的孩子节点(s◇iα1)经过若干扩展后可能作IE扩展的候选序列去掉。
2.2FMGSP算法描述
输入：各站点S i (i=1,2,…,n)对应的序列数据库DB i(i=1,2,…,n)及最小支持度minSup, 且各站点的最小支持度均为 minSup .
输出：所有全局序列模式集G
Step one :各站点产生局部序列模式，并将其压缩到语法序列树
⑴ for i=1 to n do
Collect all local sequential patterns LPS and their counts for S i;
Generate all L1 global sequential patterns L1-GPS and their counts from L1-LPS;
G= L1-GPS;
⑵ for each site
Select L1 gl-s patterns; // gl-s：全局-本地序列模式
Call generate-lexicotree();
Step two :基于选举站点方法采用I/E-S pruning剪枝技术最终获得全局计数
⑶ for i=1 to n do
Generate n L2-subtree-sets i from the lexicotree at site S i;
⑷ for j=1 to n do
Send L2-subtree-sets i(j) to sites S j;
⑸ for j=1 to n do
Receive L2-subtree-sets j(i);
Call merge() for S j;
⑹for each MT at site S j do // MT-合并后子树
Remove all infrequent patterns by using global pruning and IS-E pruning.
Map MT into MT/; // MT/-合并后全模式子树
Store subtree(unknown-node) into polling request(j) at unknown-node site;
⑺ for j=1 to n do
Send polling request(j) to unknown-node site;
⑻ for j=1 to n do
Receive polling request(j);
⑼ for each MT/ at site S j
For each node N in MT/ do
if count(N)＞minSup *|DB|;
insert N into G j;
⑽ Broadcast G j;
G=∑=n j j G1.
算法解释：该算法分为两大步骤。第一步各站点产生局部序列模式并将其压缩到语法序列树；第二步基于选举站点方法采用I/E-S pruning 剪枝策略，最终获得全局序列。在⑴中，首先通过prefixspan 算法获得局部序列模式，然后通过传统点到点广播式方法来向其它站点发送所有L1序列模式在该站点上的局部计数,累加相应计数，求得L1全局序列模式集合。⑵中，各站点选择L1全局-本地序列模式，进行预处理后压缩到语法序列树上,压缩同时依据性质2进行局部剪枝，具体压缩规则如下：①树根对应空序列，树中每一节点对应一个局部序列模式，第一层对应L1局部序列模式，第二层对应L2局部序列模式，……，第k层对应L k局部序列模式。②如果父亲节点对应一个局部序列模式s，那么它的孩子节点或者对应序列s的SE-序列扩展或者对应IE-项扩展，习惯上先执行项扩展，后执行序列扩展。③每一节点对应的局部序列模式在树中用项序扩展的新添加项表示(第一层、第二层序列除外)，即用s◇α中的α来表示，且标记扩展类别。④左孩子节点对应的局部序列模式在序列语法顺序上要比右孩子对应的小。⑶⑷⑸中，各站点把语法序列树划分为若干L2子树,然后依据hash分配函数将子树集合分配到S j选举站点；基于这些子树，merge()函数约定把L2-subtree-sets j(i)合并到L2-subtree-sets i(root(L2-subtree-sets j(i)))，即把相同根节点的L2子树合并。⑹中，主要针对合并子树进行剪枝操作。其中，count1(s◇sβ)表示序列s◇sβ在已知计数站点上的计数， count2(s◇sβ)表示序列s◇sβ在未知计数站点中父节点s的已知计数，全局剪枝和I/S-E pruning剪枝操作约定：若count/(s◇sβ)= count1(s◇sβ)+
◇s β or s ◇s α1◇α2◇…◇αm ◇i β or s ◇i α1◇α2◇…◇αm ◇s β or s ◇i α1◇i α2◇i …◇i αm ◇i β,则移走以P 为根节点的所有子树。⑺⑻中，请求并返回合并子树中未知计数序列的计数。⑼中，判断树中序列是否满足全局最小支持度。若是，则返回模式。⑽中，各站点广播以获得所有的全局序列模式。
2.3 实例分析
假设三个站点S 1，S 2，S 3，各站点上利用prefixspan 算法挖掘的以a 为前缀的局部序列模式分别为：L 1={
，L 2={
L 3={
当站点S 1和S 3对应的以ac 为根节点的子树分别传输到另一站点S 2时， 只需传输对应序列的最后一个添加项，这样省去了对重复前缀的存储，节省了存储空间； 而且还有效地减少了网络传输量，加快了网络传输速度，尤其对较长的生物DNA 序列。然后当站点S 1和S 3上以序列
图1 语法序列树1 图2 语法序列树2
图3 语法序列树3 图4 合并树
分析：在选举站点S2发送计数请求之前，假设合并树中序列
3算法分析与实验结果
3.1算法分析
FMGSP算法在各站点采用基于前缀的模式增长的序列模式挖掘算法，仅扫描各站点原始数据库两次，生成的L1投影数据库最多也只扫描三次，增加的一次是被用来请求计数，其余的投影数据库均扫描两次，减小了I/O的操作。
将生成的局部序列模式压缩到语法序列树，大大减少了传输的信息量。长度为100的生物DNA序列
在选举站点子树合并后，对合并树进行剪枝操作，利用全局剪枝和项序扩展剪枝结合能够有效地剪掉候选序列。尤其是长度较大的序列，因为像
3.2实验结果
为了验证该算法的有效性，我们利用局域网中三台计算机模拟分布环境下的三个站点来进行测试。实验环境：Windows XP、Pentium IV 2.8GHz、内存256MB，实验数据为合成数据(http：//https://www.wendangku.net/doc/2215941452.html,/cs/projects/iis/hdb/Projects/data_mining/datasets/syndata.html)，生成数据的主要参数依据：|D|：序列数、|C|：平均序列长度、|I|：项目集平均长度、|N|：不同项目数，生成的数据集随机分割在三站点上，利用Visual C++来实现对算法FMGSP的测试。本文将FMGSP算法分别与FDMSP算法[13]和在分布式环境下的改进GSP算法( Distributed Generalized Sequential Pattern ，简称DGSP )进行比较。DGSP算法主要
思想：首先将各站点上数据集中在一个站点上，然后利用GSP算法[1]挖掘全局序列模式，显然算法DGSP的执行时间由数据集中时间和序列挖掘时间组成。
为测试算法FMGSP进行了以下几组实验：第1组实验是对minSup=0.01、|D|=300k、|N|=10k(k=1024)，分别在5、10、15、20、25等5个不同平均序列长度|C|下的算法执行时间，其实验结果如图5所示。第2组实验是对数据集D1200kC10I2.5N10k，分别在0.005、0.01、0.015、0.02、0.025等5个不同最小支持度minSup 下的算法执行时间，其实验结果如图6所示。第3组实验是对minSup=0.01、|C|=10、|I|=2.5、|N|=10k，分别在400k、600k、800k、1000k、1200k等5个不同的序列数|D|下的算法执行时间，其实验结果如图7所示。
图5平均序列长度变化时三算法图6最小支持度变化时三算法DGSP 图7序列数变化时三算法DGSP, DGSP, FDMSP及FMGSP的执行时间FDMSP及FMGSP的执行时间FDMSP及FMGSP的执行时间由图5可以得出，FMGSP算法所需时间比算法DGSP和FDMSP少得多，尤其是当序列平均长度增加时，三算法所需时间均有增加，但算法FMGSP传输数据过程中简化了序列模式，传输的仅为序列的最后一项，有效地减少的网络传输量，所以算法FMGSP时间增加的幅度要小于算法DGSP和算法FDMSP。图6显示当最小支持度较高时，满足最小支持度的模式大大减少，所以算法FMGSP中I/E-S pruning 剪枝操作效率不高，算法FMGSP 和算法FDMSP执行时间几乎一样，但是当支持度较低时，算法FMGSP执行时间明显要低于算法FDMSP。而算法DGSP由于受海量数据集中时间影响，执行时间下降幅度比较小。从图7可以得出，随着序列数据量增长，算法FDMSP和算法DGSP耗时越来越大。这是因为算法FMGSP传输序列的简化模式，且利用剪枝策略跳过语法序列树上一些深层次节点，有效地约减了候选序列，整个过程中减少了网络传输量，性能要明显优于算法FDMSP具备良好的伸缩性。总之，算法FMGSP性能要远远超过算法DGSP，明显优于算法FDMSP，能够在分布式环境下有效地挖掘全局序列模式。
4结束语
本文提出了一种基于分布式环境下的快速挖掘全局序列模式挖掘算法FMGSP，该算法把各站点挖掘到的局部序列模式压缩到语法序列树上，在网络传输时有效地减少了传输量，而且合并子树后，提出了一种有效的I/S-E pruning 剪枝操作，有效地减少了候选序列，提高了挖掘全局序列模式的效率。在I/O操作、网络传输量、时间等方面理论分析及实验都表明该算法是有效的。今后我们将着重研究全局序列模式挖掘算法的更新问题以
参考文献：
[1] SRIKANT R, AGRAWAL R. Mining sequential patterns: Generalizations and performance improvements[C]// Proceedings of the 5th
International Conference on EDBT. Heidelberg, Germany: Springer, 1996: 3-17.
[2] MANNILA H, TOIVONEN H, VERKAMO A I. Discovery of frequent episodes in sequences[C]// Proceedings of the First
International Conference on KDD. New York, N. Y.,USA: ACM Press,1995:210-215.
[3] GAROFALAKIS M, RASTOGI R, SHIM K. Spirit: Sequential pattern mining with regular expression constraints [C]// Proceedings of
25th international Conference on VLDB. San Francisco, Cal., USA: Morgan Kaufmann, 1999:223-234.
[4] ZAKI M. Spade: An efficient algorithm for mining frequent sequences [J]. Machine Learning, 2001, 41(2): 31-60.
[5] HAN J, PEI J. Freespan: frequent pattern - projected sequential pattern mining[C]// Proceedings of the 2000 International Conference
on KDD. New York, N. Y.,USA: ACM Press,2000:355-359.
[6] PEI J, HAN J, MORTAZA VI-ASL B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]//
Proceedings 2001 International Conference Data Engineering. Heidelberg, Germany: Springer,2001:215-224.
[7] GURALNIK V, GARG N, VIPIN K. Parallel tree projection algorithm for sequence mining[C]// EuroPar2001. Manchester:
Springer-Verlag,2001:310-320.
[8] PARK J S, CHEN M S, YU P S. An efficient parallel data mining for association rules[C]//Proceedings of the 4th International
Conference on Information and Knowledge Management. New York, N. Y.,USA: ACM Press, 1995:31-36.
[9] AGRAWAL R, SHAFER J. Parallel mining of association rules[J]. IEEE Trans on Knowledge and Data Engineering, 1996, 8(6):
962-969.
[10] LU Jieping, YANG Ming, SUN Zhihui et al. Fast mining of global maximum frequent itemsets[J]. Journal of Software, 2005,16(4):
p.553-560. (in Chinese)[陆介平,杨明,孙志挥,等.快速挖掘全局最大频繁项目集[J]. 软件学报, 2005,16(4): 553-560.]
[11] CHEUNG D W, HAN J, NG V T, et al. A fast distributed algorithm for mining association rules[C]//Proceedings of the 4th
International Conference on Parallel and Distributed Information Systems. Los Alamitos,Cal., USA:IEEE Computer Society Press,1996:31-44.
[12] YANG Ming, SUN Zhihui, JI Genlin. Fast mining of global frequent itemsets[J]. Journal of Computer Research and Development,
2003,40(4) (in Chinese) . [杨明,孙志挥,吉根林.快速挖掘全局频繁项目集[J]. 计算机研究与发展,2003,40(4).]
[13] ZOU Xiang, ZHANG Wei, LIU Yang, et al. Study on distributed sequential pattern discovery algorithm[J]. Journal of Software,
2005,16(7): 1262-1269 (in Chinese). [邹翔, 张巍, 刘洋, 等. 分布式序列模式发现算法的研究[J]. 软件学报, 2005,16(7): 1262-1269.]
项目情况及作者介绍：
我们数据仓库系统研究与开发课题组在国家自然科学基金、国家863项目、国家和江苏省“十五”重点攻关等项目资助下,已开发出具有知识产权的数据仓库系统原型及其相关数据挖掘产品化工具,目前正在高校信息共享、企业ERP进行试点,下一步将在企事业、银行、金融等行业进行推广应用.其中,已开发出的OLAP及其报表产品化工具,与JSERP进行了集成,获得江苏省科技进步二等奖,产生了巨大的效益,使JSERP得到国家863大力支持,成为我国中小型企业ERP中的重点推广应用产品.本文是课题组在数据仓库及数据挖掘工具方面研究的最新成果.文章未尽之处,敬请各位评审专家批评指正和赐教.
胡孔法男,1970年生,现任扬州大学计算机系软件教研室主任,博士后,副教授,硕士生导师,中国计算机学会CCF高级会员,中国信息化百名学术与管理带头人,江苏省“青蓝工程”优秀青年骨干教师、扬州大学“新世纪人才工程”优秀青年骨干教师.主要研究方向为数据库及信息系统,数据仓库和OLAP等.曾在计算机集成制造系统、计算机研究与发展等国内外核心期刊发表和录用学术论文50余篇,其中SCI、EI收录论文近20篇,获部省级、市厅级及校级奖10多项.
达庆利,男,1945年生,教授,博士生导师,全国政协委员.曾任东南大学系统工程研究所所长、管理科学与工程系系主任,现任东南大学工业工程研究所所长、兼任中国优选法统筹法与经济数学研究会常务理事、《中国管理科学》杂志编委,1993年起享受政府特殊津贴.近年主要研究方向为大系统建模、仿真和优化,企业经营过程分析与决策,项目管理与投资决策以及管理系统工程等; 获13项部、省级以上鉴定成果,其中3项达国际先进水平,其余均达国内领先水平;获国家科技进步奖2等奖1项,获部省级科技进步奖5项,其中部级科技进步特等奖1项.在《管理科学学报》、《系统工程学报》、《中国管理科学》等国家级核心刊物以及国际重要学术刊物和会议论文集上发表论文220余篇,其中有多篇被SCI和EI收录；出版《大系统理论与方法》、《水环境经济系统规划中的系统方法》、《虚拟企业类生物化模型及其运作机制》等专著3本.完成和正在承担多项国家自然科学基金项目、教育部博士学点基金项目等.
陈崚男，1951年生，现任扬州大学信息工程学院院长、计算机科学系教授、博士生导师。中国计算机学会电子政务与办公自动化专业委员会委员、全国高等学校教学研究会计算机学科委员会委员、全国电子高等教育学会理事等。主要从事计算机软件、系统结构、并行算法等方面的研究，在《计算机学报》、《电子学报》、《软件学报》、《计算机研究与发展》、《Parallel Computing》、《Information Processing Letters》、《Journal of VLSI signal processing》、《Computer Systems Science Engineering》等国际国内核心刊物和学术会议上发表学术论文120余篇，其中有19篇被EI摘录，10篇被SCI摘录。出版教材及论著6部。曾有4篇文章被28篇SCI论文引用，其中最多的单篇被引用10次。2001年被评为全国优秀教师，2004年被评为全国师德先进个人等。
数据挖掘算法综述
数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监
督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是
并行序列模式挖掘
并行序列模式挖掘研究概况 1序列模式挖掘问题 R.Agrawal等人在1995年首先提出了序列模式挖掘的概念[1]，其问题描述如下。 在由多个交易组成的交易数据库中，某个交易描述了某个顾客在某时间购买物品的集合。物品的集合叫做项集。相同顾客在不同交易中包含的项集的子集，按时间先后关系排列称为一个序列。每个子集称为一个元素(element)。并且给定由用户确定的最小支持度阈值(min_support threshold)，序列模式挖掘就是去发现所有子序列的出现频率不小于给定的最小支持度的频繁子序列。 2序列模式挖掘研究概况 在序列模式挖掘的问题被提出以后，人们开始在时间序列数据库中挖掘序列模式和其他频繁模式的算法方面不断地进行研究和改进。现有的序列模式挖掘算法主要可以分为两类:第一类是基于Apriori特性的算法[2]。它是由R.Agrawal和R.srikant在1994年提出的。其基本思想是任一个频繁模式的子模式必定是频繁的。基于这一特性，人们提出了一系列类APriori的序列模式挖掘算法，这些算法中有采用水平数据格式(horizontal data format)的算法，如AprioriAll算法[1]、GSP算法[3]、PSP算法[4]等;有采取垂直数据格式(vertica data format)的算法，如SPADE算法[5]、SPAM算法[6]等。第二类是J.Han等人提出的基于模式增长(pattern-growth)策略的算法，如Freespan算法[7]、Prefixspan算法[8],[9]等。另外，C.Antunes 等人提出了SPARSE算法[10]。在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式[11],[12]，Agrawal 等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口(sliding time window)和分类约束，并提出了GSP算法[3]。 上述序列模式挖掘算法都是在一维信息中挖掘序列模式。在多维序列模式方面，H.Pint 等人提出的UniSeq算法[13]能有效地挖掘多维序列模式，但在维度较高时其挖掘性能会有所下降。当前国内外学者研究方向还包括增量式(Incermental)序列模式挖掘[14]、闭合(Closed)序列模式挖掘[15]、周期性(Peirodic)模式挖掘[16]、结构(Strueture)模式挖掘[17]、近似(Approximate)序列模式挖掘[18]等。 3并行序列模式挖掘研究概况 由于并行关联规则挖掘方面的研究起步较早，出现了许多优秀的算法[19]～[24]。而序列模式是关联规则的扩展，并行序列模式挖掘也很快被人们重视起来。 当前大多数并行序列模式挖掘算法都是对串行算法并行化的结果。随着研究的深入与问题的需要，序列模式挖掘的经典算法GSP的思想也逐渐被扩展到了并行序列模式挖掘中。Shintani等人提出了基于GSP算法的三种并行策略NPSPM、SPSPM、HPSPM[25]。在算法NPSPM中，将候选序列复制到所有处理器中，每个处理器利用本地数据库计算其本地支持度，并在每次迭代之后执行一个归约操作，最后得到其全局支持度。NPSPM在每个节点上都复制完整的候选集，在处理大型数据库时常常会导致内存溢出；SPSPM策略将候选集划分成大小相等的块后分别置于各个处理器中。但是SPSPM利用系统的聚合内存，容易引起额外的通信开销，因为为了得到序列的全局支持度，每个处理器的本地数据库必须广播到其他所有的处理器上；HPSPM采用了一个更加智能的策略，一方面基于Hash机制对候选序列进行划分，另一方面，它减少了所需的通信时间。相比前面两个并行策略，HPSPM的性能最好。 Guralnik等人提出了一类基于树投影技术的并行序列模式算法[26],[27]。根据并行策略，算法可被分为两种。一种是数据并行模式DPF：原始数据库被划分成p个大小相等的块存于p个处理器上，每个处理器拥有一个相同的字典树，各处理器计算本地支持度然后通过通
数据挖掘考试题库
1.何谓数据挖掘？它有哪些方面的功能？ 从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程称为数据挖掘。相关的名称有知识发现、数据分析、数据融合、决策支持等。 数据挖掘的功能包括：概念描述、关联分析、分类与预测、聚类分析、趋势分析、孤立点分析以及偏差分析等。 2.何谓粒度？它对数据仓库有什么影响？按粒度组织数据的方式有哪些？ 粒度是指数据仓库的数据单位中保存数据细化或综合程度的级别。粒度影响存放在数据仓库中的数据量的大小，同时影响数据仓库所能回答查询问题的细节程度。按粒度组织数据的方式主要有： ①简单堆积结构 ②轮转综合结构 ③简单直接结构 ④连续结构 3.简述数据仓库设计的三级模型及其基本内容。 概念模型设计是在较高的抽象层次上的设计，其主要内容包括：界定系统边界和确定主要的主题域。 逻辑模型设计的主要内容包括：分析主题域、确定粒度层次划分、确定数据分割策略、定义关系模式、定义记录系统。 物理数据模型设计的主要内容包括：确定数据存储结构、确定数据存放位置、确定存储分配以及确定索引策略等。在物理数据模型设计时主要考虑的因素有: 存取时间、空间利用率和维护代价等。 提高性能的主要措施有划分粒度、数据分割、合并表、建立数据序列、引入冗余、生成导出数据、建立广义索引等。 4.在数据挖掘之前为什么要对原始数据进行预处理？ 原始业务数据来自多个数据库或数据仓库，它们的结构和规则可能是不同的，这将导致原始数据非常的杂乱、不可用，即使在同一个数据库中，也可能存在重复的和不完整的数据信息，为了使这些数据能够符合数据挖掘的要求，提高效率和得到清晰的结果，必须进行数据的预处理。 为数据挖掘算法提供完整、干净、准确、有针对性的数据，减少算法的计算量，提高挖掘效率和准确程度。
数据流挖掘算法研究综述
－1130－ 1引言 所谓数据流就是大量连续到达的、潜在无限的数据的有序序列，这些数据或其摘要信息只能按照顺序存取并被读取一次或有限次。在网络监控、入侵检测、情报分析、金融服务、股票交易、电子商务、电信、卫星遥感（气象、环境资源监控等）、Web 页面访问和科学研究等众多领域中，数据以流的形式出现。由于数据流的特殊性，短时间内有大量数据连续到达，这些数据具有随时间动态变化的趋势，往往又是高维的，怎样对这些流数据使用有限存储空间进行快速处理以获取有用信息，为数据挖掘及其应用研究带来了新的机遇和挑战，也具有非常重要的意义。由于众多应用领域的需求，近几年数据流处理问题，特别是数据流挖掘问题已受到越来越多的研究人员关注。国外在数据流挖掘方面有两个比较有影响的研究小组：一个是Stanford 大学的R.Motwani 教授领导的研究小组，另一个是UIUC 的C.Aggarwal 和J.Han 教授领导的研究小组。前者的研究侧重在数据流管理、数据流的连续查询和数据流的聚类方面 [1-4] ，提出了不同于传统DBMS 的DSMS （Data Stream Management System ）概念，他们的研究得到了美国国家自然科学基金的资助。后者的研究侧重在数据流分析方面，对于数据流的在线分析,从聚类、分类、频繁项集挖掘以 及可视化等角度做了大量研究工作[5-8]，提出了倾斜时间窗口（tilted-time window ）策略，采用不同时间粒度保存数据流的信息，他们的研究得到了美国军方和国家自然科学基金的资助。目前鲜见国内在数据流挖掘方面公开发表的研究文献。本文拟对数据流挖掘的研究现状进行总结，并对存在的问题和未来的研究方向提出我们的观点。 2数据流挖掘研究现状 目前数据流挖掘方面的研究成果主要集中在数据流的聚 类、分类和频繁模式挖掘方面。 2.1数据流聚类算法研究 尽管聚类问题在数据库、数据挖掘和统计等领域得到了 广泛研究，流数据的分析仍为聚类算法提出了前所未有的挑战，由于完整甚至部分地存储过去数据的方法不可行，需要能够只使用新数据就能够追踪聚类变化的算法，这就要求算法必须是增量式的，对聚类表示要简洁，对新数据的处理要快速，对噪音和异常数据是稳健的。因为数据流可看成是随时间不断变化的无限过程，其隐含的聚类可能随时间动态地变化而导致聚类质量降低。近年来，有学者提出了应用于大规模数据集的一趟聚类算法，如Squeezer 算法[9]和BIRCH [11]算法，它们可以应用于某些数据流问题，也有学者提出了针对流数 收稿日期：2004-06-12。基金项目：国家自然科学基金项目（60273075）。 作者简介：蒋盛益(1963-)，男，湖南隆回人，副教授，博士生，研究方向为数据挖掘和网络安全；李庆华，教授，博士生导师，研究方向为并行计算、网格计算和网络安全；李新，硕士生，研究方向为数据挖掘和并行计算。 2005年5月计算机工程与设计 May.2005 第26卷第5期Vol.26 No.5 数据流挖掘算法研究综述 蒋盛益1，2 ，李庆华1，李 新1 (1.华中科技大学计算机学院，湖北武汉430074；2.衡阳师范学院计算机系，湖南衡阳421008) 摘 要：流数据挖掘是数据挖掘的一个新的研究方向，已逐渐成为许多领域的有用工具。在介绍数据流的基本特点以及数据流挖掘的意义的基础上，对现有数据流挖掘算法的主要思想方法进行了总结，并指出了这些方法的局限性。最后对数据流挖掘的发展方向进行了展望。 关键词：数据流；数据流挖掘；聚类；分类；频繁模式中图法分类号：TP3ll 文献标识码：A 文章编号：1000-7024(2005)05-1130-03 Survey on data stream mining JIANG Sheng-yi 1,2, LI Qing-hua 1, LI Xin 1 (https://www.wendangku.net/doc/2215941452.html,puter School,Huazhong University of Science and Technology,Wuhan 430074,China;https://www.wendangku.net/doc/2215941452.html,puter Department, Hengyang Normal University,Hengyang 421008,China ) Abstract ：Data stream mining is a new research aspect of data mining.It has be come a useful tool for many fields.The essential characteristic of data stream and the significance of data stream mining are introduced.The main ideal of existing data stream mining algorithms is summarized,and the limitation of the algorithms is pointed out.Some research directions about data stream mining in future work are put forward. Key words ：data stream;data stream mining;clustering,classification;frequent pattern Computer Engineering and Design
数据流高效用模式挖掘综述
第37卷第9期 计算机应用研究 V ol. 37 No. 9 录用定稿 Application Research of Computers Accepted Paper —————————— 收稿日期：2019-03-21；修回日期：2019-05-14 基金项目：国家自然科学基金资助项目(61563001)；宁夏自然科学基金资助项目(NZ17115)；北方民族大学研究生创新项目(YCX18052) 作者简介：王少峰(1993-)，男，陕西西安人，硕士研究生，主要研究方向为数据挖掘；韩萌(1982-)，女(通信作者)，河南商丘人，副教授，硕导，博士，主要研究方向为数据挖掘(2003051@https://www.wendangku.net/doc/2215941452.html,)；贾涛(1993-)，男，陕西韩城人，硕士研究生，主要研究方向为数据挖掘；张春砚(1995-)，女，河北张家口人，硕士研究生，主要研究方向为数据挖掘；孙蕊(1993-)，女，山东邹城人，硕士研究生，主要研究方向为数据挖掘． 数据流高效用模式挖掘综述 * 王少峰，韩 萌?，贾 涛，张春砚，孙 蕊 (北方民族大学 计算机科学与工程学院, 银川 750021) 摘 要：数据流高效用模式挖掘方法是以二进制的频繁模式挖掘方法为前提，引入项的内部效用和外部效用，在模式挖掘过程中可以考虑项的重要性，从而挖掘更有价值的模式。从关键窗口技术、常用方法、表示形式等角度对数据流高效用模式挖掘方法进行分析，并总结其相关算法，从而研究其特点、优势、劣势以及其关键问题所在。具体来说，说明了数据流高效用模式常用的概念；对处理数据流高效用模式的关键窗口技术进行了分析，涉及到滑动、衰减、界标和倾斜窗口模型；研究了一阶段和两阶段的数据流高效用模式挖掘方法；分析了高效用模式的表示形式，即完全高效用模式和压缩高效用模式；介绍了其他的数据流高效用模式，包括序列高效用模式、混合高效用模式以及高平均效用模式等，最后展望了数据流高效用模式挖掘的进一步研究方向。 关键词：综述；数据流挖掘；高效用模式；窗口模型 中图分类号：TP3 doi: 10.19734/j.issn.1001-3695.2019.03.0105 Survey of high utility pattern mining over data streams Wang Shaofeng, Han Meng ?, Jia Tao, Zhang Chunyan, Sun Rui (School of Computer Science & Technology , North Minzu University , Yinchuan 750021, China ) Abstract: The high utility pattern mining methods over data stream are based on the binary frequent pattern mining methods, and introduce the internal utility and external utility of the item. In the pattern mining process, it can consider the importance of the item to explore more valuable patterns. From the perspective of key window technologies, common methods and representations, this paper analyzes the high utility mining methods over data stream and summarizes the related algorithms to study its characteristics, advantages, disadvantages and key problems. Specifically, it illustrates the common concepts of high utility pattern mining over data stream; it analyzes the key window technologies for processing data flow efficient mode, involving sliding, damped, landmark and titled window model; researches one-phase and two-phase high utility pattern mining methods over data stream; analysis of representation of the high utility pattern, that is, complete high utility pattern and the compressed high utility pattern; introduces other high utility pattern mining methods over data stream, including sequence high utility pattern, hybrid high utility pattern and high average utility pattern, etc. , finally, this paper looks forward to the further research direction of high utility pattern mining methods over data stream. Key words: survey; data stream mining; high utility pattern; window models 0 引言 近年来，随着大数据的发展，数据流中存储着越来越多的有趣信息。频繁模式挖掘是挖掘数据流中有趣信息的重要方法，但传统的频繁模式挖掘算法只考虑事务中项的二进制 (0/1)值，即项存在(1)或不存在(0)，但在实际应用中，还需考虑项在每条事务中出现的次数(或数值大小)，以及项的权重。为了克服频繁模式挖掘的局限性，研究者提出了高效用模式挖掘方法用。该方法考虑事务的非二进制的内部效用和每个项的外部效用，与传统频繁模式挖掘方法相比，数据流高效用模式挖掘存在几个挑战： a) 内部效用与外部效用的设置。在传统的数据流中，如何对项添加内、外部效用，以及如何判定得到的模式为高效用模式，是需要解决的问题。 b) 向下闭包属性的维护。由于高效用模式的内部效用与外部效用大小是独立且不确定的，导致高效用模式无法满足 向下闭包属性。 c) 满足数据流特性的高效用模式挖掘方法。由于添加了内、外部效用，挖掘数据流中频繁模式方法，如FP-stream [1]、 FP-CDS [2]，DSMRM-BLW [3]、TDMC [4]等，并不适用于高效 用模式挖掘，在数据存储以及窗口模型更新等方面需要进一步改善。 d) 高效用压缩模式的挖掘。内、外部效用的加入导致高效用模式的压缩约束产生变化，如何进行针对性的高效用压缩模式的挖掘，也是重要的挑战之一。 针对以上挑战，Yao 等人[5]首次提出高效用项集挖掘的理论基础，确定了项集的有用性(即效用约束)的数学属性。只有当项集满足给定的效用约束时，用户才对它感兴趣。并引入高效用项集挖掘算法MEU ，该方法允许用户使用效用值 来量化他们对项集有用性的偏好。Liu 等人[6, 7]提出的TWU 模型，有效维护了高效用模式的向下闭包属性。该模型先得到每条事务的效用总和TU(transaction utility)，并对所求项集 存在事务的TU 相加得到项集的事务加权效用 TWU(transaction weighted utility)，用于挖掘候选模式，此模型满足向下闭包属性。Ahmed [8]提出的HUPMS 算法使用了 滑动窗口模型，在模式树中存储每个项批次的加权事务效用
Web数据挖掘综述
Web数据挖掘综述 摘要：过去几十年里，Web的迅速发展使其成为世界上规模最大的公共数据源，因此如何从Web庞大的数据中提取出有价值的信息成为一大难题。Web数据挖掘正是为了解决这一难题而提出的一种数据挖掘技术。本文将从Web数据挖掘的概念、分类、处理流程、常用技术等几方面对Web数据挖掘进行介绍，并分析了Web数据挖掘的应用及发展趋势。 关键词：Web数据挖掘；分类；处理流程；常用技术；应用；发展趋势 Overview of Web Data Mining Abstract:Over the past few decades,the rapid development of Web makes it becoming the world’s largest public data sources.So how to extract valuable information from the massive data of Web has become a major problem.Web data mining is the data mining technology what is in order to solve this problem.This article introduces the Web data mining from its concept, classification,processing,and common techniques,and analyzes the application and the development tendency of Web data mining. Key words:Web Data Mining;Classification;Processing;Common Techniques;Application; Development Tendency 0.引言 近些年来，互联网技术的飞速发展，带来了网络信息生产和消费行为的快速拓展。电脑、手机、平板电脑等终端的普及，SNS、微博等Web2.0应用的快速发展，促进了互联网信息数量的急剧增长，信息资源前所未有的丰富。但同时，海量级、碎片化的信息增加了人们获取有效信息的时间和成本[1]。因此，迫切需要找到这样的工具，能够从Web上快速有效地发现资源，发现隐含的规律性内容，提高在Web上检索信息、利用信息的效率，解决数据的应用问题，Web数据挖掘正是一个很好的解决方法。 1.Web数据挖掘概念 Web数据挖掘，简称Web挖掘，是由Oren Etzioni在1996年首先提出来的[2]。Web数据挖掘是数据挖掘在Web上的应用，它利用数据挖掘技术从与Web相关的资源和行为中抽取感兴趣的、有用的模式和隐含信息，涉及数据库技术、信息获取技术、统计学、机器学习和神经网络等多个研究领域的技术[3]。 2.Web数据挖掘分类 Web上包括三种类型数据：Web页面数据、Web结构数据和Web日志文件[4]。依据在挖掘过程中使用的数据类别，Web数据挖掘可以分为Web内容挖掘，Web结构挖掘，Web 使用挖掘三类。 2.1Web内容挖掘 Web内容挖掘是从文档内容或其描述中抽取有用信息的过程。Web内容挖掘有两种策略：直接挖掘文档的内容和在其他工具搜索的基础上进行改进。根据挖掘出来的数据可以将
遗传算法的数据挖掘综述
基于遗传算法的数据挖掘综述 朱玲 (江西理工大学信息工程学院，赣州市中国 341000) 摘要：本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。 关键词：数据挖掘;遗传算法 Data Mining Based on Genetic Algorithm Zhu Ling (College of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, China 341000) Abstract:This paper defines the concept of genetic algorithm and the source of the theory, introduces the research direction and application field of genetic algorithm, explains the related concepts, coding rules, three main operators and fitness functions of genetic algorithm, describes the genetic algorithm calculation process and Parameter selection criteria, and in the given genetic algorithm based on the combination of practical applications to be explained. Key words: data mining; genetic algorithm 前言 遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。遗传算法于20世界六七十年代由John Holland[1] 发展而成。它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。 遗传算法借助了大量的基因术语。遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。 1.遗传算法的应用领域和研究方向 1.1遗传算法的特点 遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结构对象的优化过程中显示出比传统优化方法更为独特的优势和良好的性能。它利用其生物进化和遗传的思想，所以它有许多传统算法不具有的特点[3]： ※搜索过程不直接作用在变量上，而是作用于由参数集进行了编码的个体上。此编码操作使遗传算法可以直接对结构对象进行操作。 ※搜索过程是从一组解迭代到另一组解，采
时间序列模式挖掘
第6章时间序列和序列模式挖掘(讲稿) 6.1时间序列及其应用 时间序列（Time Series）挖掘是从大量的时间序列数据中提取人们事先不知道的但又是潜在有用的信息和知识，是数据挖掘中的一个重要研究分支，有广泛的应用价值。 近年来，时间序列挖掘在宏观的经济预测、市场营销、客流量分析、太阳黑子数、月降水量、河流流量、股票价格变动（长期的观察，有周期性）等众多领域得到应用。事实上，社会、科学、经济、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。 时间序列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，是获得知识的有效途径。 从统计意义上来讲，所谓时间序列就是将某一指标在不同时间上的不同数值，按照时间先后顺序排列而成的数列。它可以是观察值也可以是记录值。 这种数列由于受到各种偶然因素的影响。往往表现出某种随机性，彼此之间存在着在统计上的依赖关系。虽然每一时刻上的取值或数据点的位置具有一定的随机性，不可能完全准确地用历史值来预测将来。但前后时刻的数值或数据点的相关性往往呈现某种趋势性或周期性变化----这是时间序列挖掘的可行性之所在。 时间序列挖掘通过对过去历史行为的客观记录分析，揭示其内在规律（如波动周期，振幅，趋势），进而完成预测未来行为等决策性工作。人们希望通过对时间序列的分析，从大量的数据中发现和揭示某一现象的发展变化规律或从动态的角度刻画某一现象与其他现象之间的内在数量关系，以掌握和控制未来行为。 简言之，时间序列数据挖掘就是要从大量的时间序列数据中提取人们事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、经济、军事和生活等行为。 从数学意义上来讲，如果我们对某一过程中的某一变量进行X(t)观察测量，在一系列时刻t1，t2，…，t n（t为自变量，且t1 研究生学位论文开题报告 题目名称：基于隐私保护的多源数据挖掘高效算法研究 姓名： 学号： 专业名称： 研究方向： 攻读学位： 学院： 导师姓名： 导师职称： 填表时间年月日 填表说明 1．开题报告是研究生培养的重要环节，研究生需在认真完成。 2．完成时间：硕士研究生的开题报告应于第三学期末前完成 3．打印要求：此表用A4纸双面打印。 4．此表与中期考核审核表、成绩单、实践报告、学术活动列表等材料一起交于学院，参加中期考核 一、课题来源，国内外研究现状、水平及发展趋势，选题的研究意义、目的，参考文献（一）课题来源 1、问题的提出 数据挖掘，顾名思义即是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在的、有用信息，提取的知识表示为概念、规则、规律、模式等形式[1]。数据挖掘要处理的问题，就是在庞大的数据库中寻找有价值的隐藏事件，加以分析，并将这些有意义的信息归纳成结构模式，提供给有关部门决策时参考。目前已经提出的常用方法有关联规则、决策树、聚类、神经网络等方法。 然而，在对数据进行挖掘的时候，都不可避免的会出现敏感信息泄露的问题，随着数据挖掘技术的日益发展，数据隐私和信息安全逐渐引起人们的关注。为了保护数据的隐私，人们不愿提供正确的信息给服务商，以免个人信息泄露造成不必要的麻烦，但是数据挖掘结果准确的重要前提是提供的数据正确。由于数据挖掘主要任务是对汇总数据的模式开发，这使得构造一个不需要访问精确的单个信息而获得准确的模式的挖掘技术成为可能。目前，基于隐私保护的数据挖掘技术已经成为一个新颖热门的研究领域，国内外已有很多成熟的研究算法和技术。 通过众多文献比对我们发现，目前已有的这些基于隐私保护的数据挖掘算法和技术大多是针对单源数据库进行挖掘和保护，而在实际应用中，有很多情况必须面对多个数据源。例如，许多大型企业、跨国公司都拥有过个子公司，每个子公司都有自己相应的数据库。这就迫切需要数据库挖掘系统具有针对多数据源进行挖掘和保护的能力。已有的国内外文献中，针对多源数据进行挖掘的模型和算法已经出现，但是基于隐私保护技术的多源数据挖掘研究却很少提及。这可能是由于多源数据挖掘本身的技术局限性，导致在对多个数据源进行挖掘时，泄露敏感信息都成为了不可避免的操作。因此，本文在对当前已有的多源序列模式挖掘技术研究的基础上，分析结合并行和隐私保护技术的特点，提出新的基于隐私保护的多源数据挖掘高效算法，使得在多源环境下既可以高效率高准确度的挖掘出高投票率模式（全局模式），又可以隐藏敏感序列模式，达到较好的隐私保护效果。 （二）国内外研究现状、水平及发展趋势 1、隐私保护技术的研究进展 关于数据的隐私保护问题，首次是由Adam N等学者在《Security-control methods for statistical databases: A comparison study》[2]一文中提出，文章中提出了一种用扰动的方式来解决数据的隐私保护。所谓“扰动”就是发布数据集失真，数据获得者无法通过其他途径构建出原始数据集，但是这个失真的数据集又仍然保持数据获得者所希望保留的某种特性。基于数据失真的技术还有随机扰动、阻塞和凝聚等。目前常用的隐私保护技术大多都是以统计模型和概率模型为主理论，应用在较低层次的数据隐私保护。在分布式环境中，Clifton C等提出使用SMC (Secure Multi-party Computation)安全多方计算加密技术保证数据的通信安全[3],这种基于加密的隐私保护技术可适用于科学计算、分布式安全查询、几何计算、分布式数据挖掘等应用。当前，关于SMC的研究主要集中在减低计算开销、以SMC为工具解决问题以及优化分布式计算协议。在国内，关于隐私保护技术的研究主要集中在基于数据失真或数据加密技术方面的研究，如基于隐私保护分类挖掘算法、关联规则挖掘、分布式数据的隐私保护协同过滤推荐、网格访问控制等。(国内研究现状) 对数据进行隐私保护，主要可分为在数据发布过程中和在数据挖掘过程中进行。目前已有的针对数据发布的隐私保护技术已经有很多，本文主要讨论数据挖掘中的隐私保护技术。 2、隐私保护数据挖掘的研究进展 数据挖掘中的文本挖掘的分类算法综述 摘要 随着Internet上文档信息的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN 文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析；最后对全文工作进行了总结和展望。 关键词：数据挖掘，文本挖掘，文本分类算法 ABSTRACT With the development of Web 2.0, the number of documents on the Internet increases exponentially. One important research focus on how to deal with these great capacity of online documents. Text classification is one crucial part of information management. In this paper we first introduce the basic information of data mining, including the methods, contents and the main existing problems in data mining fields; then we discussed the text mining, one active field of data mining, to provide a basic foundation for text classification. And several common algorithms are analyzed in Chapter 3. In chapter 4 thorough research of KNN text classification algorithms are illustrated including the statistical and dimension reduction based on LSA and in chapter 5 we make some predictions for data mining, text mining and text classification and finally we conclude our work. KEYWORDS： data mining, text mining, text classification algorithms，KNN 目录 摘要 (1) ABSTRACT (1) 目录 (1) 收稿日期:2007-08-24;修回日期:2007-11-17 作者简介:陈卓,博士,主要研究方向为数据挖掘(chenzhou613@https://www.wendangku.net/doc/2215941452.html,);杨炳儒,教授,博导,主要研究方向为数据挖掘、推理机制与知识发现等. 序列模式挖掘综述 陈 卓,杨炳儒,宋 威,宋泽锋 (北京科技大学信息工程学院,北京100083) 摘 要:综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念;其次总结了序列模式挖掘的一般方法,介绍并分析了最具代表性的序列模式挖掘算法;最后展望序列模式挖掘的研究方向。便于研究者对已有算法进行改进,提出具有更好性能的新的序列模式挖掘算法。关键词:数据挖掘;序列模式;周期模式;增量式挖掘 中图分类号:TP 311 文献标志码: A 文章编号:1001-3695(2008)07-1960-04 Sur vey of sequen tial pat ter n m inin g CHE N Zhuo,YAN G Bing-ru,S ON G Wei,S ON G Ze-feng (S chool of Infor mation Engineering,Beijing Univer sity of S cience &Technology,Beijing 100083,C hina) Abst ract :This pa per prov ided a review of the res ea rch of sequential pa tt ern m ining.Firstly,introduced the ba ckground and context .S econdly,sum m a rized the genera l m et hods of sequence pa tt ern m ining,introduced and analyz ed the m os t represent ative a lg orithm to prov ide a basis for im proving old algorit hm s or developing new effect iv e ones.Fina lly,dis cussed som e future re-s ea rch t rends on t his area . Key words:dat a m ining ;sequent ia l pat tern;periodic pa tt ern;increm enta l m ining 数据挖掘作为知识发现的核心步骤,旨在从海量数据中提取有效的、新颖的、潜在有用的、易被理解的知识。序列模式挖掘(sequent ia l pa tt ern m ining)是数据挖掘中非常重要的一个研究领域,最早是由Ra kesh Agraw al 和Ram a krishna n S rikant 在针对超市中购物篮数据的分析提出来的。序列模式挖掘是要找出序列数据库中所有超过最小支持度阈值的序列模式 [1] 。它 有着广泛的应用领域:商业组织利用序列模式挖掘去研究客户购买行为模式特征、计算生物学中序列模式挖掘用来分析不同氨基酸突变模式、用户Web 访问模式预测以及DN A 序列分析和谱分析。序列模式挖掘与关联规则挖掘在许多方面相似,但它更关心数据之间顺序的关联性。 1 序列模式挖掘任务定义 基本概念: 定义1 事务数据库(t ransaction da taba se):以超市数据为例来说明,即由顾客交易记录组成的数据库。Custom_ID 、T ra nsaction_Tim e 、It em set 分别代表顾客标志、交易时间和交易物品集合。 定义2 项集(it em s et):各个项(it em )组成的集合。定义3 序列(sequence):不同项集的有序排列。序列S 可以表示为S =〈s 1,s 2,…,s n 〉。其中:s j (1≤j ≤n )为项集,也称为序列S 的元素。 定义4 序列的元素(elem ent):表示为(x 1,x 2,…,x n )。其中:x k (1≤k ≤m )为不同的项。 定义5 序列长度:一个序列包含的所有项集的个数,长度为1的序列记为1-序列。 定义6 序列的包含:设存在两个序列α,β。其中:α=〈a 1,a 2,…,a n 〉,β=〈b 1,b 2,…,b n 〉。如果存在整数1≤j 1研究生论文开题报告--基于隐私保护的多源数据挖掘高效算法研究
数据挖掘中的文本挖掘的分类算法综述
序列模式挖掘综述