CAJ | 학술논문

频繁子图挖掘是数据挖掘领域的一个重要问题，并且有着广泛的应用。在Hadoop平台上实现了一种基于MapReduce的高效频繁子图挖掘算法Cloud-GFSG（cloud-global frequent subgraph）。该算法基于Apriori思想，在扩展边生成新的子图时，使用已经挖掘出的k-1阶的频繁子图生成k阶的频繁子图。同时，检查是否存在待扩展生成的子图，设定生成的频繁子图表示规则，保证了频繁子图信息的唯一性。较同类算法相比，该算法在挖掘频繁子图时更具通用性，并且在扩展边时避免产生大量的复制图，从而使得算法的正确性得以保证，且运行效率显著提高。
빈번자도알굴시수거알굴영역적일개중요문제，병차유착엄범적응용。재Hadoop평태상실현료일충기우MapReduce적고효빈번자도알굴산법Cloud-GFSG（cloud-global frequent subgraph）。해산법기우Apriori사상，재확전변생성신적자도시，사용이경알굴출적k-1계적빈번자도생성k계적빈번자도。동시，검사시부존재대확전생성적자도，설정생성적빈번자도표시규칙，보증료빈번자도신식적유일성。교동류산법상비，해산법재알굴빈번자도시경구통용성，병차재확전변시피면산생대량적복제도，종이사득산법적정학성득이보증，차운행효솔현저제고。
Frequent subgraph mining is an important problem in data mining domain and has been used widely. This paper proposes an efficient algorithm Cloud-GFSG (cloud-global frequent subgraph), by using MapReduce on Hadoop platform for mining frequent subgraphs. The algorithm is based on the principle of Apriori. It uses the discovered frequent subgraphs whose support is k-1 to generate the candidate frequent subgraphs whose support is k when it gener-ates new subgraphs by extending edge. Meanwhile, it checks whether there exists any subgraph which would be gener-ated and sets the frequent subgraph generation rules to ensure the uniqueness of the frequent subgraphs. Compared with the state-of-the-art algorithms, the proposed algorithm has more general function and can avoid generating replicate graphs while extending a new edge. Therefore, its correctness can be ensured and the efficiency had been improved significantly.