基于ARIZ的关联规则知识发现模式研究

翟霞　宋毅

【摘 要】 本文借助ARIZ思想深入研究了关联规则挖掘模式，综合介绍了关联规则的理论基础，进一步明确了项、项集、候选项集、频繁项集、支持度、置信度这些重要知识点，对关联规则进行了多角度的分类，研究分析了关联规则挖掘的经典算法，并对关联规则的评价标准进行了创新研究，引入了主观兴趣度和客观相关性分析，为后续研究和改进关联规则的算法提供了理论基础。

【关键词】 ARIZ 关联规则 兴趣度 相关性分析

1 ARIZ主导思想

ARIZ（Algorithm for Inventive-Problem Solving，发明问题解决算法）最初由Ahshuller于1956年提出，是TRIZ中最强有力的工具，集成了TRIZ理论中大多数观点和工具[1]。ARIZ的主导思想和观点中最重要的就是克服思维惯性。思维惯性是创新设计的最大障碍，ARIZ强调在解决问题过程中必须开阔思路克服思维惯性，主要通过利用TRIZ已有工具和一系列心理算法克服思维惯性。

TRIZ认为，一个创新问题解决的困难程度取决于对该问题的描述和问题的标准化程度，描述得越清楚，问题的标准化程度越高，问题就越容易解决。ARIZ中，创新问题求解的过程是对问题不断地描述，不断地标准化的过程。在这一过程中，初始问题最根本的矛盾被清晰地显现出来。如果方案库里已有的数据能够用于该问题则是有标准解；如果已有的数据不能解决该问题则无标准解，需等待科学技术的进一步发展。该过程是通过ARIZ算法实现的。

2 关联规则挖掘的基本理论

关联分析是和分类、聚类、演化分析等并列的一种知识发现模式，受到人们的广泛关注。Agrawal等人在1993年首次提出了商业数据库中各种商品间的关联问题，之后关于关联规则的研究层出不穷。关联规则的应用也由最初的购物篮分析扩展到其他各个领域，挖掘得到的规则说明也呈现多元化。

设I={i1，i2，…，im}是常数的集合，其中m是任意有限的正整数常量，每个常数ik（k=1，2，……，m）称为一个数据项，简称为项（item）。若X是由I中的任意数据项组成的集合，即XI，则称X为项集，若X是包含K个数据项的项集称为K-项集。

关联规则是描述数据库中数据项之间存在的潜在关系的规则，一个关联规则是形如XY的蕴涵式，其中XI，YI，并且X∩Y=Φ。项集X称为规则的前提或前项，Y称为结果或后项。关联规则直观描述事件中各个数据项同时出现概率较高的情况，如何找出这种高概率的发生，也就是说，这种高概率达到什么标准才能被认为是数据项之间是关联的。最常规的评价标准是由支持度和置信度这两个概念决定，通常被称为关联规则的评价函数。

关联规则AB在事务数据库D中成立，其中事务同时包含A和B的百分比，叫做该规则的覆盖率或支持度，记为Support（A∪B）。覆盖率高表示规则在数据库中出现的频率较高，这样规则所表现的现象发生的可能性也比较大。

关联规则AB在事务数据库D中成立，在数据库中同时出现项集A和B的记录数与出现项集A的记录数的百分比，叫做该规则的正确率或置信度，记为Confidence（A∪B）。正确率高表示规则比较可信的，正确率在90%以上的规则，我们称之为强规则。

项集的频率是事务数据库中出现该项集的记录数。如果某一项集频率大于或等于最小支持度设定的阈值，我们通常称它为频繁项集（frequent itemset）。包含有k个项的频繁项集即通常表示为k-频集。当一条规则同时满足最小支持度和最小置信度设定的阈值时，这条规则就是我们要找的真正的关联规则。

3 关联规则挖掘的分类

根据规则中所涉及的数据项的数据类型分为布尔关联规则和量化关联规则，例如：烤鸭甜面酱，被称为布尔关联规则，该规则前件和后件取值都是离散的，考虑的是某数据项存在或者不存在。在关联规则中出现数值型数据，例如：职称（“副教授”）年龄（“32…37”），这类规则称为量化关联规则。

根据规则中项或属性涉及到的维度数分为单维和多维关联规则。规则中涉及的数据项只来自于一个属性，例如：面包牛奶，这样的规则称为单维关联规则。而多维关联规则涉及事务数据库中的多个属性，例如：性别（“女”）职业（“教师”），可以称为二维关联规则。

根据规则中数据的抽象层次分为单层关联规则和多层关联规则[2]。在单层关联规则中，所有的数据项都是概括级别低的细节数据，没有层次的划分。多层关联规则体现了数据的层次性，规则中的数据可能位于同一层次，也可能位于不同的层次。例如：联想台式机HP扫描仪是单层关联规则，而“台式机HP扫描仪”是一个高一级概括层次和细节层次之间的层间关联规则，而“台式机扫描仪”则是高概括层次上的同级别关联规则。

4 关联规则挖掘的方法

Apriori算法是关联规则算法中经典的算法，它采用“宽度优先搜索策略”，核心思想是首先寻找频繁项集，然后根据找到的频繁项集产生关联规则。关联规则的产生比较容易，只需保证规则满足事先设定好的最小正确率即可。而寻找频繁项集的过程要复杂很多，整个算法的总体执行效率也是由这一步决定的。因此，针对该算法的研究热门都集中在如何快速找到频繁项集。

频繁模式增长树（Frequent Pattern-Growth）算法，是基于Apriori算法产生的，简称FP-Growth。该算法使用深度优先搜索策略替代了Apriori算法的宽度优先搜索策略[3]，把数据库压缩映射到一个小而紧凑的数据结构频繁模式树FP-Tree中，避免了多次扫描数据库。利用“模式分段增长”法避免产生大量的候选集。采用分而治之的递归算法将挖掘任务分解成若干较小任务，从而有效的缩小了搜索空间。

在关联规则的数据挖掘过程中，若是因为数据的分散性，很难在概念层次的细节层发现规则，这时一般采用多层关联规则挖掘的方法。多层关联规则挖掘一般采用自顶向下的方式，从最一般的概念层开始，到较具体的某一特定概念层，逐层寻找频繁项集，直到不能找到频繁项集为止。对于每一层，可以使用上面介绍的Apriori算法和FP-Growth算法，或是其他关联规则算法。

5 关联规则的价值评价方法

为了衡量挖掘出的某条规则是否有用，并且从结果集中过滤掉那些无用的规则，提出了基于兴趣度的定义方法，可以分为主观兴趣度和相关性分析。

一条规则是否有价值最终取决于用户的实际需求，只有用户才可以最终决定所获得的规则是否有效和可行。主观兴趣度的评价标准主要有两种：不可预期性和可操作性[4]。不可预期性是指如果挖掘出来的规则用户以前不知道，或者说与用户已知的知识刚好相反，则说该规则具有不可预期性。可操作性是指如果用户可以利用规则采取对自己有利的操作行为，则说该规则具有可操作性。

参考文献：

[1]沈萌红.《TRIZ理论及机械创新实践》[M].机械工业出版社，2012：18-26.

[2]段玉琴.数据挖掘中关联规则算法的研究[D].西安：西安电子科技大学硕士论文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.数据挖掘技术在美国院校研究中的应用[J].复旦教育论，2009，（2）：72-79.

[5]吴青，傅秀芬.水平分布数据库的正负关联规则挖掘[J].计算机技术与发展，2010，（6）：113-117.

【摘 要】 本文借助ARIZ思想深入研究了关联规则挖掘模式，综合介绍了关联规则的理论基础，进一步明确了项、项集、候选项集、频繁项集、支持度、置信度这些重要知识点，对关联规则进行了多角度的分类，研究分析了关联规则挖掘的经典算法，并对关联规则的评价标准进行了创新研究，引入了主观兴趣度和客观相关性分析，为后续研究和改进关联规则的算法提供了理论基础。

【关键词】 ARIZ 关联规则 兴趣度 相关性分析

1 ARIZ主导思想

ARIZ（Algorithm for Inventive-Problem Solving，发明问题解决算法）最初由Ahshuller于1956年提出，是TRIZ中最强有力的工具，集成了TRIZ理论中大多数观点和工具[1]。ARIZ的主导思想和观点中最重要的就是克服思维惯性。思维惯性是创新设计的最大障碍，ARIZ强调在解决问题过程中必须开阔思路克服思维惯性，主要通过利用TRIZ已有工具和一系列心理算法克服思维惯性。

TRIZ认为，一个创新问题解决的困难程度取决于对该问题的描述和问题的标准化程度，描述得越清楚，问题的标准化程度越高，问题就越容易解决。ARIZ中，创新问题求解的过程是对问题不断地描述，不断地标准化的过程。在这一过程中，初始问题最根本的矛盾被清晰地显现出来。如果方案库里已有的数据能够用于该问题则是有标准解；如果已有的数据不能解决该问题则无标准解，需等待科学技术的进一步发展。该过程是通过ARIZ算法实现的。

2 关联规则挖掘的基本理论

关联分析是和分类、聚类、演化分析等并列的一种知识发现模式，受到人们的广泛关注。Agrawal等人在1993年首次提出了商业数据库中各种商品间的关联问题，之后关于关联规则的研究层出不穷。关联规则的应用也由最初的购物篮分析扩展到其他各个领域，挖掘得到的规则说明也呈现多元化。

设I={i1，i2，…，im}是常数的集合，其中m是任意有限的正整数常量，每个常数ik（k=1，2，……，m）称为一个数据项，简称为项（item）。若X是由I中的任意数据项组成的集合，即XI，则称X为项集，若X是包含K个数据项的项集称为K-项集。

关联规则是描述数据库中数据项之间存在的潜在关系的规则，一个关联规则是形如XY的蕴涵式，其中XI，YI，并且X∩Y=Φ。项集X称为规则的前提或前项，Y称为结果或后项。关联规则直观描述事件中各个数据项同时出现概率较高的情况，如何找出这种高概率的发生，也就是说，这种高概率达到什么标准才能被认为是数据项之间是关联的。最常规的评价标准是由支持度和置信度这两个概念决定，通常被称为关联规则的评价函数。

关联规则AB在事务数据库D中成立，其中事务同时包含A和B的百分比，叫做该规则的覆盖率或支持度，记为Support（A∪B）。覆盖率高表示规则在数据库中出现的频率较高，这样规则所表现的现象发生的可能性也比较大。

关联规则AB在事务数据库D中成立，在数据库中同时出现项集A和B的记录数与出现项集A的记录数的百分比，叫做该规则的正确率或置信度，记为Confidence（A∪B）。正确率高表示规则比较可信的，正确率在90%以上的规则，我们称之为强规则。

项集的频率是事务数据库中出现该项集的记录数。如果某一项集频率大于或等于最小支持度设定的阈值，我们通常称它为频繁项集（frequent itemset）。包含有k个项的频繁项集即通常表示为k-频集。当一条规则同时满足最小支持度和最小置信度设定的阈值时，这条规则就是我们要找的真正的关联规则。

3 关联规则挖掘的分类

根据规则中所涉及的数据项的数据类型分为布尔关联规则和量化关联规则，例如：烤鸭甜面酱，被称为布尔关联规则，该规则前件和后件取值都是离散的，考虑的是某数据项存在或者不存在。在关联规则中出现数值型数据，例如：职称（“副教授”）年龄（“32…37”），这类规则称为量化关联规则。

根据规则中项或属性涉及到的维度数分为单维和多维关联规则。规则中涉及的数据项只来自于一个属性，例如：面包牛奶，这样的规则称为单维关联规则。而多维关联规则涉及事务数据库中的多个属性，例如：性别（“女”）职业（“教师”），可以称为二维关联规则。

根据规则中数据的抽象层次分为单层关联规则和多层关联规则[2]。在单层关联规则中，所有的数据项都是概括级别低的细节数据，没有层次的划分。多层关联规则体现了数据的层次性，规则中的数据可能位于同一层次，也可能位于不同的层次。例如：联想台式机HP扫描仪是单层关联规则，而“台式机HP扫描仪”是一个高一级概括层次和细节层次之间的层间关联规则，而“台式机扫描仪”则是高概括层次上的同级别关联规则。

4 关联规则挖掘的方法

Apriori算法是关联规则算法中经典的算法，它采用“宽度优先搜索策略”，核心思想是首先寻找频繁项集，然后根据找到的频繁项集产生关联规则。关联规则的产生比较容易，只需保证规则满足事先设定好的最小正确率即可。而寻找频繁项集的过程要复杂很多，整个算法的总体执行效率也是由这一步决定的。因此，针对该算法的研究热门都集中在如何快速找到频繁项集。

频繁模式增长树（Frequent Pattern-Growth）算法，是基于Apriori算法产生的，简称FP-Growth。该算法使用深度优先搜索策略替代了Apriori算法的宽度优先搜索策略[3]，把数据库压缩映射到一个小而紧凑的数据结构频繁模式树FP-Tree中，避免了多次扫描数据库。利用“模式分段增长”法避免产生大量的候选集。采用分而治之的递归算法将挖掘任务分解成若干较小任务，从而有效的缩小了搜索空间。

在关联规则的数据挖掘过程中，若是因为数据的分散性，很难在概念层次的细节层发现规则，这时一般采用多层关联规则挖掘的方法。多层关联规则挖掘一般采用自顶向下的方式，从最一般的概念层开始，到较具体的某一特定概念层，逐层寻找频繁项集，直到不能找到频繁项集为止。对于每一层，可以使用上面介绍的Apriori算法和FP-Growth算法，或是其他关联规则算法。

5 关联规则的价值评价方法

为了衡量挖掘出的某条规则是否有用，并且从结果集中过滤掉那些无用的规则，提出了基于兴趣度的定义方法，可以分为主观兴趣度和相关性分析。

一条规则是否有价值最终取决于用户的实际需求，只有用户才可以最终决定所获得的规则是否有效和可行。主观兴趣度的评价标准主要有两种：不可预期性和可操作性[4]。不可预期性是指如果挖掘出来的规则用户以前不知道，或者说与用户已知的知识刚好相反，则说该规则具有不可预期性。可操作性是指如果用户可以利用规则采取对自己有利的操作行为，则说该规则具有可操作性。

参考文献：

[1]沈萌红.《TRIZ理论及机械创新实践》[M].机械工业出版社，2012：18-26.

[2]段玉琴.数据挖掘中关联规则算法的研究[D].西安：西安电子科技大学硕士论文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.数据挖掘技术在美国院校研究中的应用[J].复旦教育论，2009，（2）：72-79.

[5]吴青，傅秀芬.水平分布数据库的正负关联规则挖掘[J].计算机技术与发展，2010，（6）：113-117.

【摘 要】 本文借助ARIZ思想深入研究了关联规则挖掘模式，综合介绍了关联规则的理论基础，进一步明确了项、项集、候选项集、频繁项集、支持度、置信度这些重要知识点，对关联规则进行了多角度的分类，研究分析了关联规则挖掘的经典算法，并对关联规则的评价标准进行了创新研究，引入了主观兴趣度和客观相关性分析，为后续研究和改进关联规则的算法提供了理论基础。

【关键词】 ARIZ 关联规则 兴趣度 相关性分析

1 ARIZ主导思想

ARIZ（Algorithm for Inventive-Problem Solving，发明问题解决算法）最初由Ahshuller于1956年提出，是TRIZ中最强有力的工具，集成了TRIZ理论中大多数观点和工具[1]。ARIZ的主导思想和观点中最重要的就是克服思维惯性。思维惯性是创新设计的最大障碍，ARIZ强调在解决问题过程中必须开阔思路克服思维惯性，主要通过利用TRIZ已有工具和一系列心理算法克服思维惯性。

TRIZ认为，一个创新问题解决的困难程度取决于对该问题的描述和问题的标准化程度，描述得越清楚，问题的标准化程度越高，问题就越容易解决。ARIZ中，创新问题求解的过程是对问题不断地描述，不断地标准化的过程。在这一过程中，初始问题最根本的矛盾被清晰地显现出来。如果方案库里已有的数据能够用于该问题则是有标准解；如果已有的数据不能解决该问题则无标准解，需等待科学技术的进一步发展。该过程是通过ARIZ算法实现的。

2 关联规则挖掘的基本理论

关联分析是和分类、聚类、演化分析等并列的一种知识发现模式，受到人们的广泛关注。Agrawal等人在1993年首次提出了商业数据库中各种商品间的关联问题，之后关于关联规则的研究层出不穷。关联规则的应用也由最初的购物篮分析扩展到其他各个领域，挖掘得到的规则说明也呈现多元化。

设I={i1，i2，…，im}是常数的集合，其中m是任意有限的正整数常量，每个常数ik（k=1，2，……，m）称为一个数据项，简称为项（item）。若X是由I中的任意数据项组成的集合，即XI，则称X为项集，若X是包含K个数据项的项集称为K-项集。

关联规则是描述数据库中数据项之间存在的潜在关系的规则，一个关联规则是形如XY的蕴涵式，其中XI，YI，并且X∩Y=Φ。项集X称为规则的前提或前项，Y称为结果或后项。关联规则直观描述事件中各个数据项同时出现概率较高的情况，如何找出这种高概率的发生，也就是说，这种高概率达到什么标准才能被认为是数据项之间是关联的。最常规的评价标准是由支持度和置信度这两个概念决定，通常被称为关联规则的评价函数。

关联规则AB在事务数据库D中成立，其中事务同时包含A和B的百分比，叫做该规则的覆盖率或支持度，记为Support（A∪B）。覆盖率高表示规则在数据库中出现的频率较高，这样规则所表现的现象发生的可能性也比较大。

关联规则AB在事务数据库D中成立，在数据库中同时出现项集A和B的记录数与出现项集A的记录数的百分比，叫做该规则的正确率或置信度，记为Confidence（A∪B）。正确率高表示规则比较可信的，正确率在90%以上的规则，我们称之为强规则。

项集的频率是事务数据库中出现该项集的记录数。如果某一项集频率大于或等于最小支持度设定的阈值，我们通常称它为频繁项集（frequent itemset）。包含有k个项的频繁项集即通常表示为k-频集。当一条规则同时满足最小支持度和最小置信度设定的阈值时，这条规则就是我们要找的真正的关联规则。

3 关联规则挖掘的分类

根据规则中所涉及的数据项的数据类型分为布尔关联规则和量化关联规则，例如：烤鸭甜面酱，被称为布尔关联规则，该规则前件和后件取值都是离散的，考虑的是某数据项存在或者不存在。在关联规则中出现数值型数据，例如：职称（“副教授”）年龄（“32…37”），这类规则称为量化关联规则。

根据规则中项或属性涉及到的维度数分为单维和多维关联规则。规则中涉及的数据项只来自于一个属性，例如：面包牛奶，这样的规则称为单维关联规则。而多维关联规则涉及事务数据库中的多个属性，例如：性别（“女”）职业（“教师”），可以称为二维关联规则。

根据规则中数据的抽象层次分为单层关联规则和多层关联规则[2]。在单层关联规则中，所有的数据项都是概括级别低的细节数据，没有层次的划分。多层关联规则体现了数据的层次性，规则中的数据可能位于同一层次，也可能位于不同的层次。例如：联想台式机HP扫描仪是单层关联规则，而“台式机HP扫描仪”是一个高一级概括层次和细节层次之间的层间关联规则，而“台式机扫描仪”则是高概括层次上的同级别关联规则。

4 关联规则挖掘的方法

Apriori算法是关联规则算法中经典的算法，它采用“宽度优先搜索策略”，核心思想是首先寻找频繁项集，然后根据找到的频繁项集产生关联规则。关联规则的产生比较容易，只需保证规则满足事先设定好的最小正确率即可。而寻找频繁项集的过程要复杂很多，整个算法的总体执行效率也是由这一步决定的。因此，针对该算法的研究热门都集中在如何快速找到频繁项集。

频繁模式增长树（Frequent Pattern-Growth）算法，是基于Apriori算法产生的，简称FP-Growth。该算法使用深度优先搜索策略替代了Apriori算法的宽度优先搜索策略[3]，把数据库压缩映射到一个小而紧凑的数据结构频繁模式树FP-Tree中，避免了多次扫描数据库。利用“模式分段增长”法避免产生大量的候选集。采用分而治之的递归算法将挖掘任务分解成若干较小任务，从而有效的缩小了搜索空间。

在关联规则的数据挖掘过程中，若是因为数据的分散性，很难在概念层次的细节层发现规则，这时一般采用多层关联规则挖掘的方法。多层关联规则挖掘一般采用自顶向下的方式，从最一般的概念层开始，到较具体的某一特定概念层，逐层寻找频繁项集，直到不能找到频繁项集为止。对于每一层，可以使用上面介绍的Apriori算法和FP-Growth算法，或是其他关联规则算法。

5 关联规则的价值评价方法

为了衡量挖掘出的某条规则是否有用，并且从结果集中过滤掉那些无用的规则，提出了基于兴趣度的定义方法，可以分为主观兴趣度和相关性分析。

一条规则是否有价值最终取决于用户的实际需求，只有用户才可以最终决定所获得的规则是否有效和可行。主观兴趣度的评价标准主要有两种：不可预期性和可操作性[4]。不可预期性是指如果挖掘出来的规则用户以前不知道，或者说与用户已知的知识刚好相反，则说该规则具有不可预期性。可操作性是指如果用户可以利用规则采取对自己有利的操作行为，则说该规则具有可操作性。

参考文献：

[1]沈萌红.《TRIZ理论及机械创新实践》[M].机械工业出版社，2012：18-26.

[2]段玉琴.数据挖掘中关联规则算法的研究[D].西安：西安电子科技大学硕士论文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.数据挖掘技术在美国院校研究中的应用[J].复旦教育论，2009，（2）：72-79.

[5]吴青，傅秀芬.水平分布数据库的正负关联规则挖掘[J].计算机技术与发展，2010，（6）：113-117.