This paper proposes efficient data mining algorithms that can find time-constrained frequent communication patterns in communication log data. Communication log data are information about communication events such as mobile phone call, e-mail, VoIP call, SMS message and web site access of network users. These data can be gathered through Lawful Interception system for the purpose of criminal investigation and so on. In this paper, communication log data are modeled by multi-digraph with timed-edges that is defined as Communication Log Graph (CLG), and data mining algorithms that can find frequent communication patterns in Communication Log Graph are proposed. According to the type of communication pattern, two data mining problems are defined. The one is Sequence Pattern Mining(SPM) problem, and the other is Connection Pattern Mining(CPM) problem. To solve the Sequence Pattern Mining problem, $Na\ddot{i}ve$ SPM algorithm and Pruning-Merging SPM algorithm are proposed. And, to solve the Connection Pattern Mining problem, $Na\ddot{i}ve$ CPM algorithm and Pruning-Merging CPM algorithm are proposed. $Na\ddot{i}ve$ SPM/CPM algorithms use brute-force search technique. On the other hand, using the method of pruning infrequent patterns in advance and efficient pattern merging technique, Pruning-Merging SPM/CPM algorithms can find frequent patterns efficiently. Experiments show that Pruning-Merging SPM/CPM algorithm outperforms $Na\ddot{i}ve$ SPM/CPM algorithm.
본 논문은 전자 감시 시스템에서 수집된 통신 로그 데이터에서 빈번하게 발생하는 사용자 간의 통신 패턴을 효율적으로 찾을 수 있는 데이터 마이닝 알고리즘을 제안한다. 전자 감시 시스템이란 사법기관이 범죄 수사 등의 목적으로 통신 시스템을 감청하기 위해 사용되는 시스템이다. 사법기관은 감시 대상자들을 포함한 통신 네트워크 사용자들의 휴대 전화 통화, 이메일 전송, VoIP 통화, SMS 메시지 전송, 웹 사이트 접속 등에 관한 통신 기록과 통신 내용 정보를 전자 감시 시스템으로부터 수집할 수 있다. 본 논문은 전자 감시 시스템을 통해 수집된 감청 데이터를 멀티 방향 그래프 형태로 표현한 통신 로그 그래프를 정의하고, 통신 로그 그래프에서 감시 기간에 걸쳐 빈번하게 발생하는 통신 패턴을 효율적으로 찾는 데이터 마이닝 알고리즘을 제안한다. 통신 패턴의 종류에 따라 두 가지 형태의 빈번히 발생하는 패턴 마이닝 문제를 정의한다. 하나는 순서열 패턴 마이닝(Sequence Pattern Mining, SPM) 문제이고 다른 하나는 연결 패턴 마이닝(Connection Pattern Mining, CPM) 문제이다. 순서열 패턴 마이닝 문제를 해결하기 위해 $Na\ddot{i}ve$ SPM 알고리즘과 Pruning-Merging SPM 알고리즘을 제안하고, 연결 패턴 마이닝 문제를 해결하기 위해 $Na\ddot{i}ve$ CPM 알고리즘과 Pruning-Merging CPM 알고리즘을 제안한다. $Na\ddot{i}ve$ SPM/CPM 알고리즘은 단순한 방식의 탐색 기법을 사용한다. 반면에, Pruning-Mergin SPM/CPM 알고리즘은 빈번하게 발생하지 않는 패턴들을 미리 잘라내는 기법과 효율적으로 패턴들을 병합하는 기법을 이용하여 통신 로그 그래프에서 빈번하게 발생하는 패턴들을 효율적으로 찾을 수 있다. 실험을 통해 Pruning-Merging SPM/CPM 알고리즘이 $Na\ddot{i}ve$ SPM/CPM 알고리즘 보다 현저하게 좋은 성능을 내는 것을 확인하였다.
