融合多維屬性相似度的云制造服務譜聚類算法

黃 雯，胡 強，任志考

(青島科技大學 信息科學技術學院，山東 青島 266061)

0 引 言

隨著云計算、大數據等新一代信息技術與先進制造技術的融合，云制造作為一種新的模式應運而生[1]。在云制造環境下，資源提供方將自身擁有的加工設備資源或制造能力通過虛擬化、服務化的方式發布到云制造平臺[2]。用戶可以在平臺中尋找所需要的云制造服務，通過租用這些云制造服務來實現超出自身制造能力的業務需求，以一種低成本代價的方式彌補業務制造能力的不足，從而提高企業競爭力。

相比普通云服務，云制造服務的屬性參數數量更多，參數的取值類型較為豐富，不僅有短文本類型的功能描述，也有數值型的工藝屬性參數。在同一類云制造服務中，不同屬性的取值通常也會跨越多個數量級。在查找云制造服務時，不僅要考慮服務的功能描述，也要同時兼顧制造工藝參數屬性值的約束，因此，從大量功能相似的云制造服務中發現適合用戶需求的云制造服務難度大、效率低。

服務聚類可將服務按照功能的相似性劃分為若干個簇，縮減搜索空間，有效提高服務查找速度[3]。目前，直接以云制造服務作為聚類對象相關研究成果仍然較少，有關工作主要關注制造設備或資源的聚類，例如，高新勤等對k-means算法進行改進，提出了基于相似度的加工設備云服務聚類方法，利用可拓論建立了服務請求與云服務類簇的物元模型，實現服務供給與服務請求的快速匹配[4]。辜振譜等將馬氏距離引入到密度峰值聚類算法的密度中心測定中，基于改進密度峰值聚類算法實現航空發動機故障診斷，所提出算法在故障特征的分類與識別上均優于K均值聚類和模糊C均值聚類[5]。郝予實等提出基于場景識別的云制造服務推薦模型，該模型重構服務組合描述的功能信息，對服務組合進行應用場景的服務聚類，為各場景建立加權庫進行服務推薦，該方法在推薦效果上有很大提升[6]。

以K-means++、層次聚類等為代表的聚類方法因實現簡單且聚類效果良好而得到廣泛應用，但這些方法多適用于線性分布的數據樣本空間。云制造服務存在多個維度的功能和屬性特征描述，且這些特征描述所采用的數據類型種類較多，數據取值差異大，因此，云制造服務在聚類時構成非線性數據樣本空間，上述聚類算法在對云制造服務聚類時效果不理想，算法容易陷入局部最優。為了更高質量地實現云制造服務聚類，選取能夠識別任意形狀樣本空間且能快速收斂于全局最優解的譜聚類算法作為云制造服務聚類算法。

為了充分利用云制造服務所擁有的多維屬性約束信息來提高聚類質量，本文提出一種基于改進譜聚類的云制造服務聚類算法。針對文本型和數值型服務屬性參數，分別構建相似度計算方法，并提出一種適用于文本型和數值型相似度矩陣融合函數，實現云制造服務多維屬性相似度的融合計算，引入服務相似矩陣的本征間隙確定聚類個數，提高譜聚類的聚類數量確定的合理性，進而實現高質量的云制造服務聚類。

1 云制造服務的相似度計算

云制造服務S定義為三元組S={n，SF，SQ}， 其中，n為服務的名稱，SF表示服務的功能屬性集合，SQ表示服務的非功能屬性集合。

不同類型的云制造服務在工藝流程、制造參數和性能上存在差異，難以統一給出SF和SQ的具體屬性參數組成，通常情況下，有關工藝流程和制造參數方面的屬性在SF中刻畫，SQ則由云制造服務性能層面的屬性組成，以某服務商提供的輪胎結構加工服務為例，SF和SQ的構成參數見表1。

表1 輪胎結構加工服務信息

1.1 文本型屬性相似度計算

云制造服務描述中，各類屬性的取值通常可以劃分為文本型和數值型兩類。文本型屬性主要包含加工對象、功能描述、類別、隸屬行業、材質等信息的描述，這些屬性值中既有段落級別的短文本，也有單個名詞或詞組。為精確地獲取服務的功能語義，本文采用GSDMM對段落級短文本信息提取主題向量，對于單個名詞或詞組，則采用Word2Vec生成對應的文本向量，然后利用上述向量求解對應屬性的相似度，將所有文本型屬性相似度的平均值作為兩個服務之間的文本型屬性的最終相似度。

對于屬性值為單詞或組詞的文本屬性，利用Word2vec生成詞向量。Word2vec分為兩種模型：CBOW和Skip-Gram，本文采用Skip-Gram模型，Skip-Gram模型是通過特定詞來預測上下文，生成詞向量[7]。Skip-Gram模型定義詞出現概率p(wo|wc)， 其計算方法參見式(1)

(1)

式中：wo，wc分別代表上下文詞和中心詞，vc表示中心詞的詞向量，uo代表上下文詞的詞向量，ui表示除中心詞以外第i個單詞的詞向量，V表示全體詞庫。Skip-Gram模型訓練函數如式(2)所示

(2)

此處，c是上下文窗口大小。

對于段落級別短文本描述的屬性值，采用GSDMM生成描述文本的主題向量。GSDMM模型是一種無監督主題概率模型，該模型基于狄利克雷混合模型(DMM)生成文檔，然后采用吉布斯采樣(Gibbs Sampling)求解模型[8]，能夠快速獲取文本集中每個文本的潛在主題。GSDMM模型中由文檔得到主題的概率為式(3)

(3)

(3)對文檔集中的所有文檔初始化完成后，得到K個屬于不同主題的集合，且每個文檔只屬于一個主題。

(5)重復步驟(4)，直到i大于最大迭代次數。

在為段落級文本屬性值生成向量時，首先借助Python工具包對文本進行分詞、去停用詞、還原詞干等操作，通過GSDMM為每個段落級別的短文本屬性值生成一個主題向量。再利用Word2Vec和GSDMM將全部文本類型的屬性值生成對應的向量后，可通過余弦夾角公式計算兩個服務對應屬性文本值之間的相似度，兩個服務最終的文本屬性值相似度定義為所有服務所有文本屬性值相似度的均值，具體參見定義1。

定義1TA={t1，t2，…，tn} 和VTA={vt1，vt2，…，vtn} 分別是云制造服務si和sj的文本屬性集合與屬性值對應的文本向量集合，即?ti∈TA，vti為ti對應的屬性文本值生成的向量，si和sj的文本屬性值相似度定義為

(4)

表2給出5個云制造服務的文本型屬性，在依據文本類型的屬性值生成對應的向量后，參考定義1計算兩個服務的文本型屬性相似度，構建了云制造服務的文本型相似度矩陣SM_T

表2 云制造服務文本型屬性信息

1.2 數值型屬性相似度計算

表3給出表2中5個云制造服務所對應的數值型屬性，為了能夠使用這些參數進行服務聚類，首先對這些參數按照類別采用“最大-最小標準化”方式進行歸一化。歸一化后的各個屬性參數值均在區間[0，1]內，兩個服務的數值型屬性相似度計算方法參見定義2。

表3 云制造服務數值型屬性信息

定義2si和sj是一組云制造服務中的兩個服務，NA={t1，t2，…，tn} 和NNA={nt1，nt2，…，ntn} 分別是服務si和sj的數值型屬性集合與屬性值對應的歸一化數值集合，即?ti∈NA，nti為ti對應的歸一化后的屬性值，si和sj的數值型屬性值相似度定義為

(5)

從定義2可知，兩個服務的數值型屬性之間的相似度通過融合冪指函數的歐式距離計算得到。在計算時，首先將屬性值進行了歸一化，然后將歸一化后的屬性值作為樣本數據，利用歐式距離公式計算兩個服務的歐式距離。由于歐氏距離的值越小，樣本數據越相似，因此引入冪指函數將歐式距離正向映射為服務之間的數值型屬性相似度。

利用表3中的5個服務的數值型屬性，構建了服務s1～s5的服務-數值型屬性矩陣(SNA_M)，將其歸一化后可得矩陣SNA_NM，利用定義2可以計算獲得服務s1～s5的數值型屬性相似度矩陣SM_N

1.3 云制造服務相似度計算

為了能夠使用譜聚類算法對云制造服務進行聚類，需要將云制造服務的文本型屬性相似度矩陣SM_T與數值型屬性相似度矩陣SM_N進行融合，構建云制造服務相似度矩陣SM。本文構建如式(6)所示的矩陣融合函數實現SM_T與SM_N的融合

(6)

算法1給出了如何求解云制造服務集合中兩個服務相似度的算法。第(1)行獲取集合S中的服務個數，以及該服務集合中服務的屬性數量。算法(2)至(8)行，分別獲取服務的每一個屬性，通過valtype()函數判定屬性的類型。若屬性值為短文本類型則采用GSDMM為其訓練文本向量，若屬性值為單詞或詞組，則采用Word2Vec生成單詞的向量；若屬性值為數值型，則對該集合中所有服務進行屬性值的歸一化。算法第(9)至(14)行用于構建服務的文本型屬性相似度矩陣SM_T和數值型服務相似度矩陣SM_N。對于給定服務si和sj，在進行文本型屬性相似度和數值型屬性相似度計算時，分別采用定義1中的TS(si，sj) 和定義2中的NS(si，sj)。 算法第(15)行利用式(6)實現文本型屬性相似度矩陣SM_T和數值型服務相似度矩陣SM_N的融合，最終返回集合S中服務的相似度矩陣SM。

算法1：CAL_ServiceSim

輸入：the set of Cloud serviceS

輸出：Service similarity matrixSM

(1)m=|S|,n=|S.TA|+|S.NA|;

(2)fori=1 tom

(3)fori=1 ton

(4)ifthe valtype(ti) is a word or phrase, trainvtiby Word2Vec;

(5)ifthe valtype(ti) is short text, trainvtiby GSDMM;

(6)ifthe valtype(ti) is numerical value, normalized it to getnti;

(7)endfor

(8)endfor

(9)fori=1 tom

(10)forj=1 tom

(11) compute theTS(si,sj) and build the similarity matrix for text-type attributesSM_T;

(12) compute the NS(si,sj) and build the similarity matrix for numeric attributesSM_N;

(13)endfor

(14)endfor

(15)generate service similarity matrixSMbased onSM_TandSM_Nby formula (6);

(16)returnSM;

本節為云制造服務中文本型和數值型屬性分別建立了相似度計算方法，在此基礎上設計了一種多維度屬性相似度融合策略，實現了云制造服務相似度的計算，全面有效刻畫云制造服務資源間的差異性，從而更精確地實現聚類。

2 基于本征間隙的云制造服務譜聚類算法

譜聚類算法是從譜圖劃分理論演化而來的，譜聚類算法可以歸納為以下3個步驟：①構造數據集的相似矩陣；②計算矩陣的特征值和特征向量；③利用聚類算法對特征向量進行聚類。

分布式能源行業能效高、低排放、技術密集決定了其投資高，再加上承擔園區供熱管網建設，以及主要設備燃機屬高端制造業，國產化進程有待時日，行業投資高于燃煤發電。

傳統的譜聚類算法能夠對數據進行較為精確的聚類，但仍有很多不足之處[9]。例如，在第(1)步構造相似矩陣時，通常采用高斯核函數來確定相似矩陣，相關參數需要人為設置，并需反復調試才能確定最優值。在第(3)步中需要人為指定聚類個數，造成聚類數量受人為主觀因素影響較大。

針對上述問題，在算法1中提出了一個多維屬性相似度計算與融合方法，提出了一種適用于云制造服務的相似度矩陣構建方法，解決了傳統高斯核函數在計算云制造服務相似度時的不足。本節引入本征間隙來確定聚類的個數，彌補傳統譜聚類算法中人為確定聚類數量的不足。根據矩陣的擾動理論，計算數據之間的本征間隙，自動計算聚類個數。

在云制造服務相似矩陣SM基礎上構建度矩陣D，在度矩陣D中，對角線元素的值為相對應行的元素值總和，非對角線元素上的值為0。在度矩陣的基礎上參照文獻[16]中的式(11)構造規范型拉普拉斯矩陣L

假設規范型拉普拉斯矩陣L存在n個特征值λ=[λ1，λ2…λn]， 對上述求得的特征值按由大到小進行排序，排序后的特征值為λsort=[λ1≥λ2≥…≥λn]， 上述L對應的λ和λsort分別為

λ=[0，0.789 626 48，0.887 051 8，0.858 900 5，0.848 123 38]
λsort=[0.887 051 8，0.858 900 5，0.848 123 38，0.789 626 48，0]

本征間隙序列定義為 {g1，g2，…，gn-1|gi=λi-λi+1}， 在序列中尋找第一個極大值gi，該值的索引i為聚類的個數k[10]

g=[0.028 151 3，0.010 777 12，0.058 496 9，0.789 626 48]

上述序列中第一個極大值為g3，g3-g1>0，g3-g2>0，g3-g4<0，第一個極大值所對應的索引為3，所以聚類個數k為3。在此基礎上，構建融合多維屬性相似度的云制造服務譜聚類算法，具體參見算法2。

算法2：FMA_SC

輸入：Cloud manufacturing service similarity matrixSM；

(1) construct degree matrixDforSM

(2) compute canonical Laplace matrixL

(3) obtain the eigenvalues of normalized Laplacian matrix

(4) sort the eigenvalues byλ1≥λ2≥…≥λn

(5)fori=1 ton-1

(6) compute eigengap sequencegi=λi-λi+1

(7)endfor

(8)fori=1 ton

(9) find the first argmin {gi-gj,j0&gi-gi+1<0}

(10)endfor

(11) assign the number of clusterskasi

(12) calculate the firstkmaximum eigenvectors [Xi,X2,…,Xk]

(13) cluster eigenvectors [Xi,X2,…,Xk] by K-means++

(14) returnkservice clusters

算法2中第(1)行計算云制造服務相似度矩陣SM的度矩陣D。度矩陣D對角線上元素的值D(i，i) 為服務相似度矩陣SM第i行元素之和，其余元素設置為0。第(2)行到第(3)行構建規范拉普拉斯矩陣并計算出該矩陣的特征值。第(4)行將特征值按由大到小進行排序。第(5)行到第(7)行，計算本征間隙序列 {g1，g2，…，gn-1|gi=λi-λi+1}。 第(8)行到第(11)行在本征間隙序列中尋找第一個極大值gi，該值所對應的索引i為聚類的個數k。第(12)行計算前k個特征值對應的特征向量，構造特征向量矩陣。第(13)到第(14)行對向量矩陣采用K-Means++算法進行聚類，得到k個服務類簇。

3 實驗與分析

從航天云網、卡奧斯工業互聯網平臺等知名云服務平臺爬取有關制造加工類服務2215條，從中選擇1892條數據描述較為完備的云制造服務用于實驗驗證，實驗機器配置采用i7-8750H處理器，Windows10操作系統，16 GB內存，利用PyCharm程序進行編寫。采用聚類評價中的常用指標CH、SC、NMI、FMI作為本文服務聚類實驗的性能評估指標，相關指標定義參見文獻[11]。所有實驗均開展10輪次，取所有輪次實驗的平均值作為最終聚類效果的對比值[12]。

本文方法FMA-SC對比了4種近年來發表的譜聚類改進算法，在構建的數據集上進行聚類，通過上述4種指標對比算法的性能。

(1)NHASC算法[13]：一種適用于非線性高維數據的譜聚類算法，將數據映射到隨機特征空間，把非線性數據映射為非線性數據，然后使用譜聚類算法進行聚類，解決非線性高維數據的聚類問題。

(2)SC_SD算法[14]：一種自適應譜聚類算法，避免樣本點的局部尺度參數受噪音點的影響，將樣本的鄰域標準差作為譜聚類的局部尺度參數，構建服務相似矩陣進行聚類。

(3)SCTSCI算法[15]：提出了一種混合型數據的度量方式，構造尺度參數自適應的核函數來構建相似矩陣，并在譜聚類中運用集成K-means算法增加算法穩定性。

(4)FITS-MSC算法[16]：設計了一種細粒度相似性融合策略來獲得最終的一致性親和矩陣。在融合過程中，探索了局部視圖間和全局視圖內的權重關系，采用稀疏子空間聚類來構造初始相似矩陣。

圖1中的CH指標和圖2中SC指標是聚類內部評價指標，從聚類的中心點距離、內部結構凝聚度等層面對服務聚類的質量進行評價。從圖1中數據可以看出，本文算法FMA-SC的CH指標得分值顯著優于NHASC、SC_SD和FITS-MSC算法，文獻[15]中的SCTSCI算法得分值略高于FMA-SC算法。此外，從圖2中的數據可以看出，本文方法在SC評價指標獲取的分數得到大幅提高，從分值上看，文獻[16]中的FITS-MSC算法的得分值最高，略優于本文方法。此外，本文算法SCTSCI性能優于NHASC、SC_SD和STSCI算法，相比其它指標提升幅度均超過40%。因此，從聚類質量的內部評價指標看，本文所提出的FMA-SC方法顯著優于已有譜聚類算法。

圖1 譜聚類類型算法的CH指標對比

圖2 譜聚類類型算法的SC指標對比

圖3和圖4所示數據對比為聚類外部評價指標NMI和FMI在不同方法中的評分，可以看出本文方法FMA-SC均優于其它方法，相比其它4種方法，本文方法在NMI和FMI性能分別平均提升了約37%和55.8%。

圖3 譜聚類類型算法的NMI指標對比

圖4 譜聚類類型算法的FMI指標對比

除與改進譜聚類算法進行對比，FMA-SC算法還與其它非譜聚類型算法進行了對比，主要對比算法如下：

(1)K-means算法[4]：該算法對加工設備的制造屬性進行描述，改進了K-means算法隨機選取初始聚類中心和聚類數目的不足，提出一種基于相似度的加工設備云服務K-means聚類方法。

(2)E-DBSCAN算法[17]：采用LDA-DBSCAN算法進行聚類，首先基于改進的LDA算法挖掘發現隱含數據，提取數據資源特征，解決數據資源無法映射到一個向量空間問題，采用DBSCAN算法進行聚類。

(3)LDA-FCM算法[18]：提出一種基于LDA-FCM方法的Web服務發現聚類方法，該算法使用LDA模型進行Web服務資源數據的重組和自適應調度，以提取web服務數據資源特征，依據數據資源特征確定其相似度，在FCM算法中，通過相似度計算隸屬度，實現web服務聚類。

各個指標的對比結果如圖5～圖8所示。從圖5中數據可以看出，本文算法FMA-SC的CH指標得分值顯著優于K-means、E-DBSCAN和LDA-FCM算法，在CH評價指標獲取的分數得到大幅提高，平均提升了35%。此外，從圖6的數據中SC指標可以看出，E-DBSCAN算法的得分值最高，其次是本文FMA-SC算法，FMA-SC算法在SC指標上優于K-means算法和LDA-FCM算法，本文FMA-SC算法與 K-means、E-DBSCAN、LDA-FCM算法相比，在SC性能上平均提升了31%。從聚類質量的內部評價指標看，本文所提出的FMA-SC方法顯著優于已有的聚類算法。

圖5 非譜聚類類型算法的CH指標對比

圖6 非譜聚類類型算法的SC指標對比

從算法運行的時間復雜度來看，NHASC算法時間復雜度為O(n×D)， 其中n為數據個數，D為數據空間維度。SC_SD算法時間復雜度為O(n2)， SCTSCI算法時間復雜度為O(n3)， FITS-MSC算法的時間復雜度為O(t(dmaxn2+n3))，dmax表示數據維度，t表示迭代次數。本文算法FMA-SC的時間復雜度為O(n2)， 在5個算法中并列排名第二，時間復雜度較低。

從圖7和圖8中的數據可以看出，FMA-SC算法在NMI和FMI指標上均優于K-means、E-DBSCAN、LDA-FCM聚類方法，在NMI和FMI性能上，本文提出的方法與文獻[17]中的方法在評分上較為接近。相比于其它3種方法，本文方法在NMI和FMI性能上分別平均提升了31%和36%。因此，從聚類質量的外部評價指標看，本文所提出的FMA-SC方法顯著優于已有的其它聚類算法。

圖7 非譜聚類類型算法的NMI指標對比

圖8 非譜聚類類型算法的FMI指標對比

K-means算法計算云服務之間的綜合相似度，構造服務相似矩陣的時間復雜度為O(n2)，n為數據個數，對數據進行處理的時間復雜度為O(nm)，m表示云服務屬性個數，獲取最佳聚類個數的時間復雜度為O(q2)，q代表類簇個數，該算法綜合時間復雜度為O(n2)。 E-DBSCAN算法對數據集的每個對象進行考察，通過檢查檢查每個點的鄰域進行聚類，該算法時間復雜度為O(n×logn)。 LDA-FCM算法提取數據特征、初始化隸屬度函數、確定聚類中心時間復雜度為O(n2)， 優化隸屬度函數的時間復雜度為O(tn)，t為迭代次數，該算法綜合時間復雜度為O(n2)。 本文算法與上述算法相比，時間復雜度處于同一個級別。

從聚類內外部評價指標評分可以得到：本文方法所構建的云制造服務聚類的質量顯著優于其它聚類方法，因此，本文所提出的融合多維相似度的云制造服務聚類方法可以有效提升云制造服務聚類的質量。

4 結束語

本文提出一種融合多維屬性相似度的云制造服務譜聚類算法。分別構建了云制造服務的文本型和數值型屬性相似度矩陣，設計了一種相似度矩陣融合函數，將上述兩種矩陣融合，通過融合多維度信息提升了云制造服務的相似度計算精度。引入本征間隙法確定聚類個數，采用的譜聚類算法可以高質量地實現具有非線性樣本特征的云制造服務聚類。實驗驗證，本文方法的聚類質量明顯優于當前流行的譜聚類改進算法和其它類型的服務聚類算法。

未來工作主要是結合服務描述文本的語境權重進一步提高文本型屬性相似度的計算精度，并在服務聚類的基礎上研究相關推薦方法，以進一步提高服務發現的準確度和效率。