基于可變長工序編碼的再制造生產調度優化方法

摘 要:回收品質量、數量以及拆卸過程中的不確定性因素使再制造生產調度問題更加復雜。針對工件加工路徑的可變性特點，建立了再制造生產中的job-shop調度模型，提出了一種基于可變長工序編碼方法的改進遺傳算法，設計了異常染色體的識別和重構方法，以及相應的遺傳算子。在參數矩陣的指導下，該算法可以實現隨機工序數目和隨機工序順序情況下再制造生產調度問題的優化求解。仿真實驗證明了該算法的有效性和可行性。

關鍵詞:再制造; 生產調度; 遺傳算法; 可變長工序編碼

中圖分類號:TP278 文獻標志碼:A

文章編號:1001-3695(2010)03-0871-03

doi:10.3969/j.issn.1001-3695.2010.03.017

Optimization approach based on variable-length operation encode for

remanufacturing production scheduling

ZHANG Hong-yu1， GAO Yang1， MA Hua2

(1.School of Business， Central South University， Changsha 410083， China; 2. Dept. of Computer， Hunan International Economics University， Changsha 410205， China)

Abstract:The uncertainties of quality， quantity and disassembly process of returns in remanufacturing cause additional complexity for its production scheduling. According to the variability of job process path， this paper proposed job-shop scheduling model for remanufacturing. In the model， put forward an improved genetic algorithm based on variable-length encode. Designed the GA operators and methods to identify chromosomes validity and reconstruct them. Under the guidance of parameters matrix， the algorithm could achieve the optimization solving for remanufacturing production scheduling with the random processing number and the random processing path of operations. The simulation results show that this algorithm is effective and feasible.

Key words:remanufacturing; production scheduling; genetic algorithm; variable-length operation encode

再制造是將耗損的耐用產品經過拆卸分解、清洗檢查、整修加工、重新裝配、調整測試恢復到既經濟又可用狀態的全生產過程[1]。作為廢棄物循環利用的重要途徑，再制造對于實現節能減排，發展循環經濟，創建環境友好型和資源節約型社會具有重要意義。現有研究已證實，再制造率不確定、拆卸后的部件處理時工藝路線和提前期隨機、回收產品數量和時機等因素帶來的額外不確定性，大大增加了再制造生產系統的復雜度，使得傳統的生產計劃與控制方法難以直接應用[2，3]。

傳統制造系統中的job-shop調度問題主要面對確定性信息條件，工件的初始狀態相對穩定，加工時間、加工路徑和到達時間等參數均相對固定[4~6]。考慮到實際生產過程的復雜性，一些離散事件動態系統適宜采用服從指數分布的隨機量描述參數[7]。文獻[8，9]分別對加工時間、加工機器不確定條件下的傳統制造生產調度問題進行了研究。然而，再制造中回收品質量、數量以及拆卸過程中的額外不確定性因素導致工件的加工路徑具有顯著的可變性，即同一類工件的處理工序、加工時間和加工機器等參數將因再制造生產過程的具體情況而隨機變化，從而加大了再制造生產調度優化的難度。

本文針對再制造生產調度的特點，建立了相應的job-shop調度模型，通過設計一種基于可變長工序編碼的改進遺傳算法對該模型進行優化求解，在參數矩陣的指導下，該算法可以有效處理以動態加工路徑為特征的再制造生產調度問題。

1 再制造job-shop調度問題描述

本文將n個工件m臺機器的再制造生產job-shop調度問題記為n/m，它滿足以下約束:a)工件要經過多道工序加工，每道工序在特定的不同機器加工;b)工件的加工路徑是可變的，即各工件的工序數目和順序隨機變化;c)每臺機器每次只能加工一個工件的一道工序;d)不同工件的工序間無先后約束關系;e)工序的加工過程不被中斷。

將再制造中的n/m問題描述如下:

a)J={J1，J2，…，Jn}，表示n個工件的集合。

b)M={M1，M2，…，Mm}，表示m臺機器的集合。

c)Oi={Oi1，Oi2，…，Oij}，表示工序的集合，工件Ji的第j道工序記為Oij，1≤i≤n，1≤j≤m。

d)TSkij和TEkij分別表示工件Ji的第j道工序Oij的加工開始時間和結束時間，TSkij≥0。

e)tkij表示工件Ji的第j道工序在機器k的加工時間，tkij=TEkij-TSkij≥0。

本文以完工時間最小化為調度目標，從而得到目標函數為min ft=min(max1≤i≤n TEkim)。

2 基于改進遺傳算法求解n/m問題

2.1 可變長工序編碼方法

為便于分析，定義工序順序矩陣O和加工時間矩陣T描述n/m問題的輸入數據。

O=O11O12…O1m

O21O22…O2m

 

On1On2…Onm

T=t11t12…t1m

t21t22…t2m

 

tn1tn2…tnm

其中:矩陣O描述了各個工件的加工順序;oij表示工件i在機器j加工的工序序號，1≤oij≤m;矩陣T描述了各個工序的加工時間;tij表示工件i在機器j所需的加工時間。考慮到再制造生產中工件的加工路徑具有可變性，當工件i無須進行第j道工序加工時，將oij稱為無效工序，令oij=0，tij=0。所以，矩陣O中各個工件的有效工序總數將表現出可變長的特點。如果采用傳統的基于工序的編碼方法[4~6]，染色體由n×m個基因組成，其中包含了大量無效基因，從而增加了染色體的存儲冗余和遺傳操作的復雜度。

為解決以上問題，本文提出了一種基于界點參數矩陣limit和解碼參數矩陣param的可變長工序編碼方法。該編碼方法的主要步驟如下:

a)按照各個工件的實際工序順序進行統一編號，基于加工順序矩陣O生成一個重新編排的連續編碼矩陣sequence，無效工序在sequence中均編號為0。

b)基于連續編碼矩陣sequence生成界點參數矩陣limit，以記錄sequence中各工件的最小、最大工序編號值，從而提高解碼的速度。

c)為便于計算適應度值，基于連續編碼矩陣sequence和加工時間矩陣T生成解碼參數矩陣param，由其記錄sequence中各個工序所對應的工件、機器和加工時間信息。

d)從連續編碼矩陣sequence中挑選出所有非零元素，隨機生成一條染色體。由于染色體中不包含無效工序，從而可大大減少染色體的基因位數。

在界點參數矩陣limit和解碼參數矩陣param的指導下，可變長工序編碼方法可以適應工序順序、加工時間或加工機器的隨機變化情況，保證染色體的相對穩定性，從而適應再制造生產調度中工件加工路徑隨機的特點。同時，該編碼方法可以兼容處理傳統制造的生產調度問題中工序數目相等的情形，因此，該方法在制造和再制造領域具有普適性。以下面的一個3/4 job-shop調度問題為例，其輸入信息如下:

O=3 1 0 22 0 1 01 3 4 2

T=4 2 0 33 0 1 02 1 5 2

由此生成的連續編碼矩陣sequence為

sequence=3 1 0 25 0 4 06 8 9 7

由sequence得到的參數矩陣limit和param如下:

limit=1 34 56 9 param=1 2 21 4 31 1 42 3 12 1 33 1 23 4 23 2 13 3 5

通過將sequence中值為0的無效工序過濾，即可得到一個可變長編碼的染色體，如[4 1 6 5 7 2 8 3 9]，該染色體長度為9，而如果使用傳統的工序編碼方法，則需要3×4個基因，可見，本文方法更優。

2.2 異常染色體的識別及重構

應用遺傳算法求解傳統制造領域的job-shop調度問題時，若得到了可能死鎖的非法解，可采用拒絕策略[10]。但是，在約束性較強的再制造生產環境中，這種方法將會壓縮可行解的搜索空間，從而不利于獲得最優解。本文的可變長工序編碼方法在參數矩陣的指導下可快速識別存在死鎖的異常染色體片斷，并對其進行有效重構。異常染色體的識別及重構方法如下:

a)根據界點參數矩陣limit，從給定的染色體中分解出各個工件的染色體片斷，這樣可以得到n個由連續工序編號構成的編碼排列。

b)逐一檢查各個工件的染色體片斷，正常染色體片斷應該是一個連續遞增的編碼序列，如果某個片斷出現遞減序列，則應對該染色體片斷作“異常”標記。

c)逐一對“異?！比旧w片斷執行重構操作，其方法是:使用插入排序法或快速排序法逐一對各個片斷中的基因進行升序排列，再將重排后的染色體片段中的基因回填到分解前染色體中的相應基因位，從而構造出新的正常染色體。

以3/4調度問題為例，令染色體為[4 1 6 5 8 2 7 3 9]，經檢查可識別出工件2的染色體片斷異常，使用上述方法對該片斷進行重構，從而生成一個新的正常染色體為[4 1 6 5 7 2 8 3 9]。這樣，通過極小的代價修復了存在死鎖的非法解，從而該染色體可以參與后續的各種遺傳操作。

2.3 適應度函數

根據再制造生產調度的優化目標，將最大完工時間作為染色體適應度的衡量指標。首先，對所有染色體進行解碼操作，計算出由染色體決定的調度方案的最大完工時間ft=max1≤i≤nTEkim，然后根據式(1)對其執行歸一化操作，從而得到各個染色體的適應度函數值。

fitnessi=ftmax-ftiftmax-ftmin if ftmax-ftmin≠01if ftmax-ftmin=0(1)

其中:ftmax=max{fti}，ftmin=min{fti}，1≤i≤np，0≤fitnessi≤1;fitnessi表示第i個染色體的適應度值，ftmax和ftmin分別表示種群中染色體個體的最大完成時間的最大值和最小值。

2.4 遺傳算子

1)選擇算子

采用傳統的輪盤賭法選擇個體。染色體i被選中概率為pi=fti/∑numj=0ftj。其中:num表示種群數。

2)交叉算子

借鑒基于位置的交叉方法(PX)和基于循環的交叉方法(CX)[11]，本文采用一種基于工件的工序移位方法進行交叉操作。該方法能夠保存父代中的優良基因，并有利于增加種群的多樣性。該方法需要先分別對兩個待交叉的染色體解碼，以得到相應的工件——工序矩陣JSi，如下:

JSi=

js11js12…js1maxjs21js22…js2max jsn1jsn2…jsnmax

其中:JSi表示染色體i的工件——工序矩陣;max代表染色體的基因個數。JSi的行對應n個工件，列對應max個連續編碼的工序。結合參數矩陣，可以完成JSi的填充。方法是將染色體中第i個基因代表的工序填充到JSi中第i列第j行上，j為工序所歸屬的工件編號。對每一對待交叉的染色體，生成一個整型隨機數ζ∈[1，n]，交換兩個染色體中第ζ個工件的所有工序，由于交換后將造成部分列有多個工序并存，此時按照就近安置策略，將發生沖突的工序移位至空缺的列，從而繁衍出新的染色體。

以3/4調度問題為例，當ζ=2時，染色體[4 1 6 5 7 2 8 3 9]和[1 6 2 4 7 8 5 9 3]交叉后生成的兩個新的染色體為[8 1 6 4 7 2 5 3 9]和[4 6 2 4 5 8 1 9 3]，可見，子代保持了父代的優良特性。

3)變異算子

變異操作采用基于機器的工序移位方法進行變異操作，變異前需要先從染色體中解碼出機器——工序序列MSi。

MSi=ms11ms12…ms1max

ms21ms22…ms2max msn1msn2…msnmax

其中:MSi表示染色體i的機器——工序矩陣，它的行對應m臺機器，列對應max個連續編碼的工序。結合參數矩陣，可以完成MSi的填充。方法是將染色體中第i個基因代表的工序填充到MSi中第i列第j行上，j為工序所位于的機器編號。生成整型隨機數ζ∈[1，n]，對染色體中的第ζ臺機器的工序進行循環左移或循環右移一位的變換操作，從而繁衍出新的染色體。

以3/4調度問題為例，當ζ=4時，染色體[4 1 6 5 7 2 8 3 9]執行循環左移一位的變異結果為[4 1 6 5 2 7 8 3 9]。

在交叉操作或變異操作完成后，均應對新生成的染色體進行合法性鑒別，并對異常染色體片斷執行重構操作。經檢查可知，3/4調度問題中交叉操作生成的兩個新染色體均需要重構，而變異操作則生成了一個正常染色體。

3 實驗仿真與分析

本文在MATLAB 7.0環境中對本文方法進行了仿真實驗。實驗機器配置:CPU Intel E2180為2.0 GHz，內存為2 GB。遺傳算法參數設置:種群規模為70，進化代數為200，交叉概率Pc=0.85，變異概率Pm=0.05。

在實驗1中，本文對經典的job-shop benchmark問題FT06和FT10[11]進行了實驗仿真，取五次仿真結果的平均值。實驗結果如表1所示。FT06和FT10是本文基于可變長工序編碼方法應用的特例，即染色體恰好由n×m個基因組成。由表可知，本文的改進遺傳算法能夠求出FT06的最優解，得到的FT10的最好解與其最優解也非常接近，并且，相比于其他傳統的基于工序的編碼方法，本文方法的計算耗時是可以接受的，從而說明了本文方法是有效和可行的。

表1 算法仿真結果

問題規模CPU時間/s平均解最優解最好解最差解平均收斂代數

FT066×656.73457.4055555961.20

FT1010×10608.766957.20930933958103.80

在實驗2中，根據再制造生產中加工路徑可變性的特點，通過修改FT10問題的輸入數據，模擬了一個再制造環境下的job-shop調度問題，將其記為FT10′問題。該問題的輸入數據如圖1所示。其中，加工時間為0的工序是無效工序。

應用本文的可變長編碼方法，將機器的起始編號設置為1，得到FT10′問題的連續編碼矩陣sequence，即

FT10′問題的當前最優解為724，其甘特圖如圖2所示。

實驗2的求解過程進化曲線圖如圖3所示。

仿真實驗表明，基于可變長工序編碼的改進遺傳算法適用于求解復雜的再制造生產調度問題，該算法的編碼方法簡單，避免了無效工序的存儲冗余和計算負擔，(下轉第882頁)

第3期

魯均云，等:基于內碼序值聚類的相似重復記錄檢測方法 

收稿日期:2009-06-20;

修回日期:2009-09-03

基金項目:國家火炬計劃資助項目(2004EB33006[0]);江蘇省高校自然科學指導性計劃資助項目(05JKD520050)

作者簡介:魯均云(1984-)，男，碩士，主要研究方向為數據挖掘、數據清理(lujunyun2008@163.com);李星毅(1969-)，男，副教授，博士，主要研究方向為數據挖掘、空間數據庫、交通信息系統和控制;施化吉(1964-)，男，教授，博士，主要研究方向為計算機網絡、分布計算、數據挖掘等;馬素琴(1980-)，女，碩士研究生，主要研究方向為數據挖掘.

基于內碼序值聚類的相似重復記錄檢測方法

魯均云， 李星毅， 施化吉， 馬素琴

(江蘇大學 計算機科學與通信工程學院， 江蘇 鎮江 212013)

摘 要:檢測和消除相似重復記錄是數據清理和提高數據質量要解決的關鍵問題之一，針對相似重復記錄問題，提出了基于內碼序值聚類的相似重復記錄檢測方法。該方法先選擇關鍵字段或字段某些位，根據字符的內碼序值，利用聚類思想將大數據集聚集成多個小數據集;然后，通過等級法計算各字段的權值，并將其應用在相似重復記錄的檢測算法中;最后，在各個小數據集中檢測和消除相似重復記錄。為避免關鍵字選擇不當而造成記錄漏查問題，采用多趟檢測方法進行多次檢測。通過實驗表明，該方法具有較好的檢測精度和時間效率，能很好地應用到中英文字符集，通用性很強，并能夠有效地解決大數據量的相似重復記錄檢測問題。

關鍵詞:相似重復記錄; 內碼序值; 聚類; 等級法

中圖分類號:TP311 文獻標志碼:A

文章編號:1001-3695(2010)03-0874-05

doi:10.3969/j.issn.1001-3695.2010.03.018

Approach for detecting approximately duplicate records based on

cluster of inner code’s sequence value

LU Jun-yun， LI Xing-yi， SHI Hua-ji， MA Su-qin

(School of Computer Science Telecommunication Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China)

Abstract:Detecting and eliminating approximately duplicated records is one of main problems needed to solve for data cleaning and improving data quality. As to such problem， this paper presented an approach for detecting approximately duplicate records based on cluster of inner code’s sequence value. The proposed method firstly chose the key field or some bits of it， and according to the inner code’s sequence value of character， clustered large datasets into many small datasets by cluster thought. Then in term of rank-based weights method， endowed each attribute with certain weight using in detecting approximately duplicate records. Finally， detected approximately duplicated records and eliminated in each small dataset. To avoid missing some records caused by choosing improper key field， the multiple-detecting method could be adopted. Experimental results show the proposed method has good detection precision and time efficiency， can be applied to English and Chinese character set， and therefore is an effective approach to solve approximately duplicate records for massive data.

Key words:approximately duplicate records; inner code’s sequence value; cluster; rank method

高質量的數據是數據挖掘成功的前提條件[1，2]。為了提高被挖掘數據源的數據質量，數據清理就變得至關重要。檢測和消除相似重復記錄是數據清理中的一個關鍵環節，也是提高數據質量要解決的主要問題之一。所謂相似重復記錄，是指客觀上表示現實世界中的同一實體，但由于表述方式不同或拼寫問題而使DBMS不能正確識別的記錄[3]。相似重復記錄識別的目的是匹配、合并和清除那些冗余的、客觀上映射同一實體但在語義表示上存在差異的數據庫記錄。

對于相似重復記錄的檢測，目前主要有“排序合并”的方法[4，5]、建索引的方法[6]、基于q-gram方法[3]、采用距離函數模型方法[7]以及標準的字符串度量方法[8]等。傳統方法在進行相似重復記錄檢測時，要有大量磁盤I/O操作，導致時間復雜度和空間復雜度較高，并且排序時由于字符位置敏感性，并不能保證相似的記錄排在鄰近的位置，以及記錄的維數不能過高。為了克服上述不足，結合傳統檢測方法，本文提出了一種基于內碼序值聚類的相似重復記錄檢測方法，該方法可以很好地應用于中英文字符集中。其主要特征有:a)采用字符內碼序值對記錄進行排序處理，增強了算法通用性;還可有效地降低常見的交換和同音輸入錯誤的影響，提高檢測精度;b)利用聚類思想，減少了各記錄間比較次數，目的是提高時間效率;c)根據等級法計算各字段的權值，以及設計多趟檢測方法，目的是提高檢測精度。

1 相關定義

定義1 字符的內碼序值是根據字符內碼值而計算出的一個表示字符特征的整數值。

定義2 設數據集合X={x1，x2，…，xn}，字段向量F={F1，F2，…，Fp}，Fk表示數據集中第k個字段。對于任意記錄xi=(xi1，xi2，…，xip)。其中:1≤i≤n;xip表示記錄xi第p維的值。用wk表示字段Fk的權值，代表字段在記錄中的重要程度，稱為字段的權重。權重向量W={w1，w2，…，wp}。

定義3 設Rik是第i個操作用戶為字段Fk所指定的等級(從1開始，用一系列連續正整數表示等級，最重要字段的等級指定為1，依此類推，數值越大，等級越低)，Tk是N個操作用戶為字段Fk指定等級的總和，1≤k≤p，1≤i≤N，如表1所示，則

Tk=∑Ni=1 Rik(1)

表1 字段等級表

字段名用戶指定的等級

user1user2…user i…userN等級總和最終統一等級

F1R11R21…Ri1…RN1T1R1

F2R12R22…Ri2…RN2T2R2

  

FkR1kR2k…Rik…RNkTkRk

  

FpR1pR2p…Rip…RNpTpRp

定義4 設Rk是字段Fk最終統一的等級，R表示所有字段中的最低等級(即數值最大的等級)，1≤k≤p。采用RC(rank-centroid)轉換法[9，10]，如果各字段指定的最終統一等級不相同，那么R=p，字段的權重可以表示為

Wk(RC)=1/R ∑Rt=Rk1t(2)

如果存在兩個或兩個以上字段具有相同等級，則式(2)應變為

Wk=Wk(RC)/∑Pk=1Wk(RC)(3)

定義5 對任意記錄xi與xj，它們第k個字段為xik與xjk，則xik與xjk的字段相似度[13]為

sim field(xik，xjk)=∑mt=1max(score(at，xjk))|xik|(4)

其中:score(at，xjk)表示xik中的原子串at與xjk中的每個原子串匹配的分值，0≤score(at，xjk)≤1;|xik|表示xik的長度;m表示xik的原子串的數量。

定義6 給定兩條記錄xi和xj，則xi和xj的記錄相似度

sim record(xi，xj)=∑pk=1sim field(xik，xjk)Wk(5)

定義7 設XO代表原數據集實際的重復記錄集合，XD代表識別出來的重復記錄集合。查準率(precision)是正確識別出來的重復記錄占識別出作為重復記錄的比率，查全率(recall)是正確識別出來的重復記錄占數據集中實際的重復記錄比率，則可表示為

precision=|XO∩XD|/|XD|(6)

recall=|XO∩XD|/|XO|(7)

2 基于內碼序值聚類的重復記錄檢測方法

2.1 計算字符的內碼序值

在傳統的相似重復記錄檢測方法中，基本上是針對于英文記錄進行處理的。與純英文記錄相比，由于中文和英文在語法、表達習慣上存在差異，以及存在中英文混合字段的情況，檢測英文重復記錄的排序方法并不完全適合于處理中文重復記錄。針對這一不足，利用字符內碼序值對記錄進行排序處理，既可應用于英文字符，又可應用于中文字符，具有通用性。

無論是中文字符還是英文字符，在計算機內部都是以其內碼形式存儲的。對于英文字符，采用的是ASCII編碼標準，使用一個字節即8位二進制數來存儲，最高位為0，其編碼范圍為01H~7FH。而中文字符信息編碼采用的是國標碼(GB2312—80)，在國家標準GB2312—80中共有7 445個字符符號，其中漢字6 763個，分成兩級，一級漢字有3 755個(按漢語拼音字母順序排列)，二級漢字有3 008個(按部首筆畫順序排列)。漢字在計算機內是以漢字內碼的形式存儲(漢字內碼=區位碼+A0A0H)，即每個漢字由兩個字節編碼表示。為了不與ASCII碼發生沖突，把國標碼每個字節的最高位置為1，其余位不變的編碼作為漢字內碼，漢字編碼范圍為B0A1H~F7FEH。因此，可根據字符與其內碼之間的一一對應關系，計算出字符對應的內碼序值。其計算公式如下:

indexvalue(c)=asctodec(c)若c是英文字符128+[hextodec(ch-B0)×94+hextodec(cl-A1)]若c是中文字符(8)

其中:ch是字符c對應的內碼高位;cl是字符c對應的內碼低位;asctodec()是將字符的ASCII值轉換為十進制形式;hextodec是將十六進制轉換成十進制形式;“128”表示將中文字符內碼序值的起始值設定為大于128;“94”表示國標碼的每個區中有94個字符，B0 A1 H是存儲第一個漢字的內碼值。

2.2 記錄聚類算法

在檢測相似重復記錄時數據集中經常存有海量數據，而傳統方法要有大量磁盤I/O操作，需要大量存儲空間的支持，導致運算時間和空間開銷相當大，以至于無法接受。針對這一不足，根據選取關鍵字段中字符的內碼序值，利用聚類技術，將相似度較高的記錄聚集到一個數據集中，把大數據集聚集成很多個小數據集，然后在各個小數據集中進行相似重復記錄檢測，從而提高了時間效率。利用字符的內碼序值進行排序處理，可以有效地降低常見的交換錯誤和同音輸入錯誤的影響，提高檢測精度。記錄聚類算法的基本思想是:

a)選取易于區別記錄的關鍵字段或字段的某些位，計算數據集中所有記錄對應的被選取字符的內碼序值。

(a)若選取的是關鍵字段的某一位，則計算該位所對應的字符內碼序值。

(b)若選取的是關鍵字段的某幾位，則計算這幾位所對應的字符內碼序值的均值。

(c)若選取的是整個關鍵字段，則計算該字段所有的字符內碼序值的均值。

b)根據字符的內碼序值對整個數據集中的記錄進行排序，盡量把潛在的、可能的重復記錄調整到鄰近的區域內，便于進行記錄聚類。

c)比較各記錄的字符內碼序值，將內碼序值相等或者內碼序值均值在較小范圍內的記錄聚集到一個數據集中，把大數據集聚集成很多個小數據集。

d)聚類后的某些數據集仍然很大，則選取其他的關鍵字段或字段的某些位，在這些數據集中按字符內碼序值再次聚類處理。

e)重復d)，直至將各數據集聚類成比較合理大小的數據集為止。

為避免在記錄聚類中因選取的關鍵字段不適當，排序時由于字符位置敏感性并不能保證相似的記錄排在鄰近位置，造成這些相似的記錄誤聚集到不同的數據集中。筆者設計了多趟檢測技術，即選取關鍵字段，將數據集聚類成合理的多個小數據集，在小數據集中檢測相似重復記錄并設置重復標記，這一輪結束后，再選取其他的關鍵字段，重新對數據集進行聚類，并在聚類后的小數據集中檢測相似重復記錄、設置重復標記，根據具體情況決定是否進行下一輪的選取聚類檢測，直到結果滿意為止。

樣本數據表如表2所示，可選取字段“姓名”中姓氏這一位，據《中華姓氏大辭典》中共收錄的姓氏多達10 000多個，其中單字姓5 000多個，根據姓氏的內碼序值，可將數據集聚類成幾百個甚至幾千個小數據集。聚類后，由于某些姓氏的數據集仍然比較龐大，例如根據全國人口普查的統計資料表明，李、王、張三大姓氏，分別占了全國總人口的7.4%、7.2%和6.8%，對于這些姓氏較大的數據集，再選取其他關鍵字段如出生日期的年月，繼續進行聚類成幾百個小數據集。此外，可選取“姓名”這個字段，根據字符的內碼序值均值，把姓名相同和相近，如“張華偉”“張嘩偉”和“張偉華”，快速地聚集到同一個數據集中，防止常見的交換錯誤和同音輸入錯誤的影響，更快地將相似重復記錄檢測出來。

其算法描述如下:

輸入:數據集X，數據集大小閾值ε。

輸出:小數據集X1，X2，…，Xs(Xs為數據集X中第s個小數據集，且XsX)。

RecordCluster(X，ε)

{SelectFieldorFieldBit(Fk，Fkb);

//選擇關鍵字段或字段的某些位

select_flag=true;

/* select_flag標志選擇字段某一位還是字段某幾位，其中true表示選擇字段某一位*/

if(select one bit of Fk)// 若選擇字段的某一位

{value[k][h]=indexvalue(c);

/*根據式(8)計算該位字符c的內碼序值，value[k][h]用于存放第k字段第h條記錄字符的內碼序值*/

select_flag=true;}

else if(select q bits of Fk)// 若選擇字段的某q位

{for(i=1; i<=q; i++)

value[k][h]= value[k][h]+indexvalue(ci)/q;

// ci表示選擇字段某q位中的第i個字符

select_flag=1;}

else {for(i=1; i<=Field[k][h].length; i++)

/*若選擇整個字段所有位，Field[k][h].length表示第k個字段第h條記錄中字符的個數*/

value[k][h]=value[k][h]+indexvalue(ci)/Field[k][h].length;

select_flag=1;}

Sort(X，value[k][h]);

//按字符的內碼序值對數據集X排序

start_mark=N+1;/*start_mark指向數據集中未被聚類的記錄位置，N表示數據集中記錄數目*/

for(i=1; i<=N; i= start_mark)

// 根據字符內碼序值進行聚類

{xt={xi};// 依次從X中取記錄放入小數據集xt中

{for(j=i+1; j<=N; j++)

// 將滿足條件的記錄聚集到一個數據集中

{if(select_flag = = true value[k][i] = = value[k][j])xt=xt∪{xj};

else if(select_flag = = 1 )

|value[k][i]-value[k][j]<=8|;Xt=Xt∪xj};

/* 如果被比較的字符內碼序值不相同且屬于同一個區但所在的位距離不超過8，或所在區是連續的，并且是首尾相連的、距離不超過8個位，說明這些字可能是讀音相同的字，防止交換和同音輸入錯誤的影響*/

else { start_mark = j;break;} }// 不滿足條件，退出循環

if(i = = N || j = = N+1)break;}}

// 最后一條記錄被聚集到某一類中，結束聚類操作

while(Xt)// 對任意一個小數據集Xt

{ if(|Xt|>ε)RecordCluster(Xt，ε);

// |Xt|表示數據集Xt中記錄數目

elsereturn (X1，X2，…，Xs);}}

2.3 等級法計算字段權重

在計算記錄相似度時，由于記錄中不同字段對反映記錄特征的貢獻是不同的，比如人口數據表中姓名顯然要比性別更能反映記錄的特征，要根據字段的重要程度，為各字段賦予相應權重，以此來提高檢測的精度。

等級法是一種計算記錄字段權重的方法，其基本思想是:首先各用戶根據字段實際重要程度為各字段指定等級;然后根據式(1)計算各字段的等級總和，并對其進行排序，為各字段賦予最終統一等級;最后根據式(2)或(3)計算各字段相應的權重。字段權值計算的算法描述如下:

輸入:字段向量F。

輸出:字段權值向量W。

ComputeWeight(F)

{ for(k=1; k<=p; k++)Rk=0;

// 對各字段的等級進行初始化，p表示字段總數

for (i=1; i<=N; i++) // N表示操作用戶總數

{for (k=1; k<=p; k++)Rik=rik;}

//rik為操作用戶給字段Fk指定的等級數

for (k=1; k<=p; k++)Tk=∑Ni=1Rik;

// 根據式(1)計算各字段等級總和Tk

sort (Tk); // 對Tk從小到大進行排序

for (k=1; k<=p; k++) Rk=rk;

// rk為各字段賦予最終統一等級數

for (k=1; k<=p; k++) compute wk;

// 根據式 (2)或(3)計算wk

return (W);}

2.4 字段匹配

字段匹配是計算記錄相似度的基礎。由于字段具有多種類型數據，大部分數據都是字符串類型的，且相似重復記錄之間的差異也是由字符串數據引起的，在進行字段匹配之前先進行字符化處理。字符化后，字段中字符串之間的比較可能有以下三種情況:

a)字符串由英文字符(包含數字等)組成。對于這種情況，現有的字段匹配技術比較成熟。假設任意兩個比較的記錄xi和xj，其中第k個字段xik和xjk是由英文字符串構成，按照英文規律分別把xik和xjk分割成合理的原子串，調用相關的字符串比較函數(函數內容參照文獻[11~13]或其他資料)，根據式(4)計算字段相似度EnglishSimField(xik，xjk)。

b)字符串由中文字符(主要是漢字)組成。對于這種情況，現有的字段匹配技術也比較成熟。假設任意兩個比較的記錄xi和xj，其中第k個字段xik和xjk是由中文字符串構成，按照中文規律分別把xik和xjk分割成合理的原子串，調用相關的字符串比較函數(函數內容參照文獻[11~14]或其他資料)，根據式(4)計算字段相似度ChineseSimField(xik，xjk)。

c)字符串由英文和中文字符混合組成。對于這種情況，不同語言字符之間進行比較不僅沒有意義，而且會浪費大量時間。為此采取了自然分割的方法，把字段中混合字符串分割成英文字符串和中文字符串后，在相同語言字符之間進行比較。例如兩個表示家庭住址信息的字符串:臺州市路橋區育才路58號B單元501室和臺州市育才路58號B單元507室，自然分割后:臺州市路橋區育才路號單元室—臺州市育才路號單元室，58B501—58B507。分割后再根據情形a)和b)兩種，分別對它們進行比較，計算它們的字段相似度的和，將其均值作為混合字段相似度。

在字段匹配過程中，主要考慮三個方面問題，即輸入錯誤、縮寫和字段值缺失。在消除輸入錯誤方面，考慮到漢字的輸入方式主要是拼音輸入和字型輸入兩種方式，輸入的錯字主要是同音、近音字或字型相似的字，因此，可按照此規律將它們組成一個相似漢字表，供漢字比較時使用。在處理縮寫方面，主要考慮漢字的各種縮寫習慣和詞組構成，根據此規律將它們組成一張字詞連環圖，通過查找字詞連環圖來判斷它們是否是習慣用語的縮寫。在字段值缺失方面，考慮到某個字段值缺失對衡量記錄相似度的影響，采用了有效權值[15]，即只有當兩條記錄在對應字段的值都不為空時，才進行字段比較，并計入該字段對應的權值。字段匹配算法描述如下:

輸入:任意兩個比較記錄的第k個字段xik和xjk。

輸出:兩字段間的相似度。

SimField(xik，xjk)

{Character Process(xik，xjk); //字符化處理

if(xik，xjk∈EnlishCharacterString)

// 字段xik和xjk由英文字符串組成

return EnglishSimField(xik，xjk);

else if(xik，xjk∈ChineseCharacterString)

// 字段xik和xjk由中文字符串組成

return ChineseSimField(xik，xjk);

else {xik→xik1+xik2;

xjk→xjk1+xjk2 ;/*字段xik和xjk由混合字符串組成，分別將它們分割成中英文字符串*/

return

((EnglishSimField(xik1，xjk1)+ChineseSimField(xik2，xjk2))/2;}}

2.5 算法總體思想及描述

前幾節分別解決了記錄初步聚類、計算字段權重以及字段匹配問題。為更好地應用于不同類型字符集，算法采用了字符的內碼序值對記錄進行排序處理，便于記錄聚類。為了提高檢測效率，根據字符的內碼序值，運用聚類思想，先對大數據集進行聚類處理，把大數據集聚集成多個小數據集，再在小數據中分別檢測相似重復記錄。為了提高檢測精度，根據字段的重要程度，利用等級法計算各字段的權值;并通過多趟檢測技術，有效地解決部分相似重復記錄漏查問題。該算法總體的基本思想如下:

a)用戶根據字段實際重要程度給各字段指定等級，系統根據規則計算各字段的最終統一等級，并把最終統一等級轉換為字段相應的權重。

b)選取關鍵字段或字段某些位，計算選取的字符內碼序值，并對整個數據集中的記錄進行排序;再根據字符的內碼序值，將大數據集聚類成多個小數據集。

c)在各小數據集中利用字段加權匹配和有效權值策略分別進行相似重復記錄的檢測，并對檢測出來的相似重復記錄進行標記處理。

d)利用多趟檢測技術，選取其他的關鍵字段或字段某些位，重復以上兩步，重新對數據集進行聚類，并在聚類后的小數據集中檢測相似重復記錄、設置重復標記，避免漏查。

e)按一定的規則輸出檢測出來的相似重復記錄。

總體算法描述如下:

輸入:數據集X，字段向量F，記錄間相似度閾值θ。

輸出:相似重復記錄。

DetectApprDupRecord(X，F，θ)

{ multidetect_flag=true; //多趟檢測的標記

for(i=0; i<=N; i++)xi.duplicate_flag=0;

// 給每條記錄添加重復記錄標記，0表示不重復

ComputeWeight(F);

while(multidetect_flag)

{scanf(ε);// 確定數據集最大記錄數的閾值ε

RecordCluster(X，ε);// 對大數據集進行聚類

for(t=1; t<=s; t++)// s表示聚類后小數據集個數

for(i=1; i<=|Xt|; i++)

// |Xt|表示第t個數據集Xt中記錄的數目

for(j=i+1; j<=|Xt|; j++)

{validweight=0;// validweight表示有效權值

SimRecord(xi，xj) = 0;

for(k=1; k<=p; k++// 計算各記錄間相似度

{if(xik==1‖xjk=1)continue;

// 存在字段值缺失，不計算該字段相似度

validweight= validweight + weight[k];

SimRecord(xi，xj)+=weight[k]*SimField(xik，xjk) ;}

// 根據式(5)計算兩記錄相似度

SimRecord(xi，xj)=SimRecord(xi，xj)/validweight;

// 兩記錄最終相似度

if(SimRecord(xi，xj)>θ)

{if(xi.duplicate_flag=0 xj.duplicate_flag=0)

// 設置重復標記

{xi.duplicate_flag = i;xj.duplicate_flag = i;}

else if(xi.duplicate_flag=0)

xi.duplicate_flag = xj.duplicate_flag;

else if(xj.duplicate_flag=0)

xj.duplicate_flag = xi.duplicate_flag;}}

if(meet termination condition)multidetect_flag=1;}

// 滿足多趟檢測結束條件

output(xi);}// 按一定規則輸出相似重復記錄xi

3 實驗

文獻[4，5]是傳統方法中比較有代表性且較優的兩種方法，它們都是先將整個數據庫記錄按字典排序，然后再進行聚類，文獻[4]采用鍵標志記錄的方法， 而文獻[5]將整個記錄作為一個字符串處理。從數據庫的角度來看，由于數據庫記錄是按一定的模式存放的，文獻[4]的方法更為合理。為了驗證基于內碼序值聚類的重復記錄檢測算法的有效性，本文將該方法與文獻[4]提出的merge/purge 方法進行性能比較。

為便于處理，基于內碼序值聚類的重復記錄檢測方法作為方法一，本文將其簡稱為ICCADD(inner code cluster approximately duplicate detect)，文獻[4]的merge/purge方法作為方法二。本文用實驗對其進行說明，實驗環境是P4 3.0 GHz CPU，物理內存512 MB，硬盤空間80 GB，操作系統Windows XP，數據庫軟件為SQL Server 2000，程序用Java語言編寫。實驗數據來源于某市常住人口數據，含有41個字段項。基本數據格式見表2所示。數據量分別取10.6、36.1、52.4、73.7、104.2萬人，通過軟件和人工等方式對以上數據處理后分別有0.86、3.04、4.94、7.85、12.47千條相似重復記錄。

用上述兩種方法檢測相似重復記錄，考慮三個測試標準，即查準率、查全率和算法運行時間。

3.1 查準率和查全率對比

先進行兩種方法的查準率(圖1)和查全率(圖2)比較。從圖1和2中可以看出，方法二的查準率和查全率遠低于方法一，且隨著數據量增大，方法二的查準率和查全率會下降，而方法一始終可以保持很高的查準率和查全率，這主要是因為方法二由于排序對字符位置敏感，不能保證將相似記錄排在鄰近位置，而方法一根據等級法給不同字段賦予不同權值且在缺失字段中使用有效權值，更能反映現實實體特征，并利用多趟檢測技術有效地提高了檢測精度。因此，用方法一查找相似重復記錄時就有更高的查準率和查全率。

3.2 運行時間對比

對于大數據集傳統方法的磁盤I/O操作成為制約算法運行時間的主要因素。兩種方法運行時間的比較如圖3所示。從圖3中可以明顯地看到，在不同數據量上，方法一的運行時間比方法二要快，這是因為方法一根據字符內碼序值的特點，采用了相似性高的記錄先聚類，聚類后在各個小數據集中進行相似重復記錄查找，總的時間復雜度接近O(n)，而方法二由于其I/O操作時間復雜度大于O(n lg n)，從而運行時間較長。

4 結束語

本文提出了一種基于內碼序值聚類的相似重復記錄檢測方法進行相似重復記錄的檢測。該方法利用等級法計算字段權重且在缺失字段中使用有效權值，以及根據字符的內碼序值對數據集聚類方法，提高了算法的運行效率和檢測精度，能夠有效地解決大數據量的相似重復數據檢測問題。通過實驗分析表明，該方法是一個合理、有效的相似重復數據檢測方法，在中英文字符集中具有較強的通用性。今后的工作是繼續改進算法的某些環節，在實際中更好地應用。

參考文獻:

[1]HAN Jia-wei， MICHELINE K M. 數據挖掘概念與技術[M].范明，孟小峰，譯.北京:機械工業出版社，2007.

[2]LEE N C. Improving data quality: development and evaluation of error detection methods[D]. Taiwan: National Sun Yat-Sen University， 2002.

[3]邱越峰， 田增平，季文赟，等.一種高效的檢測相似重復記錄的方法[J].計算機學報， 2001，24(1):69-77.

[4]HERNADEZ M， STOLFO S. The merge/purge problem for large databases[C]//Proc of SIGMOD International Conference on Management of Data. New York : ACM Press ， 1995:127-138.

[5]MONGE A， ELKAN C. An efficient domain-independent algorithm for detecting approximately duplicate database records[C]//Proc of ACM-SIGMOD Workshop on Research Issues on Knowledge Discovery and Data Mining. Tucson: [s. n.]， 1997.

[6]JIN Liang， LI Chen， MEHROTRA S. Efficient record linkage in large data sets[C]//Proc of the 8th International Conference on Database Systems for Advanced Applications. Kyoto: [s. n.]， 2003:137-148.

[7]BILENKO M， MOONEY R. Adaptive name matching in information integration[J]. IEEE Intelligent Systems， 2003，18(5):16-23.

[8]MINTON S， NANJO C， KNOBLOCK C， et al. A heterogeneous field matching method for record linkage[C]//Proc of the 5th International Conference on Data Mining. Washington: IEEE Computer Society， 2005: 314-321.

[9]BARRON F H， BARRETT B E. Decision quality using ranked attri-bute weights[J]. Management Science， 1996，42(11):1515-1523.

[10]DEY D， SARKAR S， DE P. A distance-based approach to entity reconciliation in heterogeneous databases[J]. IEEE Trans on Know-ledge and Data Engineering， 2002，14(3):567-582.

[11]MONGE A E， ELKAN C P. The field matching problem: algorithms and applications[C]//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining. 1996:267-270.

[12]MONG L， HONGJUN L. Cleansing data for mining and warehousing[C]//Proc of the 10th International Conference on Database and Expert Systems Applications. Florence: [s. n.]， 1999:751-760.

[13]張永，遲忠先. 位置編碼在數據倉庫ETL中的應用[J].計算機工程， 2007，33(1): 50-52.

[14]程國達，蘇杭麗.一種檢測漢語相似重復記錄的有效方法[J].計算機應用， 2005，25(6):1361-1365.

[15]俞榮華，田增平，周傲英.一種檢測多語言文本相似重復記錄的綜合方法[J]. 計算機科學，2002，29(1):118-121.