運用資料探勘技術來發掘通話路徑樣式，進而預測行動電話使用者的週期性移動行為傾向，已經成為行動通訊系統業者提升競爭力的一大利器。本研究採用新穎的方式來發掘週期性的行動電話通話路徑樣式，以提升資料探勘演算法的執行效率。首先，設計一個圓形資料結構，將任意選取之時間區間內的通話路徑資訊儲存到此圖形結構中。其次，設計一個圖形穿梭演算法，從之前建立的圖形結構中找出通話路徑樣式。最後，以向量達算的方式檢驗通話路徑樣式，以決定具備週期性的通話路徑。實驗結果證實，在發掘週期性行動電話通話路徑樣式的問題上，本研究所設計之探勘演算法較傳統探勘演算法展現出更優異的執行效率。 The efficiency of mining approaches is always the focus of various data mining research. In this study, a novel data mining method introducing sampling techniques is devised to fmd the periodic moving paths more efficiently. By sampling techniques, only a small portion of data is scanned and analyzed, so as to improve the efficiency of the mining processes.
First, a dedicated graph data structure is designed to store the information of moving paths of mobile phone users. The moving paths of mobile phone users are gathered for each time interval of periods. All information for mining moving patterns can be captured and retained in the proposed graph, and then the mining tasks can proceed in the graph.
Second, a sampling method for discovering the moving patterns in one of the time intervals of a period is devised. The moving paths are retrieved and decomposed, and the relative information of moving paths is stored in the graph. The graph traversal algorithm is employed to fmd the moving patterns. The set of patterns obtained in this stage is a closure set of patterns in the desired period.
Third, the moving patterns acquired in the second stage are further examined to decide the final periodic moving patterns in some predetermined period. The vector operations are used to check whether the whole or the partial discovered patterns are periodic. While all moving patterns are examined, the periodic moving patterns are gained.
The performance evaluation for mining periodic moving patterns tells that the sampling method outperforms the na�ve mining method more significantly. The experimental results reveal that we can easily apply the sampling approach to obtain the periodic calling path patterns, which are very useful for predicting the user moving trends. As we
can forecast the moving patterns more efficiently, the telecommunications system resources can be deployed more effectively.