平行化資訊理論共分群演算法

摘要

資料分群(Data Clustering)在各種領域被廣泛的應用，如:資料探勘(Data Mining)、文件檢索(Document Retrieval)、影像分割(Image Segmentation)、樣式分類(Pattern Classification)等等。傳統資料分群演算法通常只能用在小規模資料分析上。如今，做資料分群時，常常必須面臨好幾Gigabytes的資料量，一般電腦已經無法再處理龐大的資料。為了解決這些問題，許多研究員嘗試去設計出許多有效率的平行化分群演算法(Parallel Clustering Algorithm) 來做大型資料分群。 本論文中我們聚焦在Information-Theoretic Co-clustering (ITCC)演算法，ITCC是一種共分群演算法，它可以同時對行與列去作分群，並且其objective function是以行向量與列向量之mutual information作為基礎。ITCC被廣泛地用在許多領域，如: Text mining、Social recommendation system、生物資訊領域等等。 在本篇論文中，我們提出Parallel Information-Theoretic Co-Clustering (PITCC)演算法，由於要處理的資料量相當龐大，我們使用一種近幾年來新興且熱門的平行化運算平台Hadoop，以Map-Reduce的方式來進行運算。Map-Reduce廣泛的被學術界(Academia)與業界(Industry)所接受，是一種簡單而且非常強大的programming方法。Hadoop除了具有高擴充性，還具有易於使用等優點。並且我們使用了CAMRa2011比賽所release的資料集。最後我們將在實驗部分使用了三種評估效能的方法來衡量我們的實驗，並且證明我們所提出的演算法，是一個相當有效率且能處理龐大的資料集的方法。