数据挖掘导论第7章-关联分析-高级概念

1、关系分析：高级概念，第7章关系分析：高级概念，关系分析处理事务数据，rules discovered : diaper-beer，分类属性处理，有关internet用户特征的有趣信息：在线购物=隐私=是，对于很多应用程序，对称二进制属性表7-1中显示的互联网调查数据包括性别、家庭计算机、网络聊天、网上购物和隐私等对称二进制属性。还包括文化程度和公称属性，例如注释。分类属性处理，公称属性和对称二进制属性必须转换为“项目”，以便使用现有关联规则挖掘算法提取这些模式。这种类型的变更可以通过为每个不同的属性-值对创建新条目来实现。例如，表示属性文化水平可以替换为文化水平=大学文化水平=研究生文化水平=

2、高中相似，对称二进制属性性别可以替换为一对二进制项目(性别=男性，性别=女性)。处理分类属性和在二元化数据中使用相关性分析时，请考虑以下问题：(1)某些属性值可能不会经常使用，因为它们会成为频繁模式的一部分。范例：注记名称。解决方法：将相关属性值分组以形成几个类别。例如，每个州的名称可以由相应的地理区域代替。例如：分别替换为中西部、太平洋西北部、西南部和东部海岸。处理分类属性和使用辅助数据的相关分析时，请考虑以下问题：(2)某些属性值的频率可能远高于其他属性。例如，假设85%的被调查者拥有家庭计算机。如果为数据中经常出现的每个属性值创建两阶段条目，则可能会产生很多重复模式。家庭计算机=是，在线

3、购物=注重隐私=是解决方法：使用处理具有广泛支持功能的极恶数据集的技术。处理分类属性和使用辅助数据的相关分析时，请考虑以下问题：(3)计算时间可能会增加，尤其是经常生成新生成的条目时。因为将生成更多的候选集。解决方法：不要创建包含具有相同属性的多个项目的候选集。例如，您无需创建候选集(如州=X，州=Y)，因为此集支持0度。连续属性处理，internet调查数据还可以包含连续属性，如表7-3所示。连续属性挖掘将包含年收入超过120k的用户属于45-60年龄组”或“拥有3个以上电子邮件帐户，每周使用互联网超过15个小时的用户一般关注隐私”的：连续属性的关联规则称为数量关联规则(quantiativ

4、e association rule)。连续数据的相关分析方法：基于离散化的方法非基于统计的方法，基于离散化的方法，离散化是处理连续属性最常用的方法。此方法将连续属性的相邻值分组，形成有限区间。例如：年龄属性可以分为12、16、20、20、24)、56、60等部分。离散化技术：等宽、等频率、群集表7-4显示了离散化和二元化后的互联网调查数据。属性分隔的核心是分割每个属性的宗地数目和宽度。但是很难确定正确的间隔。支持阈值=5%，置信度阈值=65%。在表中，您可以介绍年龄和在线聊天的隐式强有力的规则。16，24)联机聊天=是(s=8.8%，c=81.5%) 44，60)联机聊天=否(s=16.8%

5、，c=70%)间隔宽度对关联分析结果的影响。(1)间隔太大，可能会因可靠性不足而失去一些规则。例如，当区间宽度为24岁时，上述两条规则为16，36。在线聊天=是(s=30%，57.7%) 36，60)在线聊天=否(s=28%，58.3%)，区间宽度对关联分析结果的影响(2)间隔太窄，可能会因缺乏支持而失去一些规则。(。例如，区间宽度为4岁时，上述两个规则为16，20。线上交谈=是(s=4.4%，84.6%)线上交谈=是(s=4.4%，78.6%) (3)区段宽度为8岁时，上述两条规则为44，52)线上交谈=否例如，在表7-6所示的文本文档中查找单词的关联。在文本挖掘中，分析人员对搜索词之间的关

6、联性(如数据和挖掘)更感兴趣。不是单词频率间隔(例如数据：1，4，挖掘：2，3)之间的关联。一种方法是将数据转换为0/1矩阵。其中，如果规格化字数超过了阈值t，则值为1，否则为0。该方法的缺点是很难确定阈值。另一种方法是使用min-apriori方法。S (word 1，word 2)=min (0.3，0.6) min (0.1，0.2) min (0.4，0.2) min (0.2，0)=随着包含单词的文档数量的增加，单调地增加。处理概念分层，即在一个特定域中定义的各种实体或概念的多层组织。概念分层可以用直接非循环图表示。概念分层的主要优点(1)对AC适配器等分层子项的支持可能不足，但作为

7、概念分层的父节点(例如便携式附件)，支持程度较高。(2)在较低级别找到的规则往往过于专门化，可能不如较高级别的规则有趣。(例如，脱脂吴优普通面包、脱脂吴优白面包等太特别了)，实现概念分层的方法每个事务t都被它的扩展事务t取代。其中，t包含t的所有项目及其祖先。对于交易DVD，普通面包可以使用现有算法(如DVD、普通面包、家用电器、电子产品、面包、食品和扩展数据库的Apriori)在多个概念层中查找规则。概念分层的主要缺点(1)较高级别的项目比较低级的项目支持度高。(2)概念分层的引入增加了关联分析的计算时间。(3)概念分层的引入可能产生冗余规则。规则X Y是重复的，并且具有更通用的规则X Y，

8、其中X是X的父代成员，Y是Y的父代成员，两个规则具有非常相似的置信度。例如，面包吴优、白面包脱脂吴优、麦片图案和购物车数据通常包含有关产品购买时间的信息。利用这些信息，可以将顾客一定时间内的购物结合成交易序列。但是，到目前为止所描述的关联模式的概念忽略数据的序列信息，仅强调并发关系。序列信息对于确定动态系统的郑在玹特性或预测特定事件未来的发生可能非常有价值。序列模式、按时间顺序对与对象a相关的所有事件进行排序时，可以将a的序列、sequence database :通常将序列记录为元素的已排序列表，以s=记录。其中每个EJ是一个或多个事件的集合族ej=i1、I2、ik。sequence、e1e

9、2、e1e3、e2、E3 E4、E2、element (transaction)、event()，序列模式搜索，d是否支持包含一个或多个数据序列的数据集：序列s是包含s的所有数据序列所占的百分比。如果序列s的支持大于或等于用户指定的阈值minsup，则s为序列模式(或频繁的序列)。7.1序列模式搜索定义：搜索指定序列数据库d和用户指定的最小支持阈值minsup，序列模式搜索操作是查找支持大于或等于minsup的所有序列。是，minsup=50% examples of frequent subsequence s :s=60% s=60% s=80% s=80% s=80%以下两个项目之一在项

10、目集中至少出现一次，但由于一个事件可能在序列中出现多次，因此生成了更多候选项：给定两个要素i1和I2，仅生成一个候选项2-要素集i1和I2，但是您可以生成多个候选项2-系列(例如，)。顺序在序列中很重要，但在项目集中不重要。例如，1，2和2，1表示同一组项目，而和徐璐对应于不同的序列，因此必须单独创建。先验原理建立了序列数据。包含特定k系列的所有数据系列必须包含该k系列的所有(k-1)系列。序列模式发现的类Apriori算法，候选生成，一对频繁(k-1)-序列组合，生成候选k-序列。现有的Apriori算法仅在当前k-1项相同的情况下合并一对频繁的k-项集，以避免重复候选项。类似的方法可以用于

11、序列。例子是通过合并获得的。事件3和事件4属于第二个序列的其他元素，因此在合并的序列中也属于其他元素。合并获得。事件3和事件4属于第二个序列的相同元素，因此4合并到第一个序列的最后一个元素中。候选修剪候选k序列被修剪(k-1)-至少有一个序列不经常使用。例如，假设候选人4-序列。我们必须经常检查是否是3-序列。因为这些都不频繁，所以可以删除候选者。支持度计数支持度计数中，算法列出属于特定数据序列的所有候选k序列。计数允许算法识别频繁的k序列，丢弃支持数量低于最小支持阈值minsup的候选。图7-6，时间限制约束、模式中的事件和元素强制执行时间限制约束。例如：学生a:学生b:感兴趣的模式意味着注

12、册数据挖掘课程的学生必须首先参加数据库系统和统计科目。两个学生都不是同时选择了统计和数据库系统，但很明显这种模式得到了支持。相比之下，10年前修过统计课程的学生不能认为支持这门课程的间隔太长。图7-7显示了适用于模式的一些时间限制约束。最大范围约束、最大范围约束指定整个序列中允许的事件的最晚时间和最早发生时间的最大时间差异。下表假定最大时间范围maxspan=3，并包含指定数据序列支持和不支持的序列模式。通常，maxspan越长，在数据序列中检测模式的可能性就越大。但是，如果maxspan很长，捕获不真实的图案可能会包含过时的事件。最大跨度约束影响序列模式搜索算法的支持数量。应用最长持续时间约

13、束后，某些数据序列不再支持候选模式。最小和最大时间间隔约束，时间限制约束也可以通过限制序列中两个连续元素之间的时间差异来指定。如果最大时差(maxgap)为一周，则元素的事件必须在之前元素的事件发生后一周内出现。如果最小时差(mingap)为0，则元素的事件必须在之前元素的事件发生后出现。maxgap=3，mingap=1，下表显示了阵列通过或不通过最大间距和最小间距约束的示例。与最大跨度类似，某些数据序列在具有最小间隔和最大间隔约束时不再支持候选模式，因此，这些约束会影响序列模式搜索算法的支持数量。使用最大间隙约束可能会违反先验原理。要说明这一点，请考虑图7-5中的数据集。没有最小或最大间隙

14、约束时，和的支撑度均为60%。但是，如果mingap=0，maxgap=1，则的支持级别下降到40%，的支持级别仍然为60%。这违反先验原则。例如，minsup=50% examples of frequent subsequence s :s=60% s=60% s=80% s=80% s=80% s(2)s从至少具有两个事件的任意eiw中删除一个事件，然后由w获得。(3)s是t的相邻子序列，t是w的相邻子序列。7.3修订版的先验原理定义k-序列频繁，相应的相邻(k-1)-子序列也必须频繁。在候选修剪阶段，不需要检查所有k序列，因为其中的一些可能违反最大间距约束。例如，如果maxgap=1，

15、则无需检查候选子序列是否频繁，因为元素2，3和5之间的时间差异大于一个小时单位。应只调查相邻的子序列，包括、和。窗口大小约束，最后，元素SJ的事件不必同时出现。在序列模式的任何元素中，都可以定义窗口大小阈值(ws)，该阈值指定事件最晚发生的时间和最早发生的时间之间的最大允许时间差。如果窗口大小为零，则模式相同元素的所有事件必须同时出现。以下示例使用ws=2、mingap=0、maxgap=3、maxspan=、子图形模式将关联分析方法应用于比项目集和序列复杂得多的图元。例如，化学化合物、3-D蛋白质结构、网络拓扑和树结构的XML文档。可以用图形表示建模这些图元。对这种类型数据进行数据挖掘的任务是在图集中发现一组公共子结构。这种操作称为频繁子图挖掘、图和子图，定义了具有7.5支持度的图的集合族(如图7-10所示)，子图g的支持程度定义为包含该图像的所有图的百分比。7.2考虑了5个图G1 G5，如图7-10所示。右上角的图G1是G1、G3、G4、G5的子图形，因此s(g1)=4/5=80%。同样，G2是G1、G2和G3的子项，因此s(g2)=60%。而s(G3)=40%。因为G3是G1和G3的子图形。频繁子图形挖掘，7.6频繁子图形挖掘定义给定图形的集合和支持阈值minsup，频繁子图形挖掘