符號序列多階Markov分類在銀行客戶風(fēng)險(xiǎn)預(yù)測中的應(yīng)用

程鈴鈁，陳黎飛，賴曉燕，林燕

（1.福建農(nóng)林大學(xué) 金山學(xué)院，福建 福州 350002；2.福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350117）

0 引言

當(dāng)今，由于金融行業(yè)突飛猛進(jìn)的發(fā)展，銀行可以從龐大的數(shù)據(jù)庫中挖掘出很多潛在的價(jià)值，譬如銀行賬戶資產(chǎn)信息、用戶個人以及交易等信息，以便提高銀行業(yè)務(wù)水平和運(yùn)營收益。然而在投資主體越發(fā)復(fù)雜、多元的背景下，必須高度重視風(fēng)險(xiǎn)預(yù)警工作的重要性。由此正確預(yù)測銀行客戶風(fēng)險(xiǎn)是一項(xiàng)非常重要的風(fēng)險(xiǎn)管理任務(wù)，其具有重要的意義[1-2]。

早期的銀行破產(chǎn)預(yù)測的模型較多采用傳統(tǒng)計(jì)量和統(tǒng)計(jì)方法。近年來，伴隨人工智能的不斷發(fā)展，機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘技術(shù)得到廣泛推廣，銀行風(fēng)險(xiǎn)預(yù)測因此得到行之有效的方法。

目前國內(nèi)較多學(xué)者首先通過改進(jìn)apriori算法、銀行客戶信息特性，以實(shí)現(xiàn)快速響應(yīng)和智能分析。然后采用非結(jié)構(gòu)化手段存儲客戶各項(xiàng)關(guān)聯(lián)信息，并對信息進(jìn)行清洗、轉(zhuǎn)化、標(biāo)準(zhǔn)化等處理后將有用的信息存儲在數(shù)據(jù)庫中，為下一步的數(shù)據(jù)分析提供數(shù)據(jù)源。最后構(gòu)建客戶風(fēng)險(xiǎn)評估和預(yù)測的模型[3-5]。然而，目前大多數(shù)模型都應(yīng)用于國外，國內(nèi)大多數(shù)學(xué)者的研究始終停留在定性分析的層面，尚未研究出與國情相匹配的完整模型，由此銀行在應(yīng)用模型時(shí)時(shí)常遇到亟待改進(jìn)的局限。

1 馬爾科夫模型

隱馬爾科夫模型（簡稱“HMM”）是結(jié)構(gòu)最簡單的動態(tài)貝葉斯網(wǎng)，其中的變量分為兩組，第一組是狀態(tài)變量{y1，y2…yn}，表示第i時(shí)刻的系統(tǒng)狀態(tài)。第二組是觀測變量{x1，x2…xn}，其中表示第i時(shí)刻的觀測值。模型中存在多個狀態(tài)相互之間轉(zhuǎn)換，觀測變量Xi可以是離散型也可以是連續(xù)型[6-9]。我們假定其取值范圍X為{o1，o2…om}。

從圖1可以看出，變量之間存在依賴關(guān)系，t時(shí)刻狀態(tài)yt僅依賴于t-1時(shí)刻的狀態(tài)yt-1，與此前t-2個狀態(tài)無關(guān)[10]。由此我們推出新的分布式：

隱馬爾科夫需要的3個參數(shù)分別是：

表示在任意時(shí)刻t，若狀態(tài)為Si，則在下一時(shí)刻狀態(tài)為Sj的概率。

表示在任意時(shí)刻t，若狀態(tài)為Si，則觀測值Oj被獲取的概率。

銀行客戶管理中客戶行為通常采用離散符號表示，一段時(shí)間內(nèi)的客戶行為即構(gòu)成一條符號序列。符號數(shù)據(jù)包含結(jié)構(gòu)化的符號屬性（類屬型）數(shù)據(jù)和非結(jié)構(gòu)化符號序列數(shù)據(jù)，對符號數(shù)據(jù)進(jìn)行分類是必要過程。目前得到廣泛使用的支持向量機(jī)、決策樹、近鄰（nearest neighbor，NN）分類、基于概率模型的分類的機(jī)器學(xué)習(xí)方法多針對向量型數(shù)據(jù)，同時(shí)現(xiàn)在的符號序列Markov分類多數(shù)是基于固定階Markov模型（n-階Markov模型），而階數(shù)n與所提取的序列結(jié)構(gòu)特征息息相關(guān)，其值將直接影響分類器的性能，最終會影響預(yù)測的結(jié)果，所以最優(yōu)階次n的估計(jì)和重視其他階次子序列等問題亟待解決[11-16]。

由于符號序列長度通常不相等并且數(shù)據(jù)之間有順序關(guān)系，所以符號序列相似性度量成為難題。當(dāng)前研究符號序列的主要方法主要有兩種。

第一種是直接法。通過序列比對直接度量序列間相似性，如果滿足相同的或者相似的符號子串越多相似性越大。代表性算法包括SCS、n-gram等。以n-gram算法中n=2為例，對aenhashow和aenheshowe進(jìn)行分段，可得如下結(jié)果（采用斜體標(biāo)出公共子串）：

ae，en，nh，ha，as，sh，ho，ow

ae，en，nh，he，es，sh，ho，ow，we

比對后發(fā)現(xiàn)兩序列的公共符號子串?dāng)?shù)為6。但是直接法缺點(diǎn)是不能捕捉符號序列下有序符號的隱藏信息，譬如序列中全局結(jié)構(gòu)信息等。

第二種是間接法。此法能夠捕捉隱藏在序列中的全局結(jié)構(gòu)，也稱其是基于模型的方法。然而基于模型的方法劣勢是度量兩個序列間相似性時(shí)僅僅利用兩個序列所構(gòu)建的模型，而忽略了數(shù)據(jù)集整體的統(tǒng)計(jì)信息。

上面兩種方法，即子序列法和概率模型法，用于提取序列結(jié)構(gòu)特征。第一種以n-元組為代表，目的是提取蘊(yùn)含在序列中的局部結(jié)構(gòu)信息，后者通過Markov模型、隱Markov模型記錄序列中的全局結(jié)構(gòu)信息。我們可以理解n-元組是序列中n個連續(xù)符號構(gòu)成的短子序列，相當(dāng)于n-階Markov模型中的前綴子序列。由此可以說，n-gram方法是Markov模型的一種應(yīng)用[17]。當(dāng)前，基于Markov模型的分類器已成為符號序列分類的主要工具之一[18-19]。

然而，當(dāng)n給定后，僅有固定階次的子序列進(jìn)行序列分類，而忽略其他階次子序列中的結(jié)構(gòu)信息，必然影響符號序列Markov分類的性能。

本文針對上述問題，提出一種符號序列貝葉斯分類新方法，該方法是基于多階Markov模型基礎(chǔ)上的，高階的Markov鏈表示馬爾科夫鏈的高階記憶性，即下一步的狀態(tài)不僅和當(dāng)前狀態(tài)相關(guān)，同時(shí)和之前多步的狀態(tài)也相關(guān)，這將有助于提高基于行為符號序列的銀行客戶破產(chǎn)風(fēng)險(xiǎn)的預(yù)測精度。首先開展對序列中各種符號以及符號彼此順序關(guān)系的監(jiān)督學(xué)習(xí)，預(yù)測對象的類別標(biāo)號，提出多階馬爾科夫模型；然后在一個統(tǒng)一的模型中同時(shí)使用1~n階馬爾科夫鏈模型化符號序列，并構(gòu)造新的算法，最終提出了一種新的貝葉斯分類器[20]。

2 相關(guān)工作

首先約定使用記號。W為訓(xùn)練數(shù)據(jù)集（由N個樣本構(gòu)成的），每個樣本是一個二元組（S，k），其中S表示符號序列，k∈[1，K]是序列S的類別標(biāo)示，K為類別數(shù)。序列S的長度記為L，即S表示為S=s1，s2，…sL。所有符號的集合記為D，|D|表示其中的符號數(shù)；因此，si∈D，i=1，2…L。

基于如下假設(shè)：任一序列S中符號si與其前綴子序列s0，s1…si-1相關(guān)性很大，其中s0表示序列的起點(diǎn)。采用n階馬爾科夫模型時(shí)，前綴子序列被截?cái)酁棣膌（n）=sl-n…sl-1，其中j＜0的符號sj用s0代替，所以n階馬爾科夫模型中的前綴子序列具有固定的長度n，用“（n）”標(biāo)識。序列S的概率是條件概率的乘積來估計(jì)，即：

式（1）表示的模型稱為符號序列的條件概率分布模型[13-16]。用于分類時(shí)，式中的條件概率根據(jù)訓(xùn)練數(shù)據(jù)集中符號的條件分布估計(jì)；顯然，這種條件分布隨訓(xùn)練類別的不同而有所差異。記符號sl相對于第k個訓(xùn)練類別的條件概率為，通常使用如下拉普拉斯校正估計(jì)：

其中，fk（t）表示子序列t在第k個訓(xùn)練類別的所有序列中出現(xiàn)的次數(shù)。

2.1 符號序列多階馬爾科夫模型

在一個n-階Markov模型中，序列S中符號sl的條件概率定義在長度固定為n的前綴子序列δl（n）=sln…sl-1上。對于一個給定的序列集，理想的模型階數(shù)可能是1，2，3…具體取值應(yīng)與序列結(jié)構(gòu)有關(guān)。鑒于估計(jì)最優(yōu)模型階數(shù)的困難，本文提出多階模型方案，基于如下假設(shè)：（X）給定一個較大的n，序列集最優(yōu)Markov模型的階數(shù)i∈[1，n]；（Y）任何階數(shù)為i∈[1，n]的模型都是可能的，但各模型的“可能性”不同。對于序列S中的符號sl，事實(shí)上，其n-階Markov模型下的前綴子序列已經(jīng)包含了所有i∈[1，n]階前綴子序列。注意到是的后綴子序列，這為構(gòu)造融合i∈[1，n]階的多階模型提供了基礎(chǔ)。

結(jié)合上述假設(shè)，序列S第k類的先驗(yàn)概率P(S|k)估計(jì)為：

由式（3）可以分析得出包含n個條件概率，i∈[1，n]。衡量各階次Markov模型的“可能性”，即不同階次條件概率的貢獻(xiàn)度，我們用“階次權(quán)重”（簡稱“階權(quán)”）w1-1，w2-1，…，wn-1表示。顯然，若wn=1且其他i∈[1，n]階的權(quán)重為0，式（3）退化為單階條件概率模型。另一方面，從優(yōu)化的角度看，當(dāng)所有權(quán)重均為0時(shí)P（S|k）取最大值，為避免所有階次模型具有相同的可能性，并區(qū)分不同階次的貢獻(xiàn)，務(wù)必對式（3）進(jìn)一步約束，條件是：。

2.2 多階馬爾科夫模型算法的構(gòu)造

通過遍歷掃描序列集而獲得的條件概率，既可以提高計(jì)算的效率，又能夠使得算法更加高效。為得到式（3）中的多階模型，所以為每一條序列的每一個符號sl計(jì)算條件概率pk（sl|δl（i）），我們稱這種數(shù)據(jù)結(jié)構(gòu)為“附后綴表的N階后綴樹”，簡稱n-STS，如圖2所示。

如圖2所示，序列“XYXXXYYXY”和“YYXYXYX”由‘X’和‘Y’兩個符號組成，在每個結(jié)點(diǎn)上附加一個后綴表，用來記錄當(dāng)前結(jié)點(diǎn)對應(yīng)子序列作為前綴的符號個數(shù)。其中以‘X’為后綴的3階對應(yīng)樹上5條路徑，分別是“□□X”“XXX”“YXX”“XYX”和“YYX”，假設(shè)，在序列“XYXXXYYXY”和“YYXYXYX”中，3-元前綴子序列“YYX”之后符號＇Y＇出現(xiàn)了2次，‘X’為0次，所以標(biāo)注TXYY為圖中格式。同理，子序列“YX”是“YYX”的后綴子序列，所以其結(jié)點(diǎn)是“YYX”對應(yīng)的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)，由此在“XYXXXYYXY”和“YYXYXYX”序列中，TXY的標(biāo)注表示以“YX”為前綴，其后的‘X’和‘Y’的計(jì)數(shù)分別為1和3。

圖2中的重要性質(zhì)是：前綴子序列在序列集中的計(jì)數(shù)即是后綴表中所有計(jì)數(shù)的和。所以利用式（2）和n-STS樹可得出每個符號的條件概率。譬如，對于2-元前綴子序列δl(2)=“YX”，由TXY可知fk(“YXX”)=1和fk(“YXY”)=3，則fk(“YX”)=fk(“YXX”)+fk(“YXY”)=4；由式（2）得出估計(jì)條件概率為pk(＇X＇|δl(2))=(1+1)/(4+2)≈0.33和pk(＇Y＇|δl(2))=(3+1)/(4+2)≈0.67。綜上所述最終得到式（3）所需的所有階次的條件概率。

初始模型階數(shù)n和給定訓(xùn)練集W，可以為每個類k的序列構(gòu)造一棵n-STS樹，各個樹根結(jié)點(diǎn)用NK表示，k=1，2…K；每棵樹最多有|D|棵子樹；算法掃描每條序列S，為其上每個符號sl提取其n-元前綴子序列δl（n），插入n-STS樹后更新各個結(jié)點(diǎn)的后綴表。算法過程描述如下。

算法：n-STS樹構(gòu)造算法；

輸入：訓(xùn)練集W，階數(shù)n；

輸出：K棵n-STS樹。

算法掃描序列集一次構(gòu)造出K棵n-STS樹。算法的時(shí)間復(fù)雜度為O（n×M），其中，M表示W(wǎng)中所有序列的總長度。

2.3 改進(jìn)后的貝葉斯分類器

OWYC即基于多階Markov模型的符號序列貝葉斯分類器。給定訓(xùn)練集W以及由算法生成的K棵n-STS樹，OWYC訓(xùn)練階段算法從中學(xué)習(xí)優(yōu)化的階權(quán)集合W={wi|i=1，2…n}。采用最大似然學(xué)習(xí)法，最大化下列目標(biāo)函數(shù)：

將其代入式（3）引入歸一化約束條件式后使用拉格朗日乘子法λ，目標(biāo)函數(shù)變?yōu)椋?/p>

3 實(shí)驗(yàn)方法和步驟

分別在3個不同應(yīng)用領(lǐng)域開展實(shí)驗(yàn)，形成6個數(shù)據(jù)集，包括銀行客戶行為序列、基因、語音序列（表1）。DNX序列集DS1和DS2、語音序列集YS1和YS2中序列長度較長，其中DNX取自NCYI基因庫和PYIL微生物同源基因家族庫。語音序列集由5個法語元音（＇X＇，＇e＇，＇i＇，＇o＇，＇u＇）的音頻分箱取樣而來。銀行客戶行為序列來自連續(xù)10或12個月信用卡交易行為符號序列，反映客服行為的符號數(shù)為3個。序列長度分別是10或12。相對DNX序列集序列長度較長，符號數(shù)也較多，語音序列集YS1和YS2的符號數(shù)是最多的。

3.1 實(shí)驗(yàn)數(shù)據(jù)與設(shè)置

實(shí)驗(yàn)采用4種不同方法形成分類器性能的對比，見表2，分別采用一階馬爾科夫模型的貝葉斯分類器為（簡稱為BC），BC分類器相當(dāng)于OWBC一個特例：當(dāng)wn固定為1且wi-1=0時(shí)，OWBC即可退化為BC。還采用1-NN（近鄰數(shù)為1的近鄰分類器）、SVM方法，二者都使用基于n-gram的符號序列向量表示模型。為提高分類性能，1-NN分類器采用加權(quán)投票法，SVM分類器為C-SVC，采用了LIBSVM的實(shí)現(xiàn)。使用分類精度CA作為各種分類器指標(biāo)的評估。

表2 實(shí)際序列集上不同分類器的平均分類精度及n-gram數(shù)目

CA為預(yù)測結(jié)果與真實(shí)類別相符的樣本占全體待分類樣本的比例，計(jì)算公式如下：

式（6）中I是取值0或1的指示函數(shù)，k＇S表示分類器預(yù)測的類別標(biāo)號，kS表示測試序列S真實(shí)類別標(biāo)號，|W|為測試序列的數(shù)量。由此可見，CA的值越大分類器具有越好的分類性能。

3.2 分類性能評估

表2數(shù)據(jù)顯示，由于數(shù)據(jù)高維的特性以及高維空間特征間存在相關(guān)性，所以1-NN和SVM的平均分類精度明顯低于兩個貝葉斯分類器。還看出銀行序列集經(jīng)過特征約簡后1-NN和SVM的平均分類精度基本保持不變；在基因序列和銀行序列中GS1、GS2、BS1、BS2，SVM上的平均分類精度略有提高；但在SS1、SS2上精度顯著下降。這說明固定階數(shù)子序列如果進(jìn)行特征簡單的約簡處理，其實(shí)不能有效提高分類精度。

由圖3可以看出，不同階次子序列對序列類別的預(yù)測會因?yàn)樨暙I(xiàn)程度不同導(dǎo)致預(yù)測結(jié)果不同。同時(shí)還發(fā)現(xiàn)一個有趣的現(xiàn)象：BS1，BS2的銀行客戶行為序列，GS1，GS2的DNA序列，都會隨著階次的提高對分類的貢獻(xiàn)表現(xiàn)出增加的趨勢，但是并不適用于SS1，SS2語音序列，而只有在3階子序列時(shí)貢獻(xiàn)最大。以上分析將為確定符號序列馬爾科夫模型最優(yōu)階數(shù)提供參考。

3.3 預(yù)設(shè)階數(shù)n的影響

由3.2節(jié)分析得出，OWBC算法時(shí)間復(fù)雜度為O（n×M），階數(shù)n和序列總長度M呈線性關(guān)系，算法復(fù)雜度則是O（n2×M），接下來實(shí)驗(yàn)將重點(diǎn)關(guān)注算法復(fù)雜度。從圖4不難發(fā)現(xiàn)，OWBC算法隨著階次（2＜=n＜=8）所需時(shí)間呈多項(xiàng)式增長趨勢。因?yàn)閷?shí)際應(yīng)用中n＜＜M，所以O(shè)WBC學(xué)習(xí)效率較高。6個實(shí)際序列集上的訓(xùn)練任務(wù)均可在1秒內(nèi)完成。

如圖5所示，本組實(shí)驗(yàn)采用5-折交叉驗(yàn)證法，對于兩個銀行客戶行為序列來說，OWBC平均分類精度在n＞6時(shí)略有下降。在兩個DNA序列集上，其平均分類精度隨n變大反而略有增加。但是在語音序列集上OWBC接近100%的高分類精度?？梢哉fOWBC對預(yù)設(shè)階數(shù)n的變化是魯棒的。OWBC采用的多階馬爾科夫模型加權(quán)融合機(jī)制，既能夠抵消不正確模型階數(shù)對分類器性能的影響，又可以在不同應(yīng)用領(lǐng)域序列集上取得高質(zhì)量分類結(jié)果。

4 結(jié)語

目前廣泛使用的支持向量機(jī)、決策樹等機(jī)器學(xué)習(xí)方法多針對向量型數(shù)據(jù)，而符號序列Markov分類多數(shù)是基于固定階Markov模型（n-階Markov模型），而階數(shù)n與所提取的序列結(jié)構(gòu)特征息息相關(guān)，其值將直接影響分類器的性能。本文提出多階馬爾科夫模型，為構(gòu)造多階模型，提出了后綴樹結(jié)構(gòu)，并且構(gòu)造出后綴樹的高效算法，最終提出新的貝葉斯分類器。新分類器的訓(xùn)練算法既可以學(xué)習(xí)各種符號不同階次的條件概率，還可以優(yōu)化不同階次的權(quán)重。為驗(yàn)證新分類器有效性，我們在三個實(shí)際應(yīng)用領(lǐng)域的序列集上開展實(shí)驗(yàn)，并驗(yàn)證了新的分類器對預(yù)設(shè)階數(shù)n是魯棒的。新分類器通過使用多階馬爾科夫模型加權(quán)機(jī)制，可抵消錯誤模型階數(shù)對分類器性能的影響，得出可在不同應(yīng)用領(lǐng)域的實(shí)際序列集上取得高質(zhì)量的分類結(jié)果。