摘" 要： 高維數(shù)據(jù)維度增加，數(shù)據(jù)空間的體積呈指數(shù)增長(zhǎng)，容易陷入“維數(shù)災(zāi)難”，導(dǎo)致聚類算法執(zhí)行效率低，為此，提出異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)聚類算法。構(gòu)建高維混合型數(shù)據(jù)相異度矩陣，提取高維混合型數(shù)據(jù)的統(tǒng)計(jì)序列特征值，利用時(shí)間窗口進(jìn)行特征優(yōu)化。采用K?Prototypes聚類算法提取高維混合型數(shù)據(jù)的統(tǒng)計(jì)序列特征，評(píng)估數(shù)據(jù)與類中心的相異性，計(jì)算數(shù)據(jù)與類中心的歐氏距離，實(shí)現(xiàn)高維混合型數(shù)據(jù)聚類。采用異構(gòu)并行計(jì)算技術(shù)進(jìn)行高維混合型數(shù)據(jù)K?Prototypes聚類的并行化處理，合理分配CPU與GPU工作，達(dá)到CPU與GPU的工作負(fù)載平衡，提高K?Prototypes的聚類效率。實(shí)驗(yàn)結(jié)果表明，此算法對(duì)于高維混合型數(shù)據(jù)的聚類效果好、運(yùn)行時(shí)間短、性能穩(wěn)定。

關(guān)鍵詞： 異構(gòu)并行計(jì)算； 高維混合型數(shù)據(jù)； K?Prototypes聚類算法； 歐氏距離； 統(tǒng)計(jì)序列特征； 負(fù)載平衡

中圖分類號(hào)： TN919?34； TP312"""""""""""""""""" 文獻(xiàn)標(biāo)識(shí)碼： A""""""""""""""""""""" 文章編號(hào)： 1004?373X（2024）09?0139?04

0" 引" 言

高維混合型數(shù)據(jù)在各個(gè)領(lǐng)域中越來越普遍，如基因數(shù)據(jù)分析、網(wǎng)頁內(nèi)容挖掘、金融市場(chǎng)趨勢(shì)預(yù)測(cè)等[1]。對(duì)這些數(shù)據(jù)進(jìn)行有效的聚類分析，有助于更好地理解數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和模式，提取有用的信息，為決策提供支持[2]。高維混合型數(shù)據(jù)的聚類算法研究為解決實(shí)際問題提供了有效的工具和方法。例如，在商業(yè)領(lǐng)域可以對(duì)消費(fèi)者數(shù)據(jù)進(jìn)行聚類分析，從而更好地理解客戶需求和市場(chǎng)趨勢(shì)[3]；在社交媒體領(lǐng)域可以對(duì)用戶數(shù)據(jù)進(jìn)行聚類分析，從而更好地理解用戶行為和社交網(wǎng)絡(luò)結(jié)構(gòu)。對(duì)此，研究高維混合型數(shù)據(jù)聚類算法具有重要意義。

文獻(xiàn)[4]指出的基于多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食優(yōu)化算法進(jìn)行高維混合型數(shù)據(jù)聚類。此算法基于改進(jìn)的細(xì)菌覓食算法，構(gòu)建多目標(biāo)優(yōu)化框架，引入多元學(xué)習(xí)策略提升了算法效能。設(shè)計(jì)考慮屬性權(quán)重的混合屬性轉(zhuǎn)換方法，最終實(shí)現(xiàn)了高效的高維混合型數(shù)據(jù)聚類。此算法雖然具有全局搜索能力，但在某些情況下，其局部搜索能力可能不足。對(duì)于高度復(fù)雜的優(yōu)化問題，算法可能難以找到最優(yōu)解或需要較長(zhǎng)時(shí)間才能收斂，故耗時(shí)會(huì)太長(zhǎng)。文獻(xiàn)[5]提出基于改進(jìn)Spark技術(shù)算法進(jìn)行高維混合型數(shù)據(jù)聚類，此算法利用混沌劃區(qū)方式重新構(gòu)建高維混合型數(shù)據(jù)的構(gòu)成，得到模糊的數(shù)據(jù)分布模式。對(duì)Spark技術(shù)進(jìn)行改進(jìn)，并設(shè)計(jì)并行化的增量式高維混合型數(shù)據(jù)聚類改進(jìn)算法，完成對(duì)高維混合型數(shù)據(jù)的聚類。但此算法對(duì)噪聲和異常值較為敏感，會(huì)影響聚類的準(zhǔn)確性和穩(wěn)定性。

為解決上述問題，本文提出異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)聚類算法。構(gòu)建高維混合型數(shù)據(jù)相異度矩陣，對(duì)高維混合型數(shù)據(jù)的統(tǒng)計(jì)序列特征量進(jìn)行提取，實(shí)現(xiàn)數(shù)據(jù)的降維。采用CPU?GPU異構(gòu)并行計(jì)算進(jìn)行高維混合型數(shù)據(jù)K?Prototypes聚類，按比例劃分法劃分工作的速率，以平衡CPU與GPU的工作負(fù)載，提高聚類效率。

1" 高維混合型數(shù)據(jù)特征提取

評(píng)估空間中類簇的聚類效果，因?yàn)橥活惔乩锏碾S機(jī)兩個(gè)高維混合型數(shù)據(jù)間距離較小[6]，而不同類簇間的兩個(gè)高維混合型數(shù)據(jù)間距離較大[7]。所以能夠詳細(xì)表達(dá)聚類為：在指定的高維混合型數(shù)據(jù)集[W=wii=1，2，…，n]內(nèi)，利用數(shù)據(jù)間的相似程度對(duì)數(shù)據(jù)集進(jìn)行區(qū)分，簇[Ki?W]，[Kj?W]，其中，[j=1，2，…，n]；[i+j=n]，并符合式（1）和式（2）。

[Ki?Kj=?，""" i≠j] （1）

[Ki?Kj=W] （2）

、[β=0a2，10???an，1an，2…0] （3）

式中：[au1，u2]通常是非負(fù)數(shù)，在數(shù)據(jù)[u1]和[u2]非常相似時(shí)，[au1，u2]趨于0，如果數(shù)據(jù)[u1]和[u2]兩者差異很大，則[au1，u2]就很大，相異度矩陣由此而來；[β]代表相異度矩陣，是經(jīng)過記錄[n]個(gè)數(shù)據(jù)間可能存在的兩兩相異性來實(shí)現(xiàn)存儲(chǔ)的，它的具體展現(xiàn)方式是[n×n]型矩陣，全部因子[au1，u2]就是數(shù)據(jù)[u1]和[u2]兩者間的相異性。

基于建立的相異度矩陣，提取高維混合型數(shù)據(jù)的統(tǒng)計(jì)序列特征量，以便為后續(xù)的高維混合型數(shù)據(jù)異構(gòu)并行聚類算法提供依據(jù)。高維混合型數(shù)據(jù)的數(shù)據(jù)集檢驗(yàn)統(tǒng)計(jì)序列特征值矩陣用式（4）計(jì)算：

[B=β-1e，J] （4）

式中：[J]、[B]、[e]、[β]分別代表高維混合型數(shù)據(jù)的分區(qū)匹配集、統(tǒng)計(jì)序列特征值矩陣、檢索模糊域、調(diào)節(jié)參數(shù)。

計(jì)算高維混合型數(shù)據(jù)的數(shù)據(jù)集聚類中心，以便得到高維混合型數(shù)據(jù)的特征分布域描述，如式（5）所示：

[Ls=HsB1-2πe+Dsεs] （5）

式中：[Ds]、[εs]、[Ls]、[Hs]分別代表不等式的約束條件、高維混合型數(shù)據(jù)的并行計(jì)劃聚類自適應(yīng)調(diào)整參數(shù)、高維混合型數(shù)據(jù)的特征分布域描述、高維混合型數(shù)據(jù)的并行計(jì)劃聚類加權(quán)輸出程度值。

使用平均加權(quán)法，通過模糊聚類中心描述數(shù)據(jù)庫中高維混合型數(shù)據(jù)的時(shí)間窗口，用于處理數(shù)據(jù)的時(shí)間序列特性和異構(gòu)性，時(shí)間窗口用式（6）表達(dá)：

[T=LsT1T2] （6）

式中：[T1]、[T2]、[T]分別代表高維混合型數(shù)據(jù)的事件時(shí)間、操作時(shí)間、時(shí)間窗口。

通過式（6）提取數(shù)據(jù)庫中高維混合型數(shù)據(jù)的全局優(yōu)化特征，將數(shù)據(jù)輸入處理器以計(jì)算增益值，從而完成高維混合型數(shù)據(jù)特征的提取。

2" 提高高維混合型數(shù)據(jù)聚類效率

本文在進(jìn)行高維混合型數(shù)據(jù)K?Prototypes聚類時(shí)采用CPU?GPU異構(gòu)并行計(jì)算技術(shù)進(jìn)行計(jì)算[8?9]。在由CPU與GPU組建的異構(gòu)體系中，GPU是CPU的協(xié)處理器，既處理圖形計(jì)算也處理通用計(jì)算[10?12]。

K?Prototypes聚類算法流程如下：

1） 初始類中心是在高維混合型數(shù)據(jù)集[X]內(nèi)任意抽取的[k]個(gè)數(shù)據(jù)。

2） 依據(jù)運(yùn)算數(shù)據(jù)到類中心的距離，把各個(gè)數(shù)據(jù)劃分到離其最近的類中的依據(jù)是最近原則。

3） 修正聚類中心，利用運(yùn)算一種類中數(shù)據(jù)的平均值獲取數(shù)值型特征；利用運(yùn)算各類中特征值呈現(xiàn)的頻率高低明確分類型特征。

4） 反復(fù)進(jìn)行步驟2）和步驟3），最終達(dá)到目標(biāo)函數(shù)收斂不變。

為了實(shí)現(xiàn)并行K?Prototypes聚類，在CPU端通過OpenMP手段實(shí)現(xiàn)K?Prototypes聚類過程的并行。

K?Prototypes聚類運(yùn)算數(shù)據(jù)到類中心的距離的迭代過程，可看成是一種GPU并行工作模式，因此在GPU中通過矩陣?矩陣乘積的方式獲取矩陣同其他數(shù)據(jù)點(diǎn)間的距離。能夠看到K?Prototypes聚類過程中，需要不斷利用數(shù)據(jù)完成乘積運(yùn)算，而GPU的共享內(nèi)存可實(shí)現(xiàn)數(shù)據(jù)的重復(fù)運(yùn)用[13?14]。同時(shí)，融合全局內(nèi)存和聚類線程間也存在共享數(shù)據(jù)的問題，因此將數(shù)據(jù)劃分成不同的數(shù)據(jù)塊，再向共享內(nèi)存中融入分塊后的子數(shù)據(jù)塊，并進(jìn)行乘積運(yùn)算，則可極大提高程序的運(yùn)行性能。

1） 開始迭代過程中，向共享內(nèi)存內(nèi)融入數(shù)據(jù)分塊后的子數(shù)據(jù)塊。

2） 依據(jù)一個(gè)block內(nèi)線程數(shù)，將數(shù)據(jù)塊以及子數(shù)據(jù)塊行號(hào)一致的[p]行，依據(jù)列的形式分割成不同的塊，各線程向該線程寄存器內(nèi)融入[p]行中的一列，同時(shí)通過數(shù)據(jù)的子數(shù)據(jù)進(jìn)行乘法運(yùn)算，獲取數(shù)據(jù)點(diǎn)同中心點(diǎn)間的距離，在獲取的距離中挑選出最小的一個(gè)，將其分配到對(duì)應(yīng)的聚類中。

通過CPU?GPU協(xié)同運(yùn)算過程，完成聚類算法的初始聚類劃分以及聚類中心獲取兩個(gè)過程的并行化。

采用CPU?GPU異構(gòu)并行計(jì)算進(jìn)行高維混合型數(shù)據(jù)K?Prototypes聚類時(shí)，按比例劃分法劃分CPU與GPU的工作速率，以平衡CPU與GPU的工作負(fù)載。指定CPU與GPU的工作分配為[Y0，Z0]，運(yùn)行時(shí)間為[TCPU，TGPU]，則CPU工作的運(yùn)行速率以及GPU工作的運(yùn)行速率用式（7）表示：

[VCPU=Y0TCPU，"" VGPU=Z0TGPU] （7）

如果CPU與GPU的最優(yōu)工作分配為[Y，Z]，這時(shí)兩者的工作時(shí)間是相等的，才會(huì)避免CPU與GPU在工作時(shí)互相等待的情況發(fā)生。簡(jiǎn)化算法，將流傳輸時(shí)間歸為GPU工作時(shí)間內(nèi)，則可得到式（8）：

[YVCPU=ZVGPU，"" Y+Z=1] （8）

將式（7）代入式（8）中，得到式（9）：

[Y=TGPUY0TGPUY0+TCPUZ0，"" Z=TCPUZ0TGPUY0+TCPUZ0] （9）

得到的[Y，Z]可作為下一次運(yùn)算的工作劃分的依據(jù)。可進(jìn)行多次工作分配實(shí)驗(yàn)，得出CPU與GPU的平均運(yùn)行速率，使CPU與GPU的工作負(fù)載達(dá)到平衡，提高K?Prototypes聚類效率。

3" 實(shí)驗(yàn)分析

實(shí)驗(yàn)所用CPU與GPU規(guī)格型號(hào)如表1所示。選取某微博平臺(tái)數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，其中包括文本、數(shù)值、圖像、視頻四種類型數(shù)據(jù)，數(shù)據(jù)空間維數(shù)從5～40。

為驗(yàn)證本文算法的有效性，選取四種類型數(shù)據(jù)各200條作為實(shí)驗(yàn)數(shù)據(jù)進(jìn)行聚類，聚類前后圖如圖1和圖2所示。

從圖1和圖2的聚類效果圖中可以清晰地看到，本文所提出的K?Prototypes聚類算法在處理高維混合型數(shù)據(jù)時(shí)展現(xiàn)出優(yōu)良的性能。無論是文本、數(shù)值還是圖像、視頻等不同類型的數(shù)據(jù)，都能夠?qū)崿F(xiàn)邊界分明的分離，有效地避免了誤分類的情況。這一結(jié)果有力地證明了本文算法對(duì)于高維混合型數(shù)據(jù)聚類的有效性。此外，該算法通過使用K?Prototypes方法，能夠更好地處理具有異構(gòu)特性的數(shù)據(jù)，進(jìn)一步提高聚類的準(zhǔn)確性和實(shí)用性?？偟膩碚f，本文算法對(duì)于高維混合型數(shù)據(jù)的聚類效果良好。

對(duì)比本文算法、多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食算法、改進(jìn)Spark算法對(duì)數(shù)據(jù)集聚類的運(yùn)行時(shí)間，結(jié)果如圖3所示。

由圖3的實(shí)驗(yàn)結(jié)果可知，隨著數(shù)據(jù)量的增加，三種算法的運(yùn)行時(shí)間都在增長(zhǎng)。在數(shù)據(jù)量為1 600條時(shí)，本文算法的運(yùn)行時(shí)間不到200 s，表現(xiàn)出良好的性能，相比之下，多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食算法的運(yùn)行時(shí)間明顯高于本文算法，在數(shù)據(jù)量為1 200條時(shí)，該算法的運(yùn)行時(shí)間已經(jīng)超過200 s；而改進(jìn)Spark算法的運(yùn)行時(shí)間更長(zhǎng)，在數(shù)據(jù)量為1 000條時(shí)，其運(yùn)行時(shí)間已經(jīng)接近200 s。這些結(jié)果表明，本文算法由于采用了異構(gòu)并行計(jì)算，大大縮短了運(yùn)行時(shí)間。同時(shí)，本文算法合理劃分了CPU與GPU的工作比例，確保了CPU與GPU的工作負(fù)載平衡，從而提高了聚類效率。

在不同維數(shù)空間中對(duì)數(shù)據(jù)集進(jìn)行聚類，對(duì)比本文算法、多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食算法、改進(jìn)Spark算法，在數(shù)據(jù)空間維數(shù)不同時(shí)的性能如圖4所示。

根據(jù)圖4的分析可知，隨著數(shù)據(jù)空間維數(shù)的逐步增加，本文方法的運(yùn)行時(shí)間呈現(xiàn)出一定程度的增長(zhǎng)，然而，其增長(zhǎng)幅度相對(duì)較小。在數(shù)據(jù)空間維數(shù)為40時(shí)，本文方法的運(yùn)行時(shí)間不到30 s。與此相比，多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食算法和改進(jìn)Spark算法的運(yùn)行時(shí)間明顯長(zhǎng)于本文方法。具體來說，當(dāng)數(shù)據(jù)空間維數(shù)達(dá)到20時(shí)，多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食算法的運(yùn)行時(shí)間已經(jīng)達(dá)到30 s，而改進(jìn)Spark算法在數(shù)據(jù)空間維數(shù)達(dá)到25時(shí)，其運(yùn)行時(shí)間已經(jīng)接近90 s。這些結(jié)果表明，本文方法在處理不同維度的數(shù)據(jù)空間時(shí)，表現(xiàn)出了穩(wěn)定的性能和較短的運(yùn)行時(shí)間，這有助于提高聚類的速度和效率。因此，本文方法在處理高維數(shù)據(jù)時(shí)具有顯著的優(yōu)勢(shì)，能夠有效地降低計(jì)算復(fù)雜度并提高聚類的速度。

4" 結(jié)" 論

為提高數(shù)據(jù)挖掘的效率和精度，本文提出異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)聚類算法。采用K?Prototypes聚類對(duì)高維混合型數(shù)據(jù)進(jìn)行聚類，并充分利用CPU與GPU異構(gòu)計(jì)算資源，實(shí)現(xiàn)并行化聚類。實(shí)驗(yàn)結(jié)果表明，該算法在處理高維混合型數(shù)據(jù)時(shí)具有較好的性能表現(xiàn)，對(duì)高維混合型數(shù)據(jù)的聚類效果良好，并且速度快。在未來的研究中，會(huì)進(jìn)一步探討本文算法在處理大規(guī)模數(shù)據(jù)集時(shí)的性能優(yōu)化，以提高整體的機(jī)器學(xué)習(xí)效果。本研究為異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)的聚類算法研究提供了新的思路和方法，為相關(guān)領(lǐng)域的研究和應(yīng)用奠定了基礎(chǔ)。

參考文獻(xiàn)

[1] 廖彬，黃靜萊，王鑫，等.SCEA：一種適應(yīng)高維海量數(shù)據(jù)的并行聚類集成算法[J].電子學(xué)報(bào)，2021，49（6）：1077?1087.

[2] 楊志勇，江峰，于旭，等.采用離群點(diǎn)檢測(cè)技術(shù)的混合型數(shù)據(jù)聚類初始化方法[J].智能系統(tǒng)學(xué)報(bào)，2023，18（1）：56?65.

[3] 吉珊珊.基于神經(jīng)網(wǎng)絡(luò)樹和人工蜂群優(yōu)化的數(shù)據(jù)聚類[J].南京師大學(xué)報(bào)（自然科學(xué)版），2021，44（1）：119?127.

[4] 牛奔，郭晨，唐恒.基于多目標(biāo)多元學(xué)習(xí)細(xì)菌覓食優(yōu)化算法的混合數(shù)據(jù)聚類[J].中國(guó)管理科學(xué)，2022，30（12）：131?140.

[5] 劉仁芬，楊鳳麗，王霞.基于改進(jìn)Spark技術(shù)的高維數(shù)據(jù)增量式聚類算法[J].計(jì)算機(jī)仿真，2022，39（12）：383?386.

[6] 何云斌，董恒，萬靜.移動(dòng)型數(shù)據(jù)與靜態(tài)型數(shù)據(jù)的混合聚類算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2021，26（2）：26?34.

[7] 康耀龍，馮麗露，張景安，等.基于譜聚類的高維類別屬性數(shù)據(jù)流離群點(diǎn)挖掘算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2022，52（6）：1422?1427.

[8] 陳佳佳，張旺，劉東海，等.一種融合[α]度量的混合數(shù)據(jù)K?prototypes算法[J].統(tǒng)計(jì)與決策，2023，39（10）：16?22.

[9] 王孝慈，董樹鋒，劉育權(quán)，等.基于改進(jìn)式K?prototypes聚類的壞數(shù)據(jù)辨識(shí)與修正[J].電測(cè)與儀表，2022，59（2）：9?15.

[10] 謝林娟，李荔瑄，張少?gòu)?qiáng).基于異構(gòu)并行計(jì)算的單細(xì)胞測(cè)序數(shù)據(jù)聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2022，58（24）：83?89.

[11] 趙春霞，趙營(yíng)穎，宋學(xué)坤.基于頻繁項(xiàng)集的多源異構(gòu)數(shù)據(jù)并行聚類算法[J].濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，36（4）：440?443.

[12] 萬朵，胡謀法，肖山竹，等.面向邊緣智能計(jì)算的異構(gòu)并行計(jì)算平臺(tái)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2023，59（1）：15?25.

[13] 武小梅，馮琪勁，嚴(yán)干貴，等.基于雙層優(yōu)化的電動(dòng)公交車有序充電策略[J].電網(wǎng)與清潔能源，2021，37（1）：119?126.

[14] 崔璨，楊小虎，邱煒偉，等.基于GPU的區(qū)塊鏈交易驗(yàn)簽加速技術(shù)[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2023，57（8）：1505?1515.

Research on high?dimensional mixed data clustering algorithm

under heterogeneous parallel computing

ZHU Peng

（Department of Computer Technology and Information Management， Inner Mongolia Agricultural University， Baotou 014109， China）

Abstract： As the dimensionality of high?dimensional data increases， the volume of the data space grows exponentially， making it prone to falling into the curse of dimensionality， which results in low execution efficiency of clustering algorithms. Therefore， a high?dimensional mixed data clustering algorithm under heterogeneous parallel computing is proposed. A dissimilarity matrix of high?dimensional mixed data is built， and its statistical sequence feature values is extracted. The time window is used for the feature optimization. The K?Prototypes clustering algorithm is used to extract the statistical sequence features of high?dimensional mixed data， and then evaluate the dissimilarity between the data and the class center， and calculate the Euclidean distance between the data and the class center， so as to achieve high?dimensional mixed data clustering. The heterogeneous parallel computing technology is used to parallelize high?dimensional mixed data K?Prototypes clustering， allocate the workload of CPU and GPU reasonably， so as to achieve the workload balance and improve K?Prototypes clustering efficiency. The experimental results show that the proposed algorithm has good clustering performance for high?dimensional mixed data， short running time and stable performance.

Keywords： heterogeneous parallel computing; high?dimensional mixed data; K?Prototypes clustering algorithm; Euclidean distance; statistical sequence feature; load balance

DOI：10.16652/j.issn.1004?373x.2024.09.025

引用格式：祝鵬.異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)聚類算法研究[J].現(xiàn)代電子技術(shù)，2024，47（9）：139?142.

收稿日期：2024?01?29"" """"""""修回日期：2024?03?01

基金項(xiàng)目：內(nèi)蒙古哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目：基于大數(shù)據(jù)的內(nèi)蒙古旅游目的地形象感知研究（2020NDC067）

祝" 鵬：異構(gòu)并行計(jì)算下高維混合型數(shù)據(jù)聚類算法研究

作者簡(jiǎn)介：祝" 鵬（1987—），男，山東日照人，碩士，講師，研究方向?yàn)榍度胧郊夹g(shù)、數(shù)據(jù)分析與挖掘。