[發明專利]基于冗余距離消除和極端點優化的并行k-means聚類方法

在審

• 申請號: 201610044881.6
• 申請日: 2016-01-22
• 公開（公告）號: CN105740604A
• 公開（公告）日: 2016-07-06
• 發明（設計）人: 李肯立;肖錦波;唐卓;劉錫洋;魯彬;陳俊杰
• 申請（專利權）人: 湖南大學
• 主分類號: G06F19/00
• 分類號: G06F19/00;G06K9/62
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀

技術領域

本發明屬于計算機領域，尤其涉及一種基于冗余距離消除和極端點優化的并行k-means聚類方法。

背景技術

名詞解釋：

K-means聚類方法指通過不斷地取離種子點(中心點)最近均值的進行聚類的算法。

隨著互聯網技術的高速發展，當前云計算技術已經成為一種商業模式，它已經滲透到各個領域。在醫學領域，我們使用k-means聚類方法和云計算技術相結合，從海量醫療數據中挖掘出疾病與藥品的信息。

K-means聚類方法是當前使用最多、效率最高的聚類方法之一。

MapReduce最初是由Google公司開發的，它是一種并行計算框架，非常適合海量數據集的并行計算。MapReduce內部的工作原理比較復雜，但是編碼非常簡單，它提供了一種簡易的接口，可以讓普通的開發人員根據自己的需求編寫自己的MapReduce程序。普通開發人員像編寫串行程序一樣只需要實現啟動任務的入口函數(通常是main函數)、map函數和reduce函數，更復雜一點的可以實現setUp函數和cleanUp函數即可。這樣MapReduce并行計算框架根據數據集的大小啟動相應的Map或Reduce任務同時并行的執行開發人員編寫的MapReduce程序。開發人員無須關心MapReduce內部復雜的工作原理，如數據集的分塊、數據塊的分配和排序以及多個Map或Reduce任務之間的通信。

Hadoop是由apache基金會開發的一個包含分布式計算和存儲的開源項目，它實現了谷歌的MapReduce并行計算模型。當前的Hadoop的版本已經更新到2.6，它主要由以下幾個部分組成:client(客戶端)、ResourceManager(資源管理器)、NodeManager(節點管理器)、ApplicationMaster(作業管理器)、任務。

(1)client(客戶端)

在Hadoop內部，用“作業”表示一個分布式應用程序，每個作業被切分成多個split(分塊)，Client負責將用戶編寫的作業提交到ResourceManager端。此外，Client提供一些接口可以查看作業的運行狀態。

(2)ResourceManager(資源管理器)

ResourceManager是基于應用程序對資源的需求進行調度的,主要是用于管理向應用程序分配計算資源。在Hadoop2.0以上的版本中才會有，它接收client端提交過來的作業，并為每個作業分配相應的資源，這些資源包括：CPU、內存、磁盤、網絡等。

(3)NodeManager(節點管理器)

NodeManager是每一臺機器框架的代理，主要是執行ResourceManager分配的任務，監控應用程序的資源使用情況，并且向ResourceManager匯報。

(4)ApplicationMaster(作業管理器)

每個應用都有一個ApplicationMaster，ApplicationMaster的主要職責是向ResourceManager索要適當的資源容器，運行任務，跟蹤應用程序的狀態和監控它們的進程，處理任務的失敗原因。

(5)任務

任務分為Map(映射)任務和Reduce(規約)任務兩種，均由NodeManager啟動。在Hadoop內部，數據處理的最小單位是split(分塊)，每個split會交由一個Map任務處理，Map任務和Map任務之間是并行執行的。Map任務先將對應的split迭代解析成一個個(key，value)鍵值對，并依次調用用戶自定義的map函數將其映射成一組新的(key，value)鍵值對，最終將中間數據即新的(key，value)鍵值對存放到本地磁盤上，其中中間數據被分成若干個partition(分區)，每個partition(分區)將被一個Reduce任務處理。Reduce任務用來把所有Map任務產生的partition按照key值，對對應的value值進行處理，產生多個共享相同key值的鍵組，最終完成整個作業。