[發明專利]一種基于FPGA的K均值算法的實現方法

在審

• 申請號: 202110588584.9
• 申請日: 2021-05-28
• 公開（公告）號: CN113326479A
• 公開（公告）日: 2021-08-31
• 發明（設計）人: 石晴文;馮佳瑋
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06F30/27;G06F30/331;G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明屬于數字電路設計技術領域，具體涉及一種基于FPGA的K均值算法的實現方法，包括頂層模塊(1)，聚類模塊(2)，更新模塊(3)，存儲模塊(4)。這些模塊都由RTL級代碼實現。本發明主要針對海量高維度數據存儲與處理速度慢的問題，通過利用FPGA邏輯資源豐富，開發周期短，可并行計算的優勢提高數據訪問與處理速度。

技術領域

本發明屬于數字電路設計技術領域，具體涉及一種基于FPGA的K均值算法的實現方法。

背景技術

隨著互聯網和電子商務的飛速發展，獲取信息的需求和手段越來越多，對于獲取數據的速度要求越來越高，就會導致各行各業獲取，沉淀和處理的數據呈指數增長。海量高維度的數據的存儲，使用等明顯降低了數據處理的速度，成為研究人員密切關注和希望有所突破的問題。這也是數據挖掘領域的核心內容。一種無監督的機器學習算法聚類算法被廣泛應用于數據挖掘，模式識別，圖像處理等領域，在各領域發揮其重要作用。聚類算法可以在商業領域中進行市場分析、調研信息，比如從數據庫中消費者記錄分析不同消費者的習慣、需求等；可以在生物醫學領域中加速研究，對動植物分類，對基因的相似關聯性分析等。聚類算法大致可以分為五大類，但不局限于這五類，分別為基于劃分的聚類算法，比如我們最熟識的K均值算法就是基于劃分思想的聚類算法中的一種。基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法和基于模型的聚類算法。不同的聚類算法會根據自身不同的特點局限性適用于不同分布的多種多樣的數據集。比如K均值算法，該算法原理簡單，運行速度快時間短，適用于連續型球狀分布的數據集，但在處理分布不規則的數據集時便很難得到較好的聚類效果。而其他類別中的某個或者某些算法就相對更適用于這種分布不規則的數據集，能夠達到更好的聚類效果。

目前，云計算平臺在大數據分析領域發展快速且成熟。云計算平臺由多臺CPU構成，由于CPU之間信息通信受帶寬限制，此時硬件加速平臺應運而生。而且就目前發展趨勢而言，對大數據處理能力，資源效率等問題上，借助硬件設備成為一種至關重要的辦法。現場可編程門陣列(FieldProgrammable GateArray)這種邏輯資源豐富、配置靈活、開發周期短、可并行計算的半定制數字電路設計載體更適合作為用來加速的硬件設備。

發明內容

本發明的目的是提供一種基于FPGA的K均值算法的實現方法，利用K均值算法并行特點與FPGA的并行完美融合，使得該算法對于海量高維數據在FPGA平臺上從速度，硬件資源占用等方面得到了優化。

為達到以上目的具體包括：頂層模塊(1)、聚類模塊(2)、更新模塊(3)、存儲模塊(4)。這些模塊都由RTL級代碼實現。

頂層模塊(1)由有限狀態機實現對其他模塊的控制以及數據通路，根據控制部件的信息跳轉順序的執行各個模塊。首先，在收到上位機傳入的開始命令后，狀態機進入開始狀態，將數據從寄存器中讀出送入聚類模塊(2)，開始數據聚類過程。聚類結束后反饋給頂層模塊(1)一個完成信號，狀態機繼而跳轉。最終完成數據的聚類。為了實現循環，利用多個計數器控制。

聚類模塊(2)包括控制器(201)、距離計算模塊(202)、尋找最小距離模塊(203)、確定類別模塊(204)、串入并出模塊(205)。其中涉及浮點數加法器、浮點數乘法器、比較器等。控制器(201)用有限狀態機實現，與頂層模塊(1)類似，控制聚類的過程。距離計算模塊(202)接收到控制器(201)的開始信號后，讀取數據計算輸入數據與聚類中心的曼哈頓距離，即讀取一個輸入計算該輸入與K個聚類中心的距離，在尋找最小距離模塊(203)中找到K個距離中的最小值。通過確定類別模塊(204)將該輸入分配到相應的存儲器RAM中也就是聚類到了相應的類別中，完成一個輸入數據的聚類。循環N次，完成N個數據的聚類。

更新模塊(3)包括控制器(301)、數據累加模塊(302)、除法模塊(303)、定點數轉浮點數模塊(304)。數據累加模塊(302)對聚在某一類的輸入數據累加，將累加結果送到除法模塊(303)，更新該類的聚類中心。