[發(fā)明專利]一種基于GPU-CUDA平臺(tái)以及遺傳算法的數(shù)據(jù)流并行處理方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201310229098.3
• 申請(qǐng)日: 2013-06-09
• 公開（公告）號(hào): CN103279332A
• 公開（公告）日: 2013-09-04
• 發(fā)明（設(shè)計(jì)）人: 盧曉偉;周勇;韓君;張清
• 申請(qǐng)（專利權(quán)）人: 浪潮電子信息產(chǎn)業(yè)股份有限公司
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06N3/12
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于GPU-CUDA平臺(tái)以及遺傳算法的數(shù)據(jù)流并行處理方法,?其特征在于，包括以下內(nèi)容：

利用遺傳算法動(dòng)態(tài)挖掘出最新數(shù)據(jù)的頻繁項(xiàng)集，從一組初始種群開始搜索過(guò)程，種群中的每個(gè)個(gè)體是一個(gè)可能的頻繁模式；

根據(jù)數(shù)據(jù)流的特點(diǎn)采取滑動(dòng)窗口模式，進(jìn)行流數(shù)據(jù)的挖掘，而且針對(duì)頻繁項(xiàng)集挖掘的特點(diǎn)，采用基于滑動(dòng)窗口之上的嵌套子窗口模型；

根據(jù)數(shù)據(jù)流數(shù)據(jù)量大，需要實(shí)時(shí)處理的特點(diǎn)，采用GPU-CUDA并行處理技術(shù)來(lái)進(jìn)行頻繁項(xiàng)集挖掘；

綜合處理滑動(dòng)窗口內(nèi)各嵌套子窗口中頻繁項(xiàng)集，最終獲得當(dāng)前滑動(dòng)窗口內(nèi)數(shù)據(jù)的頻繁項(xiàng)集；?

具體步驟如下：

一、利用遺傳算法的并行性搜索嵌套子窗口內(nèi)最新數(shù)據(jù)的頻繁項(xiàng)集；

步驟S110：設(shè)定滑動(dòng)窗口SW及子窗口S_SW大小，分別為w₁、w₂輸入各類參數(shù)之后，根據(jù)數(shù)據(jù)流屬性來(lái)確定窗口大小，SW內(nèi)容是根據(jù)當(dāng)前多少條事務(wù)的頻繁項(xiàng)集的興趣度來(lái)決定的，子窗口是根據(jù)數(shù)據(jù)的處理能力以及被拋棄的舊數(shù)據(jù)條數(shù)來(lái)確定，也決定了需求所要求統(tǒng)計(jì)的頻率；

給定支持度閾值S，若某個(gè)個(gè)體i,?其適應(yīng)度為F_i?,當(dāng)F_i>?=?S，事務(wù)i即為滑動(dòng)窗口內(nèi)數(shù)據(jù)集的頻繁項(xiàng)集模式；

事務(wù)的屬性種數(shù)、各屬性的取值范圍以及生成原始種群大小來(lái)確定最大迭代次數(shù)T，本處理方法是采用子窗口模型，避免在舊數(shù)據(jù)被淘汰之后，對(duì)滑動(dòng)窗口SW內(nèi)存在的數(shù)據(jù)進(jìn)行多次重復(fù)處理；

設(shè)定交叉概率P，個(gè)體變異概率Q，子窗口內(nèi)的數(shù)據(jù)分成Z?段并行計(jì)算，該處的函數(shù)采用GPU?CUDA?并行技術(shù)，將每個(gè)子窗口內(nèi)的數(shù)據(jù)交給一個(gè)線程進(jìn)行并行處理；

步驟S120：獲得初始種群，數(shù)據(jù)在流動(dòng)過(guò)程中，獲取子窗口內(nèi)最新到來(lái)的數(shù)據(jù)，同時(shí)得到此數(shù)據(jù)的頻繁1-項(xiàng)集，將頻繁1-項(xiàng)集編碼為實(shí)數(shù)串，并將頻繁1-項(xiàng)集非零項(xiàng)按原來(lái)所在位置隨機(jī)組合編碼，共同組成嵌套子窗口內(nèi)的初始種群，此種群中個(gè)體為待考察頻繁項(xiàng)集模式，具體過(guò)程如下：

1?）統(tǒng)計(jì)A、B和C的屬性值為V1，V2，V3的個(gè)數(shù)分別作為第一列、第二列和第三列；

2?）大于等于閾值N的保留，并按其所對(duì)應(yīng)的行進(jìn)行賦值，小于N的賦值0，并去掉；

3）將每一個(gè)非0值單獨(dú)成一行，并保持其原來(lái)所在行的位置，其余位置填0；

4）非零項(xiàng)按原來(lái)所在位置隨機(jī)組合編碼，共同組成初始種群；

函數(shù)是采用GPU?CUDA編程模式，采用流技術(shù)和共享存儲(chǔ)器等優(yōu)化手段，將每個(gè)屬性的求解過(guò)程進(jìn)行并行處理；

步驟S130：計(jì)算個(gè)體支持度值是初始種群內(nèi)待考察頻繁模式與實(shí)際事務(wù)匹配的過(guò)程，當(dāng)個(gè)體支持度值大于S時(shí)，將該個(gè)體模式加入當(dāng)前子窗口頻繁項(xiàng)集內(nèi)，F(xiàn)_i=W_i/W_Z?，F(xiàn)_i?為事務(wù)i的支持度，W_i為當(dāng)前子窗口內(nèi)具有相同屬性值的事務(wù)條數(shù)，W_Z為當(dāng)前子窗口內(nèi)事務(wù)總條數(shù)；

分Z?段并行匹配，雖然增大了內(nèi)存開銷，但大量減少運(yùn)行時(shí)間，對(duì)于數(shù)據(jù)流頻繁項(xiàng)集挖掘具有很大意義，并行匹配；

步驟S140：選擇，將種群中個(gè)體按支持度值進(jìn)行輪盤選擇；

步驟S150：交叉，以交叉概率P進(jìn)行一次交叉；

步驟S160：變異，個(gè)體按變異概率Q進(jìn)行基本位變異；

步驟S170：掃描確定變異后個(gè)體支持度值，新增的滿足條件的個(gè)體添加到頻繁項(xiàng)集中；

步驟S180：判斷結(jié)束條件，如迭代次數(shù)小于T，轉(zhuǎn)步驟3，T次迭代運(yùn)算后，則終止迭代并獲得當(dāng)前嵌套子窗口內(nèi)數(shù)據(jù)的頻繁項(xiàng)集；

二、獲得當(dāng)前滑動(dòng)窗口內(nèi)數(shù)據(jù)的頻繁項(xiàng)集

步驟S210：本次獲得的各個(gè)頻繁項(xiàng)集模式與之前U，U=w₁/w₂-1次獲得的頻繁項(xiàng)集模式共同組成初始種群，進(jìn)行一次搜索，最終滿足條件的模式個(gè)體為滑動(dòng)窗口內(nèi)數(shù)據(jù)的頻繁項(xiàng)集；

For??i=1：U+1；

將各段得到的頻繁模式組合成為頻繁模式群；

End；

將頻繁模式群在滑動(dòng)窗口SW內(nèi)進(jìn)行一次并行搜索；

支持度大于S的最終確定為頻繁模式；

該步驟的函數(shù)采用OpenMP共享編程模式進(jìn)行多線程并行處理；

步驟S310：隨著數(shù)據(jù)流的流動(dòng)，繼續(xù)處理新接收到的數(shù)據(jù)，并拋棄最早的數(shù)據(jù)，轉(zhuǎn)步驟S102繼續(xù)以上操作，至數(shù)據(jù)流結(jié)束為止。