属性挖掘（共6篇）
属性挖掘 篇1
近年来, 随着Web2.0与电子商务的快速发展, 互联网上各类产品的主观评论数量急剧增长, 这些观点评论对于用户做出购买决策、企业做出生产决策、改进客户关系等具有重要意义, 针对产品的意见挖掘研究领域也因此成为研究热点之一。在早期研究中, 对产品的意见挖掘大多针对产品整体的极性, 而对于产品具体属性的极性则无法判断。这种整体挖掘显然是无法满足用户与企业需求的, 因为实际的评论者可能对产品的某些属性做出正面评价, 同时对另一些属性做出负面评价。对产品的意见挖掘因此逐步走向更深的层次——产品属性挖掘。
1产品属性挖掘的相关概念
根据Kim和Hovy对意见的定义, 意见由四个元素组成:即主题 (Topic) 、持有者 (Holder) 、陈述 (Claim) 、情感 (Sentiment) 。该四元素之间具有内在联系。Popescu A M在此基础上将产品意见挖掘划分为三个子任务: (1) 挖掘产品特征; (2) 判定句子的语义倾向性; (3) 总结挖掘结果, 以此确立了产品意见挖掘的基本思路。典型的深层次的产品意见挖掘致力于前两个子任务的研究, 通常可分为属性驱动模式和情感驱动模式, 产品属性挖掘则是产品意见挖掘在属性驱动模式下的研究领域。
所谓产品属性挖掘, 就是从句子si={ w1, w2, …, wn } 所构成的序列中找到{ f1, f2, …, fn } 集合中的产品属性fi, 并以此辅助意见挖掘的研究。由于属性多表现为名词和名词短语, 因此属性挖掘可以理解为被评论的名词或名词短语的识别。在大量真实评论文本中, 这些属性通常是以以下两种方式出现: (1) 产品的部分; (2) 产品的特征及其外延。
例1:iPhone4的屏幕很好看, 但性价比不高。
上例中“屏幕”、“性价比”都是iPhone4这款手机的属性, 也是属性挖掘的对象。
2产品属性挖掘研究现状
在国外, 最早的产品属性挖掘一般都是通过专家人工完成, 如Li Zhuang对电影相关属性的构建等。无论在英文领域还是中文领域, 利用计算机辅助产品属性挖掘研究领域的兴起都是近年的事。2004年前出现过Peter等人提出过关于产品意见挖掘的初步思路, 也有一些做出了具有实际应用价值的挖掘系统如ReviewSeer等。然而这些研究主要是以产品的整体极性为主, 对于产品的属性则并未涉及。
正式系统研究产品属性挖掘的是美国伊利诺斯大学Bing Liu, Minqing Hu, 其团队在2004-2005年提出了关联规则挖掘算法, 并以此为基础设计了Opinion Observer系统, 该系统能够对指定产品的主要属性进行挖掘对比。Popescu A M等人改进了Hu的方法, 并提出了PMI检验法, 以较低召回率的代价较大幅度地提高了产品属性挖掘的准确率。
中文领域产品属性挖掘起步稍晚, 2006年姚天昉团队开发出的汉语意见挖掘系统, 是首次在意见挖掘领域中应用属性挖掘成果的系统。近几年, 余传明、吴月萍教授等对该领域进行了较深入的研究, 宋晓雷等也从命名实体识别的角度对产品属性挖掘进行了探索。
总的看来, 产品属性挖掘可分为早期的人工挖掘和近年兴起的计算机辅助挖掘两个发展阶段。
2.1人工挖掘
人工挖掘依靠专家在某个领域的专业知识, 凭借个人经验对评论中的产品属性进行手工筛选, 进而建立属性或本体表, 以此为产品意见挖掘服务。具体实现手段有以下两种:
(1) 人工建立属性列表。
Zhang L等人利用电影产品属性的相互关联, 将电影的产品属性分为电影元素 (如Screenplay, Vision Effect) 以及与电影相关的人员 (如Director, Screenwrite, Actor) 两类, 每一类包含具有内在联系的部分属性。
(2) 人工构造领域本体。
所谓领域本体是用于描述特定领域知识的一种专门工具, 是对某个领域知识概念化的详细说明。它给出了领域实体概念、领域属性概念、领域属性值及相互关系, 以及该领域所具有的特性和规律的一种形式化描述。
使用领域本体描述概念的优势在于能够清晰地描述各个概念间的层次关系。现实生活中的许多数据, 尤其是文本数据都可以使用本体语言描述, 这使得领域本体成为属性挖掘的极佳载体。
姚天昉教授在其汽车评论中引入了领域本体的思想。其为汽车的每个属性建立了父节点与子节点, 如其中对汽车总体下分“部件”、“综合”、“技术”三项子属性, 其中“部件”属性又包含“车身”、“电气设备”、“底盘”、“发动机”四项子属性。全体属性及其相互关系共同组成汽车属性领域本体, 每个属性都处于明确的本体层中, 这使得属性之间具有明晰的层次关系, 规范了产品属性挖掘的形式。
人工构造属性列表与人工构造领域本体, 二者本质上均属于人工定义形式的挖掘方式。两种方式均对个人有相当程度的依赖, 需要本领域专家参与才能完成, 一旦领域迁移或产品功能发生变化, 则需重新构造。这使得这些方法移植性与动态性较差, 无法推广使用。但近年来领域本体的自动构建发展较为迅速, 如就提出可以利用维基百科进行本体的自动构建的想法, 但实质上已不属于人工构建方法, 此不赘述。
2.2计算机辅助挖掘
计算机辅助挖掘是目前产品属性挖掘的主流方法, 也是产品属性挖掘发展的必然趋势。该类方法通过给定的模板、词典、标注语料等, 利用计算机执行一定的规则, 辅助挖掘评论中的产品属性。这些方法条目繁多, 按照不同的标准划分往往有较大的差别。如按照挖掘过程中人工干预的程度可分为:半自动与全自动;按照训练过程的不同分为:有监督与无监督;按照是否具有移植性可分为:领域依赖于非领域依赖等。这些划分都有一定道理, 其中一些指标应该成为未来属性挖掘方法追求的目标。但若从这些方法的最基础的理论依据来看, 这些方法可以归结为两类。
第一类以语言学为基础, 依靠人类语言中的结构、规则等来挖掘产品属性。
例2:这汽车的方向盘和油门很精致。
根据语法规则, 上句中“方向盘和油门”处于“的”字之后且位于句首, 同时其后“很”字为系表动词, 三者结合可以判定为主语。而“方向盘”与“油门”被“和”字连接, 应为同位语, 所以二者皆是“汽车”的可能属性。
该类方法依赖模板、词典等, 力求从每个单句中挖掘出每一个出现的属性。这类方法的优点是召回率高, 一些较为冷僻的属性都挖掘出来。但不足之处在于容易产生冗余属性, 而且需要较多的人工干预。方法的典型代表有:
(1) 关联规则法。
关联规则方法是由Hu早期提出的一种基于语言规则的属性挖掘方法。该方法用置信度与支持度作为描述元素见关联性的指标。其中 (以A, B元素为例) 支持度=包含A和B句子的数量/所有句子的数量;置信度=包含A和B句子的数量/包含A句子的数量。
在Hu的研究中, 他首先将词性标注后句子中的名词和名词短语抽取出来, 至于集合D中, 然后给出最小置信度 (Minimum Support) 和最小支持度 (Minimum Support) , 并利用Apiori关联规则算法得到候选频繁属性集合 (Candidate Frequent Features) , 再利用紧凑剪枝法 (Compactness Pruning) 去掉没有意义的多词短语, 利用冗余剪枝法 (Redundancy Pruning) 去掉冗余的单个词构成的词汇。
(2) 点互信息法。
点互信息法 (Point-wise Mutual Information PMI) 是Popescu等对Hu方法的改进, 它通过搜索引擎的结果计算两属性之间的共现度, 以此来找出产品属性。
例3:thinkpadX201i的硬盘很大。
令A=“thinkpadX201i”, B=“硬盘”, 将这两个关键词放到互联网上进行检索, 得到
PMI (A, B) =Hits (A+B) / (Hits (A) ×Hits (B) )
其中, Hits (A+B) 为AB共同出现的结果数, Hits (A) 、Hits (B) 为A、B分别出现的结果数。Popescu等人认为, 若二者的PMI超过给定阀值, 则认为二者之间存在属性关联。以此作为判断任一名词或名词短语是否为指定产品属性的依据。
(3) 句法分析法。
句法分析法通过单个语句的句内结构进行逻辑分析, 根据语言表达的固定特性找出评论语句的表达对象。如Kim SM等人的思路就是首先找出句子中的主观极性词汇, 然后以该主观极性词汇为中心, 确定一定长度的窗口, 向前或向后搜索名词或名词短语。而刘非凡等则将句子看作五个元素的集合, 利用层级隐马尔科夫模型 (HHMM) 挖掘构成句子五个元素之间的内在联系, 找出产品属性的可能出现位置。
该方法通常需要对语句进行预处理, 完成分词、词性标注、句子成分标记等预置任务。通常, 这些分词等前置步骤的完成效果对最终属性挖掘有较大影响。国内该方面常用的处理工具有中国科学院开发的ICTCLAS分词器、哈尔滨工业大学分词器及Stanford parser等。
第二类方法以概率统计学为基础, 依靠大量评论文本计算特征最为突出的属性。
该类方法的优势在于能够很大程度上减少对人工干预的依赖具有较高的自动化程度, 同时不依赖于给定词典, 具有较强的领域移植性, 是具有相当发展潜力的一类方法。当然, 目前这类方法缺点仍很明显——处理对象为评论集合, 对于单个评论语句则无能为力, 因此在相对冷僻的属性挖掘上表现不够突出。这类方法典型代表有:
(1) 潜在语义分析法。
潜在语义分析法着眼于挖掘文本中各个词汇的潜在联系。它使用统计计算的方法对大量的文本集进行分析, 从而提取出词与词之间潜在的语义结构, 并用这种潜在的语义结构, 来表示词和文本, 达到消除词之间的相关性和简化文本向量实现降维的目的。
它假定文本由一系列主题混合生成, 而每一主题下对应着相应属性, 通过将属性从高维空间映射到低维空间发觉挖掘属性与主题间的潜在关系, 进而找出产品属性等都在这方面做了初步探讨。
与潜在语义分析相类似的方法还有潜在狄利克雷分布法 (Latent Dirichlet Allocation) 、相关主题模型法 (Correlated Topic Model) , 均是类似的基于无监督的机器学习挖掘法。此外, 余传明教授提出的基于自组织映射的属性挖掘思路也是该类方法的一次有益探索。
(2) 最大熵模型法。
最大熵模型法是一种高效的基于监督学习的机器学习法, 也是目前自然语言处理领域非常盛行的一种方法, 它被广泛应用于文本分类、聚类、实体识别等领域。它假定对于一个随机事件, 已经有了一组样例, 希望建立一个统计模型, 来模拟这个随机事件的分布。为此, 需要选择一组特征, 使此统计模型在这一组特征上与样例中的分布完全一致, 同时又保证这个模型尽可能地“均匀” (也就是使模型的熵值达到最大) , 以确保除了这一组特征之外, 这个模型没有其他任何偏好[从产品评论中挖掘观点: 原理与算法分析]。
Sasha Blair-Goldensohn等人的实验表明与潜在语义分析类方法相比, 最大熵模型法表现出更高的准确率和召回率。
近年兴起的支持向量机 (SVM) 利用超平面划分的思路, 通过更少的训练预料集取得与最大熵模型的相似甚至更好的表现, 在这面做了较详细的对比。
总的来说, 以上基于语言学与基于概率统计学的两类方法在产品属性挖掘方面均具有各自不可取代的优势。第一类方法出现时间较早, 着眼于单个评论语句, 尽力挖掘出评论集合中出现的所有属性, 操作简洁且召回率高, 但人工干预较多。第二类方法出现相对较晚, 借助数学模型对评论整体进行总体挖掘, 找出评论集合中具有代表性的产品属性, 准确率高且不依赖特定领域, 对人工依赖少, 是未来的发展趋势。
鉴于以上两类方法均具有各自不可替代的优势, 一些研究者因此尝试同时使用两类方法, 使其发挥各自的优势。这方面吴月萍、宋晓雷等均作出了有益尝试, 取得了良好的效果。
3小结
随着Internet的迅速发展, 互联网络上的产品意见挖掘已经成为当今研究的热点。文本意见挖掘经过多年的研究已经在Web挖掘上得到了充分的应用, 然而常规的应用依然是基于文本的整体结构, 很难从文本的对象、观点、态度等去挖掘意见, 无法满足用户的细致的需要, 因而产品意见挖掘成为了如今Web挖掘时代一个研究的热点领域。
产品属性挖掘作为产品意见挖掘研究的一个分支, 该领域研究的历史还较短, 目前出现的各种各类方法是近十几年的产物, 理论上的发展与实践上的应用都不算成熟。从近年产品属性挖掘相关论文来看, 使用的方法在前人基础上进行的细微调整与改进居多, 原创性的新方法较少。而由于产品属性挖掘结果各项指标之间存在负向关联, 往往出现某一项指标的上升以牺牲其他指标为代价的情况, 真正可利用的能提高挖掘效果的方法不多。
笔者认为, 新的产品属性挖掘方法在兼顾查全率与查准率的基础上, 需要考虑从以下四个方面进行突破:
(1) 领域可移植性。
挖掘方法应该不局限于某一领域, 不依赖于给定语料与词典。
(2) 高自动化。
挖掘的整个过程中尽量少的人工参与。
(3) 层级性。
挖掘的属性应具有层级、从属结构, 真实反映属性间的联系。
(4) 隐式属性。
不仅挖掘出评论中出现的属性, 对于评论中没有出现但存在的属性也应尝试挖掘。
产品属性挖掘作为一个相对年轻的研究领域, 今后的发展潜力十足, 我们能做、应该做的工作还有很多。
数值属性关联规则的挖掘算法 篇2
关联规则作为数据挖掘的一个重要研究分支,其主要的研究目的是从大型数据集中发现隐藏的、有趣的、属性间存在的规律。目前,从布尔描述的数据中挖掘关联规则已经有了比较成熟的系统和方法,而对于量化关联规则则不然,这方面的研究仍然比较欠缺。本文提出了先不考虑数值属性,在找到所有频繁项集后,再在此基础上,找出数值属性的最佳分区的解决方法。
1 数据挖掘、关联规则的相关研究
1.1 数据挖掘
数据挖掘(Data Mining),也称知识发现KDD(knowledge discovery in database),是从大量原始数据中挖掘出隐含的、有用的、尚未发现的信息和知识(如知识规则,限制等),被认为是目前解决“数据爆炸”和“数据丰富,信息贫乏(Data Rich and Information Poor)”的一种有效方法,它为大量数据的利用提供了有效的工具[1]。
数据挖掘的一般包含数据抽取、数据清理、数据设计、算法设计、算法运行、结果分析六大步骤。
从数据库中发掘的规则可以有以下几种:特征规则、区分规则、聚类规则、关联规则和进化规则等。关联规则是比较新的一种,它的形式简洁,易于解释和理解并可有效捕捉数据间的重要关系。
1.2 关联规则
1.2.1 关联规则
关联规则(Association Rules)是数据挖掘研究的一个重要分支,是数据挖掘的众多知识类型中最为典型的一种。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,是数据挖掘的一个重要研究领域。它反映出一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其它事物预测到。具体描述为:
设I={i1, i2, …, im}是二进制文字的集合,其中的元素称为项(item)。记任务相关的数据D为交易T(transaction)的集合,这里交易T是项的集合,并且T⊆I。每个交易都有一个唯一的标识,如交易号,记作TID。设X是一个I中项的集合,如果X⊆T,那么称交易T包含X。
1.2.2 关联规则挖掘的算法
Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广[3]。
(1)经典频集方法
为了生成所有频繁项集,Agrawal等人在1993年设计了Apriori算法,使用了递推的方法。其核心思想如下:
这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库,即如果频繁项集最多包含10个项,那么就需要扫描交易数据库10遍,这需要很大的I/O负载。
(2)FP-tree算法
Han等人提出FP-tree算法,此算法是不产生候选项集作法的代表,因为不用产生候选项集,只需扫描数据库两次,因此节省了大量I/O的时间,整体的效能大幅提升,而且已运用在实际的产品中。
FP-tree算法和上述算法最主要的差别在于:FP-tree算法不用产生候选项集,且将数据库压缩在FP-tree的结构中,改进了扫描多次数据库的高成本。
FP-tree具体算法如下:
FP-tree 算法:使用FP-tree通过模式段增长,挖掘频繁项集。
输入:数据库D;最小支持度阀值。
输出:频繁模式的完全集。
方法:
按照前述的步骤构造FP-tree
输出满足最小支持度阀值的频繁1项集,并按其支持度大小,从小到大调用FP-growth(FP-tree,null)过程来挖掘FP-tree,该过程实现如下:
对FP-tree方法的性能研究表明:对于挖掘长的和短的频繁模式,它都是有效的和可伸缩的,并且大约比Apriori算法快一个数量级。但其缺点为实现起来较复杂,且若是从稀疏资料库中找出所有的频繁项集时效率较差。
2 多维量化关联规则
Apriori、FP-tree等现有关联规则挖掘算法都是在单维、单层、布尔关联规则下讨论的,是最简单形式的关联规则。而实际应用中,数据库中绝大部分数据是多属性的,并且又多是类别与数值属性的混合型。如何有效挖掘含有数值项目的关联规则是关联规则挖掘中一个急需解决的问题。
2.1 数值属性
数据属性可能是多值的,目前许多文献讨论关联规则的例子只是定性地描述一个交易是否包含某物品,属于挖掘布尔型关联规则问题BARP(Boolean Association Rules Problem),但它可以看作是挖掘多值量化关联规则问题QARP(Quantitative Association Rules Problem)的基础和特例,它是在属性值为布尔量的关系表中寻找属性值为“1”的属性之间的关系[2]。
实际生活中,数据属性不仅仅只有逻辑型这样—种取值类型,它可以是多值的。属性依类型又可分为类别(categorical)属性和数值(numeric)属性两种,逻辑属性可以看作是类别属性(只有“1”和“0”两个值)的一个特例。
2.2 多维量化属性关联规则挖掘任务
单维布尔关联规则的挖掘是最简单、最基本形式的关联规则的挖掘。目前许多文献都讨论了挖掘布尔型关联规则问题,它是挖掘量化关联规则问题QARP的基础,是在属性值为布尔量的关系表中寻找属性值为“1”的属性之间的关系。QARP比较复杂,一种自然的想法是将它转换为BARP。当全部属性的取值数量都是有限的时候,只需将每个属性值映射为一个布尔型属性;当属性的取值范围很宽时,则需将其分为若干区段,然后将每个区段映射为一个布尔型属性,映射为项目集,之后再用类似于布尔关联规则的挖掘算法进行挖掘,产生支持度大于等于最小支持度的频繁项目集,在频繁项目集中产生大于或等于最小信任度的规则,从产生的规则中确定出有价值的规则[4]。
挖掘多属性量化关联规则存在两个难题:
(1)如何对属性分区。
(2)如何发现频繁项目集,找出关联规则。
举例:表1为一个简单的多维量化数据表。
设:Min Support=40%,Min Confidence=50%,就可以得到形如下两式的关联规则:
(1)Age:(30-39 )and Married: Yes ⇒NumCars:2(Support:40%,conf:100%)
(2)NumCars:(0-1)⇒Married: No(Support 40%,conf:66.6%)
其中Age属性与NumCars属性为量化属性,它们要分区,将每个属性值映射为一个布尔型属性。将表1转化为属性均为布尔型的表2。
对于类别属性,可以根据相关知识在挖掘前就将相关属性概化,而在毫无相关知识的未知数值属性上时,采取这种对数值属性先分区,再归纳关联规则,将面临两大互相牵制的问题:划分区间过小会使它包含的元素变少,许多规则因支持度低于阀值而不成立,这类问题称为最小支持度问题;而区间的划分粒度过大会使许多规则因信任度过小,信息丢失而不能成立,这类问题称为最小信任度问题,如在表2中:NumCars:0=>Married:No有100%confidence,NumCars 属性减少区间数目,扩大了区间,NumCars:(0-1)=>Married: No只有66%confidence。对于minimum support问题,可以通过合并相邻的区间,减少区间数目,扩大区间来解决;增加区间数目又可以解决minimum confidence问题。但这样又会增加运行时间缓慢、产生无用规则、如何确定新的平衡的新问题。
在本文中,采用先找出其它属性的频繁项集,再对数值属性进行分区的方法来挖掘含有数值属性的多属性关联规则,希望能从含有数值属性的数据中,以自动化的方式准确找出该数值属性的最佳分区。
2.3 数据概化
数据概化是一个过程,它将大的任务相关的数据集从较低的概念层抽象到较高的概念层。对于数值属性而言,(x,l,v)表示数量属性x的值在区间[l,v]上,如果l’
大的数据集有效的、灵活的概化方法可以分为两类:数据立方体方法、属性导向归纳法。
属性导向归纳法于1989年首次提出,是一种以归纳为基础的数据分析的技术,将相关联数据集合中的每一个属性,检查其数据的分布,判断应归纳到那个相关的抽象层级。
归纳技术包括属性移除、概念树爬升、属性阀值控制和其他整合函数值等。
2.4 数值数据分区
布尔型关联规则问题BARP可以看作是挖掘多属性关联规则问题QARP的基础和特例。Agrawal提出了以“Boolean association rules”为基础的处理方法,把数量属性分成多个细小的区间,将这些区间视为不同的属性值,再把各属性所有的属性值域皆当作Boolean属性,利用Apriori算法来处理产生关联规则[5]。
常见的数值属性分区方法有:分箱、直方图分析、聚类分析、基于熵的离散化、自然分区等等。
3 数值属性关联规则挖掘
3.1 方法分析
基于上述论述,对在挖掘含有未知数值属性多维关联规则一般步骤做了一些修改。先不考虑无法被分区的未知数值属性,而将其它属性分区并找到相应的频繁项集,再在它们的基础上,针对用户感兴趣的规则,找出数值属性上有意义的区间,有意义的区间在这里定义为大于或等于最小信任度且有最大支持度的区间[6],流程如下:
取出相关数据→先不处理数值属性→对其它属性概化→其它属性由QARP到BARP转变→找出其它属性频繁项集→根据找出的频繁数据项集,引入规则约束,指定要挖掘的规则形式,在数值属性上找出有意义的数值范围,从而得到用户想要的关联规则。
从处理过程来看,有两个难点:
(1)如何找出其它属性频繁项集
寻找频繁项集是挖掘关联规则的关键,算法的总体性能是由这一步来决定的。经过比较,决定采用FPL算法。由于此算法需二次扫描数据库,在大的数据库中搜寻数据,即使多遍历一次,也是很浪费时间的,这个算法本身还存在可优化的空间。况且,在寻找的所有频繁项集时,用来过滤频繁项集的最小支持度的值的制订非常重要[6],如果定得不恰当,会造成产生过多无用的频繁模式。因此在挖掘频繁项集过程中,反复修改此值,无论此值改动的幅度是大或小,FPL算法都必须重新构建FPL结构,这相当重新挖掘一遍,是很浪费时间的,所以FPL算法必须作一些修改,来解决这个问题。
(2)如何对数值属性分区
本文采用先找出其它属性的频繁项集,再对数值属性进行分区,找出有意义的区间,挖掘含有数值属性的多属性关联规则。并可以通过调节最小信任度,找到用户满意的最佳区间。有意义的数值区间定义为超过minimum confidence且有最大support的区间。
3.2 算法实现
3.2.1 改进的FPL方法分析与描述
在产生频繁项集时,如果采用前述的FPL方法需要二次扫描数据库,在非常庞大的数据库中读取数据。基于以上,提出的挖掘频繁项集的算法将在FPL的基础上进行一些修改,将二次扫描改为一次扫描,也利用简单线性串行结构来储存数据,并在此串行上执行简单运算,以快速找出所有频繁项集。另外,FPL算法还有一个缺点:每当最小支持度的值一有变动,无论此值改动的幅度是大或小,都必须重新构建FPL结构,这相当重新挖掘一遍,是很浪费时间的。而在寻找的所有频繁项集实际操作中,往往需要反复修改此值,才能得到自己满意的结果。所以本文所提出的算法主要是针对以上两处改进了的FPL算法。具体描述如下:
第一个阶段读入每条记录,构建DB-BIT表和FPL串行。在DB-BIT表新增每个属性列,检查每条记录中的属性是否已存在FPL的串行中,若此属性已存在,则将此节点(Ni)支持度值加1,并且将DB-BIT上数据 BIT值设为1,若不存在,则新增此项目节点(Ni),此Ni支持度为1,并且将DB-BIT上数据BIT值设为1,接着将FPL串行节点依支持度值由大到小做排序。
第二个阶段检查串行节点(Ni)支持度是否大于或等于最小支持度,若是则产生Ni的频繁模式。并从满足于大于或等于最小支持度这个条件的支持度最小的串行节点开始直到只剩下一个拥有最大支持度的节点为止,构建Ni下的子串行节点,检查其支持度是否满足条件,重复上面的步骤,直至所有子串行节点只剩下一个为止,挖掘出所有频繁项集。与FPL算法相比,改进了的FPL算法不删除串行节点。
当调整了最小支持度的阀值,可以从以前串行中拷贝一份,不必重新扫描数据库,不必 重新构建FPL。大大节约了时间,具体算法如下:
算法:FPLM。使用改进的FPL算法挖掘频繁模式。
输入:数据库;最小支持度阀值;决策值。
输出:频繁模式的全集及其支持度。
方法:
(1)如果是第一次挖掘时,根据前述的方法构建DB-BIT表和FPL串行(串行包括节点的名字及出现次数)。
(2)检查FPL串行每一个节点(Ni)支持度值,若此Ni支持度值大于或等于最小支持度值则将此Ni拷贝至FPLM串行中。
(3)对于FPLM串列行的挖掘,通过调用GenFreItem(FPLM串行,null)来实现,该过程如下:
3.2.2 寻找有意义的区间
利用探索式的方法来寻找最佳的数值区间,将会有大量计算。为了简化算法,先将要考虑的数值属性分成n个小区间,将计算所需的数据预先存入一个数组中,如表3所示。
其中,an表示频繁数据项集和决策属性在数值属性上的第n个区间上包含的记录个数,bn表示频繁数据项集在数值属性上的第n个区间上包含的记录个数。
根据关联规则定义,第n个区间上的支持度为an/数据的总记录数,信任度为an/bn,区间[f,r](f≤r)上的支持度为(af+…+ar)/数据的总记录数,信任度为(af+…+ar)/(bf+…+br)。
算法的任务就是要寻找有意义的区间,作为关联规则输出。
先搜索[0,n]整个区间,如果是有意义区间,根据有意义区间定义,就不必再继续找下去,整个区间作为有意义区间输出,否则缩小区间[0,n-1],试探是否是有意义的区间,如果不是,继续缩小区间[0,n-2],要是找到有意义区间[f,q](0≤f≤q≤n),作为有意义区间输出,相邻的以q+1开始的区间肯定没有最有意义的区间,否则,两个区间合并,会在上一个有意义区间寻找中被找出。接着从[f+1,n]区间搜索。
具体算法如下:
算法:在一个已知的频繁项集上寻找最有意义的区间。
输入:已知的频繁项集;最小信任度阀值;决策值。
输出:有意义区间。
方法:
(1)将数值属性的区间分为n个足够小的区间。
(2)将计算所需的数据预先存入数组中。
(3)寻找有意义的区间,该过程procedure btnApply()如下:
4 结束语
提高挖掘的效率是关联规则挖掘的核心问题,通常效率指的是运行时间和结果的可用性,现有的算法在两者之间很难做到有效的平衡,运行时间过长,或是规则的数量过大,这都为使用者带来了很大的不便。在此改进了的FPL算法寻找频繁项集,提高了算法的效率;引入约束,使挖掘的目的朝着以用户需求为核心的方向进行,避免了泛泛的挖掘。这些都是围绕如何提高关联规则挖掘效率这一核心问题展开的。
摘要：文中研究一种如何有效挖掘含有未知数值属性的多属性数据关联规则方法。对FPL算法进行了改进,扫描一次数据库,就可以找出所有频繁项集,且当最小支持度变动时,不需重新构建FPL,能快速找出所有频繁项集。
关键词：数值属性,关联规则,数据挖掘
参考文献
[1]何华灿,等.泛逻辑学原理[M].科学出版社,2001:15-24.
[2]Zhang Zhao-hui,Lu Yu-chang.An effective partitioning-combiningalgorithm for discovering quantitative association rules[C].Pro-ceedings of PAKDD,Singapore:World Scientific Publishing Co,2008:241-251.
[3]Cheung D.Efficient mining of association rules in distributed data-bases[J].IEEE Transactions on Knowledge and Data Engineering,2006,8(6):911-922.
[4]Lin D,Kedem Z M.Pincer-search A new algorithm for discoveringthe maximum frequent set[C].Proceedings of the 6th InternationalConference on Extending Database Technology,2008:105-119.
[5]王君,任永功.基于FP-tree最大频繁模式超集挖掘算法[J].郑州大学学报,2011(3).
属性挖掘 篇3
随着数据科学的兴起和大数据时代的到来,数据挖掘正悄然影响和改变着传统的经济社会活动。在金融领域,每天都记录下了大量的交易数据,随着时间推移,数据越来越多。当前,对银行、股票数据的挖掘如火如荼,但是在期货领域,数据挖掘相关的研究工作还很少涉入。由于期货数据的特殊性,当前对期货数据挖掘多数借鉴股票等其它金融数据挖掘工具。事实证明,采用这些数据挖掘工具进行期货数据挖掘效果并不好,分类和预测的准确率不佳,其中一个很重要的原因在于未对原始期货数据进行预处理。
Weka[1,2]是怀卡托智能分析环境(Waikato Environment for Knowledge Analysis)的英文字母缩写,它使用Java语言编写数据挖掘机器学习软件,是GNU软件协议下分发的开源软件,包括一套完整的数据处理工具、学习算法和评价方法,具有数据可视化图形用户界面,同时该环境还可以比较和评估不同的学习算法性能。Weka系统包括了处理标准数据挖掘问题的所有方法:回归、分类、聚类、关联规则以及属性选择。Weka[3]提供了良好的用户界面,主界面成为Weka GUI选择器,图形用户接口包括探索者(Explorer)、实验者(Experimenter)、知识流(KnowledgeFlow)、简单命令行(Simple CLI)。
本文采用开源数据挖掘工具Weka作为平台,选择决策树分类算法J48,探讨了一种适合期货数据的连续属性划分策略,使期货数据挖掘能够获得较高的准确率。
1 相关定义
数据挖掘首先要对数据进行预处理。Weka提供了很多用户数据可视化和预处理工具。输入数据有两种形式,一种是以ARFF格式为代表的文件,另一种是直接读取数据库表。其中,以ARFF格式为代表的文件是Weka特有的数据文件,也是主要的文件形式。
1.1 ARFF文件格式
ARFF文件分为两部分:第一部分给出了头信息(Head Information),包括对关系的声明和对属性的声明;第二部分给出了数据信息(Data Information),即数据集中给出的数据。从“@data”标记开始,然后是数据信息。
1.1.1 关系声明
关系名称以ARFF文件的第一个有效行来定义,格式为:
@relation<relation-name>。
<relation-name>是一个字符串。如果这个字符串包含空格则必须加上引号(指英文标点的单引号或双引号)。
1.1.2 属性声明
属性声明一律以“@attribute”开头的语句表示。数据集中的每个属性都有它对应的“@attribute”语句,定义它的属性名称和数据类型。属性声明格式为:
@attribute<attribute-name><datatype>
其中<attribute-name>是必须以字母开头的字符串,和关系名称一样,如果这个字符串包含空格则必须加上引号。
Weka支持的数据类型有4种,分别是数值型(numeric)、标称型(nominal)、字符串型(string)和日期型(date)。
1.2 J48算法
决策树[4,5,6,7,8](Decision Tree)是一种预测模型,它包括决策节点、分支和叶节点3个部分。其中,决策节点代表一个测试,通常代表待分类样本的某个属性,在该属性上的不同测试结果代表一个分支,分支表示某个决策节点的不同取值。每个叶节点存放某个类别标签,表示一种可能的分类结果。C4.5算法[6]即Weka中的J48算法,作为决策树算法的最优秀代表,是澳大利亚悉尼大学Ross Quinlan教授[9]对早先的ID3算法进行改进而提出来的,C4.5[10,11,12]算法在以下几个方面对ID3算法进行了改进:(1)能够处理连续型属性和离散型属性数据;(2)能够处理具有缺失值的数据;(3)使用信息增益率作为决策树算法的属性选择度量标准;(4)构建树的过程中进行剪枝,降低过度拟合。
C4.5算法使用通用决策树归纳算法TreeGrowth作为生长树算法。它的输入是训练集E和属性集F。算法递归选择最佳属性以划分数据并扩展树的叶节点,直到满足结束条件,算法伪代码如下:
2 连续属性划分理论
连续属性划分[13,14]是在特定的连续属性的数域范围内设定若干个划分点,将属性的数域范围划分为一些离散化区间,最后用不同的符号代表落在每个子区间中的属性值。
连续属性划分通过将属性数域划分为区间,减少给定连续属性值的个数,使数据更接近于知识级表达。通过连续属性的划分,使得数据挖掘分类算法具有更大的应用范围、更强的实用价值和更高的准确性。下面介绍常见的连续属性划分方法。
2.1 等宽划分法
等宽划分法是最常用、最简单的划分方法,它根据划分指定的区间数据K,将数值属性的数域[Xmin,Xmaxl划分为K个区间,并使每个区间宽度相等,即都等于(Xmax-Xmin)/K。但是,当存在区域偏斜极为严重的点时,这种划分方法不再适用。
2.2 等频划分法
等频划分法是将数值属性的值域划分为K个小区间,K同样是划分者自定义的区间数目。等频算法与等宽算法的不同之处在于其不是要求每个区间宽度一样,而是要求落在每个区间的对象数目相等,也就是说,如果属性的整个取值区间内有M个点,那么等频区间所划分的K个小区域内,每个区域含有M/K个邻近值点。
2.3 K-均值聚类
K-均值聚类[15,16]是一种应用广泛的数据聚类算法。在划分者指定了离散化产生的区间数目K后,K-均值算法如下:(1)从数据集中随机找出K个数据作为K个初始区间的质心;(2)以质心的欧氏距离为根据,如果数据X距质心Mi最近,则将X划归Mi所代表的那个区间;(3)重新计算各区间的质心,并利用新的质心重新聚类所有样本;(4)逐步循环重复第(2)步和第(3)步,直到所有区间的中心不再随算法循环而改变为止。
3 实验与分析
为了得到最优的连续属性划分策略,分析了各种连续属性划分对J48准确性的影响,通过实验进行解释和发现。
3.1 实验环境
(1)硬件环境:Intel i3处理器、内存2G、主频2.57GHz的计算机一台。
(2)软件环境:操作系统Windows XP、开发平台JDK+Eclipse+Weka,数据库平台MySQL。
3.2 实验数据
实验数据[17]以2014年1月的期货数据为例,具体包括蒜苗现货价格、鸡蛋现货价格、玉米期货价格、豆粕期货价格、鸡蛋期货价格,其中鸡蛋期货价格作为类别属性,其余4个作为条件属性。原始数据如表1所示。
3.3 实验结果
为了进行等宽、等频、K均值划分,进行如下约定:
约定1:等宽划分时,区间度d/K计算按四舍五入法则,多余的区间并到最后一个区间,区间开闭情况约定前闭后开。设定分段区间数K=5。
约定2:等频划分时,区间可容纳记录数计算时按四舍五入法则。
约定3:等频划分时,出现等值数据时,若区间记录数未满,则将所有等值数据一并纳入。
约定4:K均值划分时,通过Weka工具的SimpleK-Means算法分别计算各属性的质心,并将其用作数据区间的划分点。
划分后的数据集进行测试,选取奇数行号的11条记录作为训练数据,偶数行号的10条数据作为测试数据。经过数据的处理、运行、调试后可得到训练好的结果,从上到下分别为等宽、等频、K均值划分后生成的决策树,如图1所示。
生成决策树后,用另外10条数据进行测试,预测数据,如表2所示,表2(c)依次是表2(a)等宽划分、表2(b)等频划分、表2(c)K均值划分后的预测结果。
3.4 实验分析
为了进行结果统计和比较,定义3个准确率公式:
(1)分类准确率A1=分类正确的记录数目/参与分类训练的总记录数目;
(2)预测准确率A2=预测正确且准确率超过60%的记录数目/参与预测的总记录数目;
(3)绝对预测准确率A21=预测正确且准确率为1的记录数目/参与预测的总记录数目。
根据实验结果进行计算,得到分类准确率和预测准确率,如表3所示。
根据表3发现K均值划分的分类准确率A1和绝对预测准确率A21最高,但预测准确率A2不及等宽划分。等频划分的分类准确率、预测准确率、绝对预测准确率均最低,可见,其不适合期货数据挖掘划分。等宽划分的预测准确率最高,但是绝对预测准确率只有40%,可见其总体划分性能不算好。总体来说,K均值划分是最优的连续属性划分策略,它能够适应J48算法,适合进行期货数据的分类挖掘与预测。
4 结语
属性挖掘 篇4
互联网上每天都会实时报道各地发生的新闻事件,涉及政治、经济、军事、外交、自然灾害、国家安全等方面,开源情报分析人员不仅关心事件的发展态势,而且关注各个事件是否存在某种内在的关联。本文研究的目标就是通过对事件发生的时间、地点、涉及主体、类型、内容等多个属性维组合成的多维频繁模式进行挖掘,从而发现各事件属性间存在的关联规则。
多维频繁模式挖掘是多维关联规则挖掘的核心内容,多维关联规则最早是由Micheline Kamber、Jenny Y.Chiang等[1]在1997年提出的。他们通过构建数据立方体(Data Cube,DC)并引入用户定义的元规则来引导挖掘。此后提出的多维关联规则算法大多是利用改进的Apriori算法或FP-Growth算法对数据立方体进行分析,这些算法在尽量不牺牲大项集精度或不产生候选项的前提下尽量减少扫描数据库的次数。多维关联规则中有关多维频繁模式挖掘的现存大多方法都依赖于数据立方体的创建。而数据立方体非常不适合高维数和高维度势的关系数据库,因为数据立方体的创建、分析的时空消耗是随维数和维度势呈指数增长。虽然利用冰山或浓缩数据立方体等数据结构能在一定程度上缓解时空消耗危机,但仍不能从根本上解决数据立方体的消耗增长问题。
将多维关联规则应用到新闻事件多维关系数据挖掘还需要解决数据稀疏性问题。关联规则挖掘主要是挖掘出一些频繁出现的事件实体组合(例如在某个时间、地点,某主体经常参与某事件),而在相同时间、地点、发生相同事件的可能性很小,所以可能很难挖掘出新闻事件多维频繁模式。
针对数据立方体的空间消耗及新闻事件数据稀疏性等问题,本文参考文献[2]的多维索引树数据结构,并结合概念分层技术[3],提出一种面向新闻事件频繁模式挖掘的多维属性索引树(Multi-dimensional Attribute Index Tree,MAIT)模型,该数据模型既能有效存储高维数和高维度势的关系数据库,又能解决新闻事件数据稀疏问题。然后在MAIT的基础上对新闻事件多维频繁模式进行挖掘。最后通过实验对比,验证了本文方法的有效性。
2 相关概念
根据新闻事件相关性质,定义新闻事件多维关联规则挖掘的相关概念。
定义1:新闻事件多维属性关系数据库
根据新闻的定义,对于一个完整的新闻事件报道,必须包含以下4类特定属性:事件时间、地点、涉及主体、事件内容。本文以四个属性为基础建立新闻事件多维属性关系数据库,数据库示例如表1所示。
新闻事件关系数据库中一条记录对应一个新闻事件,每个记录除包含新闻的四个要素属性外,还人工添加了事件类别字段,该字段说明了事件的类型。表中个别属性字段值使用“Any”表示空缺,即“Any”可能是该字段中任何合法的可能值,相当于通配符。表中内容属性值具有多值性,由事件报道中的多个关键词组成(内容项集),其它属性均为单值,因此在构建MAIT的过程中将数据信息分成两个部分:内容属性信息和非内容属性信息。非内容属性主要包括时间属性、地点属性、主体属性、类型属性,每一条事件记录对应一个非内容属性值组合。
对于给定的新闻事件数据库DT(例如表1),每个事件记录用m个属性描述,并且每一个属性值均为字符串值。下面给出新闻事件多维关联规则挖掘相关定义及性质。
定义2:新闻事件属性集
新闻事件属性集是包含k个合取属性值对(谓词项)的集合,其中1≤k≤m,属性集亦可称为谓词集。
定义3:新闻事件关联规则
新闻事件关联规则是形如的蕴含式,其中属性集A=A1∧A2∧…∧Al且l<5,B=B1∧B2∧…∧Bn且n<5,Ai和Bj均是事件属性-值对,并且A∩B≠.
定义4:属性集包含关系
事件属性集A和B,包含关系表示:对于A中任一属性值对a,必有a∈B成立;真包含关系表示:对于A中任一属性值对a,必有a∈B成立,同时存在属性值对b∈B,使得成立。
定义5:属性集支持度
属性集A的频率是DT中包含该属性集的事件记录数s,如果属性集A的频率除以DT中总的事件记录数|DT|,则得到该属性集的支持度,标记为Support(A),公式如下:
定义6:频繁属性集
当某属性集的支持度大于或等于预先设置的最小支持度(MinSup),则称该属性集为频繁属性集。
定义7:新闻事件关联规则支持度
新闻事件关联规则的支持度即属性集A∪B的支持度,公式表示如下:
其中,|A∪B|表示DT中包含属性集A∪B的事件记录数。
定义8:新闻事件关联规则置信度
新闻事件关联规则的置信度是指包含属性集A∪B的事件数与包含属性集A的事件数之比,记为Confidence(),公式表示如下:
其中,|A|表示DT中包含属性集A的事件记录数。
定义9:强关联规则
强关联规则是指同时满足最小支持度(Min-Sup)和最小置信度(MinConf)的规则,即
定义10:新闻事件多维频繁模式
当非内容属性值组合与其对应的内容属性项集的支持度大于或等于预先设置的最小支持度,则非内容属性值组合与其对应的内容属性项集共同构成一个新闻事件多维频繁模式。
定义11:反索引项
反索引项是一个2-元组R={v,p},其中v表示一个属性值,p表示一个指向下层属性值的指针。
参考文献[3],可得如下多维关联规则挖掘的性质。
性质1频繁属性集的所有非空子集都是频繁的。
性质2如果一个属性集不是频繁的,则它的所有超集均不是频繁的。
推论1 如果一个非内容属性值组合(属性集)不是频繁的,则包含该属性值组合的新闻事件多维模式也不是频繁的。
3 新闻事件多维频繁模式挖掘
基于上节的定义,本文提出一种新闻事件数据库存储结构模型:多维属性索引树(MAIT),并基于MAIT模型挖掘新闻事件多维频繁模式。该方法能够用来处理具有相当维度和维度势的新闻事件关系数据集。
3.1 多维属性索引树模型
多维属性索引树(MAIT)是一个树形结构,具备如下特征:①MAIT包含根节点、子节点、事务桶;②MAIT的根节点和所有子节点均是一个反索引项集合;③MAIT具有层次性,每个层次代表不同的属性,包含多个该属性的子节点;④事务桶是一个二-元组B={Sup,TIDs},其中频度字段Sup表示事务桶的频数,TIDs表示事件ID列表,每个事务桶对应一条树路径{Ti,Lj,Pk,Sl}(路径表示为非内容属性值组合);⑤事件内容属性值数组,记录了每一个事件ID对应的事件内容项集,如001={i1,i4,i11,i34},in表示一个事件内容项。
以表1 为例,说明MAIT的创建过程。开始时,MAIT是一个空的根节点和一个空的事件内容属性值数组。顺序扫描表1,逐个考察记录的非内容属性值组合中的每个属性值,如果在MAIT中存在该属性值组合的对应的一条树路径,且该路径直接和一个事务桶相关联,则将该事件ID注册到该路径的事务桶中,并对频度增加1;否则,如果MAIT中不存在该路径,则在MAIT中创建一个路径;最后,将该事务的事件ID和项集部分存入事件内容属性值数组。具体创建过程:从表1中的第一条记录(事件ID:001)开始,其非内容属性值组合中的第1个属性值是T1,MAIT中不存在其相应的反索引项,因此将T1存至根节点,并创建由根节点到一个事务桶的路径Root→A→B→C→D,该路径对应一个非内容维值组合{T1,L1,Any,S1},将频度和事件ID列表存入该路径事务桶,并将桶中事件ID其对应的内容属性包含的项集{i1,i2,i6,i13}存入事件内容属性值数组;接下来顺序处理事件记录002,其非内容属性值组合中的第1个维度是T2,因根节点中不存在T2反索引项,所以将T2存至根节点,并创建由根节点到一个事务桶的路径,该路径对应为{T2,Any,P1,S2},将频度和事件ID列表存入事务桶,并将桶中事件ID及其对应的内容属性包含的项集{i1,i2,i5,i7,i9}存入事件内容属性值数组;依次顺序处理表1中的记录,直到事件005;事件记录005中的非内容属性值组合{T2,L3,P1,S2}的第1 个属性值也为T2,由于通配符“Any”的存在,使得路径{T2,Any,P1,S2;1;002}满足记录005 的非内容属性值组合,因此需要更新路径{T2,Any,P1,S2}对应的事务桶中频度和事件ID列表字段值,记录005第二个维度值为L3,而MAIT中不存在{T2,L3,P1,S2}对应的路径,所以将L3加入到节点H,并增加路径{L3,P1,S2},将频度和事件ID列表存入事务桶,并将事件ID及其对应的内容属性包含的项集存入事件内容属性值数组;如此类推,当原始数据表中所有的事件记录处理完毕时,即可得到表1对应的多维属性索引树,结果如图1所示。
多维属性索引树具有很好的灵活性,能够方便的进行更新。当一个新的数据集到来时,逐一将每条新记录的非内容属性值组合加至MAIT中,删除则执行相反的过程,由根节点到事务桶节点递归的检查是否存在有待删除的反索引项,如果有则将其删除。无论是添加还是删除都无须对现存的MAIT数据结构进行重建。不仅如此,还可以向MAIT中加进新的维度,该操作相当于向MAIT引入新的层次,可直接实现。
3.2 多维属性索引树的概念分层
概念分层即对属性维度定义一个映射序列,将底层属性值概念映射到更一般的较高层属性值概念。例如考虑地点维的概念分层,假设有四条记录的地点维值分别是长沙、株洲、湘潭和郴州,这些地点是在“城市”概念层,这些地点是不同的,但是将这些城市名称通过概念分层映射到高一级的省份概念层,则四条记录的地点属性值全变成了湖南,这样四条记录的地点名全相同。参考文献[4]定义的映射序列,可以将时间、地点、主体、类别属性值进行概念泛化,这样使得许多属性值组合的频数相应增加,从而能够挖掘出一部分强关联规则,这部分关联规则是从底层属性值概念层得不到的。通过概念分层定义的映射序列,将底层属性值映射到高层属性值后,相应的多维属性索引树结构也要进行调整。这种调整主要就是将同一节点反索引项集中部分不同属性值进行泛化或合并,相应索引树结构发生变化,部分路径可能需要合并,对应的事务桶存储的事件ID列表也需要合并且频数相加。
下面利用图1展示的多维属性索引树进行概念分层应用说明。假设通过概念泛化,地点层节点H中L2和L3反索引项对应的属性值被泛化到一个高层的属性值L11,则将L11取代节点H中的L2和L3,因此需要将节点I和J的节点项集合并成一个节点项集K,即{P1,P2,Any},其中I中的P2和J中的P2合并成一个反索引项,并将P2的指针同时指向下层的对应的S1和S2,将L11的指针指向节点I和J合并后的节点项集K。同样可以假设类别层C节点中的S1和S3被泛化到同一维值S19,则将S19取代C节点中的S1和S3,并将S1和S3对应的事务桶合并成一个事务桶,从而得新事务桶{3;001,003,007},通过以上步骤将图1进行概蓬泛化后得到图2的多维属性索引树结构。
3.3 基于MAIT的多维频繁模式挖掘
构建多维属性索引树后,即可进行频繁非内容属性集挖掘。假定用户想从图1所示的多维属性索引树中发现所有的频繁非内容属性值组合集,且设定最小支持度为2。首先搜索MAIT,找到所有事务桶的频度大于或等于2的桶,每个桶到根节点存在唯一一条路径,该路径上的所有反索引项对应属性值集合就构成一个频繁非内容属性集。这些桶分别是:{2;003,007},{2;008,011},{2;002,005},{2;004,010}。然后把每个捅的事件ID列表中的事件ID和其内容属性项集当成一个子数据库,利用文献[3]中的FP-growth树方法从每个子数据库中挖掘频繁内容项。最后,将频繁的非内容属性值组合和其对应的频繁内容项组装,即得新闻事件多维频繁模式挖掘结果并输出。
3.4 新闻事件多维关联规则提取
根据3.2节得到新闻事件多维频繁模式集后,提取关联规则就相对比较容易了,关联规则提取过程分为两步:①对于每个新闻事件多维频繁模式FP,求出其所有多维频繁模式的非空子集;②对于多维频繁模式FP的每个非空子集FPsub,根据定义8计算规则FPsub(FP-FPsub)的置信度。
根据得到的FP及置信度,以及关联规则的定义知:多维频繁模式中大于最小置信度的规则为强关联规则。
4 实验分析
实验数据为全球恐怖主义数据库(Global Terrorism Database,GTD)[5]中的真实数据。GTD是由美国马里兰大学恐怖主义研究应对协会管理的免费开放的一个公共数据库,该数据库详细记录了1970年初至2011年底世界范围内发生的104689起恐怖袭击事件。GTD中的数据存储在Excel表中,表的一行就是一条恐怖袭击事件记录,表中记录包含一百多个字段。本文选取2010~2011年的1423条记录中的的时间、地点、恐怖分子组织、袭击事件类别、事件概述内容构建新闻事件多维关系数据表,这些记录的“summary”字段值不为空。
本文实验首先开发了一个小的原型系统,用于展示基于多维属性索引树存储的实验数据,结果如图3所示。图中的时间属性概念层是月,地点概念层是城市,主体概念层是群体(组织)。然后在图3的数据结构上再进行本文的多维频繁模式挖掘相关算法的性能实验分析。
对比实验主要对MAIT数据结构模型及数据立方体结构模型应用到多维频繁模式挖掘的性能进行比较,其中基于数据立方体的频繁模式挖掘算法参考文献[6]。随着数据集大小的变化,扫描数据立方体和处理扫描得到的数据集的时间开销会有显著变化,需要的存储空间也会有很大变化,同时,挖掘的频繁模式数量是由关联规则的最小支持度决定,因此数据集大小和最小支持度都是影响频繁模式挖掘性能的重要因素。本实验从数据集数量和最小支持度设置两方面来对两种数据结构进行对比分析。
首先分析事物数(Num of Tran)变化对频繁模式挖掘的性能(Run Time)影响。实验将支持度设置为0.1%,即支持度频度为2,事物数从200变化至1400,变化步长为200。通过对基于MAIT和基于数据立方体(DC)的频繁模式挖掘,得到不同事物数时两组实验的时间消耗数据,建立两组实验数据曲线图,结果如图4所示。从图中可以看出,基于DC和MAIT两种数据结构模型的频繁模式挖掘都随着事务数的增大而增大,并且数据立方体数据结构受事务数量的影响较大,曲线变化明显。但在事务数很小的时候,基于DC的挖掘算法要略优于基于MAIT的挖掘算法,因为MAIT建树需要一定时间,且时间较稳定,受事务数影响不大,而基于数据立方体算法在事务数很小时,效率很高。
接下来分析最小支持度(MinSup)变化对频繁模式挖掘的性能影响。实验将支持度设置为七种不同值,分别是0.1%、0.2%、0.3%、0.5%、0.8%、1%、2%.在7种不同支持度时分别对基于MAIT和基于数据立方体(DC)的频繁模式进行挖掘,得到两种数据模型对应的时间消耗数据,建立实验结果曲线图,结果如图5所示。从图中可以看出,随着支持度的增大,两种数据模型对应的算法的运行时间均在减少,因为随着支持度变大,得到的多维频繁模式集将相应减少,从而处理多维频繁模式集的时间越来越少。同时可以看出,基于数据立方体的挖掘算法受支持度变化的影响较大,因为支持度很小时,算法需要花费大量的时间处理候选频繁模式集。
5 结论
本文对新闻事件多维关联规则中的频繁模式发现进行研究,提出了基于多维属性索引树的新闻事件频繁模式挖掘方法。该方法较好地解决了数据立方体时间消耗增长以及新闻事件数据稀疏的问题。通过与传统的数据立方体方法相比,本文方法能够以较少的时间消耗快速地挖掘出关系数据库中的多维频繁模式。
摘要：提出一种基于多维属性索引树的新闻事件多维频繁模式挖掘方法。该方法首先根据新闻事件属性建立多维关系数据库,然后将属性集按其特性分成非内容属性集和内容属性集两部分,依据非内容属性集创建多维属性索引树,同时利用概念分层对索引树属性进行概念泛化,以解决数据稀疏问题;最后基于多维索引树挖掘新闻事件多维频繁模式。通过真实数据集上的实验,验证了方法的有效性和优越性。
属性挖掘 篇5
关键词：关联规则,遗传算法,连续属性,小生境
关联规则挖掘[1]是数据挖掘的一个重要方面,是指发现数据库中项集之间的关联,对于决策支持、医疗诊断等领域有广泛的应用价值[2]。
在现有的关联规则挖掘算法中,Agrawal 等人提出的Apriori算法应用最广[3],然而该算法应用于具有连续属性的数据集上效果较差。遗传算法是一种模拟生物进化过程的算法[4],与传统算法相比有高鲁棒性、全局搜索性、内在并行性等优点[5],为许多以前无法解决或难以解决的复杂问题提供了新的计算方法[6]。论文主要研究拥有连续属性的数据集上关联规则挖掘方法。该方法主要采用遗传算法来获取关联规则,并利用三段式编码和小生境来提高挖掘性能,从而挖掘出隐含于拥有连续属性的数据集中的知识。
1 关联规则相关知识简介
关联规则[7]是形如A⇒B的蕴含式,通常前件A由多项属性组成,后件B由一项属性组成,可具体表示为a1∧a2∧…∧am⇒b,其中ai∈A,b∈B,分别称为条件属性、决策属性。
一般用2个指标衡量一条规则的好坏:可信度、支持度。
设D是一个记录集,|D|表示D的基数,x是一条规则,x的可信度:
其中,DA为D中与规则x前件匹配的子集,DB为与x后件匹配的子集,DA∩DB为与x前件和后件均匹配的子集。可信度越高,规则就越准确。x的支持度S(x)=|DA∩DB |/|D| 。支持度越高,x对于D就越重要。
2 本文挖掘方法设计
2.1 三段式编码设计
如果属性值是连续的,应对其离散化,即先选取分割点,将属性值划分成区间,选取的分割点在哪里对挖掘结果影响很大,可能导致提取的规则太少(还有有价值的规则没找出)或太多(不便找出真正有价值的规则),甚至错误,为此本文提出一种新的编码方式。
设A={a1,a2},a1、a2是连续的,候选分割点分别为0.9、1、5.2、6和0.5、2、4,B={b},b是离散的(如果是连续的,编码方法同a1、a2),值为0、1、2、3,采用二进制编码,连续属性占2段,离散属性占1段,某个体编码为
0110010 1100110 10
第1段表示选取的a1、a2的分割点,长度为候选分割点个数之和,每位对应一个候选分割点,1表示选取该分割点,第2段对应位有效,0表示不选取该分割点,第2段对应位无效。0110 010表示选取的分割点分别为1、5.2和2。如果某属性对应位全为0,表示该属性无论取何值,不影响规则的成立与否,即属性是冗余的,可以去除。注意本例本段(即属性a1、a2对应位)不能全为0,它表示的规则没有意义。
第2段表示根据选取的分割点确定的a1、a2的具体区间,长度与第1段相同,每位表示属性值在分割点的哪个方向,0表示小于或等于分割点,1表示大于分割点。1100 110表示 a1>1,a1≤5.2,即 l<a1≤5.2(如a1>1,a1>5.2,则 a1>5.2),a2>2。
第3段表示b的值,长度取决于它的值的个数,00表示属性值为0,01表示属性值为1,…,10表示b=2。
综上所述,该个体代表规则(l<a≤5.2)∧(a2>2)⇒b=2。
2.2 适应度函数设计
这里令个体的适应度函数可定义为
其中,a,b为常数,由用户根据需要设置,从而使评价的偏重可以变化,使进化沿着期望的方向进行。
普通遗传算法通常采用比例选择[8],在进化的初期,可能出现个别适应度很高的个体,而大多数个体适应度还很低,这样的个体被选择的概率远高于其它个体,可能充斥下一代群体,使得进化难以继续。生物在进化过程中一般总是与自己相同的物种生活在一起,可以应用到遗传算法中,使个体在一个特定的生存环境中进化,这就是小生境技术。
定义个体xi 和xj的海明距离
其中n为个体的编码长度。
适应度距离d2(xi,xj)=|f(xi)-f(xj)|。
类共享函数(为了和普通小生境遗传算法使用的共享函数相区别):
这里σ1、σ2分别为个体间的海明距离、适应度距离在—个小生境内的最大距离。
根据类共享函数对个体的适应度进行调整:
可见,一个个体与其它个体差异越大,类共享函数值越大,调整后的适应度越大,算法依据这个调整后的新适应度来进行选择操作,可以限制相似个体的过多复制,从而维持群体的多样性,有助于找出更多的有价值的规则。
普通小生境遗传算法定义的是共享函数,一个个体与其它个体差异越大,共享函数值越小,根据共享函数对个体的适应度进行调整
2.3 遗传操作设计
2.3.1 选择算子
采用轮盘赌算子,用个体的适应度与群体中个体的适应度的总和的比值,作为其被选择的概率。个体的适应度越高,被选择的概率越大。
2.3.2 交叉算子
采用单点交叉,随机产生交叉起始位,然后交换两个个体从交叉起始位开始的串,形成2个新个体。例如对于个体1111111和0000000,产生的交叉起始位是3,则交叉后的新个体为1110000和0001111。对于前面的例子,最后还要检查新个体的第1段是否全为0,如果全为0,随机产生1个个体,这样可以增强群体的多样性。
2.3.3 变异
采用简单变异, 随机产生变异位,然后对变异位作翻转操作,形成1个新个体。例如对于个体1111111,产生的变异位是3,则变异后的新个体为1101111。对于前面的例子,最后还要检查新个体的第1段是否全为0,如果全为0,随机产生1个个体。
2.4 本文方法简述
采用上述设计的遗传算法,进行具有连续属性数据的关联规则解决方法描述如下:
(1) 设置支持度、可信度阈值、适应度函数的系数a、b、终止代数T、种群规模M,交叉概率、变异概率,进化代数t=0,随机生成M个个体,作为初始群体;
(2) 扫描数据库,计算出各个个体的适应度f*(x);
(3) 选择;
(4) 交叉;
(5) 变异,得到下一代群体;
(6) 如果t=T,结束,否则t=t+1,转到(2)。
算法结束后,扫描最终群体中的每个个体,去除冗余的属性,如果支持度、置信度大于阈值,输出,最后得到属性的约简集合、满足要求的规则集合。
3 实例验证
为了检验算法的性能,使用UCI机器学习数据库中的iris,ecoli 2个数据集,分别运行本文算法、普通遗传算法和Apriori算法(关联规则挖掘的经典算法),设置参数M=40,T=300,Pc=0.95,Pm=0.01,支持度阈值为0.3,可信度阈值为0.6,数据集情况见表1,训练集和测试集的记录比例为1∶2。
使用普通遗传算法时,先用它搜索连续属性的最优分割点集,再用它提取规则。使用Apriori算法时,先用基于断点重要性的方法对连续属性进行离散化[1],结果如表2和表3所示。
可以看出,本文算法的约简后属性数与普通遗传算法差不多,其他方面都比它好,说明本文算法引入小生境技术,得到的最终群体更接近问题的最优解。本文算法的分割点数和离散化后的Apriori算法差不多,其他方面都比它好 (特别是Apriori算法不能约简属性,本文算法却能较好地约简)。
4 结束语
对具有连续属性的数据进行关联规则挖掘,本文算法事先不确定具体分割点,而由搜索的实际确定,将使最后确定的分割点更加合理,又引入小生境技术(对具有离散属性的数据进行关联规则挖掘也适用),可以限制相似个体的过多复制,维持群体的多样性,得到更多的规则更全面、简洁、有效,和经典算法比,性能有较大提高。
参考文献
[1] Cokpinar C,Gündem T I.Positive and negative association rulesmining on XML data streams in database as a service concept.Ex-pert Systems with Applications,2012;39(8):7503—7511
[2] Wang Xin,Liu Xiaodong,Pedrycz W.Mining axiomatic fuzzy set as-sociation rules for classification problems.European Journal of Opera-tional Research,2012;212(1):202—210
[3] Nebot V,Berlanga R.Finding association rules in semantic web da-ta.Knowledge-Based Systems,2012;25(1):51—62
[4] Fung K Y,Kwong C K,Siu K W M.A multi-objective genetic algo-rithm approach to rule mining for affective product design.ExpertSystems with Applications,2012;39(8):7411—7419
[5] Yang Jianhua,Singh H,Hines E L.Channel selection and classifica-tion of electroencephalogram signals:an artificial neural network andgenetic algorithm-based approach.Artificial Intelligence in Medi-cine,2012;55(2):117—126
[6] Mamdoohi G,Abas A F,Samsudin K.Implementation of genetic al-gorithm in an embedded microcontroller-based polarization controlsystem.Engineering Applications of Artificial Intelligence,2012;25(4):869—873
[7] Altuntas S,Selim H.Facility layout using weighted association rule-based data mining algorithms:Evaluation with simulation.ExpertSystems with Applications,2012;39(1):3—13
属性挖掘 篇6
关键词：布尔区分矩阵,属性约简,关联规则挖掘,Apriori算法,并行计算
0 引 言
粗糙集理论作为一种处理不精确、不完整、不确定性数据的有效数学工具,自20世纪80年代由波兰数学家Pawlak[1,2]提出后,在短短30年时间里,已经发展得相当成熟,在众多领域获得了广泛应用。属性约简作为其重要理论基础,在粗糙集理论中占有极其重要的地位,目前为止,属性约简的方法主要可以分为两类,一类是基于正域不变的属性约简算法,包括代数观下的约简[3,4,5,6,7]和信息观下的约简[8,9,10,11];另一类则是基于区分矩阵的约简算法[12,13,14,15,16,17]。文献[3]提出了一种基于划分差量的方法,由此刻画属性的重要性,并设计了高效的启发式算法;文献[4]则提出了以基本块为基础计算正域进而求得约简的算法。文献[5,6,7]也分别提出了代数观下的其它属性约简方法。文献[8]从信息熵的角度出发设计属性重要性的度量指标,进而用于指导约简过程,文献[9]则通过首先计算简化决策表,然后用信息熵计算约简的方法,具有较低的时间复杂度,文献[10,11]也以信息熵为出发点,设计了相应的约简算法。在基于区分矩阵的约简研究上,文献[12]提出了改进的差别矩阵,通过核增量式更新算法,可用于处理对象动态增加时的约简问题,文献[13]提出了基于简化差别矩阵的约简方法,文献[14,15,16,17]也从其它角度提出了以区分矩阵为基础的约简算法。由于寻找最优约简已经被证明为NP-hard问题[18],因此,第一类约简算法目前主要在于设计各种启发式信息,用于寻找近似最优约简,该类算法思路简单,但设计合理的启发式信息存在一定难度,在第二类算法中,启发式信息主要是基于简单的属性频率,容易理解,但存储空间随记录数增长较快。
本文为了克服第二类算法的缺陷,提出了一个基于布尔区分矩阵的属性约简算法BDM-ARM(Attributes reduction algorithm based on Boolean Discernibility Matrix and Association Rule Mining),算法不仅可以减少存储空间,还能寻找到系统的所有约简。
1 基本概念和定义
S=(U,A,V,f)是一个知识表达系统,其中U是对象的非空有限集合,称为论域;A是属性的非空有限集合;
设S=(U,A,V,f), B⊆C,满足POSB(D) =POSC(D)且对∀B′⊂B,都有POSB′(D) ≠POSC(D),则称B为决策系统S的一个约简。
为方便本文算法表述,定义下列运算规则或函数,先给出一个示例决策表如表1所示。
定义1 设xi,xj∈U,则dm=unequal(xi,xj)为一个区分属性求解运算,其形式为一个布尔矩阵式行向量,用于计算对象xi和xj在哪些属性下是可区分的,dm可写为dm=(dm1,dm2,…,dmm),m=|C|,dmk的具体赋值规则如下:
其中ck∈C。
定义2 设dm1,dm2均为布尔行向量,则dm=conjunction(dm1,dm2)为一个向量间按元素进行合取运算,运算规则为若对应元素均为1,则合取结果为1,否则为0;同理定义dm=alternative(dm1,dm2)为向量间按元素进行析取运算,运算规则为若对应元素均为0,则合取结果为0,否则为1。
定义3 设M为一个矩阵,则sm=sum(M,w)为一个矩阵求和运算,w∈{1,2}为状态变量,w=1时表示按列求和,其结果sm为一个行向量;w=2时表示按行求和,其结果sm为一个列向量。
定义4 设I为一个行向量,则cm=find(I,value)为一个位置标记运算,用于寻找向量I中元素值为value的元素编号或下标,其阶数不超过I的阶数。若不∃i使得Ii=value,则cm=(Φ)。特别地,若I为一个布尔式行向量,则value一般只取0或1。
例1:根据定义1～定义4,在表1中,则有:
① dm=unequal(x1,x3)=(1,1,0,0,1,0);
② 若dm1=(0,0,1,1,0,1),dm2=(1,0,1,0,1,1),则dm=conjunction(dm1,dm2)=(0,0,1,0,0,1);
dm=alternative(dm1,dm2)=(1,0,1,1,1,1);
③ 若取w=2,dm=(1,1,0,0,1,0),则sm=sum(dm,2)=3;
④ 若取value=1,dm=(1,1,0,0,1,0),则有cm=find(dm,1)=(1,2,5)。
2 约简算法
2.1 数据预处理
为方便算法的执行,提高执行效率,先对数据进行如下处理:
(1) 对决策表按决策属性值的大小进行升序排列,此操作可由EXCEL表格或MATLAB排序函数快速完成;
(2) 对决策属性值进行1～k连续编号(k为决策表的决策类别总数);
(3) 将处理后的决策表保存为新的决策表S=(U,A,V,f)。
2.2 BDM-ARM约简算法
算法1 BDM-ARM属性约简算法
输入:S=(U,A,V,f)。
输出:S的所有约简集RED。
(1) 计算划分U/D={D1,D2,…,Dk},每个Di包含所有条件属性及其在该属性下的取值,可视为一个独立的子表,删除重复对象,且不再储存决策属性;
(2) 寻找核属性,执行函数findcore(U/D),返回核core;
(3) 利用核属性构造布尔区分矩阵,执行函数generate_dm (U/D, core),返回布尔区分矩阵DM;
(4) 以关联规则挖掘思想逐级寻找所有决策系统的所有约简,执行函数allreduction(DM, core),返回约简集合RED;
(5) 算法结束,输出核core及所有约简RED。
算法1中涉及到的三个函数,形式化表示如下:
函数1 寻找核属性findcore(U/D)
输入:U/D。
输出:core。
(1)初始化核core1×m=[00…0],m为条件属性的个数;
(2)依次取xip∈Di,xjq∈Dj(i≠j),计算dm=unequal(xip,xjq)和sm=sum(dm,2),若sm=1则表明存在核属性,使用cm=find(dm,1)将核属性标出,并将core的对应位置置为1;
(3)选取下一个xip∈Di,xjq∈Dj(i≠j),重复(2),遍历完所有决策类下的对象对;
(4)输出核属性集合core。
函数2 构造布尔区分矩阵generate_dm(U/D , core)
输入:U/D,core。
输出:布尔区分矩阵DM。
(1) 初始化区分矩阵DM=[Φ];
(2) 依次取xip∈Di,xjq∈Dj(i≠j),计算dm=unequal(xip,xjq)和sm=sum(dm),若sm≥2,转入(3),否则转入(5);
(3) 计算cm=conjunction(dm,core),若sm=sum(cm)=0,转入(4),否则转入(5);
(4) 若DM=[Φ],则将dm加入到DM中,否则依次取出DM中的行DM(i,:),计算cm=conjunction(DM(i,:),dm),若sum(cm)= sum(dm),则以dm取代原DM(i,:)并结束对比下一个DM(i,:),若sum(cm)<min(sum(DM(i,:)),sum(dm)),则将dm加入DM中;
(5) 选取下一个xip∈Di,xjq∈Dj(i≠j),重复(2)～(4),遍历完所有决策类下的对象对;
(6) 输出布尔区分矩阵DM。
函数3 寻找所有约简allreduction(DM, core)
输入:DM,core。
输出:所有约简集合RED。
(1) 初始化一项约简集L1=Φ,一项候选集C1=Φ;
(2) 若DM=[Φ],则转入(7),否则转入(3);
(3) 对DM按列求和sm=sum(DM,1),对∀smi,若smi=n0,则将对应属性ci加入到L1中,若0<smi<n0,则将对应属性ci加入到C1中,其中n0为DM的行数;
(4) 对C1中的元素,进行两两连接,由一项集产生二项集,即∀ci,cj∈C1,令P=ci∪cj,并对DM的第i列和第j列进行析取(布尔加法或逻辑或运算),得dm=alternative(DM(:,i),DM(:,j)),sm=sum(dm,1),若sm=n0,则将对应二项属性集P加入到L2中,否则将P加入到C2中;
(5) 以候选二项集C2为基础,采用类似Apriori算法[20]中的连接操作,由二项候选集产生三项候选集,连接条件为∀Pi,Pj∈C2,若Pi,Pj除最后一个元素不同外,其它元素均相同,则可进行连接,否则不予连接,此外,需要进行剪枝操作,即对Pi∪Pj的所有二项子集p,若均有p∈C2,则可进一步进行析取操作,否则无需进行计算;
(6) 重复步骤(5),以k项候选集Ck产生k+1项候选集Ck+1和k+1项约简集Lk+1,直至Ck=Φ不能再产生更高阶的约简集为止;
(7) 若core≠[0,0,…,0],则令core=find(core,1),对任意的li∈Lj(j=1,2,…,k),li=li∪core,并对li中的元素重新按升序排列;
(8) 输出所有约简集
2.3 理论证明
定理1 同一个决策类下的对象可不作区分,不影响约简的正确性。
证明:U/D={D1,D1,…,Dk},若xi,xj∈Dm,(1) 若[xi]=[xj],此时显然成立,即xi,xj可视为重复对象,不作区分不影响约简结果;(2) 若[xi]≠[xj]则xj∉[xi],不妨设U/C= {C1,C1,…,Cl}。由于约简的本质是保持分类能力不变,即在属性个数减少时,仍能将对象xi归入其应属的决策类Dm中,因此,只要f(xi,D)= f(xj,D)我们就认为二者是一样的,不作区分。
定理1保证了算法1中第(2)、(3)步的正确性,同时大大减少了区分矩阵的构造规模。
定理2 在区分矩阵中,对于存在包含关系的属性集,删除大属性集,不影响约简的正确性。
证明:定理2可形式化表述为:设B1⊆C为对象xi,xj的可区分属性集,B2⊆C为对象xp,xq的可区分属性集,若B1⊂B2,则从区分矩阵DM中删除B2,不会影响结果的正确性。不妨设red为S的一个约简,则对∀Bi∈DM都有Bi∩red≠Φ,即∃b∈B1⊂B2满足b∈red,即若B1可在red下被约简,则B2必定也可在red下被约简,故可删除,不会影响结果的正确性。
定理2保证了算法1中第(3)步的正确性,用此定理可大大简化区分矩阵DM的规模。
在关联规则挖掘中,存在如下定理:若项目集X是频繁项目集,那么它的所有非空子集都是频繁项目集;若项目集X是非频繁项目集,那么它的所有超集都是非频繁项目集[20]。对于区分矩阵DM,有下述性质成立:
性质1 若属性集B是S的一个D约简,则Q=B-core组成的属性集可区分DM中的所有行,称Q为S的一个去核D约简;
性质2 若Q为S的一个去核D约简,则Q中的所有属性在DM中的对应列进行析取运算的结果为全1列向量;
性质3 若Q为S的一个去核D约简,则Q的所有超集Q'均能区分DM中的所有行,称Q'为S的一个去核D伪约简;
性质4 若Q为S的一个去核D约简,则Q的所有子集Q'均不是S的去核D约简;
性质5 若Q不是S的一个去核D约简,则Q的所有子集Q'均不是S的去核D约简。
定理3 算法1(函数3)可以寻找到决策系统的所有约简。
证明:由性质1～5可知,在约简集的逐级寻找过程中,若Lk中的元素表示属性集长度为k的去核约简,Ck中的元素表示属性集长度为k的非去核约简,在产生Lk+1和Ck+1时,必须满足Ck中的任意两元素Pi,Pj的并集Pi∪Pj的所有k项子集均在Ck中,否则,Pi∪Pj必有t项子集在Lt中,即Pi∪Pj为S的一个去核D伪约简,故不会将其加入到Lk+1或Ck+1中。
定理3既能保证找出系统的所有约简,同时可保证不会产生伪约简,无需进行属性冗余检查操作,还可在同等条件下减小搜索规模。
3 算例求解
为使算法执行过程更加清晰,以表1数据为例执行如下:
求解划分U/D={D1,D2,D3},具体如下:D1={x1,x2,x3,x4,x5,x6,x7},D2={x8,x9,x11,x14,x15,x16}, D3={x20}(各对象不再保存决策属性值且删除重复对象)。
寻找核,结果为core={100101},其中D13与D21比较产生a,D13与D22比较产生f,D26与D31比较产生d(其中Dij表示决策类Di下的第j个对象)。
构造区分矩阵,得结果如表2所示。
sm=sum(DM,1)=(0,1,1,0,2,0),则L1={e},C1={b,c},由C1中的元素进行连接,得P={bc},P的所有一项子集均在C1中,且dm=alternative(DM(,:2),DM(:,3)) =(1,1)T,满足sm=sum(dm,1)=2,故将其加入到L2中得L2={bc},C2=Φ,不再进行下一次连接操作,得一项去核约简集L1={e},二项去核约简集L2={bc}。由于core={100101},即core={adf},将core加入L1,L2的对应元素中,并重新排序得L1={adef},L2={abcdf},则RED=L1∪L2={adef,abcdf};
输出系统的核为core={adf},约简为RED={adef,abcdf}。
4 实验仿真与复杂度分析
4.1 仿真实验
为验证算法的效率和正确性,选取了四个数据库进行实验(实验环境:Windows7 32位操作系统,CPU AMD N830三核,内存2GB,硬盘500GB),实验结果见表3,其中系统1为表1所示的决策系统,系统2～4分别来自UCI数据库中Breast Cancer Wisconsin (Diagnostic)、Abalone和Adult的数据[21]。在算法对比上,由于一般的正域约简算法均为启发式算法,仅仅获取一个约简,获得全部约简的时间复杂度相相当之高,而关于区分矩阵的约简文献中,亦极少有文献就如何由区分函数获取系统的全部约简进行说明,故本文的算法对比存在一定困难,为此,本文根据正域约简的一般理论,与文献[19]中的算法(称为算法A)进行对比,即根据约简前后正域相等的理论寻找约简,实验结果如表3所示。
实验表明算法能以较快的速度找到决策系统的全部约简,即使针对规模庞大的系统,仍能在可接受的时间内找到约简,并且当决策系统存在核属性时,能使得运算效率大大提高。对比试验显示,当数据规模越大,即对象越多或属性集越大时,本文算法的优越性越明显,尤其是当属性集增多时,本文算法的表现不甚敏感,而正域约简算法的时间复杂度将急剧增加。
4.2 复杂度分析
在算法1中,步骤(1)的时间复杂度为O(|U|2|A|),步骤(2)中,最坏情况下为每个对象为一个决策类,则需比较|U|(|U|-1)/2次,故复杂度为O(|U|2|A|),步骤(3)中,构造区分矩阵的比较次数与步骤(2)相同,为|U|(|U|-1)/2相同,但还需多出每一个dm与DM中元素的重复性判断过程,一方面,|DM|≤|U|(|U|-1)/2,另一方面,|DM|≤C
事实上,尽管复杂度看似较高,但在实际中几乎不可能遇到这种极端情况,对于规模较大的系统仍能在较短时间内求得约简。此外,由于算法采用MATLAB程序实现,且区分项采用布尔矩阵形式存储,整个过程始终秉承矩阵操作思想,减少循环层,对数据实行整行或整列运算,利用MATLAB的并行计算能力进一步使得算法效率大为提高,因此其执行效率实际上比正域约简下的NP问题要高很多。
关于MATLAB的并行计算,笔者进行了仿真实验,选取对矩阵执行简单的按列求和运算,分别采用无循环、单循环和嵌套循环三种方式实现,其运算结果如表4所示(以运行时间的倍数关系表示,矩阵规模为n×1000)。
从表4可以看出,采用无循环(即调用系统函数sum(A,1))方式的执行效率相比于传统的循环实现方式有较大优越性。
5 结 语
本文提出的算法的主要思想是同一决策类下的对象可不作区分,并将寻找核属性和构造区分矩阵分开执行,利用核属性和集合的吸收律大大简化了区分矩阵的规模,然后利用关联规则挖掘思想逐级寻找系统的所有约简。整个算法始终以矩阵为基础进行整体操作,利用MATLAB的并行计算能力加快算法的执行,理论分析和仿真实验均表明算法是正确的且具有较高的效率。
由于本文在于寻找决策系统的所有约简(包括最优约简),因此,本文难免要涉及到NP-hard问题的求解,但在绝大多数情况下,该算法能在可接受的时间复杂度下可以找到决策系统的最优约简和所有约简。事实上,对于属性集异常庞大的系统,为加快寻找约简的速度,可在算法第(4)步中稍作修改,只将满足一定置信度的候选约简集加入到Ck中,并在找到一个约简后即可退出循环,同样可保证算法能求得系统的最优约简,但此时无法找出全部约简。