1. FIND
  2. 國際案例
  3. 「數據分布特徵疊代萃取」技術

「數據分布特徵疊代萃取」技術


一、關鍵技術研發

本計畫關鍵技術為「數據分布特徵疊代萃取」（以下簡稱本技術），本技術線上分群串流數據，每一筆新數據流入時，數值相近者合併統計、相遠者則保留原值，顯示異於眾數之離群組合分析圖，協助使用者精準瞭解數據分布並識別離群/異常組合，利於發現問題成因及盡早排除之。

為避免處理過大數據量而影響運算效能，本技術基於漸進式數據串流處理模式，應用Apache Storm、mongoDB、R等開源軟體，開發計算時間與儲存空間複雜度恆定的技術架構，強化資料蒐集與儲存的整備度，進而提高資料取用與分析的準確度。如圖1所示：

  1. 應用Storm執行非監督漸進式資料分群(Unsupervised Incremental Binning)，先將原始資料(meta data)去蕪存菁，保留值得參考的資料，儲存於mongoDB（NoSQL資料庫）；
  2. 應用穩健統計(Robust Statistics)的計算架構，克服真實離群/異常值的識別難度，分析異常起因；
  3. 應用R執行階層式分群(Hierarchical Clustering)，依需求分析如測試站點或測試機台的離群程度，視覺化正異常分布，顯示關鍵問題。

資料來源: 本計畫繪製

圖1、數據分布特徵疊代萃取技術架構

從技術架構圖可知，本技術主要是執行一連串數據線上分群、小量多批及依需匯集的流程，如下說明主要的演算法。

演算法1：非監督漸進式資料分群→降低計算複雜度

非監督漸進式資料分群(Unsupervised Incremental Binning, UIB)唯一需要設定的參數是分群數量的上限，目的是減輕大量原始資料的計算和儲存負擔，期以分群處理後的部分數據分析，還能保有如同以全部數據分析的準確度。

每接收到一筆新數據時，會放置在當下最合適的數值群之中，一旦超過設定的分群數量上限（例如：100群），會將數值最接近的兩群合併為新的一群。由於分群數量固定，亦即加權的最大數量是給定常數，計算複雜度受到該常數限制，不會隨著數據量大而等比增加。

Algorithm 1: UIB, the Unsupervised Incremental Binning.

Initialize ( maxNumBins ) :

  1. M ← maxNumBins
  2. [ Bin ] ← [ empty ]

Push ( value ) :

  1. insert ( value, 1 ) into [ Bin ] /* Insert one more bin with sum value and count 1 into [ Bin ] */
  2. if the number of created bins exceeds M
  3. Sort [ Bin ] w.r.t their ascending means
  4. Bi ← argmin( Mean ( Bx+1 ) – Mean ( Bx ) ), x = 1…M /* Find two nearest bins Bi and Bi+1 */
  5. increment sum( Bi ) and count( Bi ) by sum( Bi+1 ) and count( Bi+1 ), respectively
  6. remove Bi+1 from [ Bin ] /* The number of created bins remains M */
  7. end
  8. return [ Bin ]

Mean ( Bin ) :

  1. return sum( Bin ) / count ( Bin ) 

演算法2：穩健計算分群的中位數與四分位距→避免受到異常值影響

真實的數據集中常存在異常值，亦可稱為離群值。以半導體測試數據為例，異常值主要來自於有缺陷的產品或設備故障。一般使用經典的擬合方法來診斷異常值，但經典方法可能受到異常值的強烈影響而無法確實檢測出異常分布（例如：平均值會受到極端異常值的影響而導致誤判如圖2(a)），即為遮蔽效應。

區分異常值看似簡單，但圖2(a)僅以平均數和中位數得出第13組為離群卻是假陽性警報。反觀圖2(b)是以數據落點（例如：平均數、中位數）、離散程度（例如：常態分配、四分位距）來確定數據分布是否異常。

本計畫提出穩健統計方法的計算架構，以不受異常值影響的中位數和四分位距(Interquartile Range, IQR)及平均反正切絕對百分比誤差(Mean Arctangent Absolute Percentage Error, MAAPE)等無偏差統計值來觀察數據分布的離散程度。

Algorithm 2: Computing the quantile and IQR on bins.

Quantile ( [ Bin ] , q% ) :

  1. Sort [ Bin ] w.r.t their ascending means.
  2. quantile ← q% weighted quantile in [ Bin ] /* Please refer to [9] for details. */
  3. return quantile

IQR ( [ Bin ] ) :

  1. return Quantile ( [ Bin ] , 75% ) - Quantile ( [ Bin ] , 25% ) 

演算法3：應用階層式分群拆分資料為兩個群聚→找出異於眾數的離群

承演算法1以UIB方法將原始資料拆分為數小群的資料，每個小群包含產品類型P、特徵集F及相對應之測試物理組件C，此處再以階層式分群方法拆分C為兩個不同的群聚Cleft和Cright，兩個群聚的相似度可由兩者的中位數間距而知，兩群的中位數值越相近，則產品類型、特徵集越相似。

Algorithm 3: Split2ByHC, splitting a set of components into two by hierarchical clustering.

Split2ByHC ( C , ( p , f ) , D ) :

  1. [ Bins( c1 ), Bins( c2 ), … Bins( cn ) ] ← Get bins in D with product p and feature f; then group by

c1..n ∈ C

  1. [ Bins ] ← [ Bins( c1 ), Bins( c2 ), … Bins( cn ) ] /* Initially each component c∈ C is itself a

cluster. */

  1. repeat when the number of clusters in [ Bins ] > 2
  2. i, j ← argmin | Quantile ( Bins( x ) , 50% ) – Quantile ( Bins( y ) , 50% ) |, x≠y
  3. Bins( m ) ← Collect ( Bins( i ), Bins( j ) ) /* Collect Bins( i ) and Bins( j ) into Bins( m ) */
  4. [ Bins ] ← [ Bins ] – Bins( i ) – Bins( j ) + Bins( m ) /* The number of clusters decreases by 1 */
  5. end
  6. return Bins( left ) as Cleft , Bins( right ) as Cright /* Consequently, C is split into Cleft and Cright . */

半導體設備的電性參數屬於常態分配，可比較兩個群聚的中心及分布散度來顯示離群程度。利用上述演算法Split2ByHC()所得的Cleft和Cright，透過下列算式(1)、(2)、(3)，評比它們的重疊率（介於-1和1之間）。圖2 (b)是評比Cleft [Bins(C1), Bins(C3), Bins(C4), ... , Bins(C12)]和Cright [Bins(C2)]為0.06的示例。當評比的數值越小，Cleft和Cright的距離就越大，即代表有離群現象，通常異常狀況來自於數量較少的一群，如[Bins(C2)]在圖2 (b)顯示為離群。

-1 ≤ Score ( Cleft , Cright ) =  ≤ 1                              (1)

where

UB ( [Bin] ) = Quantile ( [Bin] , 75%) + 1.5 * IQR ( [Bin] )                                    (2)

and

LB ( [Bin] ) = Quantile ( [Bin] , 25%) – 1.5 * IQR ( [Bin] )                                      (3) 

演算法4：結合演算法1~3

結合上述演算法，以半導體測試產線的即時串流數據驗證，測試組件的規模約為數十（例如：最終測試的多站點測試）到數百（例如：裸晶測試的多站點測試），計算複雜度相當於O(1)，實際上計算時間和計算所需的儲存空間幾乎不會因測試過程持續進行而等比增長。

Algorithm 4: Put it all together.

Initialize_Once ( C, ( P, F ), D ) :

  1. for each c∈ C, p∈ P, f∈ F
  2. Collective_Anomaly_Scorer as CAS ( c, ( p, f ) ) ← Initialize ( 100 )
  3. Store CAS ( c, ( p, f ) ) as a computing object associated with ( c, ( p, f ) ) in database D.
  4. end

Operate_Online ( c, ( p, f ), measured_value, D ) :

  1. CAS ← Retrieve the computing object from database D associated with ( c, ( p, f ) ).
  2. [ Bins ] ← CAS.Push ( measured_value ) /* Respond to one received value. */
  3. Store [ Bins ] associated with CAS in database D.

資料來源：本計畫繪製

圖2、(a)應用一般檢定誤判第13組為離群；(b)應用異常檢定識別第2組實為離群 

二、製造場域驗證

半導體測試是指檢測晶圓及封裝後IC的電性功能與外觀，保證IC功能具備一定品質的良率標準，理論上，假設測試正確率100%，則良率標準也會穩定持平。然而，每次測試使用的機台、設備和執行人員不盡相同，可能因機台與設備的耗損、人員經驗的不足，導致產品被誤測為不良品，良率水準時有差異。

再者，半導體測試廠終年不停機，每部機台每日測試上萬顆IC，每顆IC的測試項目多達上萬組，機台數據是以串流模式呈現，全部測試資料高達千億筆，無法單靠肉眼發現資料之間的關連性。每當出現良率問題時，需經過繁複的檢查流程，才確知是哪個環節出錯，這種作法不僅費時費工，而且難以發現根本原因。

本計畫應用國內半導體測試大廠的設備紀錄及測試機台資料，驗證本技術架構之有效性，包含逾4千種半導體設備的6萬種不同特徵，總共2.33億個量測值，即時監控裸晶測試(Chip Probe, CP)及最終測試(Final Test, FT)的檢測狀況。應用在於檢視測試數據之穩定性與分布狀況，以中位數、四分位距、群聚重疊率作為離群/異常的比較標準，辨識設備組合低效情形。在每秒1MB數據串流的資料環境下，每日資料量逾3TB，回應延遲小於1分鐘，計算複雜度相當於O(1)，亦即計算空間複雜度及時間複雜度很低。

如表1所示，驗證過程以UIB方法將原始數據分作50、80及100群。由於不同產品特徵的量測值範圍差距極大（負數、正數或是零都有可能，取決於相對應的產品設計規格），故選擇平均反正切絕對百分比誤差(MAAPE)作為檢測指標，因MAAPE具有指標獨立性，不會隨著實際值變為零時而無限大。經驗證發現這三種分群的誤差率皆小於0.4％，即準確度高達99.6%，滿足工業應用情境所需。且當分群數量越大時，MAAPE值越小，亦即識別離群的準確度越高。此例以分作100群的精準度最佳。

相比使用原始數據運行和使用本技術架構運行的計算時間，發現無論以UIB方法設定的分群數量多寡，計算時間近似恆定，而使用原始數據運行的計算時間則是呈正比成長。如圖3所示，運算效率不會隨著數據量大而延遲。同時，使用本技術架構運行所需的儲存空間也是近似恆定，且受到演算法1的分群數量的參數設定而固定。如圖4所示，計算所需的儲存空間不會隨著數據量大而等比增加。

表1、製造場域驗證以UIB方法分群

                                   註：Eq. (1)為演算法3的算式(1)、(2)、(3)

資料來源: 本計畫整理

資料來源: 本計畫繪製

圖3、計算時間近似恆定

資料來源: 本計畫繪製

圖4、儲存空間近似恆定

參考來源：

[1] W. R. Daasch, et al., “Statistics in Semiconductor Test: Going beyond Yield,” IEEE Design & Test of Computers 26(5): 64-73, 2009.
[2] L.-C. Wang, “Experience of Data Analytics in EDA and Test-Principles, Promises, and Challenges,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36(6): 885-898, 2017.
[3] C.-F. Chien and J.-Z. Wu, “Analyzing repair decisions in the site imbalance problem of semiconductor test machines,” IEEE Transactions on Semiconductor Manufacturing 16(4): 704-711, 2003.
[4] V. Chandola, A. Banerjee and V. Kumar, “Anomaly detection: A survey,” ACM Comput. Surv. 41, 3, Article 15, 58 pages, 2009.
[5] P. J. Rousseeuw and M. Hubert “Robust statistics for outlier detection,” Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery 1(1): 73-79, 2011.
[6] R. J. Tibshirani, “Fast computation of the median by successive binning,” arXiv preprint arXiv: 0806.3301, 2008.
[7] Raj Jain and Imrich Chlamtac, “The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations,” Communication of ACM 28, 1076-1085, 1985.
[8] Y. Wu, S. Wang, L. Chen and C. Yu, "Streaming analytics processing in manufacturing performance monitoring and prediction," 2017 IEEE International Conference on Big Data (Big Data), Boston, MA, pp. 3285-3289, 2017.
[9] R. Hyndman and Y. Fan, “Sample Quantiles in Statistical Packages,” The American Statistician, 50(4), 361-365, 1996.
[10] K. Zhang, et al., “Research of Probability Distribution of Semiconductor Test Parameter,” Advanced Materials Research 1049-1050: 754-761, 2014.
[11] S. Kim and H. Kim, “A new metric of absolute percentage error for intermittent demand forecasts,” International Journal of Forecasting 32(3): 669-679, 2016.
[12] W.-K. Lin, “Theoretical Derivation of Junction Temperature of Package Chip, Electronics Cooling,” SM Sohel Murshed, IntechOpen, 2016.

 

延伸閱讀
作者相關文章
數據