论文部分内容阅读
[摘要] 随着经济的迅猛发展，市场信息化和现代化程度的不断提高，信息不确定性的影响越来越大，在数据挖掘中引入模糊逻辑，以及部分不确定性的表达很有必要。本文在引入相似度算子等相关概念，以及对原有的算法进行了相应的模糊改进后，使得原有的带有满意度的依赖关联在保留更多有用的初始信息基础上有了更进一步的修正。
[关键词] 数据挖掘 关联规则 模糊逻辑 相似度算子
随着经济的迅猛发展，企业信息化的程度不断得以提高，于是，信息不确定性的影响越来越大。数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，尤其是在有关互联网的海量数据搜索，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程设计和科学探索等。数据挖掘是从大量数据中提取或挖掘知识，而数据挖掘技术则是对一些相关技术的集成，所以数据挖掘的方法也都是基于机器学习、模式识别，以及统计方法等来实现的。当然，不同的技术下的方法得到的知识的表达形式可能是不同的。从知识的表达形式上，可以将数据挖掘分为分类、回归、关联、聚类、概要、发现变化和偏差等等，其中，关联因为其广泛适用性，以及方法的成熟性，成为了最重要的也是应用最为广泛的数据挖掘方法之一，于是，基于关联规则的研究是始终受到关注。
自从关联规则的概念由Agrawal等人提出，关联规则在众多领域的应用，如金融、证券市场、气象学、营销、医学、制造业、电子商务等等促使人们对于关联规则的挖掘有了大量的研究。此外，Agrawal及Srikant等人研究发现关联规则是利用Apriori这一典型的有关于挖掘的运算法则来运算的最基本的挖掘方法。除了关联规则之外，另一种普遍关注的关联是功能依赖，它是另外一种兴趣度的关联。功能依赖可以从逻辑上在原先设计好的关系上面假设或者构造。同时，在将数据挖掘看成是一种反转工程的情况下，功能依赖的发现受到了很高的重视。模式关联是第三种关联方式。真正的应用软件中遇到时间序列模式一般会有如下几种情况：生产、销售、经济学，以及股票数据。由于时间序列反映了在连续的因素如时间中的数据变化的演变过程，所以发现时间序列中的关系有比较特殊的作用。通常时间序列模式会有很多方式的彼此相互关联。
通常在商务智能或人工智能的知识发现中引入不确定性的描述和表达源自于两个方面的需要:一个是在知识表达和发现中的内在不确定性的需要;另一个是在复杂决策过程中经常遇到的对抽象化概念，以及具有自然语言表达的需要。这两个方面的问题使得在知识发现中引入模糊逻辑，以及部分不确定性的表达很有必要。
一、满意度依赖关联
依赖关联作为关系数据库理论和应用中的一个重要概念，在知识发现领域的研究非常不够，首先，它对普遍存在于数据库中的噪音不能很好地在挖掘模型中进行处理，从而导致大量有价值的信息的丢失；其次，传统依赖关联概念表达的是一种完全的知识，也就是说对于整个关系都成立的，但是除了诸如此类的强知识之外，有一些在部分程度上成立的知识也是存在并且有意义的。因此一种新的依赖关联的概念——带有满意度的依赖关联就产生了。简而言之，它是通过概率估计来描述某个依赖关联在数据库中成立的程度的。一方面，它能够以满意度来描述某个依赖关联在该数据库中成立的程度，从而能够容纳噪音所带来的问题。另一方面，它能够量化地表达部分成立的知识，并且，由于它通过简单加总来描述满意度的测度，从而得到的结果更具有直观性和易于解释性。这个新的概念有一系列的相关定义及性质的证明。在相关的定义下，关系T不再是完全支持或者只完全不支持某个依赖关联，而是以某个度——满意度——来支持。具体来说，TRUTHT(A→B)就称为依赖关联A→B的满意度，它的含义为关系T支持依赖关联的程度。总得来说，该概念可以容纳噪音并且能够将部分知识量化进行表达和评价，而且和在数据库中挖掘传统关联规则相比，带有满意度的依赖关联具有更加好的理论和数学性质，也具有更容易理解的语义和更重要的价值。
二、相似度算子的选择与实现
由于很多实际的数据库中的数据是庞杂而凌乱的，基本上没有什么数值完全一致的数据，而根据原有的带有满意度的依赖关联的定义“如果ti(A)≠tj(A)，则TRUTH(ti,tj)(A→B)=1”，那么基本上所有的数据都是可以相互依赖关联的，这样做出的结果是没有任何意义的。所以，为了寻求数据在一定意义上的同一性，我们引入了相似度算子对数据库中同一属性的不同值进行了相似度的计算，然后用相似度作为衡量标准对数据进行进一步的依赖关联上的处理。
這里选择e-t作为相似度的算子，其具体的实现方式是对同一属性在不同时期的值做一个差的绝对值运算，然后再对其进行相似度的运算。例如，在一个股票交易市场的数据库中，现有两只股票A、B，假设每只股票有三天的收盘价格a1、a2、a3，b1、b2、b3，不失一般性地，a1、a2、a3，b1、b2、b3每三个数互不相同，如果按照以往的依赖关联的计算方式，那么一定可以得到A→B是成立的，而这种结论是没有意义的，所以，现在要改用相似度算子的方式来计算A与B之间的依赖关联程度:先算出a1、a2之间的差的绝对值d12，然后计算得出α12=e-d12，同理得到α13,α23;先算出b1、b2之间的差的绝对值s12，然后计算得出β12=e-s12，同理得到β13，β23。
在计算完了相似度之后，就要对计算所得出的α12、α13、α23，以及β12、β13、β23进行模糊关联运算来得出A与B的依赖关联程度。用于计算模糊关联的算子有很多，像S算子，G算子，KDL算子，DA算子等等，我们挑选了其中的KD算子来使用。KD模糊关联算子的公式为KD(a,b)=max(1-a,b)。也就是说我们可以算出k12=KD(α12,β12)=max(1-α12,β12)，同理可得k13及k23，当k12即依赖关联A→B的满意度不小于预先规定的最小支持度θ的时候，则认为（t1,t2）(A→B)的值为有意义的。最后，根据这几个值来计算最后的TRUTHT（A→B）的值。另外，需要注意的是，如果有多个前件的话，那么每次取其中最小的一个来进行KD运算，同理，有多个后件也照此处理。下面给出相关规则的定义及其扩展：
1.设R（I1,I2,…,Im）为一个在论域D1,D2,…,Dm上的关系模式，其中Ik的论域为Dk。若A和B分别为属性集合I={I1,I2,…,Im}的子集，即A,B包含于I，且T为R的一个关系，即T 包含于D1×D2×…×Dm，其中ti,tj∈T，且ti≠tj。则我们称，对于一个事物记录对（ti,tj），B依赖关联于A，表示为（ti,tj）(A→B)，假设TRUTH（ti,tj）(A→B)=kij。
（1）如果ti(A)与tj(A)相似度很高，并且ti(B)与tj(B)相似度也很高，也就是说αij与βij都不小于θ，那么，kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。
（2）如果ti(A)与tj(A)相似度很高，并且ti(B)与tj(B)相似度不高，也就是说αij不小于θ，可是βij小于θ，那么（a）如果θ不大于0.5，那么kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。（b）如果θ大于0.5，那么kij一定小于θ，则（ti,tj）(A→B)没有意义，但仍取TRUTH（ti,tj）(A→B)=kij。
（3）如果ti(A)与tj(A)相似度不高，也就是说αij小于θ，那么（a）如果αij<0.5，那么kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。（b）如果αij<0.5，那么如果可是βij不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij，反之则（ti,tj）(A→B)没有意义，但仍取TRUTH（ti,tj）(A→B)=kij。
2.给定T(有n条事务记录)和I，且A包含于I，B包含于I。设T（A→B）表示为，对于关系T上，B依赖关联于A。则T支持依赖关联A→B的度σ表示为TRUTHT(A→B）。
3.给定一个R(I1,I2,…,Im)上的关系T(T包含n条事务记录)，并且给定阈值ρ（0≤ρ≤1），A，B包含于I，如果A→B的满意度，即TRUTHT(A→B）≥ρ，则我们将A→B称为是一个合格的依赖关联。
在引入了相关概念及对原有的算法进行了相应的模糊改进后，原有的带有满意度的依赖关联就有了更进一步的修正，从而较以前可以保留更多有用的信息，并且，需要说明的是，这种带有模糊的满意度依赖关联算法同样也适用于原来的同一属性的值基本相同的情况。也就是说，这种带有模糊算子的满意度依赖关联算法更具有一般性。
三、结束语
由于模糊关联挖掘具有对自然语言的表达和不确定知识的处理上的优越性，它无论是对于研究人员还是对于实际应用者来说都是一个十分有前途的领域。另外对于理论研究领域，一些应用软件和系统平台已经被开發出来甚至应用到实际中了。大量的理论研究包括知识发现，不确定性模型、工具、计算复杂度和算法改进在近些年来不断地出现，而日益增加的丰富的应用和执行软件又促使着发展不断地前进。更具体地来说，模糊关联规则是大家的研究重点,其中,为了规则表达而进行的分割或者聚类连续赋值数据、语义摘要、语言学修正和逻辑牵连等得到了大量的关注。另外,有越来越多的研究表明了有不确定性关系的数据之间是存在着依赖的。最后，模式关联的发现被看作是一个在未来很有发展前途的研究领域,时间序列数据和顺序行为很值得去研究。
参考文献:
[1]Jiawei Han，Micheline Kamber，《数据挖掘概念与技术》，机械工业出版社
[2]C. Giannella, C. M. Wyss, Finding Minimal Keys in a Relation Instance, http://citeseer.nj.nec.com/
[关键词] 数据挖掘 关联规则 模糊逻辑 相似度算子
随着经济的迅猛发展，企业信息化的程度不断得以提高，于是，信息不确定性的影响越来越大。数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，尤其是在有关互联网的海量数据搜索，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程设计和科学探索等。数据挖掘是从大量数据中提取或挖掘知识，而数据挖掘技术则是对一些相关技术的集成，所以数据挖掘的方法也都是基于机器学习、模式识别，以及统计方法等来实现的。当然，不同的技术下的方法得到的知识的表达形式可能是不同的。从知识的表达形式上，可以将数据挖掘分为分类、回归、关联、聚类、概要、发现变化和偏差等等，其中，关联因为其广泛适用性，以及方法的成熟性，成为了最重要的也是应用最为广泛的数据挖掘方法之一，于是，基于关联规则的研究是始终受到关注。
自从关联规则的概念由Agrawal等人提出，关联规则在众多领域的应用，如金融、证券市场、气象学、营销、医学、制造业、电子商务等等促使人们对于关联规则的挖掘有了大量的研究。此外，Agrawal及Srikant等人研究发现关联规则是利用Apriori这一典型的有关于挖掘的运算法则来运算的最基本的挖掘方法。除了关联规则之外，另一种普遍关注的关联是功能依赖，它是另外一种兴趣度的关联。功能依赖可以从逻辑上在原先设计好的关系上面假设或者构造。同时，在将数据挖掘看成是一种反转工程的情况下，功能依赖的发现受到了很高的重视。模式关联是第三种关联方式。真正的应用软件中遇到时间序列模式一般会有如下几种情况：生产、销售、经济学，以及股票数据。由于时间序列反映了在连续的因素如时间中的数据变化的演变过程，所以发现时间序列中的关系有比较特殊的作用。通常时间序列模式会有很多方式的彼此相互关联。
通常在商务智能或人工智能的知识发现中引入不确定性的描述和表达源自于两个方面的需要:一个是在知识表达和发现中的内在不确定性的需要;另一个是在复杂决策过程中经常遇到的对抽象化概念，以及具有自然语言表达的需要。这两个方面的问题使得在知识发现中引入模糊逻辑，以及部分不确定性的表达很有必要。
一、满意度依赖关联
依赖关联作为关系数据库理论和应用中的一个重要概念，在知识发现领域的研究非常不够，首先，它对普遍存在于数据库中的噪音不能很好地在挖掘模型中进行处理，从而导致大量有价值的信息的丢失；其次，传统依赖关联概念表达的是一种完全的知识，也就是说对于整个关系都成立的，但是除了诸如此类的强知识之外，有一些在部分程度上成立的知识也是存在并且有意义的。因此一种新的依赖关联的概念——带有满意度的依赖关联就产生了。简而言之，它是通过概率估计来描述某个依赖关联在数据库中成立的程度的。一方面，它能够以满意度来描述某个依赖关联在该数据库中成立的程度，从而能够容纳噪音所带来的问题。另一方面，它能够量化地表达部分成立的知识，并且，由于它通过简单加总来描述满意度的测度，从而得到的结果更具有直观性和易于解释性。这个新的概念有一系列的相关定义及性质的证明。在相关的定义下，关系T不再是完全支持或者只完全不支持某个依赖关联，而是以某个度——满意度——来支持。具体来说，TRUTHT(A→B)就称为依赖关联A→B的满意度，它的含义为关系T支持依赖关联的程度。总得来说，该概念可以容纳噪音并且能够将部分知识量化进行表达和评价，而且和在数据库中挖掘传统关联规则相比，带有满意度的依赖关联具有更加好的理论和数学性质，也具有更容易理解的语义和更重要的价值。
二、相似度算子的选择与实现
由于很多实际的数据库中的数据是庞杂而凌乱的，基本上没有什么数值完全一致的数据，而根据原有的带有满意度的依赖关联的定义“如果ti(A)≠tj(A)，则TRUTH(ti,tj)(A→B)=1”，那么基本上所有的数据都是可以相互依赖关联的，这样做出的结果是没有任何意义的。所以，为了寻求数据在一定意义上的同一性，我们引入了相似度算子对数据库中同一属性的不同值进行了相似度的计算，然后用相似度作为衡量标准对数据进行进一步的依赖关联上的处理。
這里选择e-t作为相似度的算子，其具体的实现方式是对同一属性在不同时期的值做一个差的绝对值运算，然后再对其进行相似度的运算。例如，在一个股票交易市场的数据库中，现有两只股票A、B，假设每只股票有三天的收盘价格a1、a2、a3，b1、b2、b3，不失一般性地，a1、a2、a3，b1、b2、b3每三个数互不相同，如果按照以往的依赖关联的计算方式，那么一定可以得到A→B是成立的，而这种结论是没有意义的，所以，现在要改用相似度算子的方式来计算A与B之间的依赖关联程度:先算出a1、a2之间的差的绝对值d12，然后计算得出α12=e-d12，同理得到α13,α23;先算出b1、b2之间的差的绝对值s12，然后计算得出β12=e-s12，同理得到β13，β23。
在计算完了相似度之后，就要对计算所得出的α12、α13、α23，以及β12、β13、β23进行模糊关联运算来得出A与B的依赖关联程度。用于计算模糊关联的算子有很多，像S算子，G算子，KDL算子，DA算子等等，我们挑选了其中的KD算子来使用。KD模糊关联算子的公式为KD(a,b)=max(1-a,b)。也就是说我们可以算出k12=KD(α12,β12)=max(1-α12,β12)，同理可得k13及k23，当k12即依赖关联A→B的满意度不小于预先规定的最小支持度θ的时候，则认为（t1,t2）(A→B)的值为有意义的。最后，根据这几个值来计算最后的TRUTHT（A→B）的值。另外，需要注意的是，如果有多个前件的话，那么每次取其中最小的一个来进行KD运算，同理，有多个后件也照此处理。下面给出相关规则的定义及其扩展：
1.设R（I1,I2,…,Im）为一个在论域D1,D2,…,Dm上的关系模式，其中Ik的论域为Dk。若A和B分别为属性集合I={I1,I2,…,Im}的子集，即A,B包含于I，且T为R的一个关系，即T 包含于D1×D2×…×Dm，其中ti,tj∈T，且ti≠tj。则我们称，对于一个事物记录对（ti,tj），B依赖关联于A，表示为（ti,tj）(A→B)，假设TRUTH（ti,tj）(A→B)=kij。
（1）如果ti(A)与tj(A)相似度很高，并且ti(B)与tj(B)相似度也很高，也就是说αij与βij都不小于θ，那么，kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。
（2）如果ti(A)与tj(A)相似度很高，并且ti(B)与tj(B)相似度不高，也就是说αij不小于θ，可是βij小于θ，那么（a）如果θ不大于0.5，那么kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。（b）如果θ大于0.5，那么kij一定小于θ，则（ti,tj）(A→B)没有意义，但仍取TRUTH（ti,tj）(A→B)=kij。
（3）如果ti(A)与tj(A)相似度不高，也就是说αij小于θ，那么（a）如果αij<0.5，那么kij一定不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij。（b）如果αij<0.5，那么如果可是βij不小于θ，则（ti,tj）(A→B)有意义，取TRUTH（ti,tj）(A→B)=kij，反之则（ti,tj）(A→B)没有意义，但仍取TRUTH（ti,tj）(A→B)=kij。
2.给定T(有n条事务记录)和I，且A包含于I，B包含于I。设T（A→B）表示为，对于关系T上，B依赖关联于A。则T支持依赖关联A→B的度σ表示为TRUTHT(A→B）。
3.给定一个R(I1,I2,…,Im)上的关系T(T包含n条事务记录)，并且给定阈值ρ（0≤ρ≤1），A，B包含于I，如果A→B的满意度，即TRUTHT(A→B）≥ρ，则我们将A→B称为是一个合格的依赖关联。
在引入了相关概念及对原有的算法进行了相应的模糊改进后，原有的带有满意度的依赖关联就有了更进一步的修正，从而较以前可以保留更多有用的信息，并且，需要说明的是，这种带有模糊的满意度依赖关联算法同样也适用于原来的同一属性的值基本相同的情况。也就是说，这种带有模糊算子的满意度依赖关联算法更具有一般性。
三、结束语
由于模糊关联挖掘具有对自然语言的表达和不确定知识的处理上的优越性，它无论是对于研究人员还是对于实际应用者来说都是一个十分有前途的领域。另外对于理论研究领域，一些应用软件和系统平台已经被开發出来甚至应用到实际中了。大量的理论研究包括知识发现，不确定性模型、工具、计算复杂度和算法改进在近些年来不断地出现，而日益增加的丰富的应用和执行软件又促使着发展不断地前进。更具体地来说，模糊关联规则是大家的研究重点,其中,为了规则表达而进行的分割或者聚类连续赋值数据、语义摘要、语言学修正和逻辑牵连等得到了大量的关注。另外,有越来越多的研究表明了有不确定性关系的数据之间是存在着依赖的。最后，模式关联的发现被看作是一个在未来很有发展前途的研究领域,时间序列数据和顺序行为很值得去研究。
参考文献:
[1]Jiawei Han，Micheline Kamber，《数据挖掘概念与技术》，机械工业出版社
[2]C. Giannella, C. M. Wyss, Finding Minimal Keys in a Relation Instance, http://citeseer.nj.nec.com/