一種基于核典型相關分析的煤炭矸石鑒別方法*

翟永前，王 浩，趙 力*

(1.南京鐵道職業技術學院，南京210015;2.東南大學信息科學與工程學院，南京210096)

矸石分選是煤礦生產中的重要環節，即在煤塊中將矸石挑選出來，或者從矸石中將煤塊分揀出來。目前在我國主要是靠手工分選的方法存在很大的弊端。近年國內一些研究人員將圖像識別技術運用于矸石分選，提高了生產效率和矸石分選自動化水平［1］。

特征提取是識別技術中重要的步驟，在已有的圖像特征抽取方法中，Fisher 線性鑒別分析(FLDA)被認為是較好的方法之一［2］。由于矸石圖像用向量表示是一個高維的樣本，所以在識別過程中不可避免的存在著小樣本問題，即每個類別可得到的樣本數遠小于樣本特征維數，這會導致Fisher 準則中類內散度陣和類間散度陣均為奇異陣，導致求解存在病態問題。目前，Fisher 鑒別分析在圖像識別中已被廣泛接受和應用，而和Fisher 鑒別分析有等價關系的典型相關分析(CCA)卻沒有在鑒別分析中引起注意和廣泛應用。鑒于此，本文提出利用基于核的典型相關分析(KCCA)來抽取小樣本矸石圖像的非線性鑒別特征，并用其進行鑒別。由CCA 和FLDA 的等價性，這樣得到的非線性特征本質上等價于核Fisher 非線性最佳鑒別特征。為驗證所得特征的有效性，實驗比較了KCCA 和FLDA 所得矸石圖像鑒別特征的識別性能。

1 基于KCCA 的矸石特征抽取和識別方法

矸石圖像識別問題是典型的小樣本問題，若對此小樣本圖像樣本直接構造數據陣X，則得到的Sx是一個較大的奇異陣，無法進行CCA。而核方法是解決小樣本學習問題的有效方法［3］，因此本文在文獻［3］推導CCA 的基礎上，用核方法得出了一種基于核的典型相關分析(KCCA)方法。由CCA 和FLDA 的等價性［5］，此KCCA 方法得到的非線性鑒別特征，等價于核Fisher 鑒別分析得到的Fisher 非線性最佳鑒別特征。

1.1 KCCA 方法的導出

核方法的基本思想是用一個非線性映射將Rd空間中的樣本x 映射到特征空間F，在特征空間中進行分析。設非線映射為Φ:Rd→F，x→Φ(x)，則本矩陣X 變為［Φ(x11)，Φ(x12)，…，Φ(xCnc)］T，為表示方便，將此矩陣中樣本的下標按所在列數順序表示，即XΦ=［Φ(x1)，Φ(x2)，…，Φ(xn)］T。樣本經非線性變換后在特征空間中的內積運算，可用滿足Mercer 條件的正定核函數k(x，y)= Φ(x)TΦ(y)完成。本文使用多項式核函數k(x，y)= (xTy+1)p。用非線性變換后的樣本矩陣XΦ定義矩陣K

n×n 對稱陣K 的第i 行第j 列元素為Kij=k(xi，xj)。

KCCA 的目的是要求解兩個投影矢量aΦ和b，使如下的相關系數最大

約束條件為

由核方法可知，所求鑒別矢量aΦ在所有樣本{Φ(xi)}(i=1，…，n)的張成空間中，即存在n 維列矢量α，使得

求解矢量aΦ只需求解矢量α。將式(5)代入式(2)、式(3)得到約束最優化問題為

約束條件為

和文獻［3］求解CCA 的方法相同，用拉格朗日乘子法求解此帶約束的極值問題，令λ 和μ 為拉格朗日乘子，構造拉格朗日函數為

分別求L(α，b，λ，μ)對α，b 的偏導數，并令其為零，得到

式(10)兩邊乘αT后用約束式(7)代入，式(11)兩邊乘bT后用約束式(8)代入，可得

將上式代入式(10)可得

若K 為非奇異陣，則有

求解矢量α 只需求解此特征方程式非零特征值對應的特征矢量。

1.2 中心化處理和非線性特征抽取

和CCA 需要對樣本零均值化處理相同，上述KCCA 同樣需要樣本映射到特征空間后先零均值化。由于非線性映射的具體形式未知，非線性變換后的訓練樣本零均化是通過下式對矩陣K 中心化完成［6］

其中1n，n為元素全為1 的n×n 矩陣。

K 經中心化后秩減少1，無法直接求解矢量α。本文使用K 的廣義逆K+，得式(16):

K+存在且唯一，其秩為n－1。

矩陣YTY 的秩為C－1，因此可得到C－1 個非零特征值λ1≥λ2≥…≥λC－1和其對應的n 維特征矢量αk(k=1，2，…，C－1)。求出αk后，令A=(α1，α2，…，αC－1)和AΦ=(aΦ1，aΦ2，…，aΦC－1)，即可得到樣本y 的C－1 維的非線性最佳鑒別特征~yΦ

其中Ky為n 維的列向量，其第i 個元素為(Ky)i=k(xi，y)(i=1，2，…，n)。

其中1n為元素全為1 的列向量。y 可是訓練樣本或待識別樣本。

總結KCCA 方法抽取矸石圖像非線性鑒別特征和識別的步驟如下:

(1)用所有樣本由式(1)計算矩陣K，再用式(13)對其中心化，并根據XΦ中每行樣本所屬類別由式(10)構造矩陣Y;

(2)解特征方程式(14)得到C－1 個特征矢量αk(k=1，2，…，C－1);

(3)由式(15)對每個訓練樣本xi求其C－1 維的非線性最佳特征=ATKxi，(i=1，…，n);對待識別樣本y 求其C－1 維的非線性最佳特征=ATKy;

本文用最近鄰分類準則，矢量的2 范數作為距離測度，即待識別樣本和訓練樣本的距離定義為，上標H表示共軛轉置。

2 實驗結果

實驗將40 幅矸石圖像隨機分成兩組，一組為訓練樣本，一組為測試樣本，兩組樣本之間沒有重疊。總類數為40，因此最多可得39 個非線性最佳特征。用最近鄰準則分類，每類所選樣本數均相同。為消除單次選擇樣本的隨機性，每次實驗均重復20 次，最后取平均識別率。對取不同訓練樣本數和不同特征數對識別率的影響進行了實驗，KCCA 方法中用2階多項式核函數，并和FLDA［2］方法進行了比較，每次實驗中不同方法所得結果均是用相同訓練樣本和測試樣本得到，特征個數均取為39 個。

為測試所得特征的鑒別力，在3 個類別中隨機選取5 個樣本，用KPCA 方法分別抽取每個樣本的前兩個最佳鑒別特征，圖1 為每個樣本用兩個最佳鑒別特征表示的散點圖，可看出得到的最佳鑒別特征具有很好的類可分性，即類間散度大而類內散度小。

圖1 樣本的兩個最佳鑒別特征

表1 為取不同樣本數對識別率的影響結果。從表1 可看出KCCA 在樣本數較少時優于FLDA 方法，其對樣本數的變化不敏感;而FLDA 方法對樣本數的變化較敏感，當樣本數較少時識別求解存在病態問題而不能識別。

表1 取不同樣本數時KCCA 和FLDA 的平均識別率

3 結論

本文根據典型相關分析和Fisher 線性鑒別分析的等價性，用核方法將CCA 推廣為KCCA，并用于抽取小樣本矸石圖像的非線性最佳鑒別特征。由CCA 和FLDA 的等價性，這樣得到的特征本質上等價于核Fisher 非線性最佳鑒別特征。實驗結果表明，當識別樣本數較少時KCCA 的識別結果明顯優于FLDA 得到的線性最佳鑒別特征。

［1］ 劉富強，錢建生.基于圖像處理與識別技術的煤礦矸選自動分選［J］.煤炭學報，2000，25(5):534－537.

［2］ Belhumeur P N，Hespanha J P，Kriegman D J. Eigenfaces vs.Fisherfaces:Recognition Using Class Special Linear Projection［J］. IEEE Trans. on Pattern Analysis and Machine Intelligence，1997，19(7):711－720.

［3］ Ma J，Sancho－Gómez J L，Ahalt S C.Nonlinear Multiclass Discriminant Analysis［J］. IEEE Signal Processing Letters，2003，10(7):196－199.

［4］ Lattin J M，Carrol J D，Grean P E. Analyzing Multivariate Data［M］.USA:Brooks/Cole，2003.

［5］ Barker M，Rayens W.Partial Least Square for Discrimination［J］.Journal of Chemometrics，2003，17:166－173.

［5］ Scholkopf B，Somla A，Muller K R.Nonlinear Component Analysis as a Kernel Eigenvalue Problem［J］.Neural Computation，1998，10(5):1299－1319.

［7］ Liu K，Cheng Y Q，Yang J Y，et al.An Efficient Algorithm for Foley－Sammon Optimal Set of Discriminant Vectors by Algebraic Method［J］.Int.J.Pattern Recg.Artif.Intell.1992，6(5):817－829.