基于免疫克隆算法的網(wǎng)店屬地判定

程新黨，張新剛，趙學武

淘寶網(wǎng)的交易量與日劇增，據(jù)浙江省商務廳發(fā)布的《浙江省網(wǎng)絡零售業(yè)發(fā)展報告》統(tǒng)計，截至2014年底，淘寶網(wǎng)入住店鋪數(shù)量達到147萬家［1］，而且店鋪數(shù)量和交易量每天都在增加。各地工商管理部門有責任監(jiān)管本地區(qū)的網(wǎng)店，而網(wǎng)店并不在本地工商系統(tǒng)內注冊登記，導致屬地工商局難于管理。雖然淘寶網(wǎng)提供了按地區(qū)搜索店鋪的功能，但經(jīng)工商管理部門的實際驗證發(fā)現(xiàn)該功能不僅返回網(wǎng)店數(shù)量嚴重偏少，而且準確率較低。因此，目前部分地市工商管理部門采用人工篩選、逐個核實的方式查找屬于本地區(qū)的網(wǎng)店。這種方式雖然準確，但人工處理所屬區(qū)域標注不準、數(shù)量龐大的店鋪不僅效率低下，而且很難做到全面查找。利用計算機技術實現(xiàn)的自動化屬地判定不僅可以節(jié)省人力物力，而且在屬地判定的同時也可對網(wǎng)店進行整理備案，有利于監(jiān)管。為此，我們提出了一種使用自動化網(wǎng)頁分析技術快速判斷網(wǎng)店屬地的方案。該方案使用免疫克隆算法和感知機模型，根據(jù)網(wǎng)店頁面特定內容對網(wǎng)店進行屬地判定，可以快速判斷網(wǎng)店的屬地，并且每周更新一次，對于隨時都在增加和消亡的網(wǎng)絡店鋪的監(jiān)控具有重要意義，能夠滿足工商管理部門對網(wǎng)店的監(jiān)管需求，對消費者維權具有一定的意義。

1 相關工作

對于各地工商管理部門來說，僅需要監(jiān)管所在地區(qū)內的網(wǎng)店經(jīng)營情況，即僅需判定特定網(wǎng)店是否屬于本地區(qū)即可。因此，屬地判定技術屬于二類分類的范疇。近年來，人們針對文本分類問題提出了很多模型，如樸素貝葉斯分類法［2］、決策樹算法［3］、神經(jīng)網(wǎng)絡［4］和支持向量機［5］等。但純文本分類的方法對結構化的網(wǎng)頁分類誤差較大。針對這個問題，蘭均等［6］提出基于特征詞的復合權重的關聯(lián)網(wǎng)頁分類技術，并取得了較好的效果。不過，對位置權重采用專家經(jīng)驗賦值的方法有一定的應用局限性。但他們的研究表明：對于網(wǎng)頁這種半結構化文本的分類，不同位置的特征權重有很大的區(qū)別，在判定模型的選擇時需要考慮到不同位置的特征差異性，而感知機模型、支持向量機模型、Logistic回歸模型等的多項式系數(shù)都可以理解為權重信息。張長水在參考文獻［7］中指出文本分類是最容易發(fā)生“維數(shù)災難”的機器學習應用場景，雖然通過分詞字典限制、部分提取等手段可有效地降低特征的維數(shù)，但實際特征總數(shù)仍達2 000多項，這使模型計算的復雜度較高，并且其中很多分詞在地域的判定上毫無意義，需要通過特征選擇技術選取與問題相關的特征并去除冗余。

特征選擇在保留數(shù)據(jù)任務的同時，不僅能夠提供與原數(shù)據(jù)近似的表現(xiàn)，而且對問題的本質具有更強的可解讀性。特征選擇也是有效的降維手段，可使計算更簡單。

特征選擇作為一種數(shù)據(jù)預處理手段，已經(jīng)引起了國內外學者的廣泛關注并被應用到多個行業(yè)，如圖像分析、社會網(wǎng)絡分析和入侵檢測技術［8］等。應用較多的特征選擇方法有文檔頻率、信息增益、互信息、開方擬和檢驗等。單松巍等［9］對中文網(wǎng)頁分類中這幾種特征選取方法進行了比較研究，指出這些方法的共同缺點是需要人工控制選擇特征的數(shù)量，增大了算法的不可靠性和隨機性。近年來，出現(xiàn)了一些有特色的優(yōu)化問題求解方法［10-15］,如模擬退火、遺傳算法（GA）、免疫克隆選擇（ICSA）和基于粗糙集理論（BRS）等方法。Dong等［10］與 Ghareb 等［11］的研究結果表明：遺傳算法雖然具有較強的全局搜索性能，但在實際應用中容易產(chǎn)生早熟收斂問題，導致在進化后期特征信息對問題求解的指導作用被限制。Wang 等［13］與段潔等［14］提出了基于粗糙集依賴度量的特征子集選擇方法，但該方法較為耗時。比較而言，參考文獻［16-17］給出的免疫克隆算法具有收斂速度快、求解精度高和穩(wěn)定性好等優(yōu)點，能有效克服早熟問題。因此，我們選擇免疫克隆算法進行特征選擇，通過親和度函數(shù)進行評估，得到最優(yōu)的感知機模型，然后使用該模型對網(wǎng)店進行屬地判定。

2 感知機與網(wǎng)店特征向量化

2.1 感知機模型

感知機是一種二類線性分類模型，通過細微調節(jié)權重值可以減少感知機的期望輸出和實際輸出之間的差別。感知機的訓練屬于有監(jiān)督學習算法，簡單來說，可以采用基于誤分類的損失函數(shù)對分類質量進行評估，再利用隨機梯度下降法或其他算法對損失函數(shù)進行極小化，從而得到模型參數(shù)。基本模型可以用

表示，其中w為感知機模型權重參數(shù)，b為偏置量。

本文算法利用感知機模型的權重來區(qū)分網(wǎng)頁中不同位置分詞特征的重要性，不僅能夠滿足應用需求，而且感知機模型相對于支持向量機、Logistic回歸等模型而言具有模型簡單、算法易于實現(xiàn)、占用內存少等優(yōu)點。

2.2 網(wǎng)店特征向量化

通過對大量網(wǎng)店人工分析發(fā)現(xiàn)，網(wǎng)店只有在店鋪標題（位置編號1）、店鋪名稱（位置編號2）、店鋪首頁Meta元素（位置編號 3）、店鋪介紹（位置編號 4）、所在地信息（位置編號5）、配送信息（位置編號6）、商品描述（位置編號7）等網(wǎng)頁位置的分詞中含有較多的地域特征，而其他位置幾乎不含與地域相關的分詞信息，并且這些不同位置的特征分詞對于網(wǎng)店屬地的判定所起作用的重要性差別也很大。模型整體示意圖如圖1所示。

圖1 網(wǎng)店特征向量示意圖

為了體現(xiàn)位置重要性的差別，我們采取了兩步措施。第一步是先按位置對網(wǎng)頁中的分詞分別進行統(tǒng)計，再按照順序組合，構成表達網(wǎng)店的文本特征向量。向量在各維度的取值表示對應特征的權重。特征的取值方式采用傳統(tǒng)的TF-IDF（term frequency－inverse document frequency）法，如圖 1 中的［x1，x2，…，xk］向量。這種TF-IDF計算方法不能表現(xiàn)分詞在網(wǎng)頁中位置的不同，而在我們所研究的問題中存在如店鋪標題內的地域信息等在對屬地的判定中所起的作用要比商品描述內的地域信息更重要的情況，因此屬地判定模型還需要能夠表示網(wǎng)頁位置特征這一重要差異。故采取的第二步措施是使用感知機模型的權重系數(shù)來表示位置差異。在網(wǎng)頁中位置相同的各個特征項共享同一個權重系數(shù) （如構成店鋪標題的各個分詞），如圖1中的{w1，w2，…，wk}序列。

由于分詞項按上述7個不同位置分別統(tǒng)計可能導致部分特征被重復統(tǒng)計，當7個位置的特征分詞組合后，特征數(shù)量將超過2 000項，因此需要引入免疫克隆算法進行特征選擇去除冗余特征，降低模型的計算復雜度。

網(wǎng)店的特征表示是進行屬地判定的基礎。在向量空間（VSM）模型中，網(wǎng)頁空間可被看作是由一組正交詞條向量組成的向量空間。將樣本中每個網(wǎng)店按7大位置要素的順序分別采集分詞并去掉停用詞，再根據(jù)7大要素分別計算各分詞的TF-IDF值，然后將每個樣本的各TF-IDF值按照位置編號順序組合成單一向量，如特征總數(shù)為n，則構成n維向量，即樣本可以表示為

全體樣本可以表示為

其中m為樣本總數(shù)。各樣本特征向量被分為7段，分段長度表示為

3 免疫克隆選擇搜索算法

免疫克隆選擇機制［18］最早是由Burnet等人提出的，該算法在設計上集中了全局搜索和局部搜索的優(yōu)點，包含了細胞學習、記憶、克隆、變異和抗體多樣性等多種生物特性。算法中B細胞和抗原對應著選擇最優(yōu)特征子集問題，而抗體對應著問題的可行解?？寺∵x擇的本質是搜索出與抗原親和度較高的抗體，然后對搜索出的抗體進行變異，這相當于在較優(yōu)解的領域進行跳躍式搜索，可有效防止進化早熟，避免搜索陷入局部最優(yōu)。同時，使用克隆選擇也可加快收斂速度。我們使用免疫克隆選擇算法將分段特征選擇算法與感知機模型的訓練結合起來，在獲得最優(yōu)特征組合的同時得到各個特征分段的位置權重信息，用于解決網(wǎng)店屬地判定問題，這對將網(wǎng)頁按主題分類也具有參考意義。

3.1 抗體編碼

數(shù)據(jù)集 D 中含有 m 個樣本 D={d1，d2，…，dm}，每個樣本都有特征集合X={x1，x2，…，xn}，X包含n維特征。特征選擇是在特征集合X中找到一個最優(yōu)的特征子集S，使S含有k維特征，且有k＜n。算法中每個抗體都表示一種特征組合，對應著X的一個子集。

我們所研究的案例采用二進制基因串編碼方案?；虼L度是特征總個數(shù)，抗體中每個基因位對應兩種模式，即某位值為1時表示相應特征被選中，為0時表示相應特征未被選中。設特征向量di長度為n，對應抗體 ai編碼為（β1i，β2i，…，βji，…，βni），j=1，2，…，n，則

3.2 親和度函數(shù)設計

我們希望在特征選擇的同時搜索到相應的感知機模型，因此在親和度函數(shù)設計時需要考慮感知機模型的參數(shù)信息。根據(jù)感知機模型［式（1）］，設抗體群為P={a1，a2，…，an},其中 ai（1≤i≤n）表示 X 的一個子集 Si，定義親和度函數(shù)為

其中， λ 是一個大于0且小于1的權值參數(shù)，r表示以Si為特征時算法在交叉驗證時的分類召回率。

召回率r（recall）是衡量算法正確識別的概率，根據(jù)感知機模型，定義為

式（6）中：C為樣本中正例的個數(shù)；I為指示函數(shù)，當yi=1 且（wx+b）＞0 時 I為 1，否則為 0。

式（5）中的e表示與原始特征集X相比子集Si的簡化率，定義為

這里的|X|、|Si|、|X|分別表示各集合中元素的數(shù)量。可以看出， λ 越大，r對親和度的影響越大，反之e對親和度的影響越大。

我們在親和度函數(shù)中選擇使用召回率r而不使用正確率的原因是：在屬地判定應用中是以高召回率為標準來判定系統(tǒng)的優(yōu)劣的，即要求具有較少的監(jiān)管盲區(qū)。由于特征選擇的原則是用盡量少的特征代替原本數(shù)量較多的特征，且使分類召回率較之前更好或者不發(fā)生較大改變，那么原問題就可以轉化為式（5）所表示函數(shù)的最大化問題。

3.3 算法設計

算法總體上分為以下幾個步驟：產(chǎn)生包含若干抗體的初始抗體群；使用隨機梯度下降法結合特征分段與特征選擇進行感知機模型的訓練并計算對應抗體的親和度；根據(jù)親和度大小克隆出數(shù)量不等的抗體；按照一定的概率進行免疫操作后進行抑制操作，向抗體群補充新抗體來保證群體的多樣性。

3.3.1 算法總體流程

算法流程如Algorithm1所示。

Algorithm1：免疫克隆搜索算法輸入：

樣本集 D={TR，TE}；

轉換后特征段長序列 L={l1，l2，…，l7}；

輸出：感知機模型與對應特征子集；

①初始種群大小p，最大進化代數(shù)TCmax，抑制操作比例Rs=0.25，克 隆 比 例 Rclone=0.25，p=50，λ =0.85，af=0.8，γ=0.9，TCmax=500；n=l7；

②P=population（random（）,p,n） //初始抗體群for t to TCmax//未到最大進化代數(shù)時繼續(xù)

③for each aiin P //對抗體群中的每個ai

執(zhí)行Algorithm2計算模型

執(zhí)行Algorithm3計算親和度

④SortByFitness（P） //按親和度降序排序P

⑤判斷是否達到精度要求，是則退出

⑥z=p×Rclone//選擇需要克隆的抗體數(shù)

for j=0 to z //計算各選中抗體克隆數(shù)量

kc=int（（z×af/（i+3））×ln（z-i+1）-1）

Clone（P,i,kc）→PStemp

for each pjmin PStemp

//按概率 pmutate=1-exp［fj-fmax-0.1）/t］變異

PSmutate→P

⑦population（random（）,p,n）→P //多樣性

⑧af=af× γ//更新加速因子，返回③繼續(xù)

⑨到最大進化代數(shù)輸出結果并退出

3.3.2 設計原理

算法每個步驟設計原理和詳細描述如下。

（1）產(chǎn)生初始抗體群。隨機產(chǎn)生初始抗體群P，設初始抗體群規(guī)模大小為p=|P|，軟件中生成方式為

這里 n 為特征長度，random（）為在（0，1）上均勻分布的隨機函數(shù)。函數(shù)population（）的功能是：先用random（）函數(shù)值生成p×n階矩陣，再對矩陣元素四舍五入使之轉變?yōu)?或1，這樣便返回p個由n位二進制位串表示的抗體，每個抗體的長度為n，與特征向量長度相同。但因特征向量由7個分段構成，而二進制位串編碼方式未含各段長度信息，故需要與段長相結合。段長表示為序列L={l1，l2，…，l7}，L的值在網(wǎng)店特征向量化之后已經(jīng)確定。為了便于計算，將L的各元素做如下處理l1=l1；li=li-1+li；i=2，3，…，7。算法中使用的 L 均指轉換之后的L。

（2）搜索感知機模型。對抗體群P中各個抗體a，先計算各抗體對應特征子集選擇時的感知機模型參數(shù)，再使用該模型計算出對應的親和度函數(shù)值。這部分可以分為計算模型參數(shù)和計算親和度兩個部分。

1）計算模型參數(shù)

根據(jù)圖1的描述，特征向量x的總長度為n，但實質上是由7段不同性質的特征分量按照固定順序構成，每段特征分量共享同一個權重值wj，即該模型最多有 7 個權重 w1、w2、…、w7，段長序列為 L。 因此該模型的訓練與常規(guī)算法不同，采用隨機梯度下降法。算法如Algorithm2所示。

Algorithm2：特征分段感知機模型訓練算法輸入：

訓練樣本集TR；

轉換后特征段長 L={l1，l2，…，l7}；

待評估抗體 am=［β1m，β2m，…，βjm，βnm］；

最大迭代次數(shù)Tmax和學習率η；

輸出：模型參數(shù)w和b；

①初始化參數(shù)：w=0，b=0，k=0，Err=0；

②for t=0 to Tmax//循環(huán)迭代Tmax次

③{TR}→di=（xi，yi）//從訓練集中隨機選擇出 di

④k=0 //計算wx

for j=0 to n-1

if j＞lkthen k←k+1

ifβim==1 then dtemp←dtemp+wk×xij

⑤if（dtemp+b）×yi＜0 then

⑥Err←Err+1

⑦for j=0 to n-1 //更新w

if j＞lkthen

k←k+1

wk←w+tx×yi×η

else ifβim==1 then tx←tx+xi

⑧b←b+yi×η

⑨if t＞|TR|and Err==0 then

return w，b //誤分類為0時退出

⑩返回②繼續(xù)

11return w，b //到達最大迭代次數(shù)退出

Algorithm 2中的步驟④是根據(jù)待評估抗體am和段長序列L將選中的特征值xij與該特征對應的權重wk相乘后累加。步驟⑤用來判斷：如在當前值和b值下分類錯誤，則由步驟⑦循環(huán)更新各個權重，由步驟⑧更新b值。算法最終返回模型參數(shù)w和b。最壞情況下的時間復雜度為 O（2n×Tmax）。

2）計算親和度

使用測試樣本集T及w和b的值，根據(jù)式（5）、（6）和（7）計算親和度，算法如 Algorithm3所示。Algorithm 3 的時間復雜度為 O（n×|TE|），|TE|表示集合中元素的數(shù)量。

Algorithm3：親和度計算輸入：

測試樣本集TE；

轉換后特征段長序列 L={l1，l2，…，l7}；

待評估抗體 am=［β1m，β2m，…，βjm，βnm］；

感知機模型參數(shù)w和b；

輸出：親和度函數(shù)值f；

①初始化：TP=0，F(xiàn)N=0，TN=0，F(xiàn)P=0，Te=0;

②for j=0 to n-1 //計算簡化率

if βim==1 then Te←Te+1

e=（n-Te）/n

③for each diin{TE}

④di（xi，yi） //從測試集中順序取 di

⑤k=0 //計算 w·x

for j=0 to n-1

if j＞lkthen k←k+1

ifβim==1 then dtemp←dtemp+wk×xij

⑥if（dtemp+b）×yi＞0 then //分類正確

⑦if yi==1 then TP←TP+1 //樣本為正例

else TN←TN+1 //樣本為負例

⑧else //分類錯誤

if yi==1 then FN←FN+1 else FP←FP+1

⑨返回④取下一個樣本di+1繼續(xù)

⑩r=TP/（TP+FN） //計算召回率

（3）親和度排序比較。將所有抗體按親和度值進行降序排列，如果種群達到最大進化代數(shù)Tmax或者精度達到預定要求，則將抗體群中親和度最高的抗體進行映射輸出，即為算法所選擇的特征子集。同時，輸出感知機參數(shù)w和b，即搜索到了最優(yōu)感知機模型。否則，轉（2）。

（4）克隆選擇。對按親和度值降序排列后的抗體群，選擇前z=p×Rclone個抗體進行克隆，并且要求每個抗體克隆新抗體個數(shù)與親和度值成正向關系，同時刪除其他親和度較低的抗體。所有從選中的抗體克隆出的抗體總數(shù)由

決定。其中i為z個最優(yōu)抗體的排序號，int（）為取整函數(shù)。通過式（9）中自然對數(shù)和乘法規(guī)則將抗體數(shù)按優(yōu)劣進行了層次劃分。

式（9）中的 af為加速因子［19］，它隨著進化代數(shù)動態(tài)更新。引入加速因子是為了加快算法收斂速度。在每一代結束時按照

進行更新。af的初始值小于1，γ 的取值范圍為［0.5，1.1］，根據(jù)參考文獻［20］，當af=0.89且γ =0.9時收斂速度與最優(yōu)解達到最佳。

（5）基因免疫。所有克隆產(chǎn)生的抗體在進入下一代之前，都需要進行基因免疫。本算法僅利用變異操作進行免疫，即對代表抗體的基因位按照

表示的概率pm進行0/1反轉操作；同時刪除重復抗體來保持多樣性，保證新抗體尚未在候選抗體群中出現(xiàn)過。

式（11）中fmax表示本代抗體群中親和度的最大值，fp表示基因免疫前該抗體的親和度值，t為當前進化代數(shù)。在進化初期t取值較小而pm值較大時，抗體中有較多的基因位被反轉，擴大了搜索范圍，在一定程度上避免陷入局部最優(yōu)。隨著進化代數(shù)t增大，pm值減小，抗體中較少的基因位被反轉，相當于執(zhí)行局部精確搜索。在同一代抗體中，親和度較小的抗體所對應的可行解距離全局最優(yōu)解較遠，由式（11）計算得到的pm值較大，因而抗體中被反轉的基因位就較多，即免疫后的新抗體距離原抗體較遠，這樣的pm值設計確保了基因免疫操作的有效性。

（6）抑制操作。為了保證對抗體群的多樣化的抑制操作，即隨機產(chǎn)生一定數(shù)量的抗體加入候選抗體群中，必須保證新產(chǎn)生的抗體尚未在候選抗體群中。

（7）重復（2）～（6）中算法各步驟直到取得最優(yōu)解。

3.4 算法分析

算法的時間復雜度主要由幾部分構成：感知機模型訓練 O（2n×Tmax）、親和度計算 O（n×|TE|）、親和度排序 O（p×p/2）、基因免疫與抑制操作 O（n×p），其中 n 為樣本的特征長度。當進化代數(shù)為TCmax時，算法整體時間復雜度為 O（TCmax×2n×Tmax+TCmax×n×|TE|+TCmax×n×p+TCmax×p×p/2）≈O（TCmax×3n×Tmax），與進化代數(shù)、感知機模型訓練迭代次數(shù)和特征長度相關。

本算法與其他智能算法（如進化算法、遺傳算法等）相比有如下不同：僅選擇優(yōu)秀抗體進行克隆，配合加速因子加快了算法的收斂速度；引入變異概率pm，在進化初期執(zhí)行較多全局搜索，在進化后期執(zhí)行較多局部搜索，實現(xiàn)了全局與局部搜索較好的平衡；抑制操作體現(xiàn)出了免疫反應的自我調節(jié)功能；感知機模型訓練算法結合了特征分段與特征選擇技術；其中特征分段技術可使段內特征分量共享同一權值，較好地區(qū)分了網(wǎng)頁中不同位置的特征分詞在分類時的重要性差異。

4 實驗及分析

4.1 評估標準

為了評價本算法得到的最優(yōu)特征子集和相對應的感知機模型的分類質量，需要將樣本數(shù)據(jù)進行二次劃分：先將樣本按照交叉留存驗證法劃分為訓練集TR和測試集TE，再用留一法將訓練集TR作為完整樣本劃分為訓練集TR1和測試集TE1，并在TR1上使用本算法搜索得到的最優(yōu)特征子集和相對應的感知機模型，最后使用測試集TE1進行驗證評估。

為了比較算法的性能，在算法搜索階段，我們在相同的數(shù)據(jù)集上還進行了基于粗糙集理論的特征選擇和基于遺傳算法的特征選擇實驗，并且使用準確率（precision）、召回率（recall）以及 F1 測量（F1-Measure）三個指標對分類結果進行比較。準確率是對算法決策正確性的衡量，召回率是衡量算法正確識別的概率，F(xiàn)1測量測試綜合考量兩種因素。計算方法是：precision=這里的TP為正確找到的屬于某地的店鋪，AC為找到的所有屬于某地的店鋪，CC為樣本中屬于某地的店鋪。

4.2 數(shù)據(jù)來源

實驗數(shù)據(jù)樣本通過如下方法得到。

工商局工作人員通過人工查找和電話確認的方法，找到屬于南陽市的網(wǎng)店720個，確定不屬于南陽市的網(wǎng)店2 200個，在不屬于南陽市的網(wǎng)店集合中隨機加上800個屬地未確定的網(wǎng)店，得到了3 000個樣本數(shù)據(jù)，記為樣本1。

感知機模型系數(shù)僅用來區(qū)分網(wǎng)頁分詞的位置權重，因此，在理論上使用某個地市樣本獲得的模型權重參數(shù)w應具有通用性，而偏置量b則不具有通用性。為了驗證模型的通用性假設，選取屬于鄭州市的網(wǎng)店300個，不屬于鄭州市的網(wǎng)店1 200個，記為樣本2。

在實驗中，樣本數(shù)據(jù)采用＜URL,分類標貼＞對的形式表示，即一個網(wǎng)店可以表示為di={URLi,Yi},如d1={https://zhat.taobao.com,1}表示該網(wǎng)店屬于某地，d2={https://sulbin.taobao.com,-1}表示不屬于某地。將所有{URL，值}存入數(shù)據(jù)表中，根據(jù)URL通過采集程序訪問指定頁面，取指定位置的詞，分詞后存入本地文件中，按照2.2中的方法將各網(wǎng)店樣本數(shù)據(jù)向量化并形成新的樣本格式。

4.3 結果分析

與其他的免疫克隆選擇算法相比，我們所用算法的基本流程與盧曉勇等在參考文獻［20］中所采用的流程類似，均對進化與親和度計算的順序有所調整。免疫克隆算法需要設置的參數(shù)較多，主要有初始化抗體群的抗體數(shù)、克隆選擇抗體的比例、進行基因免疫的抗體比例、抑制操作的比例以及進化代數(shù)等［21］。我們進行了大量實驗，結果表明：初始化抗體群的抗體數(shù)的選擇僅僅影響算法的運行時間，對特征選擇和感知機模型幾乎沒有影響。

為了簡化算法，我們將克隆選擇抗體的比例和抑制操作的比例定為25%，進行基因免疫的抗體比例定為100%。為了確定進化代數(shù)，設初始值TCmax=5 000，在實驗的算法搜索階段，記錄的進化代數(shù)與誤分類數(shù)關系如圖2所示。

圖2中共有三條曲線，分別是無特征選擇下感知機模型（Only-Percep.）、使用遺傳算法進行特征選擇下的感知機模型（GA）和使用免疫克隆算法進行特征選擇下的感知機模型（ICSA）。當進化代數(shù)在470時，ICSA的誤分類數(shù)最小，故最大進化代數(shù)選擇500即可。從無特征選擇下感知機模型的實驗結果可以看出：由于網(wǎng)店屬地判定的特殊性，分詞（原有特征）中無效項或干擾項太多，導致樣本數(shù)據(jù)線性不可分；進化代數(shù)從600到900，誤分類數(shù)基本不變（針對線性不可分的情況，我們將誤分類數(shù)降到10個以下作為終止條件）。從圖2中還可以看出ICSA的收斂速度比GA快，誤分類率也低。

在GA中，根據(jù)適應度函數(shù)選出的雙親基因相似度較高，它們產(chǎn)生的后代與雙親的基因也會更接近，在一定程度上使基因模式單一化，這不僅會減慢進化速度，甚至會導致進化停滯不前；而ICSA結合了變異概率設計，可以在較優(yōu)解附近進行跳躍式或精細化搜索，在收斂速度與最優(yōu)搜索上表現(xiàn)得更加優(yōu)秀。

圖2 三種算法進化代數(shù)與誤分類數(shù)關系

從表1可以看出特征選擇算法整體上較無特征選擇算法表現(xiàn)更佳。這說明：對特征冗余度較大的數(shù)據(jù)集，特征選擇不僅能降低計算的復雜度，而且可以提高判定精度。與GA相比，ICSA算法在F1-Measure和準確率上表現(xiàn)較好，說明ICSA算法搜索到了更優(yōu)解，而GA可能陷入了局部最優(yōu)，即ICSA比GA更適合本文中的應用領域。從圖3中四種算法的ROC（receiver operating characteristic curve）曲線可以看出ICSA和 RSB（rough set-based）特征選擇算法表現(xiàn)優(yōu)異，但由于RSB召回率較低，不適合本文中的情況。

表1 四種算法分類結果比較

圖3 四種算法的ROC曲線

式（5）中的參數(shù) λ 直 接影響召回率和特征簡化率對親和度的貢獻。λ 的大小與召回率的影響成正比關系，與特征簡化率成反比關系。取 λ 初值為0.05，然后按照0.05的步長逐步增加到0.95，共進行19次試驗，誤分類數(shù)與 λ 的關系如圖4所示。從圖4可以看出：誤分類數(shù)隨著 λ 的增大而振蕩減小，在 λ =0.85時達到最小值。這說明冗余特征對屬地判定具有較大的負面影響，同時也說明了進行特征選擇的必要性。

圖4 ICSA算法中λ取值與誤分類數(shù)關系

對于克隆選擇比例設置，我們設計的實驗是Rclone從0.1以步長0.05增加到0.9。實驗中發(fā)現(xiàn)：在Rclone＞0.3后，克隆出子代總數(shù)與選擇克隆抗體數(shù)之和大于種群大小，即 p＜z+∑int（[z×af/（i+3）]×ln（z－i+1）+1），為了保證種群大小固定就必須加大抑制操作的比例，而抑制操作就需要刪除一定數(shù)量的優(yōu)秀抗體或其子代，這會導致部分克隆和免疫操作無效，不僅占用了CPU的運算時間，減慢了收斂速度，而且有可能錯過全局最優(yōu)解。加速因子af的加入在一定程度上抵消了克隆選擇比例較大帶來的影響，但加速因子為一變值，只會隨著進化代數(shù)的增加而逐漸減小來增加影響，這樣就導致了過大的抑制比例，在進化后期會帶來不利影響。如果抑制比例也采用變值，則又增大了算法的復雜度，使參數(shù)確定更加困難。克隆選擇比例與迭代次數(shù)的關系如圖5所示。

圖5 克隆選擇比率與迭代次數(shù)的關系

使用樣本2作為本文算法的輸入，其他參數(shù)不變，求得感知機模型記為M2，由樣本1求得的模型記為M1，M1和M2各參數(shù)值如表2所示。由表2可知，整個感知機模型sign（wx+b）不具備通用性。對應權重參數(shù)之差絕對值之和為0.69，而對應權重參數(shù)差直接求和僅為0.01。這些均表明了運用感知機權重參數(shù)表征網(wǎng)頁位置重要性差異是正確可行的。這種分段式特征項統(tǒng)計方法可為研究網(wǎng)頁分類提供參考。需要指出的是，在使用本文算法解決網(wǎng)店屬地判定的問題時，必須先采集本地樣本進行訓練，求得對應的感知機模型。

表2 M1和M2參數(shù)對照表

5 結束語

根據(jù)免疫克隆選擇算法搜索到的感知機模型和選中的特征項，先應用爬蟲程序自動抓取每個網(wǎng)店頁面中的分詞,分段計算被選中的特征項的TF-IDF值，并按照規(guī)定順序組合形成網(wǎng)店特征向量，然后使用搜索到的感知機模型判定該網(wǎng)店是否屬于某個特定地區(qū)，將屬于該地區(qū)網(wǎng)店的首頁URL存入監(jiān)管系統(tǒng)數(shù)據(jù)庫中。系統(tǒng)運行兩周之后，將淘寶網(wǎng)網(wǎng)店掃描完畢，共發(fā)現(xiàn)屬于南陽本地的店鋪1 1000多個，經(jīng)工商管理部門實際驗證，準確率達到95%。該判定方法同樣適用于其他地區(qū)，只需對該地區(qū)樣本數(shù)據(jù)進行訓練即可求得對應模型。

實驗結果與系統(tǒng)的實際使用效果表明我們提出的算法在淘寶個體網(wǎng)店的屬地判定上是可行的，而且所提出的網(wǎng)頁分詞特征位置權重的自動化訓練方法、特征分段統(tǒng)計以及改進的免疫克隆特征選擇算法在對網(wǎng)頁這種半結構化文本的分類中也有一定的參考價值。

參考文獻：

［1］ 浙江省商務廳.浙江省網(wǎng)絡零售業(yè)發(fā)展報告［R/OL］.（2015-06-17）［2017-05-10］.http://www.zcom.gov.cn/art/2015/6/17/art_1127_176182.html.

［2］ 曹守富.社交媒體大數(shù)據(jù)的樸素貝葉斯分類方法研究［D］.長沙：湖南大學，2016.

［3］ 王靖,王興偉,趙悅.基于變精度粗糙集決策樹垃圾郵件過濾［J］.系統(tǒng)仿真學報，2016，28（3）：705-710.

［4］ 沈夏炯,王龍,韓道軍.人工蜂群優(yōu)化的BP神經(jīng)網(wǎng)絡在入侵檢測中的應用［J］.計算機工程，2016，42（2）：190-194.

［5］ 杜紅樂，滕少華，張燕.協(xié)同標注的直推式支持向量機算法［J］.小型微型計算機系統(tǒng)，2016，37（11）：2443-2447.

［6］ 蘭均，施化吉，李星毅，等.基于特征詞復合權重的關聯(lián)網(wǎng)頁分類［J］.計算機科學，2011，38（3）：188-190.

［7］ 張長水.機器學習面臨的挑戰(zhàn)［J］.中國科學：信息科學,2013，43（12）：1612-1623.

［8］ EESA A S,ORMAN Z,BRIFCANI A M A.A novel feature-selection approach based on the cuttlefish optimization algorithm for intrusion detection systems［J］.Expert systems with applications,2015,42（5）:2670-2679.

［9］ 單松巍，馮是聰，李曉明.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較［J］.計算機工程與應用，2003，22：145-148.

［10］ DONG H,TENG X,ZHOU Y,et al.Feature subset selection using dynamic mixed strategy［C］//IEEE Congress on Evolutionary Computation,IEEE,May 25-28,2015,Sendai:IEEE,2015:672-679.

［11］ GHAREB A S,BAKAR A A,HAMDAN A R.Hybrid feature selection based on enhanced genetic algorithm for text categorization［J］.Expert systems with applications,2016,49:31-47.

［12］ LIN SW,LEE Z J,CHEN SC,et al.Parameter determination of support vector machine and feature selection using simulated annealing approach［J］.Applied soft computing,2008,8（4）:1505-1512.

［13］ WANG C,QI Y,SHAO M,et al.A fitting model for feature selection with fuzzy rough sets［J］.IEEE transactions on fuzzy systems,2017,25（4）:741-753.

［14］段潔，胡清華，張靈均，等.基于鄰域粗糙集的多標記分類特征選擇算法［J］.計算機研究與發(fā)展，2015， 52（1）：56-65.

［15］ MAINAKI M,MARINAKIS Y.A hybridization of clonal selection algorithm with iterated local search and variable neighborhood search for the feature selection problem［J］.Memetic computing,2015,7（3）:181-201.

［16］ DU H F,JIAO L C,WANG SA.Clonal operator and antibody clone algorithms［C］//International Conference on Machine Learning and Cybernetics 2002 Proceedings,November 4-5,2002,Beijing.［S.l.］:IEEE,2002:506-510.

［17］ DE CASTRO L N,VON ZUBEN F J.Learning and optimization using the clonal selection principle［J］.IEEE transactions on evolutionary computation,2002,6（3）:231-259.

［18］ BURNET F M.Clonal selection theory of immunity［J］.Nature,1964,204:924-925.

［19］盧曉勇，陳木生，吳政隆，等.基于免疫克隆特征選擇和欠采樣集成的垃圾網(wǎng)頁檢測［J］.計算機應用，2016，36（7）：1899-1903.

［20］ MARYAM S H,SEYED A S.Artificial immune system based on adaptive clonal selection for feature selection and parameters optimisation of support vector machines［J］.Connection science,2016,28（1）:47-62.