仝伯兵，王士同，梅向東

（1. 江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122； 2. 贊奇科技發(fā)展有限公司，江蘇 常州 213000）

?

稀疏條件下的兩層分類算法

仝伯兵1，王士同1，梅向東2

（1. 江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122； 2. 贊奇科技發(fā)展有限公司，江蘇 常州 213000）

在有限樣本下距離量的選擇對最近鄰算法（K-nearest neighbor，KNN）算法有重要影響。針對以前距離量學(xué)習(xí)泛化性不強(qiáng)以及時間效率不高的問題，提出了一種稀疏條件下的兩層分類算法（sparsity-inspired two-level classification algorithm，STLCA）。該算法分為高低2層，在低層使用歐氏距離確定一個未標(biāo)記的樣本局部子空間；在高層，用稀疏貝葉斯在子空間進(jìn)行信息提取。由于其稀疏性，在噪聲情況下有很好的穩(wěn)定性，可泛化性強(qiáng)，且時間效率高。通過在噪聲數(shù)據(jù)以及在視頻煙霧檢測中的應(yīng)用表明，STLCA算法能取得更好的效果。

稀疏貝葉斯；兩層分類；距離學(xué)習(xí)；視頻煙霧檢測；最近鄰算法；有限樣本；泛化性；時間效率

在分類問題中，最近鄰算法（K-nearest neighbor， KNN）是一種古老而又精確的確定決策邊界的非線性分類算法。給定一組訓(xùn)練數(shù)據(jù)，KNN通過k個臨近的樣本中大多數(shù)標(biāo)簽集對未知樣本進(jìn)行預(yù)測。研究表明[1]，最近鄰規(guī)則的漸近錯誤率最多是貝葉斯分類錯誤率的2倍，而且跟所使用的距離量無關(guān)。

當(dāng)訓(xùn)練集有無限數(shù)量的樣本時，類條件概率在無窮小的未標(biāo)記測試樣本域中是常量而與所采用距離量的形式無關(guān)。由于歐氏距離在輸入空間中具有均勻的各向同性的性質(zhì)，因此，歐氏距離作為距離度量來確定最近鄰樣本是自然的選擇。在缺乏先驗(yàn)知識的情況下，大多數(shù)基于KNN的方法使用簡單的歐氏距離衡量樣本間的相似性。然而，在現(xiàn)實(shí)情況下，無限數(shù)量的訓(xùn)練樣本是不存在的。因此，在有限樣本下，假設(shè)局部的類條件概率為常量是不成立的，這樣歐氏距離在訓(xùn)練數(shù)據(jù)中不能充分利用統(tǒng)計規(guī)律。因而，選擇一個合適的距離量來提高最近鄰分類的性能變得至關(guān)重要。

在統(tǒng)計分類和信息檢索中，距離度量的學(xué)習(xí)起到了很大的作用。例如，先前研究表明[2]，適當(dāng)?shù)木嚯x度量可以明顯提升KNN算法的分類精度。大多數(shù)的距離度量學(xué)習(xí)可以分為以下兩大類：1）基于判別分析的度量學(xué)習(xí)如Domeniconi 和 Gunopulos[3]提出一種利用支持向量機(jī)作為指導(dǎo)來定義一個局部靈活度量（local flexible metric classification based on SVMs ， LFM-SVM）的方法。然而，利用核函數(shù)方式使轉(zhuǎn)換數(shù)據(jù)從輸入空間轉(zhuǎn)換到高維特征空間時，數(shù)據(jù)不變性難以維持；2）基于統(tǒng)計分析的度量學(xué)習(xí)如Zhang 等[4]提出了一種通過知識嵌入從訓(xùn)練數(shù)據(jù)集中學(xué)習(xí)距離度量的算法。由于它們位置接近而且局部特征具有相似性，使用新的距離度量可以確定輸入空間中的未標(biāo)記的測試樣本近鄰。Gao等[5]提出了一種基于自適應(yīng)距離度量的兩層最近鄰分類算法（two-level nearest neighbor ， TLNN），該算法在低層以歐氏距離定義一個局部子空間，然后在高層用AdaBoost算法進(jìn)行信息提取，算法框架如圖1所示。AdaBoost算法是由Freund和Schipare[6-8]提出的一種高效的分類方法，然而AdaBoost在有噪聲的情況下容易產(chǎn)生過度擬合導(dǎo)致泛化性差，而且由于AdaBoost進(jìn)行弱分類器訓(xùn)練時需要對訓(xùn)練數(shù)據(jù)進(jìn)行多次遍歷，進(jìn)而導(dǎo)致時間效率較低。

文中提出了一種在稀疏條件下的兩層分類算法（sparsity-inspired two-level classification algorithm， STLCA）。在STLCA算法低層，先用歐氏距離定義一個未標(biāo)記的樣本局部子空間限制高層分類器過度延伸，然后在分類器的高層，用稀疏貝葉斯方法在未標(biāo)記樣本局部子空間進(jìn)行信息提取，算法模型框架如圖2所示。

圖1 TLNN算法模型

圖2 STLCA算法模型

先構(gòu)建核函數(shù)分類器，在求解權(quán)值過程中引入EM方法，根據(jù)稀疏貝葉斯理論使大部分權(quán)值趨于零，其對應(yīng)的核函數(shù)樣本組成相關(guān)向量，保證分類器稀疏性。由于其稀疏性，在噪聲影響下也有很好的穩(wěn)定性，且由于分類器不必多次遍歷訓(xùn)練樣本使得時間效率較高。將得到的權(quán)值與核分類器組建概率模型，利用最小絕對誤差原則進(jìn)行距離度量學(xué)習(xí)，將新距離量應(yīng)用到最近鄰算法中，構(gòu)成一種新的強(qiáng)分類器STLCA算法。通過對比實(shí)驗(yàn)可知，STLCA算法在噪聲數(shù)據(jù)和視頻煙霧檢測應(yīng)用中有很好的效果。

1 方法模型

1.1 用最小絕對誤差進(jìn)行距離度量學(xué)習(xí)

設(shè)x是要預(yù)測的類標(biāo)簽未知的樣本點(diǎn)，x′是x的最鄰近點(diǎn)。對于一般的最近鄰算法，未知樣本x被錯分的概率如式（1）[9]：

PN（e|x）=P（w1|x）P（w2|x′）+P（w2|x）P（w1|x′）=P（w1|x）[1-P（w1|x′）]+P（w2|x）P（w1|x′）=2P（w1|x）P（w2|x）+[P（w1|x）-P（w2|x）]·

式中：N表示訓(xùn)練樣本的數(shù)量，w1,w2表示類標(biāo)簽，為了簡便起見此處只考慮二分類，對于多分類問題通常轉(zhuǎn)換成多級二分類問題來處理。當(dāng)訓(xùn)練樣本的數(shù)量N→時，漸近條件錯誤率為

這樣，式（1）和式（2）都表示最近鄰法的條件錯誤率，只不過式（1）針對有限樣本，而式（2）是對無限樣本而言，如果考慮兩者之間的誤差，式（3）：

PN（e|x）-P（e|x）=[P（w1|x）-P（w2|x）]·

在有限樣本或無限樣本訓(xùn)練樣本下的平均絕對誤差的誤差率為式（4）：

定義式（5）為

那么式（5）中σ（x,x′）和P（w1|x）-P（w1|x′）之間的對應(yīng)關(guān)系如圖3所示。

圖 3 σ（x,x′）線性關(guān)系圖

由于[P（w1|x）-P（w2|x）]在式（3）中是一個常數(shù)項(xiàng)，那么最小化|PN（e|x）-P（e|x）|相當(dāng)于最小化σ（x,x′）。通?？梢酝ㄟ^增加訓(xùn)練樣本的數(shù)量最小化σ（x,x′），或者定義一個等價距離量如文獻(xiàn)[5]中所采用的方法。然而在這里所論述的，是想通過另外的方式求解。

在2類問題y∈{1,-1}中（此時規(guī)定標(biāo)簽w1=1,w2=-1），對于給定的x可以通過廣義線性模型[10]確定屬于某一類的概率：

式中：h（x）為分類器，γ為分類器權(quán)重向量。而此處Φ（z）為高斯累計分布函數(shù)（也被稱為鏈接函數(shù)），其形式為式（7）：

將概率模型的輸入特征進(jìn)行非線性轉(zhuǎn)換可以應(yīng)用到非線性函數(shù)中，對于權(quán)值向量γ其基本形式包括以下3種形式[10-11]：

1）線性分類器：h（x）=[1 x1… xd]，此時γ是一個d+1維的向量；

2）非線性分類器：h（x）=[1 φ1（x） ... φk（x）]T，此處φ（·）是非線性函數(shù)，γ為k+1維向量；

3）核函數(shù)分類器：h（x）=[1 K（x,x（1）） … K（x,x（n））]T，此處K（·,·）為核函數(shù)，γ為n+1維向量。

如果能夠得到γ值，那么就可以對變量x的標(biāo)簽做出預(yù)測。對于普遍使用的參數(shù)估計方法如最大似然函數(shù)法有式（8）的表現(xiàn)形式：

或拉普拉斯條件概率分布，如式（10）：

式中：α是假設(shè)參數(shù)向量。由于不能從公式中直接獲得參數(shù)γ，本文采用EM迭代方法獲取參數(shù)γ。對于參數(shù)γ按式（10）的拉普拉斯條件概率分布，可采用下面EM迭代步驟進(jìn)行求解（算法1）：

1）對于給定的訓(xùn)練數(shù)據(jù)集計算矩陣H；此處采用核函數(shù)對矩陣進(jìn)行運(yùn)算，其中h（x）=[1 K（x,x（1）） … K（x,x（n））]T，

H=[hT（x1） hT（x2） … hT（xn）]T

2）計算γ的初始值，可以通過如下公式對γ 進(jìn)行初始化：

式中：ε為初始參數(shù)，I為單位矩陣。

稀疏貝葉斯方法與給似然函數(shù)加上懲罰函數(shù)等方法的不同之處在于：稀疏貝葉斯方法在迭代優(yōu)化的過程中能使大部分權(quán)值γi趨于零，其相應(yīng)的核函數(shù)和訓(xùn)練樣本被剔除，只保留少數(shù)的權(quán)值γi不為零，這樣可以保證分類器的稀疏性，其對應(yīng)的保留下來的訓(xùn)練樣本稱為相關(guān)向量（relevance vector， RV）。在概率模型中，一個重要的特性是該模型包含一個隱含變量即式（15）所示：

式中：η為均值為零單位方差的高斯變量。對于二分類問題，假設(shè)分類器定義為y=1如果z（x,γ）≥0，且y=-1當(dāng)z（x,γ）<0。那么概率模型可以表示為式（16）：

h（x）|0,1）=

P（γTh（x）+η≥0）

（16）

則式（5）可以表示為式（17）：

σ（x,x′）=|P（1|x）-P（1|x′）|=

|Φ（γTh（x）|0,1）-Φ（γTh（x′）|0,1）|=

|P（γTh（x）+η≥0）-P（γTh（x′）+η≥0）|

（7）

則新的距離量可以改寫為式（18）：

D′（x,x′）=|P（γTh（x）+η≥0）-P（γTh（x′）+η≥0）|∝|sign（γTh（x）+η≥0）-sign（γTh（x′）+η≥0）|=

此時已經(jīng)定義了一個新的距離量，下面將給出算法步驟。

1.2 稀疏條件下的兩層分類算法

文中提出的稀疏條件下的兩層分類算法。先用最近鄰算法建立一個局部子空間，即在低層使用歐氏距離為每個測試數(shù)據(jù)選定k個近鄰樣本組成子空間，這樣可以限制稀疏貝葉斯信息提取時過度延伸；然后在STLCA分類器的高層，用上文中的新距離量從子空間選定近鄰來確定測試數(shù)據(jù)標(biāo)簽。稀疏貝葉斯算法通過EM迭代優(yōu)化的方法對權(quán)值γ進(jìn)行求解，使大部分權(quán)值趨于零，保證了分類器的稀疏性，在噪聲情況下也有很好的穩(wěn)定性。由于在求解過程中直接進(jìn)行矩陣運(yùn)算而不同于AdaBoost對訓(xùn)練集多次遍歷評估弱分類器性能，因此時間效率較好。

綜上所述，STLCA算法描述如下（算法2）：

1）利用上文中的算法一對權(quán)值向量γ值進(jìn)行參數(shù)估計；

4）對于給定的觀測值x判定其標(biāo)簽y：y=sign（avex′∈R′（x）y′）。

2 實(shí)驗(yàn)與分析

本次試驗(yàn)均在MATLAB7.10.0平臺下完成，實(shí)驗(yàn)環(huán)境為CPU Intel Core（TM） i3-3240 3.40 GHz,內(nèi)存4 GB。通過UCI數(shù)據(jù)集和視頻煙霧2種數(shù)據(jù)對算法有效性進(jìn)行對比驗(yàn)證。

2.1 UCI標(biāo)準(zhǔn)數(shù)據(jù)集

在本節(jié)中，使用真實(shí)數(shù)據(jù)集對幾種算法進(jìn)行比較以驗(yàn)證文中提出的算法和其他算法的分類效果及抗噪能力。從UCI數(shù)據(jù)庫中挑選二分類數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)類別標(biāo)記為+1和-1，刪除屬性值缺失的實(shí)例，數(shù)據(jù)的基本信息如表1所示。

表1 UCI數(shù)據(jù)集的基本信息Table 1 Description of UCI dada sets

實(shí)驗(yàn)中所有訓(xùn)練數(shù)據(jù)特征先進(jìn)行歸一化到零均值和單位方差，測試數(shù)據(jù)使用相應(yīng)的均值和方差進(jìn)行歸一化。將每個數(shù)據(jù)集隨機(jī)分成2個大小相等的子集，使用其中一個子集作為訓(xùn)練集，另一個作為測試集，然后再將2個子集交換。將過程重復(fù)10次（10×2交叉驗(yàn)證），取平均值作為結(jié)果。在TLNN和STLCA算法中，近鄰數(shù)量關(guān)系設(shè)置為k1=2·k2+1，此處設(shè)置k2=3。在AdaBoost與TLNN算法中，以單特征值訓(xùn)練泛化型AdaBoost的弱分類器，最大訓(xùn)練迭代次數(shù)T=30。在稀疏貝葉斯和STLCA算法求解向量γ值時，設(shè)置ε=10-6和δ=10-3，在計算矩陣H時，核寬值如表2所示。

2.2 STLCA算法比較與分析

將STLCA與AdaBoost、TLNN、KNN和稀疏貝葉斯進(jìn)行對比，各算法分類錯誤率如表3所示。

表2 UCI數(shù)據(jù)集核寬值Table 2 Kernel width of UCI data sets

表3 UCI數(shù)據(jù)集分類錯誤率

Table 3 Classification error rate of UCI data sets%

注：表中數(shù)值為錯誤率+標(biāo)準(zhǔn)差形式。

表3中顯示了不同算法數(shù)據(jù)分類的錯誤率，文中將錯誤率最低的數(shù)據(jù)加黑。從實(shí)驗(yàn)結(jié)果看，在16組數(shù)據(jù)中，AdaBoost和TLNN算法各有2組數(shù)據(jù)取得最低錯誤率，KNN算法和稀疏貝葉斯算法分別有1組和3組數(shù)據(jù)取得最低錯誤率，而STLCA算法在8組數(shù)據(jù)中取得最優(yōu)結(jié)果。在STLCA算法未取得最優(yōu)結(jié)果的8組數(shù)據(jù)中仍有3組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果優(yōu)于稀疏貝葉斯方法，可見STLCA算法在分類精度上整體要優(yōu)于TLNN和稀疏貝葉斯等方法。

任何現(xiàn)實(shí)的算法模型在樣本學(xué)習(xí)中必須處理噪聲問題，因此，有必要測試在噪聲數(shù)據(jù)的影響下STLCA算法的性能。本文通過對表1中16組數(shù)據(jù)引入標(biāo)簽噪聲來比較5種算法的抗噪性能。在訓(xùn)練集中隨機(jī)挑選部分?jǐn)?shù)據(jù)，然后調(diào)換它們的標(biāo)簽，而其他樣本保持不變。這樣構(gòu)造5%、10%、15%、20%的隨機(jī)噪聲數(shù)據(jù)集。表4～7給出了4種不同噪聲下5種算法分類錯誤率結(jié)果。

表4 5%噪聲數(shù)據(jù)分類錯誤率

Table 4 Classification error rate with 5% noise%

注：表中數(shù)值為錯誤率+標(biāo)準(zhǔn)差形式。

表5 10%噪聲數(shù)據(jù)分類錯誤率Table 5 Classification error rate with 10% noise%

表6 15%噪聲數(shù)據(jù)分類錯誤率

Table 6 Classification error rate with 15% noise%

注：表中數(shù)值為錯誤率+標(biāo)準(zhǔn)差形式。

表7 20%噪聲數(shù)據(jù)分類錯誤率

Table 7 Classification error rate with 20% noise%

注：表中數(shù)值為錯誤率+標(biāo)準(zhǔn)差形式。

將表4～7給出的 5種算法在標(biāo)簽噪聲分布數(shù)據(jù)錯誤率最低的數(shù)據(jù)加黑。從實(shí)驗(yàn)結(jié)果可以看出，AdaBoost算法在5%、10%、15%、20%的隨機(jī)噪聲數(shù)據(jù)集中分別有2組、1組、2組、2組數(shù)據(jù)中取得最優(yōu)，然而除contraceptive數(shù)據(jù)集外，其他最優(yōu)結(jié)果數(shù)據(jù)集并不一致，可見AdaBoost算法有一定波動性，容易受噪聲影響。TLNN算法分別在1組、1組、0組、0組數(shù)據(jù)集中取得最優(yōu)，表明TLNN算法在噪聲條件下性能出現(xiàn)一定退化。稀疏貝葉斯和KNN算法未出現(xiàn)明顯波動，性能較為穩(wěn)定。而STLCA在標(biāo)簽噪聲為5%、10%、15%和20%的結(jié)果中分別有8組、9組、9組和11組數(shù)據(jù)取得最優(yōu)，隨著噪聲數(shù)據(jù)增加分類結(jié)果變優(yōu)，表明STLCA算法在噪聲情況下有很好的穩(wěn)定性，泛化能力強(qiáng)。

2.3 視頻煙霧檢測

火災(zāi)嚴(yán)重威脅人類的生命和財產(chǎn)安全，因此及時檢測和預(yù)防火災(zāi)具有重要意義, 在火災(zāi)監(jiān)控中，煙霧檢測對于實(shí)現(xiàn)早期火災(zāi)預(yù)警[15-17]具有重要作用。

文中將STLCA算法應(yīng)用到視頻煙霧檢測中，以驗(yàn)證算法的檢測效果。實(shí)驗(yàn)中的煙霧視頻來源于土耳其Bilkent大學(xué)機(jī)器視覺研究室（http://signal.ee.bilkent.edu.tr/VisiFire/）視頻資源庫（http://imagelab.ing.unimore.it/visor/video_categories.asp）。圖4所示為4組實(shí)驗(yàn)視頻截取第60幀圖像的場景，從左至右、從上至下依次為Video1～Video4。

圖4 實(shí)驗(yàn)視頻場景

視頻分辨率為240×320，實(shí)驗(yàn)中將每一幀圖像分為60像素×60像素的小塊，因此圖像被分為3×4塊。實(shí)驗(yàn)中每組圖像數(shù)據(jù)為從相應(yīng)視頻中每6幀取一幀圖像組成數(shù)據(jù)集，然后將每個數(shù)據(jù)集隨機(jī)分成2個大小相等的子集，其中一個為訓(xùn)練集，另一個為測試集，數(shù)據(jù)集詳細(xì)信息如表8所示。

表8 煙霧檢測實(shí)驗(yàn)數(shù)據(jù)信息Table 8 Description of smoke detection

將STLCA算法與文獻(xiàn)[20]中采用的AdaBoost算法以及文獻(xiàn)[5]中的TLNN算法進(jìn)行煙霧檢測，并采用離散余弦變換和離散小波變換2種特征提取方式進(jìn)行對比試驗(yàn)。在STLCA算法與TLNN算法中近鄰數(shù)量關(guān)系設(shè)置為k1=2·k2+1，設(shè)置k2=3。在AdaBoost與TLNN算法中，以單特征值訓(xùn)練泛化型AdaBoost的弱分類器，最大訓(xùn)練迭代次數(shù)T=30。在STLCA算法求解向量γ值時，設(shè)置ε=10-6和δ=10-2，在計算矩陣H時核寬值選擇如表9所示。

表9 煙霧檢測核寬值Table 9 Kernel width of smoke detection

實(shí)驗(yàn)通過分類準(zhǔn)確率和算法運(yùn)行時間（訓(xùn)練時間+測試時間）2個方面對算法的效率進(jìn)行評估，算法運(yùn)行結(jié)果如表10和表11所示。

表10 煙霧檢測精度

Table 10 Accuracy of smoke detection %

算法Video1Video2Video3Video4AdaBoost+DCT93.5990.5696.1289.97TLNN+DCT93.4390.0096.2693.70STLCA+DCT95.9193.7896.5696.79AdaBoost+DWT92.7988.1196.9891.56TLNN+DWT93.7588.2296.7793.53STLCA+DWT94.3491.5696.7795.59

表11 煙霧檢測運(yùn)行時間

Table 11 Time-consumed of smoke detection s

算法Video1Video2Video3Video4AdaBoost+DCT40.5981.39178.66330.70TLNN+DCT41.4983.78182.57337.61STLCA+DCT15.0138.92140.20229.92AdaBoost+DWT37.3084.11162.66292.66TLNN+DWT47.2376.89163.37301.21STLCA+DWT13.3627.2196.45199.19

表10和表11分別為AdaBoost、TLNN和STLCA算法并結(jié)合離散余弦變換和離散小波變換2種方式進(jìn)行實(shí)驗(yàn)，從檢測精度和運(yùn)行時間2個方面得到的實(shí)驗(yàn)結(jié)果。從實(shí)驗(yàn)結(jié)果看，4組視頻中采用離散余弦變換進(jìn)行特征提取檢測煙霧時， STLCA在4組數(shù)據(jù)中都取得了最優(yōu)的結(jié)果，在采用離散小波變換進(jìn)行特征提取進(jìn)行煙霧檢測時，除Video3外在其余3組視頻中取得最優(yōu)結(jié)果。從整體實(shí)驗(yàn)結(jié)果看，STLCA算法在Video1、Video2和Video4等3組視頻數(shù)據(jù)中取得最優(yōu)結(jié)果，在Video3數(shù)據(jù)中，雖然未取得最優(yōu)結(jié)果，但STLCA算法結(jié)合離散小波變換方式檢測結(jié)果與最優(yōu)結(jié)果非常接近。在時間效率方面，由于AdaBoost與TLNN算法在弱分類器訓(xùn)練時需要多次對訓(xùn)練集進(jìn)行遍歷，時間效率較低。采用STLCA算法進(jìn)行視頻煙霧檢測，由于以稀疏貝葉斯方式為基礎(chǔ)，使訓(xùn)練時間大幅減小，無論采用離散余弦變換或者離散小波變換，STLCA算法的時間效率都明顯優(yōu)于其他2種算法。因此STLCA算法有明顯的優(yōu)勢。

3 結(jié)束語

文中提出了一種新的在稀疏條件下的2層分類算法（STLCA），先用最近鄰算法建立一個局部子空間，這樣可以限制稀疏貝葉斯信息提取時過度延伸，然后在STLCA分類器的高層，用稀疏貝葉斯在未標(biāo)記樣本子空間進(jìn)行信息提取。該方法使用少量核就可以達(dá)到很高的分類精度，由于其稀疏性在噪聲影響下仍有很好的穩(wěn)定性，且時間效率高。STLCA算法性能通過在噪聲數(shù)據(jù)以及在視頻煙霧檢測中的應(yīng)用得到驗(yàn)證。然而該算法由于需要對矩陣進(jìn)行運(yùn)算，在對大量數(shù)據(jù)組成的矩陣求逆時需要大量內(nèi)存空間，這也成為制約該算法性能的瓶頸，所以如何提取有效特征對數(shù)據(jù)矩陣進(jìn)行壓縮，提高運(yùn)算效率是未來研究的方向。

[1] COVER T M, HART P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13（1）: 21-27.

[2]GOLDBERGER J, ROWEIS S, HINTON G, et al. Neighborhood components analysis[J]. Advances in Neural Networks, 2005, 16（4）: 899-909.

[3]DOMENICONI C, GUNOPULOS D. Adaptive nearest classification using support vector machines[C]// Advances in Neural Information Processing Systems. Boston: MIT Press, 2002: 655-672.

[4]ZHANG Yungang, ZHANG Changshui, ZHANG D. Distance metric learning by knowledge[J].Pattern Recognition, 2004, 37（1）: 161-163.

[5]GAO Yunlong, PAN Jinyan, JI Guoli, et al. A novel two-level nearest classification algorithm using an adaptive distance metric[J]. Knowledge Based Systems, 2012, 26: 103-110.

[6]FREUND Y, SCHAPIRE R. A Decision-theoretic generalization of on-line learning and application to boosting[J].Journal of Computer and System Sciences,1997,55（1）,119-139.

[7]FREUND Y, SCHAPIRE R. Experiments with a new boosting algorithm[C] //Proc of the 13th International Conference on Machine Learning. Bari, Italy,1996: 14 8-156.

[8]SCHAPIRE R, SINGER Y. Improved boosting algorithms using confidence-rated predictions[J]. Machine Learning, 1999, 37（3）: 297-336.

[9]張學(xué)工，邊肇祺.模式識別:2版[M].北京：清華大學(xué)出版社， 2000: 156-158.

[10]FIGUEIREDO M A T. Adaptive sparseness for supervised learning [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25（9）: 1150-1159.

[11]KRISHNAPURAM B, HARTEMINK A J, CARIN L, et al. A Bayesian approach to joint feature select and classifier design[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26（9）: 1105-1111.

[12]FIGUEIREDO M A T, JAIN A K. Bayesian learning of sparse classifiers[C]// Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. [s.l.], 2001： 35-41.

[13]張旭東，陳鋒，高雋,等.稀疏貝葉斯及其在時間序列預(yù)測中的應(yīng)用[J].控制與決策, 2006, 26（5）： 585-588. ZHANG Xudong, CHEN Feng, GAO Jun, et al. Sparse Bayesian and its application to time series forecasting[J]. Control and Decision, 2006, 26（5）： 585-588.

[14]TIPPING M E. Sparse Bayesian learning and the relevance vector machine[J]. Journal of Machine Learning Research, 2001（1）: 211-244.

[15]CHEN Juan, HE Yaping, WANG Jian. Multi-feature fusion based fast video flame detection[J]. Building and Environment, 2010, 45（5）:1113-1122.

[16]KO B C, KWAK J, NAM J. Wildfire smoke detection using temporal-spatial features and random forest classifiers[J]. Optical Engineering, 2012, 51（1）: 1-10.

[17]羅勝，JIANG Yuzheng.視頻檢測煙霧的研究現(xiàn)狀[J].中國圖象圖形學(xué)報,2013,18（10）:1225-1236. LUO Sheng, JIANG Yuzheng. State-of-art of video based smoke detection algorithms[J].Journal of Image and Graphics, 2013, 18（10）: 1225-1236.

[18]GUBBI J, MARUSIC S, PALANISWAMI M. Smoke detection in video using wavelets and support vector machines

[J]. Fire Safety Journal, 2009, 44（8）: 1110-1115.

[19]盛家川.基于小波變換的國畫特征提取及分類[J].計算機(jī)科學(xué), 2014, 41（2）: 317-319. SHENG Jiachuan. Automatic categorization of traditional Chinese paintings based on wavelet transform[J]. Computer Science, 2014, 41（2）: 317-319.

[20]WANG Zhijie, BEN Salah , ZHANG Hong. Discrete wavelet transform based steam detection with Adaboost[C] // International Conference on Information and Automation. Shenyang, China, 2012: 542-547.

仝伯兵，男，1989生，碩士研究生，主要研究方向?yàn)槿斯ぶ悄芘c模式識別、數(shù)字圖像處理。

王士同，男，1964生，教授，博士生導(dǎo)師，主要研究方向?yàn)槿斯ぶ悄?、模式識別和生物信息。

梅向東，男，1966生，高級工程師，主要研究方向?yàn)槎嗝襟w及計算機(jī)應(yīng)用。

Sparsity-inspired two-level classification algorithm

TONG Bobing1， WANG Shitong1， MEI Xiangdong2

（1. School of Digital Media, Jiangnan University, Wuxi 214122, China; 2. Zanqi Science Technology Development Co.,Ltd, Changzhou 213000, China）

The selection of distance greatly affects KNN algorithm as it relates to finite samples due to weak generalization and low time efficiency in the previous learning of distance. In this paper, a new sparsity-inspired two-level classification algorithm （STLCA） is proposed. This proposed algorithm is divided into two levels: high and low. It uses Euclidean distance at the low-level to determine an unlabeled sample local subspace and at the high level it uses sparse Bayesian to extract information from subspace. Due to the sparsity in noise conditions, STLCA can have good stability, strong generalization and high time efficiency. The results showed that the STLCA algorithm can achieve better results through the application in noise data and video smoke detection.

parse Bayesian; two-level classification; distance learning; video smoke detection; KNN; finite samples; generalization; time efficiency

2014-07-14.

日期：2015-01-13.

國家自然科學(xué)基金資助項(xiàng)目（61170122,61272210）；江蘇省自然科學(xué)基金資助項(xiàng)目（BK2011417）;江蘇省“333”工程基金資助項(xiàng)目（BRA2011142）.

仝伯兵. E-mail：tongbobing@163.com.

10.3969/j.issn.1673-4785.201407019

http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.004.html

TP391.4

A

1673-4785（2015）01-0027-10

仝伯兵，王士同，梅向東. 稀疏條件下的兩層分類算法[J]. 智能系統(tǒng)學(xué)報， 2015, 10（1）: 27-36.

英文引用格式：TONG Bobing，WANG Shitong，MEI Xiangdong. Sparsity-inspired two-level classification algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10（1）:27-36.