[發(fā)明專(zhuān)利]一種基于FPGA的K均值算法的實(shí)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110588584.9
• 申請(qǐng)日: 2021-05-28
• 公開(kāi)（公告）號(hào): CN113326479A
• 公開(kāi)（公告）日: 2021-08-31
• 發(fā)明（設(shè)計(jì)）人: 石晴文;馮佳瑋
• 申請(qǐng)（專(zhuān)利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類(lèi)號(hào): G06F17/18
• 分類(lèi)號(hào): G06F17/18;G06F30/27;G06F30/331;G06K9/62
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于FPGA的K均值算法的實(shí)現(xiàn)方法，主要結(jié)構(gòu)包括頂層模塊(1)、聚類(lèi)模塊(2)、更新模塊(3)、存儲(chǔ)模塊(4)，頂層模塊(1)由有限狀態(tài)機(jī)實(shí)現(xiàn)對(duì)其他模塊的控制以及數(shù)據(jù)通路，根據(jù)控制部件的信息跳轉(zhuǎn)順序的執(zhí)行各個(gè)模塊，首先，在收到上位機(jī)傳入的開(kāi)始命令后，狀態(tài)機(jī)進(jìn)入開(kāi)始狀態(tài)，將數(shù)據(jù)從寄存器中讀出送入聚類(lèi)模塊(2)，開(kāi)始數(shù)據(jù)聚類(lèi)過(guò)程，聚類(lèi)結(jié)束后反饋給頂層模塊(1)一個(gè)完成信號(hào)，狀態(tài)機(jī)繼而跳轉(zhuǎn)，最終完成數(shù)據(jù)的聚類(lèi)，為了實(shí)現(xiàn)循環(huán)，利用多個(gè)計(jì)數(shù)器控制，存儲(chǔ)模塊(4)除存儲(chǔ)所有輸入數(shù)據(jù)的ROM外，還利用RAM動(dòng)態(tài)存儲(chǔ)聚類(lèi)中心和K類(lèi)輸入數(shù)據(jù)，每次聚類(lèi)時(shí)讀出聚類(lèi)中心進(jìn)行聚類(lèi)，聚類(lèi)完成時(shí)將每類(lèi)輸入寫(xiě)入，更新模塊時(shí)從K類(lèi)輸入數(shù)據(jù)分別讀出更新中心，更新后的中心寫(xiě)入存儲(chǔ)聚類(lèi)中心的RAM里，其中：

頂層模塊(1)：輸入端輸出端都與聚類(lèi)模塊(2)中的控制器(201)，更新模塊(3)中的控制器(301)相連；

存儲(chǔ)模塊(4)：輸入端輸出端都與聚類(lèi)模塊(2)、更新模塊(3)的輸入輸出端相連。

2.根據(jù)權(quán)利要求1所述的一種基于FPGA的K均值算法的實(shí)現(xiàn)方法，其特征在于，所述聚類(lèi)模塊(2)包括控制器(201)、距離計(jì)算模塊(202)、尋找最小距離模塊(203)、確定類(lèi)別模塊(204)、串入并出模塊(205)，控制器(201)用有限狀態(tài)機(jī)實(shí)現(xiàn)，與頂層模塊(1)類(lèi)似，控制聚類(lèi)的過(guò)程，距離計(jì)算模塊(202)接收到控制器(201)的開(kāi)始信號(hào)后，讀取數(shù)據(jù)計(jì)算輸入數(shù)據(jù)與聚類(lèi)中心的曼哈頓距離，即讀取一個(gè)輸入計(jì)算該輸入與K個(gè)聚類(lèi)中心的距離，在尋找最小距離模塊(203)中找到K個(gè)距離中的最小值，通過(guò)確定類(lèi)別模塊(204)將該輸入分配到相應(yīng)的存儲(chǔ)器RAM中也就是聚類(lèi)到了相應(yīng)的類(lèi)別中，完成一個(gè)輸入數(shù)據(jù)的聚類(lèi)，循環(huán)N次，完成N個(gè)數(shù)據(jù)的聚類(lèi)，其中：

距離計(jì)算模塊(202)：輸入端與存儲(chǔ)模塊(4)、控制器(201)輸出端相連，輸出端與串入并出模塊(205)、確定類(lèi)別模塊(204)、控制器(201)的輸入端相連；

尋找最小距離模塊(203)：輸入端與串入并出模塊(205)輸出端相連，輸出端與確定類(lèi)別模塊(204)輸入端相連；

確定類(lèi)別模塊(204)：輸入端與距離計(jì)算模塊(202)、尋找最小距離模塊(203)、控制器(201)輸出端相連，輸出端與控制器(201)、存儲(chǔ)模塊(4)的輸入端相連；

串入并出模塊(205)：輸入端與距離計(jì)算模塊(202)、控制器(201)輸出端相連，輸出端與尋找最小距離模塊(203)、控制器(201)輸入端相連。

3.根據(jù)權(quán)利要求1所述的一種基于FPGA的K均值算法的實(shí)現(xiàn)方法，其特征在于，所述更新模塊(3)包括控制器(301)、數(shù)據(jù)累加模塊(302)、除法模塊(303)、定點(diǎn)數(shù)轉(zhuǎn)浮點(diǎn)數(shù)模塊(304)，數(shù)據(jù)累加模塊(302)對(duì)聚在某一類(lèi)的輸入數(shù)據(jù)累加，將累加結(jié)果送到除法模塊(303)，更新該類(lèi)的聚類(lèi)中心，其中：

數(shù)據(jù)累加模塊(302)：輸入端與控制器(301)、存儲(chǔ)模塊(4)的輸出端相連，輸出端與控制器(301)、除法模塊(303)、定點(diǎn)數(shù)轉(zhuǎn)浮點(diǎn)數(shù)模塊(304)的輸入端相連；

除法模塊(303)：輸入端與控制器(301)、數(shù)據(jù)累加模塊(302)、定點(diǎn)數(shù)轉(zhuǎn)浮點(diǎn)數(shù)模塊(304)的輸出端相連，輸出端與控制器(301)、存儲(chǔ)模塊(4)的輸入端相連；

定點(diǎn)數(shù)轉(zhuǎn)浮點(diǎn)數(shù)模塊(304)：輸入端與數(shù)據(jù)累加模塊(302)的輸出端相連，輸出端與除法模塊(303)的輸入端相連。