基于非負矩陣分解的產品結構相似性判斷及其應用

徐新勝　王　誠　肖　穎

中國計量學院，杭州，310018

?

基于非負矩陣分解的產品結構相似性判斷及其應用

徐新勝王誠肖穎

中國計量學院，杭州，310018

為了快速發現可重用產品結構，提出了基于非負矩陣分解的產品結構相似性判斷方法。通過將產品結構鄰接矩陣轉化為鄰接向量，構建包含全部結構信息的庫矩陣；利用Multiplicative Updates(MU)算法對庫矩陣進行非負矩陣分解，實現以低維空間向量描述的產品結構；在此基礎上，通過計算低維向量的歐氏距離，可以判斷產品結構之間的相似性；最后通過實例對所提出原理和方法進行了驗證，結果表明，該方法比目前的相似性判斷方法更高效。

產品結構；非負矩陣分解；相似性；歐氏距離

0　引言

大規模定制生產中，針對客戶定制的產品，從企業的產品庫中找到相似的模型或產品結構，加以充分利用，可以降低定制企業的成本、縮短交貨期。因此，相似性研究受到了國內外專家與學者的廣泛關注。成組技術[1]是一種傳統的相似性分析方法，通過分類編碼將零件歸類，或將產品結構歸為一族。此外，基于功能特征的相似性分析[2-3]和面向形狀的相似性分析[4-7]在設計、制造領域也得到了應用。

產品結構是企業在長期設計、制造過程中形成的結構性數據，能夠體現出復雜產品的零部件組成情況與關聯關系[8]，所以，以此為對象的相似性研究也逐漸引起了關注。丘宏俊等[9]基于XML文檔結構相似性判定方法，提出了綜合結構操作類型及其成本、節點位置等信息的產品結構相似性計算模型，并在飛機制造中得到應用。Romanowski等[10]基于產品結構，提出了最小加權對稱差的分析方法，將一類無序的產品結構樹歸類到產品族中。Tsai等[11]提出了基于構件匹配算法和模糊模式組合的產品結構相似性判定方法。

然而，上述方法在研究產品結構相似性時，并沒有考慮產品結構中節點之間的數量約束關系。對此，Shih[12]提出了基于正交Procrustes分析的產品結構相似性判定方法，并將其應用于產品結構聚類。但這種方法需要對產品結構的鄰接矩陣進行奇異值分解，因此，在產品中零部件較多時，將會導致計算過程步驟多、計算量大，其實用性受到一定限制，并且處理過程比較抽象，無法直觀地反映產品之間的相似性關系。

非負矩陣分解算法具有易于實現、存儲空間小，而且能夠有效地保持數據的非負性等特點[13]，本文基于此提出產品結構相似性判定方法，目的是在簡化計算步驟的基礎上，進一步提高相似性判定的高效性，豐富相似性計算結果的內涵。

1　產品結構相似性與非負矩陣分解

1.1產品結構描述及其相似性分析

通常，產品采用具有層次的結構來描述。產品結構中，節點表示產品部件或者零件，邊表示零部件之間的裝配或者隸屬關系，如圖1所示，從上到下，同一條邊上面的點代表父件，下面的點稱為子件，圖1中的部件a既是c的父件，又是o的子件。邊旁邊的數字表示生產單位父件時所需子件的數量。

圖1　產品結構

對于圖1描述的產品結構，其對應的鄰接矩陣如下：

oabcdefghi

大規模定制生產中，針對客戶的產品定制需求(通常對應一個虛擬的產品結構)，怎樣從定制企業的產品庫中找到最合適的產品實例或者產品模型，充分重用其零部件在設計、制造、質量、管理等方面的數據和信息，對于降低大規模定制產品的生產成本、縮短交貨期，具有重要的意義。

通常，企業的產品庫中會有多個產品實例或者模型待選，對這些產品實例或模型進行統一比較，依照相似性大小排序，可以有效簡化產品結構相似性分析和計算過程，提高效率。為實現這個目標，本文提出基于非負矩陣分解(non-negative matrix factorization，NMF)的產品結構相似性判定方法。

其中，P(*，k)為矩陣P的第k個列向量;qki是矩陣Q的第k行第i列的元素。上述等式表明βi被從m2維的空間映射到r維空間中(m2

產品結構被定量地表示到這個低維空間中，于是，通過計算目標產品結構與各查詢產品結構對應的低維向量之間的距離便可以來判斷產品結構相似性。

1.2非負矩陣分解基本原理

非負矩陣分解最初由Paatero等[14]于1994年提出，現在已在文本分類、圖像分析、復雜網絡等方面得到廣泛應用，與其他矩陣分解(奇異值分解、特征值分解)類似，非負矩陣分解也實現了線性的維數約簡，但要求分解后的所有分量均為非負實數，這種分解方式符合直觀理解：整體是由部分組成的[15]。因此，它能夠在某種意義上抓住產品結構數據的本質[13]，這種特性表明，采用非負矩陣分解后的降維數據保留了原有產品結構的本質特征。

下面對非負矩陣分解問題的基本原理進行說明。不失一般性，假設G=[gij]p×q(gij>0)是任意給定的非負矩陣，非負矩陣分解算法的目標便是尋找兩個非負矩陣Wp×r=[wij]p×r和Hr×q=[hij]r×q，使得

Gp×q=[γ1γ2…γq]p×q=WH=

(1)

其中，矩陣G首先表示為列向量的形式，γi為組成矩陣G的第i列向量(i=1，2，…，r)。

當原有矩陣G的各列即γi線性無關時，以這q個向量為基可以張成一個線性空間Vq。非負矩陣分解的運算就是把γi從q維線性空間Vq映射到W各列向量張成的r維線性空間Vr中。設

實際計算中，非負矩陣分解問題可以描述成數學模型：

(2)

式中，‖*‖F為矩陣的F-范數。

基于Multiplicative Updates(MU)算法[16]，W和H分別計算如下：

(3)

(4)

其中，(GHT)ia表示矩陣G和HT相乘后，所得矩陣的第i行第a列元素。式(3)、式(4)描述了一個迭代-更新過程，即每一次更新W和H中的元素，均利用原有的W和H進行運算，研究表明，這種算法是收斂的[16]。

實際生產中，企業為了減少產品數據冗余，現有產品結構之間不能相互組合而成，因此組成庫矩陣S的各列βi線性無關，這滿足非負矩陣分解中原有矩陣各列向量線性無關的條件，因此該方法可以用來解決前文所述的產品結構相似性判斷問題。

對應問題的描述為求解矩陣P=[pij]m2×r和Q=[qij]r×(n+1)，使得S=PQ，基于MU算法，產品結構的非負矩陣分解及其相似性判定流程如圖2所示，圖中，I表示迭代總次數，不同的問題中，使‖S-PQ‖F在迭代過程中達到穩定所需的次數不盡相同，因此I的選取需要依據具體問題而定。因為該算法的分解結果與P、Q初始值的選取有關，因此，在實際計算過程中，一般重復多次計算矩陣分解過程，從中選取使‖S-PQ‖F最小的分解作為最終結果。

圖2　相似性判定算法流程

2　產品結構相似性判定的應用

為了驗證非負矩陣分解方法的適用性，本文以文獻[12]中某系列電燈的結構數據(圖3～圖11)為對象，表1說明了編碼對應的產品零部件名稱。圖3～圖11中連線旁邊的數字表示生產一個父件所需要的子件數量。客戶定制產品結構為S1，而D1～D8是企業現有產品的實例結構。企業設計人員需要從查詢產品結構(企業現有產品結構)找出與目標產品結構(客戶定制產品結構S1)最相似的產品結構，通過重用降低定制產品生產成本，縮短交貨期。

圖3　定制產品結構S1

圖4　現有產品結構D1

圖6　現有產品結構D3

圖7　現有產品結構D4

圖8　現有產品結構D5

圖9　現有產品結構D6

圖10　現有產品結構D7

圖11　現有產品結構D8

編碼名稱編碼名稱B1007″基礎部件B1018″基礎部件S10014″黑色燈罩S10115″白色燈罩S10215″乳白色燈罩A100單孔電源部件A101三孔電源部件1100軸端12007″直徑鋼板12018″直徑鋼板1300轂14001/420螺絲1500持釬器1600單孔接口1601三孔接口1700連線部件21003/8″鋼管220016表燈線2300標準插頭引出端

以目標產品結構S1為例，按照如表2所示的零部件排列順序，構建鄰接矩陣Zs=[zij]20×20，根據圖3所示的S1產品零部件關系以及權重，可知單個部件B100需要4個子零件1400。因為表2中部件B100的順序為2，零件1400的順序為13，所以Zs中元素z2(13)=4。依此表示方法類推可知，z12=z14=z17=z29=z2(10)=z2(12)=z7(14)=z7(15)=z7(17)=1，z9(18)=26，Zs中的其余元素均為零。

表2　零部件排列順序

其他產品結構的鄰接矩陣構建方法與此類似，不再贅述。接著按照前文所述，便可得到庫矩陣S400×9。令r=3，于是庫矩陣S400×9被分解為P400×3Q3×9的形式。在MATLAB軟件中對算法編程實現，計算得矩陣Q：

矩陣Q中各列表示降維后各產品結構在三維空間中的坐標，其中，第1列表示目標產品結構，其余各列分別表示查詢產品結構。分別計算矩陣Q中第1列即[0.11740.00320.1264]T，與第2列至第9列的歐氏距離，即目標產品結構與查詢產品結構的相似性，列向量之間的距離越小表示對應的產品結構之間越相似，結果如表3所示。

表3　目標產品結構與查詢產品結構之間的相似性結果

從表3中可以看出，查詢產品結構S1與目標產品結構D1最相似，D6、D8則最不相似，該結果與文獻[12]的方法計算結果相同。定制企業將會把產品結構D1及其零部件相關信息調出，實施資源重用，以減少定制企業在設計、管理等方面的工作。

3　算法分析與管理內涵

非負矩陣分解方法主要是通過降維來實現快速相似性計算，因此具體降維的維度對于產品結構的相似性計算具有重要的影響。為此，在計算r分別為1、2、4、5時相似性計算結果、矩陣分解所引起的差異E=‖S-PQ‖F以及算法運行時間，并與前文(r=3)的結果作比較，如表4所示。

表4　r=1，2，3，4，5時相似性計算結果及程序運行時間

注：η為產品結構相似度。

從表4中可以發現，在計算產品結構之間的相似性時，為了找出最相似的查詢產品結構，所選取的r不能過小。因為r過小會導致E偏大，即分解后的矩陣并不能完整描述原有產品結構，例如r=1，2時的計算結果差異較大，無法判斷出最相似的結構產品。r較大時，需要更多的迭代計算步驟和時間，如表4最后一行所示。因此，在滿足工程需求的情況下，企業可以根據生產和經營目標，選取合適的r作為相似性計算的降維目標。

同時，從表3中可以看出，文獻[12]雖然采用了兩種相似性度量方式，卻無法判斷出D1、D3、D4與目標產品S1相似度的差異，通過觀察可以發現，事實上D1較D3、D4更相似于S1。本文提出的方法在確保D1、D3和D4相對于其他產品與S1更相似的基礎上，對這三者的相似度進行了區分：D1最相似，D4次之，使結果更為合理。

此外，與文獻[12]相比，本文提出的方法不但計算過程簡化、結果更為合理，而且相似性計算結果具有更廣的應用范圍，由于上述矩陣Q包含了所有產品結構降維后在三維空間中的坐標，如表5所示。

表5　產品結構降維后在三維空間的坐標

上述三維坐標可以直觀地反映在三維空間圖中，于是，產品設計人員通過分析三維空間圖中各點之間距離的遠近，不僅能夠直觀、有效地發現與目標產品結構最相似的查詢產品結構，以實現實例庫產品結構重用，而且可以發現各查詢產品結構之間的相似性程度，為實現相似產品結構實例融合、減少實例庫冗余作準備。文獻[12]提出的方法則只能夠用于判斷目標產品結構與各個查詢產品結構之間的相似程度，不能同時發現查詢產品結構之間的相似性關系，因此其應用范圍具有局限性。

4　結論

(1)給出了基于非負矩陣分解的產品結構相似性計算的思路及其數學描述。

(2)通過非負矩陣分解，實現了產品結構降維，簡化了計算過程。

(3)本文提出的相似性計算方法不但計算比現有方法更加簡單，而且產品結構之間的相似度更加容易區分，還便于設計人員發現查詢產品結構之間的相似性。

[1]ElMaraghyH，SchuhG，ElMaraghyW，etal.ProductVarietyManagement[J].CIRPAnnals-ManufacturingTechnology，2013，62(2)：629-652.

[2]BhattaSR，GoelAK.FromDesignExperiencetoGenericMechanisms：Mode-basedLearninginAnalogicalDesign[J].ArtificialIntelligenceforEngineeringDesignAnalysisandManufacturing，1996，10(2)：131-136.

[3]貢智兵，李東波，于敏健.基于產品功能樹的實例推理研究[J].中國機械工程，2006，17(2)：123-126.

GongZhibing，LiDongbo，YuMingjian.Case-basedReasoningBasedonProductFunctionalTree[J].ChinaMechanicalEngineering，2006，17(2)：123-126.

[4]TuzikovAV，RoerdinkJB，HeijmansHJ.SimilarityMeasuresforConvexPolyhedralBasedonMinkowskiAddition[J].PatternRecognition，2000，33(6)：979-995.

[5]OsadaR，FunkhouserT，ChazelleB，etal.Matching3DModelswithShapeDistributions[C]//InstituteofElectricalandElectronicsEngineers.2001InternationalConferenceonShapeModelingandApplications，ShapeModelingInternational(SMI).NewYork：IEEE，2001：154-166.

[6]SunTL，SuCJ，MayerRJ，etal.ShapeSimilarityAssessmentofMechanicalPartsBasedonSolidModels[C]//DesignforManufacturingConference.SymposiumonComputerIntegratedConcurrentDesign.NewYork：ASME，1995：953-962.

[7]SungR，ReaHJ，CorneyJR，etal.AssessingtheEffectivenessofFiltersforShapeMatching[C]//AmericanSocietyofMechanicalEngineers.2002InternationalMechanicalEngineeringCongressandExposition.NewYork：ASME，2002：687-696.

[8]諶炎輝，周德儉，馮志君，等.基于BOM的復雜產品模塊劃分方法研究[J].中國機械工程，2012，23(21)：2590-2593.

ChenYanhui，ZhouDejian，FengZhijun，etal.ResearchonModularityMethodofComplexProductsBasedonBOM[J].ChinaMechanicalEngineering，2012，23(21)：2590-2593.

[9]丘宏俊，俞文靜.產品結構相似度量方法[J].計算機工程，2010，36(9)：274-27.

QiuHongjun，YuWenjing.MethodforProductStructureSimilarityMeasurement[J].ComputerEngineering，2010，36(9)：274-276.

[10]RomanowskiCJ，NagiR.OnComparingBillsofMaterials：aSimilarity/DistanceMeasureforUnorderedTrees[J].IEEETransactionsonSystemsManandCyberneticsPartA：SystemsandHumans，2005，35(2)：249-260.

[11]TsaiCY，TienFC，PanTY.DevelopmentofanXML-basedStructuralProductRetrievalSystemforVirtualEnterprises[J].InternationalJournalofProductResearch，2004，42(8)：1505-1524.

[12]ShihHM.ProductStructure(BOM)-basedProductSimilarityMeasuresUsingOrthogonalProcrustesApproach[J].Computers&IndustrialEngineering，2011，61(3)：608-628.

[13]李樂，章毓晉.非負矩陣分解算法綜述[J].電子學報，2008，36(4)：737-743.

LiLe，ZhangYujin.ASurveyonAlgorithmsforNon-negativeMatrixFactorization[J].ActaElectronicaSinica，2008，36(4)：737-743.

[14]PaateroP，TapperU.PositiveMatrixFactorization：aNon-negativeFactorModelwithOptimalUtilizationofErrorEstimatesofDataValues[J].Environmetrics，1994，5(2)：111-126.

[15]LeeDD，SeungHS.LearningthePartsofObjectsbyNon-negativeMatrixFactorization[J].Nature，1999，401(6755)：788-791.

[16]LeeDD，SeungHS.AlgorithmsforNon-negativeMatrixFactorization[C]//AdvancesinNeuralInformationProcessingSystems.Vancouver：NIPS，2001：556-562.

(編輯張洋)

Similarity Judgment of Product Structure Based on Non-negative Matrix Factorization and Its Applications

Xu XinshengWang ChengXiao Ying

China Jiliang University，Hangzhou，310018

In order to find reusable product structure promptly, an approach of measuring the similarity among product structures was proposed based on non-negative matrix factorization. A comprehensive matrix which containsed all structures was constructed on the basic of adjacent vectors that were transformed from the adjacent matrices of product structures. The non-negative matrix factorization for the comprehensive matrix was implemented based on Multiplicative Updates(MU) algorithm. Then all product structures might be described in low dimensional space. On the basis of these, the similarity between two product structures could be measured by calculating the Euclidean distance among these low dimensional vectors. Finally, an example was presented to verify the principles and methods mentioned above. The results show that the proposed methodologies are more effective than those of the existing methods.

product structure；non-negative matrix factorization；similarity；Euclidean distance

徐新勝，男，1976年生。中國計量學院質量與安全工程學院副教授。主要研究方向為先進制造技術、大規模定制、產品質量管理。發表論文50余篇。王誠，男，1991年生。中國計量學院質量與安全工程學院碩士研究生。肖穎，女，1976年生。中國計量學院質量與安全工程學院講師。

2015-06-18

國家自然科學基金資助項目(51405462,51175486);浙江省科技廳公益性技術應用研究計劃資助項目(2013C31132，2014C31117)

TP14; TH128

10.3969/j.issn.1004-132X.2016.08.014