K-means 的應用混合數據算法

張宇亭

（南京理工大學，南京 210000）

1 介紹

每個組織在某個時候都會經歷一場數據驅動的革命。企業采用大數據工具，從社交媒體活動、網絡瀏覽、手機使用、視頻、音頻、圖像、短信，以及移動網絡的、物聯網中獲取新的數據，這些數據中有大量的細粒度的數據，需要另外進行區分和保存。對大數據的分析有望產生深刻的見解和預測，從而徹底改變管理層的決策。大數據提供了一種方式，將世界上許多從未被量化的方面呈現了出來，這個過程也被稱為“數據化”。

在Hadoop 平臺中，依據HDFS 文件系統，可以對大量的進程進行處理，主要依據的是MapReduce 的計算框架。此外，還有用于分析各種業務用途的信息的其他功能和工具（例如機器學習算法）。能夠結合大數據工具與不同的數據分析工具，如Apache Hive 和Apache Pig!，以及為處理數據而設計的各種其他大數據工具，如ETL。Apache 的Hadoop 是一個平臺，通過HDFS 存儲、管理、讀、寫和操作大量數據/文件的能力，HDFS 是一個基于谷歌文件系統（GFS）的系統，可以分析不同目的的信息。雖然這些方法提高了處理大量數據的可能性，但它們并沒有提供用于分析和決策有效數據的結構算法。例如IBM 的沃森可能在自然語言處理方面處于前沿，但就系統通過互聯網吸收和解釋大數據的相關數據，它還有很長的路要走。這些觀察結果反映出，在一個新興的大數據生態系統中，需要開發新的方法來結構化和分類大量數據。

依據K-means 算法的特征，在處理非數值數據的時候，依據經驗，可以有如下的解決方案。首先創建一個過程，“扁平化”所有數據，從分類和數字數據到純數字的數據。根據分類組合將所有分類過濾成不同的組，這樣就可以單獨分析每個組（因為我們處理的是大數據，所以分組過程和K-means 過程都是通過大數據平臺進行的）。也就是說，只對其余的數值變量執行K-means 算法。最后，根據所做的實驗，對結果集進行分析，這些結果集可以作為進一步研究的基礎。

本研究提出了一種以前不可能處理大數據中混合數據的方法。該方法提高了處理大量數據的能力，例如在決策中，因為可以更有針對性的方式執行分析、預測。

2 模型開發

我們認為，將K-means 算法應用于大數據生態系統中的混合數據，可以增強決策能力，使決策者能夠處理海量數據。因此，本研究分析了K-means 算法在大數據平臺中應用于數值和分類（非數值）數據時的影響。該模型假設數據集包含m 個分類變量和n 個定量變量，分類變量j 可能具有j≥2 種不同狀態。K-means算法程序：

要求1：大數據中的非數值數據可以賦值。

證明：首先對數據集執行K-means 算法，步驟如下：

（1）創建∏mj=1 不同類型的組，它們的類別變量的值不同。對于每個記錄，都會有相應的分組，然后把每個記錄放到相應的分組中去。

（2）第一步生成的每個組都是大數據平臺中的一個文件（或其他存儲格式）（這將在接下來的步驟中啟用并行計算）。

（3）根據數值變量對所有組執行并行K-means算法。

（4）將步驟3 中的所有集群（每個組中的K 個集群）聚合到一個結果，以進行進一步分析，如第4 節所述。

3 算法案例的實現

（1）將數據集和分類文件上傳到HDFS（在Apache Hadoop 中），每個類別變量的值可能的組合在一個單獨的文件中。每個文件都會有相應的記錄，這是一個強制性步驟，因為需要根據定義/業務需求創建所有可用狀態的組合。注意，如果沒有具有相應分類值的記錄，則可能存在空文件（組）。

（2）將所有文件（從步驟1 開始）相乘以創建多行。每一行都描述了一個獨特的組合。所有行都存儲在HDFS 文件中(在Apache Hadoop 中），用于并行分析（在大數據平臺中）。

（3）過濾每個惟一文件的數據集（從步驟2 開始），并將相關的定量變量發送到相關文件。

（4）在每個文件上運行（通過bash 腳本）K-means算法（Apache Mahout），這些文件位于一個單獨的目錄中（步驟3），參數如下：

●迭代次數的可配置參數x（在本例中，我們對所有K-means 運行使用5 次迭代）；

●集群的數量，K，這受到每個唯一文件的記錄數量的影響（從步驟3 開始）。每個文件的數量增加的時候，在集群中，對應的k 的數量也會相應的增加。

（5）將所有集群收集到一個定義的結構中，以進行額外的分析（比較集群、順序、分析等）。

4 端到端的程序實現案例研究

4.1 數據集

對于數據集的生成，本文生成了3 個數據集，分別對應的變量的數量為14 個、8 個、6 個。它包含1100萬條記錄，總共約為1.05GB。所有變量（分類變量和數值變量）的列表如下：

數量變量：年齡、工作年限、工資、受教育年限、房屋數量、子女數量、每年旅行次數、車輛數量。

表1 對給出了相應的可能性的數值。注意，這六個分類變量的組合最多可以創建1600 個不同的特征。

根據每個集群記錄數的預定義，創建了5000 個集群。

4.2 過程流

圖1 描述了端到端用例的端到端技術實現。主要內容有：

（1）HDFS 是一個分布式的文件系統。完整的數據集被上載到HDFS。然后，創建所有不同的組合，并從完整的數據中篩選相關字段。所有過濾器都存儲在HDFS 中，用于分析過程。

（2）MapReduce ，這是主組件，它處理和管理所有并行處理在分析數據時完成（在實現示例中，我們使用Apache Mahout 作為 K-means 算法）。

（3）bi，這個組件是可能性的需求，包括了智能需求。顯然，需求會隨著組織的不同而變化，但是針對特定專業文件的需求在不同的業務中可能是相同的（在查詢的目的中，可以通過查詢值本身、數據、預期結果等來區分這些需求）。

圖1 用例的端到端技術實現圖

4.3 運行標準

運行該過程后，集群被聚合到一個包含所有結果和時間戳的文件中。注意，不是房屋所有者、而是金融專家的記錄，沒有數值。總的來說，通過過濾過程，確定了40 個數值為空的組類型。在100 個目錄的組中執行K-means 算法，其中預定義的集群數量。

表1 分類變量

表2 過程步驟

根據每組/文件/子集數據集的重新排序次數選擇，如表3 所示。每個K-means 過程的迭代次數為5 次。

表3 根據預定義的集群數量記錄數目

根據表3，K-means 算法總共創建了5940 個集群（對于1560 個有值的組，每組1 到10 個集群）。注意，識別40 個沒有包含任何數量信息/值的概要文件是非常重要的，因為可能有不同的業務需求和需求需要對概要文件進行標識，而沒有任何值或沒有任何記錄/觀察。

4.4 BI用例

主要問題是：組織如何使用聚集成一個大型數據集的大量集群來進行決策?聚合的集群數據集包含獨特的概要文件和組，形成了一個有價值的信息模式，可以針對特定的人群進行定位。

本節演示一個用于特定決策需求的用例示例。我們假設已經收集并創建了聚合的集群數據集，并且公司希望根據公司的目標和需求來檢查投資于特定的概要文件細分是否有利可圖。

表4 目標查詢值

作為一個示例，我們從1560 個組生成的5940 個集群開始。5940 個集群總共包含1100 萬個特定資源（其中每個資源都是一個特定的用戶觀察）。表4 顯示了為定義目標人口的需求指定的值（在本例中）。

如表 5 所示，5940 個配置文件中只有 5 個（clus?ter）滿足目標配置文件的要求。由于這種分析過程，公司只能關注這些概要文件中的用戶。

表5 業務查詢目標概要文件

5 結語

在本文中，提出了一種新的方法，克服了在大數據環境下使用混合數據進行決策的困難。根據業務需求將概要文件聚類并縮小到目標組的能力改進了決策過程。在對K-means 算法的測試和實現中，發現該算法在實際運行中運行良好。然而，程序分析的復雜性必須在未來的研究中進行測試。過程的復雜性更有效率的復雜性相比，常規的K-means 算法運行在一個完整的數據集，因為它能夠減少數據集的大小。該算法運行在子集，擁有更少的記錄每組。這影響每個組的K-means 迭代的數量。此外，請注意，在大數據環境中，所有的K-means 計算都可以在不同的數據節點上并行進行。因此，復雜度主要受將生成的最大組。

需要注意的是，本文沒有將大數據環境下混合數據的K-means 方法與混合數據的K-means 算法進行復雜度分析比較。然而，所提出的方法的復雜性更好。

（1）減少數據集大小：每組分析的觀測值更少（由于過濾了相關數據；見第2 節和第3 節）；

（2）分析流程并行化：大數據架構使我們能夠并行執行分析流程（基于MapReduce 作業在HDFS 平臺上分配的每個組/文件）。基于所有數據節點具有相同的容量和性能（在過程運行時）的假設，我們還可以假設最大的組（子集數據集）將具有最高的復雜性，因此將以最大的方式影響總體復雜性。然而，這一理論假設還有待驗證。