劉珊中， 郎新科

（河南科技大學(xué) 電子信息工程學(xué)院，河南 洛陽 471003）

在批量生產(chǎn)過程中，配方定義了產(chǎn)品的生產(chǎn)要求所需的信息。改變配方，相同的設(shè)備組合可以生產(chǎn)不同的產(chǎn)品，不同的設(shè)備也可以生產(chǎn)相同的產(chǎn)品，因此極大地增強了批量生產(chǎn)的靈活性，縮小了產(chǎn)品更新的周期［1］。所以在批量生產(chǎn)過程中，經(jīng)常會出現(xiàn)配方的改變，但是對于一個生產(chǎn)過程來說，配方的每次改變相當(dāng)于給控制過程增加了一個階躍干擾信號，對固定參數(shù)的控制器、軟測量儀表的精度帶來很大的影響，從而對設(shè)備和生產(chǎn)過程造成影響。考慮能否根據(jù)配方的相似度對配方數(shù)據(jù)進行聚類，只針對這幾類配方數(shù)據(jù)對控制參數(shù)進行調(diào)整，這樣只需要設(shè)置幾組參數(shù)即可，當(dāng)配方變化時，相應(yīng)的控制參數(shù)調(diào)整到最佳的值即可。

文獻［2］使用一種改進的模糊聚類的算法對配方進行分類，文獻［3］使用了概率神經(jīng)網(wǎng)絡(luò)的方法對配方進行分類，這2種辦法對于簡化的配方模型聚類都取得了很好的效果，但是簡化的配方模型并不能體現(xiàn)配方數(shù)據(jù)大規(guī)模、高維的特點。對于大規(guī)模高維的配方數(shù)據(jù)這些方法能否適用，還有待考慮。

本文使用一種改進的子空間聚類算法，能夠針對配方數(shù)據(jù)的特點進行聚類，并與以前的配方聚類算法以及傳統(tǒng)的子空間聚類對比，顯示該算法的優(yōu)越性。

1 配方模型的建立及數(shù)據(jù)預(yù)處理

1.1 配方模型的建立

在S88標(biāo)準(zhǔn)中配方包括主配方、現(xiàn)場配方、一般配方和控制配方。配方的內(nèi)容一般包括5個方面的信息：標(biāo)題（Header）、過程（Procedure）、公式（Formula）、其他信息（Other information）、設(shè)備要求（Equipment requirements）［4］。標(biāo)題包括了該配方對應(yīng)的產(chǎn)品名稱、配方制作的地點、配方制作的時間表和有效期、配方的制作人員等有關(guān)信息。過程主要是配方執(zhí)行中具體的操作步驟，如添加物料的順序等。公式包括了生產(chǎn)過程的輸入、輸出和操作參數(shù)。其他信息通常有額外的文件對配方進行闡釋，雖然這些信息并不是在生產(chǎn)過程中必須執(zhí)行的，但是也是配方發(fā)送者與接受者之間認(rèn)可的，例如合同文件、產(chǎn)品的結(jié)構(gòu)圖甚至是期望的產(chǎn)品圖片。設(shè)備要求是生產(chǎn)過程對設(shè)備的要求，例如生產(chǎn)的材料、設(shè)備的類型［3］。

為了對配方進行建模，需要對配方數(shù)據(jù)進行簡化處理，由于本文所研究的配方聚類只是針對某個批量單元過程而不是針對整個批量生產(chǎn)過程，因此配方過程可以略去，批量生產(chǎn)過程的單元設(shè)備一般是不變的，因此也可以省略，其他信息與實際的批量生產(chǎn)過程并無聯(lián)系，也可以忽略。最后簡化得到配方模型由配方名、原料、加工順序和操作參數(shù)4個要素組成，見表1所列。

表1 配方示例數(shù)據(jù)

配方中常出現(xiàn)的數(shù)據(jù)類型有：區(qū)間標(biāo)度型、二元型、標(biāo)稱型、序數(shù)型及混合型等。相似性是聚類定義的基礎(chǔ)，對大多數(shù)聚類過程而言，對來自同一特征空間的2個樣本之間的相似性度量都是必要的。由于特征的種類和范圍多種多樣，相似性量度必須根據(jù)具體情況謹(jǐn)慎選擇。

1.2 基本聚類

定義1（基本聚類） 為了處理不同的數(shù)據(jù)類型，需要對不同類型的數(shù)據(jù)做前期處理，對于連續(xù)型（區(qū)間標(biāo)度型）數(shù)據(jù)采用傳統(tǒng)的k－均值聚類算法在每一維上對所有數(shù)據(jù)對象進行聚類；對于分類型數(shù)據(jù)，根據(jù)分類數(shù)據(jù)的無序性特點，在每一維上將屬性相同的數(shù)據(jù)對象作為一個自然類。并把以上方法產(chǎn)生的每一維上的聚類稱為基本聚類，記為C1。

對于表1的配方數(shù)據(jù)，采用上述方法進行基本聚類，結(jié)果見表2所列。

表2 基本聚類表

2 一種改進的子空間聚類

2.1 算法要求及算法框架

2.1.1 算法要求

配方數(shù)據(jù)是包含了多種數(shù)據(jù)類型的大規(guī)模高維數(shù)據(jù)。傳統(tǒng)的聚類方法大多只針對數(shù)值型數(shù)據(jù)，而子空間聚類在高維數(shù)據(jù)的聚類中表現(xiàn)出了其自身的優(yōu)勢，配方數(shù)據(jù)的特點決定了一般的聚類算法很難達到配方聚類的要求［5］。

為了達到配方聚類的目的，可以借鑒傳統(tǒng)的子空間算法和針對分類數(shù)據(jù)的聚類算法，對子空間算法進行改進，使其能夠針對不同數(shù)據(jù)類型的大規(guī)模、高維數(shù)據(jù)（配方數(shù)據(jù)），可以發(fā)現(xiàn)任意形狀和不同密度的子空間，并在此基礎(chǔ)上提高子空間算法的可靠性。

2.1.2 算法框架

本文采用一種改進的子空間算法來對配方數(shù)據(jù)進行聚類。該算法使用一種新的聚類間相似度度量的方法，通過保留k最相似聚類確定子空間的搜索方向，并將子空間聚類擴展到不同的數(shù)據(jù)類型，以便能夠進行配方聚類。其算法步驟如下：

（1）每一維上找到基本聚類，將不同類型的數(shù)據(jù)轉(zhuǎn)換成相同的垂直表示方式。

（2）選擇合適的k值，為每個基本聚類找到k個最相似聚類。

（3）采用合適的局部密度閥值，根據(jù)k值確定的子空間搜索方向找到可以合并的候選，通過合并候選聚類得到子空間聚類。

（4）若結(jié)果中存在未被任何子空間聚類覆蓋的數(shù)據(jù)對象，則將根據(jù)其與現(xiàn)存子空間聚類的相似性將其分配到相應(yīng)子空間聚類中。

（5）處理剩余的數(shù)據(jù)點。

2.2 相關(guān)定義

定義2（Jaccard相似度） 給定基本聚類c1，c2∈C1，其中，c1∈Ai，c2∈Aj，且i≠j，基于Jaccard系數(shù)的相似度（δ）定義為：

其中，A＝（A1，A2，…，Ai，…，Aj，…，Am）代表一個數(shù)據(jù)維集合；A＝A1×A2×…×Am代表一個m維的數(shù)據(jù)空間；i和j表示維；分母主要用于將數(shù)值歸一化至0～1之間。

定義3（最相似聚類） 給定聚類c∈C1，c的最相似聚類 MSC（c）∈C1滿足條件：?cp∈C1，sim（c，MSC（c））≥sim（c，cp），其中，c≠MSC（c）。

定義3有助于發(fā)現(xiàn)大的聚類而忽略一些小的但又對配方有意義的聚類，且由于子空間聚類的特點，一個基本聚類中的數(shù)據(jù)對象可能被多個子空間聚類包含，因此進一步給出定義4。

定義4（k最相似聚類） 給定基本聚類c∈C1和正整數(shù)k，c的第k個最相似聚類稱為k最相似聚類，記為MSCk（c），c的第k個最相似聚類滿足：

這樣定義有助于在合并初期找到相似度最大的聚類，同時又不丟失對子空間聚類貢獻較大的基本聚類。通過給定的k值，能夠確定子空間的搜索方向。采用合適的k值就可以覆蓋整個子空間，這樣既不會忽略較小的有意義的基本聚類，又可以縮減子空間搜索。

對于表2的基本聚類，取k＝2，得到c1的最相似聚類：

定義5（子空間合并候選） 給定Sn子空間和已合并到其中的n個基本聚類c1，c2，…，cn∈C1，Sn子空間的合并候選為這n個基本聚類的k個最相似聚類的交集，記為SCn。

其中，c1，c2，…，cn為Sn子空間中已經(jīng)合并的基本聚類。

在表2中，對于子空間S2與已合并的c1、c7，給定k＝2，得到SC2＝｛c3｝。

2.3 局部密度閥值

對于給定的子空間合并候選，需要合適的標(biāo)準(zhǔn)來選擇要合并的基本聚類。在以往的子空間算法中如CLIQUE［6］中采用全局密度閥值［7］，其缺點是忽略了子空間聚類本身的特點，將其數(shù)據(jù)看作是均勻分布的，這樣會使遺漏包含數(shù)據(jù)對象較少，但是對于相對密集的配方聚類，這些空間對于配方聚類的作用是不可忽略的，對于配方數(shù)據(jù)，這樣的全局密度閥值顯然是不可取的。所以考慮不同的子空間采用不同的局部閥值。

假設(shè)th（Sm）為Sm子空間的密度閥值，nm為Sm子空間的數(shù)據(jù)對象數(shù)目：??S，假設(shè)是密集的，如果th（）≥th（Sk），則子空間Sk?是密集的。

本文根據(jù)子空間的期望密度設(shè)定子空間的密度閥值如下：

其中，m為給定值，對于配方數(shù)據(jù)一般取值為0～1。

其中，DB代表由n個位于m維特征空間的數(shù)據(jù)對象組成的集合，即Xi·Aj｝，其中，點的第j個屬性值為其在Aj維上的取值。

2.4 子空間合并

定義6（子空間合并聚類） 給定基本聚類cx，cx是Sm子空間的合并聚類的條件是：其中，左式為c1，c2，…，cm，cx之間的密度。

在表2中，對于子空間S2與已合并的c1、c7，給定密 度 閥 值 M＝0.85，則 th（S3）＝1.4，即c3為子空間S2與已合并的c1、c7的合并候選。

2.5 子空間搜索

如果子空間已沒有可合并聚類，并且當(dāng)前子空間不為結(jié)果子空間MS中任何子空間的子集，那么當(dāng)前子空間加入MS中，否則繼續(xù)子空間搜索。子空間搜索算法描述如下：

輸入：候選子空間Sp、m、k

輸出：子空間結(jié)果集

返回子空間結(jié)果集MS；

2.6 剩余點處理

在子空間搜索算法結(jié)束后，有時候會出現(xiàn)沒有分類到子空間聚類中的數(shù)據(jù)，將其稱為剩余點。計算剩余點與其相應(yīng)屬性的子空間聚類的相似度，對比設(shè)定密度閥值判斷剩余點歸為子空間聚類，還是判定為噪聲點。

3 配方聚類結(jié)果與分析

（1）構(gòu)建配方數(shù)據(jù)集。為了全面測試本文算法性能，在實驗中使用的配方數(shù)據(jù)集為人造的數(shù)據(jù)集和真實的數(shù)據(jù)集。其中人造數(shù)據(jù)集為SQL Server產(chǎn)生的多維數(shù)據(jù)集，共50維，15 000個數(shù)據(jù)對象，包括6個不同維度、不同密度的子空間聚類；其中，第3個和第5個子空間聚類數(shù)據(jù)對象分布最稀疏，且不包括全維上的聚類。實驗中真實數(shù)據(jù)集采用UCI［8］數(shù)據(jù)庫中的多維數(shù)據(jù)集zoo、Car Evaluation、Computer Hardware。其中，zoo包含101個樣本，每個樣本有17個特征；Car E－valuation包含1 728個樣本，每個樣本有6個特征；Computer Hardware包含209個樣本，每個樣本有9個特征；這3個數(shù)據(jù)集都是包含了不同類型的數(shù)據(jù)值，完全可以看作配方數(shù)據(jù)。

（2）算法的可行性分析。將本文算法與CLIQUE、SUBCLU算法在人造和真實數(shù)據(jù)集上的聚類準(zhǔn)確度作比較。通過采用取得最好聚類結(jié)果的參數(shù)，得到基于人造數(shù)據(jù)集的準(zhǔn)確度，如圖1所示。可以看出，本文算法在密度較低的第3個15維子空間和第5個25維子空間的準(zhǔn)確度均高于CLIQUE和SUBCLU算法。傳統(tǒng)的子空間聚類算法CLIQUE和SUBCLU不能夠處理分類屬性的真實數(shù)據(jù)，對比于文獻［2］、文獻［3］中的算法，本文算法聚類準(zhǔn)確度高于這2種算法，更適用于處理不同類型的數(shù)據(jù)，見表3所列。

圖1 基于人造配方數(shù)據(jù)集的準(zhǔn)確度

表3 基于真實數(shù)據(jù)的配方聚類準(zhǔn)確度 %

（3）算法的伸縮性對比。對比本文算法與CLIQUE、SUBCLU［9］、文獻［2］、文獻［3］算法在人造數(shù)據(jù)集和真實數(shù)據(jù)集上的伸縮性，圖2所示為以上5種算法對數(shù)據(jù)對象數(shù)目伸縮性的比較結(jié)果。圖3比較了5種算法對數(shù)據(jù)維數(shù)的伸縮性。可以看出，文獻［2］中算法在數(shù)據(jù)維數(shù)較低的情況下，具有非常好的聚類效果，但是隨著維數(shù)和數(shù)據(jù)個數(shù)的增加所需的時間也呈指數(shù)增長。其他4種算法與數(shù)據(jù)維數(shù)都呈線性關(guān)系，但本文算法在數(shù)據(jù)維數(shù)的伸縮性上優(yōu)于其他4種算法。

（4）參數(shù)調(diào)試。最相似聚類數(shù)k和密度閥值d2個參數(shù)的改變會對配方聚類準(zhǔn)確度造成影響。圖4給出k取不同值時對配方聚類準(zhǔn)確度的影響，隨著k值的增大，聚類準(zhǔn)確度有所改善，對于文中的配方數(shù)據(jù)，當(dāng)k值在15～20之間時，可以達到最好的聚類精度。圖5反映了密度閥值對聚類準(zhǔn)確度的影響，當(dāng)d取值在0.80～0.90之間時，算法能夠取得最好的聚類效果。

圖2 數(shù)據(jù)對象數(shù)目的伸縮性對比

圖3 數(shù)據(jù)維數(shù)的伸縮性對比

圖4 參數(shù)k對聚類準(zhǔn)確度的影響

圖5 參數(shù)d對聚類準(zhǔn)確度的影響

4 結(jié)束語

在批量生產(chǎn)過程中，配方聚類有助于提高批量生產(chǎn)過程的產(chǎn)品更新周期，避免產(chǎn)品更新時重新對配方進行處理，并且可以降低配方切換時對固定參數(shù)的控制器和軟測量儀表帶來的影響。由于配方數(shù)據(jù)是包含不同數(shù)據(jù)類型的大規(guī)模高維數(shù)據(jù)，而傳統(tǒng)的聚類算法很難處理這種數(shù)據(jù)類型，本文提出一種基于子空間的聚類改進算法，實驗仿真結(jié)果表明，對比于傳統(tǒng)的高維數(shù)據(jù)子空間聚類算法，本文算法提高了子空間聚類的精度和伸縮性。對比于前人的配方聚類算法，本文算法更適合于高維的大規(guī)模配方數(shù)據(jù)。

［1］ANSI／ISA－S88.01－1995，Batch Control Part 1：Models and Terminology［S］.

［2］侯迪波，張光新，周澤魁，等.間歇生產(chǎn)過程配方的模糊聚類方法［J］.江南大學(xué)學(xué)報：自然科學(xué)版，2005，4（2）：33－38.

［3］陳曉芳，劉珊中.基于概率神經(jīng)網(wǎng)絡(luò)的批量生產(chǎn)過程配方分析［J］.化工及自動化儀表，2010，37（7）：24－27.

［4］ANSI／ISA－S88.02－2001，Batch Control Part 2：Data Structures and Guidelines for Languages［S］.

［5］Chen X，Ye Y，Xu X，et al.A feature group weighting method for subspace clustering of high－dimensional data［J］.Pattern Recognition，2012，45（1）：434－446.

［6］Duan Dongsheng，Li Yuhua，Li Ruixuan，et al.Incremental K－clique clustering in dynamic social networks［J］.Artificial Intelligence Review，2012，38（2）：129－147.

［7］Liu Guangcan，Lin Zhouchen，Yan Shuicheng，et al.Robust recovery of subspace structures by low－rank representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（1）：171－184.

［8］Wagstaff K，Cardie C，Rogers S，et al.Constrained k－means clustering with background knowledge［C］／／18th International Conference on Machine Learning （ICML 2001），2001：577－584.

［9］Amir A，Lipika D.Ak－means type clustering algorithMfor subspace clustering of mixed numeric and categorical datasets ［J］.Pattern Recognition Letters，2011，32（7）：1062－1069.