Apriori算法用于频繁子图挖掘的改进方法

Ｃｏｍｐｕ￣ｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　２０１１，４７（１０）　１１３　Ａｐｒｉｏｒｉ算法用于频繁子图挖掘的改进方法　陈立宁，罗　可　ＣＨＥＮ　Ｌｉｎｉｎｇ，ＬＵＯ　Ｋｅ　长沙理工大学计算机与通信工程学院，长沙４　１　００７６　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈａｎｇｓｈａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４　１　００７６，Ｃｈｉｎａ　ＣＨＥＮ　Ｌｉｎｉｎｇ．ＬＵＯ　Ｋｅ．Ｉｍｐｒｏｖｅｄ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　Ａｐｒｉｏｒｉ－ｂａｓｅｄ　ｆｒｅｑｕｅｎｔ　ｓｕｂ－ｇｒａｐｈ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉ—　ｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ。２０１１．４７（１０）：１１３－１１７．　Ａｂｓｔｒａｃｔ：ＡＧＭ（Ａｐｒｉｏｒｉ—ｂａｓｅｄ　Ｇｒａｐｈ　Ｍｉｎｉｎｇ）ａｌｇｏｒｉｔｈｍ　ｉｓ　ｔｈｅ　ｆｉｒｓｔ　ｏｎｅ　ｔｏ　ｐｕｔ　ｔｈｅ　Ａｐｒｉｏｒｉ　ｉｄｅａ　ｉｎｔｏ　ｔｈｅ　ｕｓｅ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｓｕｂ—ｇｒａｐｈ　ｍｉｎｉｎｇ．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｉｍｐｌｅ　ａｎｄ　ｂａｓｅｄ　ｏｎ　ｒｅｃｕｒｓｉｏｎ　ｓｔａｔｉｓｔｉｃｓ．Ｂｕｔ　ｇｒａｐｈ　ｄａｔａ　ｓｅｔ　ｉｓ　ｖｅｒｙ　ｌａｒｇｅ　ａｎｄ　ｓｕｂ—ｇｒａｐｈ　ｉｓｏｍｏｒｐｈｉｓｍ　ｐｒｏｂｌｅｍ　ｉｓ　ａｖａｉｌａｂｌｅ，ｗｈｅｎ　ｃａｎｄｉｄａｔｅ　ｓｕｂｇｒａｐｈｓ　ａｒｅ　ｇｅｎｅｒａｔｅｄ　ａｎｄ　ＳＯ　ｍａｎｙ　ｒｅｄｕｎｄａｎｔ　ｓｕｂ—ｇｒａｐｈｓ　ｗｏｕｌｄ　ｂｅ　ｇｅｎ—　ｅｒａｔｅｄ，ｗｈｉｃｈ　ｍａｋｅｓ　ｔｈｅ　ｈｉｇｈ　ｃｏｓｔ　ｉｎ　ｃｏｍｐｕｔｉｎｇ　ｔｉｍｅ．Ａｎ　ｉｍｐｒｏｖｅｄ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ＡＧＭ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｇｅｔ　ｔｈｅ　ｒｅｄｕｃｔｉｏｎ　ｏｆ　ｒｅｄｕｎｄａｎｔ　ｓｕｂ・ｇｒａｐｈｓ　ａｎｄ　ｍａｋｅ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｍｈ　ｍｏｒｅ　ｅｆｉｆｃｉｅｎｔ　ｉｎ　ｃｏｍｐｕｔｉｎｇ　ｔｉｍｅ，ｃｏｍｐａｒｅｄ　ｔｏ　ＡＧＭ　ａｌｇｏｒｉｔｈｍ．Ｔｈｉｓ　ｐａ—　ｐｅｒ　ｅｘａｍｉｎｅｓ　ｔｈｅ　ｃｏｍｐｕｔｉｎｇ　ｔｉｍｅ　ｆｏｒ　ｖａｒｉｏｕｓ　ｍｉｎｉｍｕｍ　ｓｕｐｐｏｒｔ，ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｗｈｉｃｈ　ｐｒｏｖｅｓ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｃｕｔｓ　ｄｏｗｎ　ｔｈｅ　ｃｏｍｐｕｔｉｎｇ　ｔｉｍｅ，ｃｏｍｐａｒｅｄ　ｔｏ　ＡＧＭ　ａｌｇｏｒｉｔｈｍ，ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｅｆｉｆｃｉｅｎｃｙ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｓｕｂ—ｇｒａｐｈ　ｍｉｎｉｎｇ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｒｅｑｕｅｎｔ　ｓｂｕ—ｒｇａｐｈ　ｍｉｎｉｎｇ；Ａｐｒｉｏｒｉ－ｂａｓｅｄ　Ｇｒａｐｈ　Ｍｉｎｉｎｇ（ＡＧＭ）ａｌｇｏｒｉｔｈｍ；ｓｕｂ－ｇｒａｐｈ　ｉｓｏｍｏｒｐｈｉｓｍ　摘要：ＡＧＭ算法最早将Ａｐｒｉｏｒｉ思想应用到频繁子图挖掘中。ＡＧＭ算法结构简单，以递归统计为基础，但面临庞大的图数据集　时，由于存在子图同构的问题，在生成候选子图时容易产生很多冗余子图，使计算时间开销很大。基于ＡＧＭ算法，针对候选子图　生成这一环节对原算法进行改进，减少了冗余子图的生成，使改进后的算法在计算时间上具有高效性；测试了在不同最小支持度　情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间，提高了频繁子图的挖掘效率。　关键词：频繁子图挖掘；ＡＧＭ算法；子图同构　ＤＯＩ：１０．３７７８￣．ｉｓｓｎ．１００２—８３３１．２０１１．１０．０３２　文章编号：１００２—８３３１（２０１１）ｌ０．Ｏ１１３．０５　文献标识码：Ａ　中图分类号：ＴＰ３１１．１１　１引言　但如果图集数据庞大的话，该算法效率较低。主要是因为　随着数据挖掘算法在频繁项集和频繁序列上的成功应　ＡＧＭ在生成候选子图时要判断是否存在等价ｋ一１子图，如果　用，目前数据挖掘技术开始研究结构化模式挖掘问题——频　ｋ值很大的话，时间的开销很大。再者，候选子图的生成会一　繁子图挖掘…。现实生活中大量存在图形数据，使得关联规则　并产生许多冗余斛１子图。剪枝过程中，判断每个候选子图是　数据挖掘也涉及到图形领域。基于图的数据挖掘提出的时间　否频繁也要花费相当多的时问，并且剪枝后的候选子图仍有　并不长，在图数据集中频繁子图的挖掘是数据挖掘的新方　很多，需要多次重复扫描数据库来计算支持度。这就占用了　向。但图论作为数学的一个研究领域已有很长的研究历史，　大量内存空间和ＣＰＵ处理时间，很难发现长模式的频繁子图，　因此频繁子图挖掘很快发展起来，并被广泛应用。例如化学　效率不高。　领域，通过频繁子图挖掘算法找出有毒物质的分子结构，通过　根据以上分析，ＡＧＭ算法主要是在候选子图生成时没有　对网站浏览日志的挖掘分析出最频繁的浏览模式，以及生物　很好解决子图同构所带来的冗余子图生成的问题，从而在计　信息处理等等。因此频繁子图挖掘算法也成为当前数据挖掘　算支持度时也造成了大量的时问开销用于扫描和判断冗余子　领域里一个非常活跃的课题　。　图，影响了算法的效率。因此在ＡＧＭ算法基础上作出一些改　Ａｋｉｈｉｒｏ　Ｉｎｏｋｕｃｈｉ等人最早将Ａｐｒｉｏｒｉ算法应用到频繁子　进，采用邻接矩阵作为图的存储结构，在生成候选子图前加入　图挖掘　，这就是ＡＧＭ算法。给定一个图集Ｇ＝｛Ｇ　，Ｇ：，…Ｇ　｝　矩阵正规形判别算法，减少冗余子图的产生，提高算法的效率。　频繁子图挖掘就是发现不低于最小支持度阀值的子图。但是　频繁子图挖掘算法在性能方面存在两个瓶颈：候选子图的生　２算法相关知识　成；候选子图的支持度的计算　。前者主要是如何快速生成候　２．１　Ａｐｒｉｏｒｉ算法思想与原理　选子图，避免产生冗余的子图。后者就是解决子图同构问题。　Ａｐｆｉｏｆｉ算法采用一种逐层搜索的迭代方法，　项集用于搜　ＡＧＭ算法结构简单，以递归统计为基础，挖掘所有频繁子图，　索ｋ＋ｌ项集。算法的主要步骤如下：（用厶表示七项频繁集，Ｇ　基金项甘：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｍａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．１０９２６１８９，Ｎｏ．１０８７１０３１）；湖南省科技计划项　目（Ｎｏ．２００８ＦＪ３０１　５）。　作者简介：陈立宁（１９８４一），男，硕士，主要从事数据库技术、数据挖掘的研究；罗可（１９６１一），男，博士，教授。Ｅ—ｍａｉｌ：８８３８０２３１＠ｑｑ．ｃｏｒｎ　收稿日期：２００９—１１－０４；修回日期：２０１０．０１．０２　１１４　２０１１，４７（１０）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ算机工程与应用　表示　项候选集）　（３）计算候选子图的支持度就是计算图数据库中与该图　编码相同的图的个数，换言之就是找出候选子图与输入数据　库中哪些图是子图同构的关系。　（１）连接步　通过将厶一。进行自身连接产生候选ｋ项集，即Ｇ。　（２）剪枝步　Ｇ是厶的超集，Ｇ的成员既包含频繁项也含有非频繁项，　但所有频繁ｋ项集一定都包含在ｃ　中。对数据库进行扫描，确　定Ｇ中每个候选的计数，从而确定厶。但是，Ｇ可能很大，这　样所涉及的计算量很大。因此，利用任何非频繁的ｋ一１项集　都不是频繁ｋ项集的子集这一性质来压缩Ｇ　。若候选ｋ项集　３改进算法的设计思想　３．１邻接矩阵的正规化　诱导子图的支持度定义如下：　ｓｕｐ（Ｇ　㈤　的ｋ一１项子集不在厶一　中，则该候选项也不可能是频繁的，可　以从Ｇ中删除。　ＡＧＭ算法同Ａｐｒｉｏｒｉ算法一样，也是由用户设定最小支持　度，挖掘支持度不小于最小支持度的图，即频繁图。在满足下　２．２图的相关定义　顶点和边带有权值的图定义如下：　定义１　Ｖ（Ｇ）＝ｆｖ。，ｖ　，…　为图顶点的集合，Ｅ（Ｇ）：　ｆ　ｖｆ，＿吩　，　∈　Ｇ）｝为边的集合，　（　Ｇ））＝｛ｌｂ（ｖ　）１　Ｖ　Ｖｉ∈Ｖ（Ｇ）｝　为点的权值集，边的权值集为Ｌ（Ｅ（Ｇ））＝｛Ｉｂ（　）Ｉ　ｖｅｈＥＥ（Ｇ）｝。则　图Ｇ可以定义为Ｇ＝（　Ｇ），Ｅ（Ｇ），Ｌ（　Ｇ）），Ｌ（Ｅ（Ｇ）））　。　定义２邻接矩阵元素定义如下：　［ｎｕｍ（１ｂ）ｉｆ　，ｖ　）∈Ｅ（Ｇ）　，、　Ｊ一１０　ｉｆ　）　三ｌ（Ｇ）　这里，ｎｕｍ（１ｂ）表示边的权值，Ｇ（　）表示图Ｇ的存储结构是邻　接矩阵　图的大小即邻接矩阵的维度用ｌ　Ｇ）ｆ来表示，也就　是顶点的个数。　邻接矩阵的第ｉ行第ｉ列表示图中顶点ｖ　，但是如果顶点标　识分配不同，就是同一个图，也会有多种不同的邻接矩阵表　示，也就是图同构的问题。为了减少复杂性，顶点标识的分配　按点的权值大小的顺序进行设定。图Ｇ的邻接矩阵Ｘ满足关　系暇　ｌ　ｆ∈Ｇ（ＸＤ）＜－，６（　ｊ＋ｌ　｛＋１∈Ｇ（　）　＝１，２，・一，ｋ一１，令　接　矩阵的第　行标识和第ｆ列标识相当于图中第ｆ顶点。　定义３无向图和有向图的邻接矩阵编码分别定义如下：　ｃｏｄｅ（Ｘｋ）＝ｘ１２　１．３　２．３　１，４…Ｘｋ　２ｋｘ　（２）　．，ｌ，　同样有向图编码为，　ｃｏｄｅ（Ｘｋ）＝ｘｌ２　２．１　１．３　３，１Ｘ２３Ｘ３２…Ｘｋ　２ｋＸ　１，，，，（３）　，　定义４图Ｇ的诱导子图定义为：　Ｇ　＝　（Ｇ　），Ｅ（Ｇ　），Ｌ（Ｖ（Ｇ　）），Ｌ（Ｅ（Ｇ　）））　其中　Ｇ　）ｃ　，Ｅ（Ｇ　）ｃＥ（Ｇ）Ｖｕ，ｖ∈Ｖ（Ｇ　），　，ｖ）∈Ｅ（Ｇ　）营　（Ｕ，ｙ）∈Ｅ（Ｇ）。　２．３　ＡＧＭ算法简介　ＡＧＭ算法最早将Ａｐｒｉｏｒｉ思想用于频繁子图挖掘，该算法　能在交易数据库中挖掘出满足最小支持度的所有频繁诱导子　图。ＡＧＭ算法采用邻接矩阵作为图的存储结构，并且根据邻　接矩阵生成该图的编码。由于存在一图多矩阵的情况，将编　码最小的矩阵作为图的唯一邻接矩阵，以避免直接进行子图　同构的计算。　（１）根据Ａｐｒｉｏｒｉ思想，首先将频繁顶点作为初始项集，判　断Ｘ、　是否包含同一个ｋ一１子图ｘ…若包含，则将二者按　编码从小到大顺序将其作为第１操作因子，第２操作因子，生　成候选子图　。ｉ　＋　，这样每次通过添加一个顶点生成候选　抖１子图。　（２）由Ａｐｒｉｏｒｉ性质，若　。的后子图中有一个是非频繁的，　那么ｚ“。也一定是非频繁的，对　进行剪枝。　面３个条件时按顺序自底向上生成候选子图。　（１）两个顶点数为ｋ的图，其邻接矩阵用　和　来表　示。　和　包含相同的ｋ一１阶子矩阵时，按下述方式结合，　生成２．“　矩阵。　．　＝　＝　］　㈥　ｆＩ　　一－　＋１＝Ｊ，；＝…，０　ｚ　　＋・］　ｏ／　Ｉ　　（６）　，表示ｋ一１阶邻接矩阵，　，　（ｉ＝１，２）是（ｋ—１）×１的列向　量。Ｘ、　叫做２　的第１生成矩阵和第２生成矩阵。　（２）ｚ＿“。应当满足以下关系：　ｌｂ（ｖ　Ｉｖ　∈Ｖ（Ｇ（　）））＝ｌｂ（ｖ　Ｉｖ　∈　（Ｇ（　＋　）））　ｌｂ（ｖ　Ｉｖ『∈Ｖ（Ｇ（ｒＤ））＝ｌｂ（ｖ　Ｉｖｆ∈Ｖ（Ｇ（　＋１）））　，６（Ｖ　Ｉｖ　∈Ｖ（Ｇ（　）））　ｌｂ（ｖ　＋。Ｉｖ　＋１∈ｖ（ｃ－（ｘＤ））　似Ｖ　Ｉｖ　∈　（Ｇ（　）））＝ｌｂ（ｖ女Ｉｖ　∈Ｖ（Ｇ（Ｚｋ＋１）））　，６（Ｖ　Ｉｖ　∈Ｖ（Ｇ（　）））＝ｌｂ（ｖ　Ｉｖ　∈　（Ｇ（　＋１）））　，６（Ｖ　Ｉｖ　∈Ｖ（Ｇ（　）））　ｌｂ（ｖ　Ｉｖ　∈Ｖ（Ｇ（　）））　元素　，　以及　。　。并不由　和　所决定，因为图的状　态有很多种，无向与有向，顶点和边是否包含权值，以及孤立　点（即该点与其他顶点之间无边联系）的情况，ｚｈ。有　（Ｅ（Ｇ））Ｉ＋１　种。为方便叙述，以及减少复杂度，本文只讨论无向图的情　况，并在生成ｚ＾＋。时一律将　。　。和　设为１。有向图的情况　可以类似地考虑。　（３）图Ｇ（Ｘｋ）和Ｇ（　）的第ｋ个顶点权值等价时，Ｘ、ｌ　结合　所生成的结阵往往冗长，为了避免，仅在满足ｃｏｄｅ（第１生成矩　阵）Ｓｃｏｄｅ（第２生成矩阵）的情况下将邻接矩阵进行结合。满　足上述３个条件的邻接矩阵称作正规形。　Ｇ（　）是频繁图的必要条件是Ｇ（ｚ＿“。）的全部诱导子图都　是频繁图。由Ａｐｒｉｏｒｉ的性质，频繁项集所有非空子集也是频　繁的，因此，除去Ｇ（　。）的第ｆ顶点（１＜ｉ＜ｋ一１）的诱导子图的　邻接矩阵如果全部表示的都是频繁图的话，那么Ｇ（ｚ｜“。）就称　作候选频繁图。改进算法主要是探索生成正规形的邻接矩　阵，因此，有必要对非正规形的邻接矩阵进行正规化。以无向　图为例，给定图和对应的邻接矩阵，如图１所示。　该图有４个顶点，先将这４个点排成４个矩阵，４个点本身　必须是正规形矩阵。选定其中１个矩阵如图２所示。图２中选　取的是顶点ｖ。，将该点与其他３个点的矩阵结合，并求出相应　矩阵的编码。接下来从这３个２维矩阵开始重复前面的方式，　继续对邻接矩阵进行结合。　陈立宁，罗　可：Ａｐｒｉｏｒｉ算法用于频繁子图挖掘的改进方法　　．ｖ】厂＿　——　１　ｒＯ　０　１０　Ｏ、　１　ｌ　０　１　０　１　１　　　ｌ　ｌＬ０　ｌ　１　０　非正规形邻接矩阵ｘ　图１　无向图以及对应的邻接矩阵图　０　０　０　０　０　ｌ　０　１、　Ｏ０１　１　１　０　１　ｆ　Ｖｌ　Ｖ２　Ｏ　Ｏ　１　０　Ｏ　Ｏ　ｌ１１　１　ｌ　邻接矩阵　Ｏ１１　图２邻接矩阵的正规化图　在求得候选子图后，再通过剪枝，扫描数据库计算支持度　以求出频繁图。由于存在子图同构的问题，同一个图也有可　能多个邻接矩阵表示，为了避免同构，选取编码最小的矩阵作　为图的唯一标识。　３．２正准型　图的邻接矩阵集合，记为Ｍａｔｒ＆Ｓｅｔ（Ｇ）中拥有最小编码的　邻接矩阵称为正准型。记作，　＝ｍｉｎ　ｃｏｄｅ（Ｘ），Ｘ∈ＭａｔｒｉｘＳｅｔ（Ｇ）　（７）　Ｘ和　所表示的图等价时，从Ｘ到　的变换矩阵　构成　如下：　：』ｌ１当　的第ｆ０其他　顶点等于　的射顶点　（一　８）　则　可以用　和　来表示，即　＝　。　任意矩阵都有其正准型的变换矩阵。除去Ｇ（Ｘｋ）的第ｍ　顶点（１＜ｍ＜ｋ），对邻接矩阵进行正规化，用７　表示求正规化　的变换矩阵。已正规化了的邻接矩阵求其正准型的变换矩阵　用　表示，那么　的变换矩阵　，　可以通过　卫　，　。　求得：　１　，，０　ｆ　七一１，０≤　七一１　＝｛ｌ（ｉ＝ｋ，Ｊ＝ｋ　（９）　１０，其他　ｆ　ｍ，　＜　，ｊ＊ｋ　ｔ　ｍ＿１＿，，ｆ＞　，－，≠ｋ　（１０）　１．ｉ＝　．Ｊ＝ｋ　０，其他　这里　，ｓ　ｍ，ｔ　，ｆ　，分别是　，　。，　，　的元素。　对于　，其正准型的编码为：　＝　ａｒ，ｉｎ　ｃｏｄｅ（（ｒ２ｓＴ）　（　））　（１１）　则　的正准型变换矩阵就是使得　值最小的　。不过，　在计算过程中若已知正准型的变换矩阵Ｓ　，则　的正准型可　由下式得出，而不必计算所有的七值进行比较。　Ｓ　（　）　（　：）　（１２）　４　算法的改进　４．１　顶点标识以及边标识的顺序关系　由上面所叙述的思想，求矩阵的正规形必须考虑到邻接矩阵顶点与顶点之间，边与边之间标识的顺序关系，凶为这直　接关系到候选子图生成的冗余以及同构问题。随着顶点以及　边标识排列不同，会导致同一个图所对应的邻接矩阵也不同，　进而正规形也不同。为了减少复杂性，对于非频繁图的图中　顶点标识进行统一排序。在交易中按所含各个顶点权值数目　的平均值升序排列。用ａｖｇ（１ｂ　）表示ｌｂ　在交易中数目的平均值　ｉｆ　ａｖｇ（１ｂ　）＜ａｖｇ（／ｂ，）ｔｈｅｎ　ｌｂ　＜ｌｂ，　其中ｉ，Ｊ＝１，２，…，ｌ　（　（Ｇ））ｌ，ｌｂ　＜ｌｂ　。　至于边的顺序关系，同样按各个边权值在交易中数目平　均值进行升序排列。不过，若是稀疏矩阵的情况，用０表示顶　点问没有边联系时的权值。函数　寸邻接矩阵的元素重新进　行调整分配，并返回大于０的整数值。ａｖｇ（Ｏ）是表示交易输入　的邻接矩阵中所含０的个数的平均值，规定：　ｉｆ　ａｖｇ（／ｂｆ）＜ａｖｇ（／ｂ，）ｔｈｅｎ　ｆ（ｎｕｍ（１ｂ　））＜ｆ（ｎｕｍ（１ｂ　））　ｉｆ　ａｖｇ（１ｂｆ）＜ａｖｇ（Ｏ）ｔｈｅｎ　ｆ（ｎｕｍ（１ｂ　））＜／（０）　ｉｆ　ａｖｇ（Ｏ）＜ａｖｇ（１ｂ　）ｔｈｅｎ　ｆ（０）＜ｆ（ｎｕｍ（１ｂ　））　于是邻接矩阵的编码可以写成：　￣ｏｄｅ（Ｘ，）＝／（　１．２）＿厂　ｌ，３）／（　２．３）　（　１　４）－‘＿厂（　ｌ　，）　【１３）　４．２候选子图生成的判定条件　如３．１节所示，导入正规形概念，生成候选子图，扫描支持　度求取频繁图，需要用到定理：正准型的第１生成矩阵也是正　准型。　证明某个正准型　，其第１生成矩阵，第２生成矩阵分别　为Ｘ　假定　一。非正准型，则存在邻接矩阵Ｘ　结构同　Ｇ（Ｘｋ一。）等价，编码小于ｃｏｄｅ（Ｘ￣一．）则有邻接矩阵ｙ　一　满足同　Ｘ　结合的条件，且结构同Ｇ（Ｘｋ一。）等价，但Ｘ　与　一。结合　生成的邻接矩阵　的编码比　要小，这与Ｘ是正准型相矛　盾，原命题得证。　要求取频繁图，必须生成所有的正准型，因此必须求出正　规形。上述定理亦可以理解为正准型的所有子矩阵亦是正准　型。根据上述定理给出候选子图生成的一个很重要的判定条　件：当且仅当Ｘ是正准型时，才能与　结合生成候选子图　。　矩阵的正准化对正规化算法而言十分必要，因此矩阵的　正规化除满足３．１节中叙述的３个条件外，还应考虑到上述判　定条件。针对以上论述，给出矩阵正规化的算法：　１．ｉ＝１：　２．ｗｈｉｌｅ（ｉ≠　）｛　３．　ｉｆ（ｘ￣是正规形）｛　４　＝　ＴＸ　＝　（　）　Ｘｋｆ（Ｓ　）；　５．　ｉ＋＋；）　６．　ｅｌｓｅ｛　７．　的第ｉ一１行第ｉ一１列与第珩第　列交换　８．　ｉｆ（　是正规形）｛　９．　＝　Ｔ　Ｓ　＝ｌ厂（　）　Ｘｋｆ（Ｓ　１ｏ．　ｉ＋＋：｝　１１　ｅｌｓｅ　１２．　ｉ一一；＞）　１３．ｒｅｔｕｒｎ　ｘｋ。　ｘ表示　个顶点的邻接矩阵，ｘ是从第１行第１列开始到　第纤亍第　列的子矩阵（１　ｆ＜．｝ｉ），Ｓｉ是ｘ的正准型变换矩阵。函　数／和　的关系是：　１１６　２０１１，４７（１０）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ硎　４　『ｆｃ口ｆｆＤ　计算机工程与应用　ＡＧＭ＋顶点标识排序　属茁琳４｛　０≤星莒琳　艇琳制　１　０　０　Ｏ　Ｏ　０　０　０　Ｏ　Ｏ　星曾琳　０《苗罾琳　嫩蜮　Ｏ　９　８　７　６　５　４　３　２１　Ｏ　１０Ｏ　８０　６０　４０　最小支持度／（％）　图３顶点标识排序后的改进算法同原算法　计算时问比例图　１．Ｏ　ＡＧＭ堠选子图生成条件　０　９　０．８　０．７　Ｏ．６　０．５　Ｏ．４　０．３　０．２　０．１　亘莒敞　苫０ｖ／厦窖琳　媳球斟　垦曾琳　至０ｖ／厘鲁　媳妹裁　０　９　８　７　６　５　４（　］　３　２１　Ｏ　＝　（　：，Ｌ是”阶单位矩阵　（１４）　改进算法流程如下：　输入：图集Ｇ：｛Ｇ　，Ｇ２，…，Ｇ，…Ｇ｝，其中，Ｇ　（Ｖ（Ｇｊ），Ｅ（Ｇ），　三（　Ｇ）），三（　（Ｇ）））　输出：频繁图集Ｇ，　１．对每个图Ｇ将顶点和边分别按其权值从小到大顺序分配标识，　并转换成唯一确定的邻接矩阵。　２对每个图Ｇ所对应的邻接矩阵按照上述算法进行正规化，并求　其相应编码，按编码从小到大的顺序对各个图排序。　３．生成候选子图集。按编码大小的升序序列将每个ｋ阶图的邻接　矩阵分别与其身后的矩阵结合。对于两个ｋ阶的邻接矩阵，判断二者　的编码，若其编码的前ｋ一２项相同，说明两矩阵包含同一个．１｝一１子　图，可以生成候选“ｌ子图，若不相等，则放弃结合，继续判断其后面　的矩阵。　４对斛１子图集进行剪枝。　５．扫描数据库，计算抖１候选子图的支持度，并根据最小支持度进　行判断，生成斛１频繁图。　６．转第２步，重复上述步骤，直到不再产生新的候选子图为止，算　法结束。　５实验结果及分析　实验针对网络结构中数据流量的变化，对频繁网络环节　点信息数据进行采集，挖掘频繁网络结构模式。算法实验环　境为ＣＰＵ：Ｉｎｔｅｌ　Ｃｏｒｅ　Ｄｕｏ　Ｔ２０５０＠８０１　ＭＨｚ／１．６０　ＧＨｚ，内存　信息：ＰＣ２－５３００　ＤＤＲ２　６６６　ＭＨｚ双通道１　ＧＢ。实验数据：数　字电视宽带网络流量统计图。　结合４．１和４．２节的内容，在原ＡＧＭ算法的候选子图的生　成这一环节，考虑到图集中顶点以及边权值标识顺序关系，对　顶点和边的标识加以排序，以唯一确定图的对应邻接矩阵，避　免了将图转换成矩阵表示时出现一图对应多个矩阵的繁杂情　况。同时算法也考虑到候选子图的生成将不可避免地产生冗　余子图，这会增加计算机扫描冗余子图而造成无谓的时问开　ＡＧＭ＋边标识排序　１００　８０　６０　４０　２０　最小支持度／（％）　图４边标识排序后的改进算法同原算法计　算时问比例图　ＡＧＭ＋　１．０　０．９　０．８　０　７　０．６　０．５　０．４　０＿３　０．２　０．１　销。因此，在候选子图生成之前，对图的邻接矩阵进行正规化　并求出相应的编码得到图的正准型矩阵，一定程度上减少了　冗余子图的生成数量，同时也避免了对子图同构的直接计　算。实验将原ＡＧＭ算法结合本文所提出的改进方法，针对不　同最小支持度情况下，对结果加以收集并绘制成图表。实验　原始数据由湖南有线邵阳网络有限公司提供。　图３中，“ＡＧＭ＋顶点标识排序”表示在原ＡＧＭ算法基础　上对图的顶点标识按权值大小进行排序；图４中，“ＡＧＭ＋￣标　识排序”表示在原ＡＧＭ算法基础上对图的边标识按权值大小　进行排序；图５中，“ＡＧＭ＋候选子图生成条件”表示在原ＡＧＭ　算法基础　加入４．２节所叙述的判定条件；图６中，“ＡＧＭ＋”表　示在ＡＧＭ算法基础上结合前面３项改进措施后的改进算法。　图３～图６分别表示，上述４种改进算法在不同最小支持度下同　原ＡＧＭ算法的计算时间的比值。　由图４可以看出“ＡＧＭ＋边标识排序”算法同原算法在计　算时间上几乎没有区别，比值接近于１，效率上没有什么改　进。这是因为子图同构问题主要同构成图的顶点间的标识分　配关系比较大，与边的关系比较小，无向图更明显。顶点标识　分配不同直接影响到图的邻接矩阵的结构，这通过图３的实验　结果可以得到验证。“ＡＧＭ＋顶点标识排序”算法计算时间明显　少于“ＡＧＭ＋边标识排序”，二者分别同原ＡＧＭ算法计算时间　的比值，前者比后者大约削减了３５％￣６０％。　４．２节中所阐述的判定条件，所起到的改进作用主要在于　矩阵与矩阵结合生成候选子图时候减少冗余子图的生成。因　为正准型是编码最小的邻接矩阵，将其作为图的邻接矩阵避　免了对子图同构的直接计算，同时为后一步的候选子图剪枝　也减轻了计算量，缩短了判断候选子图是否频繁所花费的时　间。但是ＡＧＭ算法的弊端主要还是来自于初始状态下图在　转换成邻接矩阵时由于图本身顶点以及边标识分配的不确定　性而造成一图多矩阵情况，从而在一开始就产生多个冗余矩　阵为后面的同阶子图的判断以及候选子图的生成增加了计算　时问的开销。因此图５的改进算法的效果不如图３。　陈立宁，罗　可：Ａｐｒｉｏｒｉ算法用于频繁子图挖掘的改进方法　图６所示的“ＡＧＭ＋”算法综合了４．１节与４．２节所叙述的　时间上比原算法具有优势。　２０１１．４７（１０）　１１７　内容，由实验数据表明，“ＡＧＭ＋”算法在时间花费上大约削减　了３５％－６５％，是上述所有改进算法中效果最优的一种。　本文虽然针对ＡＧＭ算法进行了改进，但仍存在尚待解决　的问题：（１）如何进一步减少冗余子图的生成，降低算法的时　间开销；（２）改进的算法在每次生成高频频繁图集时，仍然需　要扫描数据库，这同原算法无异。如何采用更好的数据结构　或方法来减少数据库的扫描次数，将成为下一步的研究重点。　实验结果显示，改进算法随着用户所给定的最小支持度　的递减，计算时间亦呈递减趋势。说明在支持度较小的情况　下，改进算法在时间效率方面比原算法更具优势。　６结论　本文提出了一种基于ＡＧＭ算法的改进方法。传统的　参考文献：　［１］李先通，李建中，高宏．一种高效频繁子图挖掘算法［Ｊ］ｌ软件学报，　ＡＧＭ算法虽然采用了邻接矩阵作为图的存储结构，但也只是　２００７，ｌ８（１０）：２４６９—２４７２．　单纯对输入图集进行筛选判断，生成候选子图，并没有很好地　［２］王映龙，杨瑁，周法国，等．加权最大频繁子图挖掘算法的研究［Ｊ】．　解决因图的邻接矩阵表示的不确定性所带来的冗余子图的生　计算机工程与应用，２００９，４５（２０）：３１－３４．　成，以及子图同构的问题。面临庞大的图数据集，在候选子图　［３］吴甲，陈峻．一种快速的频繁子图挖掘算法［Ｊ］ｌ计算机应用，２００８，　生成时冗余子图的数量也呈指数级增长。原算法效率低主要　２８（１０）：２５３３—２５３４．　体现在候选子图生成时要判断是否存在等价ｋ一１子图，初始　［４］谢均，尚学群，王淼，等．解决数据样本不平衡性的频繁子图挖掘算　情况下若图存在多个冗余矩阵的话，就增加了判断所需要的　法ｆＪ】计算机工程与应用，２００８，４４（３６）：１４６—１４７．　计算量。同时，这也造成了候选子图生成时大量冗余子图的　［５］Ｉｎｏｋｕｃｈｉ　Ａ，Ｗａｓｈｉｏ　Ｔ，Ｍｏｔｏｄａ　Ｈ．Ｃｏｍｐｌｅｔｅ　ｍｉｎｉｎｇ　ｏｆ　ｆｒｅｑｕｅｎｔ　产生，进而在剪枝步判断每个候选子图是否频繁也大大增加　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｇｒａｐｈｓ：Ｍｉｎｉｎｇ　ｇｒａｐｈ　ｄａｔａ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，　了计算量，时间的开销也增大，从而影响了算法效率。本文的　．２００３，５０（３）：３２４—３４０．　改进算法针对子图同构，以及冗佘子图生成的问题，对初始图　［６］王艳辉，吴斌，王柏．频繁子图挖掘算法综述［Ｊ　Ｊ＿计算机科学，２００５，　顶点、边标识进行排序以唯一确定图的邻接矩阵，同时对矩阵　３２（１０）：１９３—１９４．　进行正规化，并求其正准型，以此作为候选子图生成的前提，　［７】白似雪，朱涛，梅君．基于图的Ａｐｒｉｏｒｉ改进算法［Ｊ］＿南昌大学学报，　这在一定程度上减少了冗余子图的生成。改进算法还有优于　２００９，３１（１）：３６—３７．　原算法的一点的是：在判断两ｋ阶矩阵是否存在相同ｋ一１阶子　［８］黄建明，赵文静，王星星＿基于十字链表的Ａｐｒｉｏｒｉ改进算法［Ｊ】．计算　矩阵时，由于已经对矩阵正规化，所以无需考虑矩阵本身结构　机工程，２００９，３５（２）：３７—３８．　只需比较两矩阵的编码的前ｋ一２项，如相同即可认为两矩阵　［９］严蔚敏，吴伟民．数据结构［Ｍ］．北京：清华大学出版社，１９９６，７：　可以结合生成　ｌ候选子图。实验结果表明，改进算法在计算　１６】一】６６　（上接１０９页）　增长的不同速度。结果表明，该方法仅以很少的性能损失，大　间。对于一个校验节点，，译码器须存储集合　Ｉ１／ｅ　Ｃｉ｝中的最　幅减少译码器存储空间，降低了系统复杂度。　小值、次小值，最小值的相对位置；对于行重为６的ＬＤＰＣ码，　需３　ｂｉｔ描述该位置　；集合　１ｉ∈Ｃｉ｝中元素的符号位，汁６　ｂｉｔ。　参考文献：　由表３可知，采用Ｑ（８，６）的算法比采用Ｑ（６，４）的改进算法，　［１］Ｇａｌｌａｇｅｒ　Ｒ　Ｇ．Ｌｏｗ—ｄｅｎｓｉｔｙ　ｐａｒｉｙｔ—ｃｈｅｃｋ　ｃｏｄｅｓ［Ｄ］．Ｂｏｓｔｏｎ：ＭＩＴ，　要多花费２５％的存储空间。由第３章可知，ＬＤＰＣ译码器的主　ｌ９６３．　要模块都能受益于短位宽的信息量化，因此改进算法和动态　【２］Ａｒｂｏｒ　Ａ．Ａ　ｃｏｍｐａｒｉｓｏｎ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｓｕｍ－ｐｒｏｄｕｃｔ　ａｎｄ　ｔｈｅ　ｒａｉｎ—ｓｕｍ　量化方式能以很小的译码性能损失来有效地降低ＬＤＰＣ译码　ｉｔｅｒａｔｉｖｅ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｄｅｎｓｉｔｙ　ｅｖｏｌｕｔｉｏｎ［Ｃ］／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｇｌｏｂａｌ　Ｔｅｌｅｃｏｍ　Ｃｏｎｆｅｒｅｎｃｅ，２００１，２：１０２１—１０２５．　器的硬件复杂度。　［３］Ｍａｎｓｏｕｒ　Ｍ　Ｍ．Ａ　ｔｕｒｂｏ—ｄｅｃｏｄｉｎｇ　ｍｅｓｓａｇｅ—ｐａｓｓｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　表３　Ｑ（６，４）改进算法所需存储空间与　ｓｐａｒｓｅ　ｐａｒｉｔｙ—ｃｈｅｃｋ　ｍａｔｒｉｘ　ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｓｉｇｎａｌ　９（８，６）未改进算法比较　Ｐｒｏｃｅｓｓｉｎｇ，２００６，５４（１　１）：４３７６—４３９２．　算法以及量化　“存储比特数　存储比特数总计／ｂｉｔ比例，（％）　［４］Ｃｈｕｎｇ　Ｓ　Ｙ，Ｒｉｃｈａｒｄｓｏｎ　Ｔ　Ｊ．Ａｎａｌｙｓｉｓ　ｏｆ　ｓｕｌｎ　ｐｒｏｄｕｃｔ　ｄｅｃｏｄｉｎｇ　ＴＤＭＰ　ＮＭＳ　Ｑ（８，６）　（５＋５＋３＋６）×１　１５２　８ｘ２　３０４　４０　３２０　１００　Ｏｆ　ｌｏｗ－－ｄｅｎｓｉｔｙ　ｐａｒｉｔｙ・－ｃｈｅｃｋ　ｃｏｄｅｓ　ｕｓｉｎｇ　ａ　Ｇａｕｓｓｉａｎ　ａｐｐｒｏｘｉ－－　改进ＴＤＭＰ　ＮＭＳ　Ｑ（６，４）（３＋３＋３＋６）×１　１５２　６ｘ２　３０４　３ｌ　１０４　７５　ｍａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，２００１，４７（２）：６５７—６７０．　［５］Ｔａｎｎｅｒ　Ｒ　Ｍ．Ａ　ｒｅｃｕｒｓｉｖｅ　ａｐｐｒｏａｃｈ　ｔｏ　ｌｏｗ　ｃｏｍｐｌｅｘｉｙｔ　ｃｏｄｅｓ［Ｊ］．　５结语　ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，１９８１，２７（５）：５３３—５４７　对于采用ＴＤＭＰ．ＮＭＳ算法的ＬＤＰＣ码译码器，本文提出　［６］Ｂａｏ　Ｄ，Ｘｉａｎｇ　Ｂ，Ｚｅｎｇ　Ｘ　Ｙ．Ｐｒｏｇｒａｍｍａｂｌｅ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　了能有效降低其硬件复杂度的方法。硬件复杂度的降低主要　ｌｆｅｘｉ－・ｍｏｄｅ　Ｑｃ・－ＬＤＰＣ　ｄｅｃｏｄｅｒ　ｓｕｐｐｏｒｔｉｎｇ　ｗｉｒｅｌｅｓｓ　ＬＡＮ／ＭＡＮ　ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　ｂｅｙｏｎｄ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｃｉｒｃｕｉｔｓ　ａｎｄ　Ｓｙｓｔｅｍｓ—Ｉ：　通过使用短位宽的信息量化方式。为了克服短位宽引起的信　Ｒｅｇｕｌａｒ　Ｐａｐｅｒｓ，２０１０，５７（１）：１２５—１３８　息饱和噪声，改进了现有算法和固定的量化方式，在译码过程　［７］Ｈａ　Ｊ，Ｋｉｍ　Ｊ．Ｒａｔｅ—ｃｏｍｐａｔｉｂｌｅ　ｐｕｎｃｔｕｒｉｎｇ　ｏｆ　ｌｏｗ—ｄｅｎｓｉｔｙ　ｐａｒｉｙｔ。　中通过不断降低信息的量化精度来增大信息的量化范围。这　ｃｈｅｃｋ　ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，２００４，５０（１　１）：　种动态量化方式基于一种自适应的方法，来满足信息绝对值　２８２４—２８３６．