浅谈关于特征选择算法与Relief的实现
一、 背景
1) 問題
在機器學習的實際應用中，特征數量可能較多，其中可能存在不相關的特征，特征之間也可能存在相關性，容易導致如下的后果：
1.???? 特征個數越多，分析特征、訓練模型所需的時間就越長，模型也會越復雜。
2.???? 特征個數越多，容易引起“維度災難”，其推廣能力會下降。
3.???? 特征個數越多，容易導致機器學習中經常出現的特征稀疏的問題，導致模型效果下降。
4.???? 對于模型來說，可能會導致不適定的情況，即是解出的參數會因為樣本的微小變化而出現大的波動。
特征選擇，能剔除不相關、冗余、沒有差異刻畫能力的特征，從而達到減少特征個數、減少訓練或者運行時間、提高模型精確度的作用。
2) 如何做特征選擇
特征選擇，即是指從全部特征中選取一個特征子集，使得使構造出來的模型效果更好，推廣能力更強。如何做特征選擇呢，如果要從全部特征中選擇一個最優的子集，使得其在一定的評價標準下，在當前訓練和測試數據上表現最好。
從這個層面上理解，特征選擇可以看作三個問題：
1.??從原始特征集中選出固定數目的特征，使得分類器的錯誤率最小這是一個無約束的組合優化問題；
2.??對于給定的允許錯誤率，求維數最小的特征子集，這是一種有約束的最優化問題；
3.??在錯誤率和特征子集的維數之間進行折中。
上述3個問題都是一個NP難問題，當特征維度較小時，實現起來可行，但是當維度較大時，實現起來的復雜度很大，所以實際應用中很難實用。上述三種特征選擇都屬十NP難的問題。由于求最優解的計算量太大，需要在一定的時間限制下尋找能得到較好次優解的算法。以下介紹對次優解的求解過程。
二、 特征選擇的一般過程
特征選擇的一般過程可用圖1表示。首先從特征全集中產生出一個特征子集，然后用評價函數對該特征子集進行評價，評價的結果與停止準則進行比較，若滿足停止準則就停止，否則就繼續產生下一組特征子集，繼續進行特征選擇。選出來的特征子集一般還要驗證其有效性。
綜上所述，特征選擇過程一般包括：特征子集產生過程，評價函數，停止準則，驗證過程，這4個部分。
特征子集產生過程( Generation Procedure )
采取一定的子集選取辦法，為評價函數提供特征子集。根據搜索過程的方法的不同，可以將特征選擇分為窮舉、啟發式、隨機幾種方法。
以上幾種方法不改變特征的原始屬性，而有些方法通過對特征進行空間變換，去除相關性。比如PCA、傅立葉變換、小波變換等.
評價函數( EvaluationFunction )
評價函數是評價一個特征子集好壞程度的一個準則。評價函數的設計在不同的應用場景下會不同，比如有的會根據其分布是否均勻判斷，或者看對最終模型的效果進行判斷。每種評價函數各有優劣，所以需要根據實際情況進行選擇。根據不同的評價準則，可以分為：過濾器模型、封裝器模型以及混合模型。過濾器模型是將特征選擇作為一個預處理過程，利用數據的內在特性對選取的特征子集進行評價，獨立于學習算法。而封裝器模型則將后續學習算法的結果作為特征評價準則的一部分根據評價函數的不同(與采用的分類方法是否關聯)，可以將特征選擇分為獨立性準則、關聯性度量。
篩選器通過分析特征子集內部的特點來衡量其好壞。篩選器一般用作預處理，與分類器的選擇無關。篩選器的原理如下圖1：
圖1. Filter原理(RicardoGutierrez-Osuna 2008 )
封裝器實質上是一個分類器，封裝器用選取的特征子集對樣本集進行分類，分類的精度作為衡量特征子集好壞的標準。封裝器的原理如圖2所示。
圖2. Wrapper原理(RicardoGutierrez-Osuna 2008 )
停止準則( StoppingCriterion )
停止準則是與評價函數相關的，當評價函數值達到某個閾值后就可停止搜索。比如對于獨立性準則，可以選擇樣本間平均間距最大；對于關聯性度量，可以選擇使得分類器的準確召回最高作為準則。
驗證過程(Validation Procedure )
度量測試數據集上驗證選出來的特征子集的有效性。最好采取與前期選擇方法不相關的度量方法，這樣可以減少其間的耦合。
?
圖3特征選擇的過程 ( M.Dash and H. Liu 1997 )
這幾個過程中的不同方法可以看作一種組件，分別進行組合。比如可以采取啟發式特征篩選方法，結合相關性度量作為評價函數等。
三、 特征子集產生過程???
產生過程是搜索特征子空間的過程。搜索的算法分為完全搜索(Complete)，啟發式搜索(Heuristic)，隨機搜索(Random)3大類，如圖4所示。
圖4搜尋過程分類
?
當然，每種方法都不是互斥的，也可以將多種方法結合起來使用，取長補短。下面對常見的搜索算法進行簡單介紹。
1) 完全搜索(complete)
完全搜索分為窮舉搜索(Exhaustive)與非窮舉搜索(Non-Exhaustive)兩類。完全搜索部分考慮特征之間的相關性，從而能更好地找到最優集合。
A.????廣度優先搜索( Breadth First Search )
算法描述：廣度優先遍歷特征子空間。
Step1：首先將根節點放入隊列中。
Step2：從隊列中取出第一個節點，并檢驗它是否為目標。
substep：如果找到目標，則結束搜尋并回傳結果。
substep：否則將它所有尚未檢驗過的直接子節點加入隊列中。
Step3：若隊列為空，表示所有特征都檢查過了。結束搜尋并回傳「找不到目標」。
Step4：重復step2。
算法評價：枚舉了所有的特征組合，屬于窮舉搜索，時間復雜度是O(2n)，實用性不高。
B.????分支限界搜索( Branch and Bound )
算法描述：在窮舉搜索的基礎上加入分支限界。例如：若斷定某些分支不可能搜索出比當前找到的最優解更優的解，則可以剪掉這些分支。
C.?????定向搜索(Beam Search )
算法描述：首先選擇N個得分最高的特征作為特征子集，將其加入一個限制最大長度的優先隊列，每次從隊列中取出得分最高的子集，然后窮舉向該子集加入1個特征后產生的所有特征集，將這些特征集加入隊列。
D.????最優優先搜索( Best First Search )
算法描述：與定向搜索類似，唯一的不同點是不限制優先隊列的長度。
2) 啟發式搜索(heuristic)
啟發式搜索更多地采用貪心的思想，某些算法沒有考慮特征之間的相關性，而單純考慮單個特征對最終結果的影響，然而現實中的特征可能存在各種相關性。某些算法也從這些方面進行改進，比如增L去R選擇算法，序列浮動選擇。
A.????序列前向選擇( SFS , Sequential Forward Selection )
算法描述：特征子集X從空集開始，每次選擇一個特征x加入特征子集X，使得特征函數J( X)最優。簡單說就是，每次都選擇一個使得評價函數的取值達到更優的特征加入，是一種簡單的貪心算法。
算法評價：缺點是只能加入特征而不能去除特征。例如：特征A完全依賴于特征B與C，可以認為如果加入了特征B與C則A就是多余的。假設序列前向選擇算法首先將A加入特征集，然后又將B與C加入，那么特征子集中就包含了多余的特征A。
B.????序列后向選擇( SBS , Sequential Backward Selection )
算法描述：從特征全集O開始，每次從特征集O中剔除一個特征x，使得剔除特征x后評價函數值達到最優。
算法評價：序列后向選擇與序列前向選擇正好相反，它的缺點是特征只能去除不能加入。
另外，SFS與SBS都屬于貪心算法，容易陷入局部最優值。
C.?????雙向搜索( BDS , Bidirectional Search )
算法描述：使用序列前向選擇(SFS)從空集開始，同時使用序列后向選擇(SBS)從全集開始搜索，當兩者搜索到一個相同的特征子集C時停止搜索。
雙向搜索的出發點是??。如下圖所示，O點代表搜索起點，A點代表搜索目標。灰色的圓代表單向搜索可能的搜索范圍，綠色的2個圓表示某次雙向搜索的搜索范圍，容易證明綠色的面積必定要比灰色的要小。
圖5. 雙向搜索
D.????增L去R選擇算法( LRS , Plus-L Minus-R Selection )
該算法有兩種形式:
<1>算法從空集開始，每輪先加入L個特征，然后從中去除R個特征，使得評價函數值最優。( L> R )
<2>?算法從全集開始，每輪先去除R個特征，然后加入L個特征，使得評價函數值最優。( L< R )
算法評價：增L去R選擇算法結合了序列前向選擇與序列后向選擇思想， L與R的選擇是算法的關鍵。
E.?????序列浮動選擇( Sequential Floating Selection )
算法描述：序列浮動選擇由增L去R選擇算法發展而來，該算法與增L去R選擇算法的不同之處在于：序列浮動選擇的L與R不是固定的，而是“浮動”的，也就是會變化的。
序列浮動選擇根據搜索方向的不同，有以下兩種變種。
<1>序列浮動前向選擇( SFFS, Sequential Floating Forward Selection )
算法描述：從空集開始，每輪在未選擇的特征中選擇一個子集x，使加入子集x后評價函數達到最優，然后在已選擇的特征中選擇子集z，使剔除子集z后評價函數達到最優。
<2>序列浮動后向選擇( SFBS, Sequential Floating Backward Selection )
算法描述：與SFFS類似，不同之處在于SFBS是從全集開始，每輪先剔除特征，然后加入特征。
????? ? 算法評價：序列浮動選擇結合了序列前向選擇、序列后向選擇、增L去R選擇的特點，并彌補了它們的缺點。
A.?????決策樹( Decision Tree Method , DTM)
算法描述：在訓練樣本集上運行C4.5或其他決策樹生成算法，待決策樹充分生長后，再在樹上運行剪枝算法。則最終決策樹各分支處的特征就是選出來的特征子集了。決策樹方法一般使用信息增益作為評價函數。
3) 隨機算法(random)
A.????隨機產生序列選擇算法(RGSS, Random Generation plus Sequential Selection)
算法描述：隨機產生一個特征子集，然后在該子集上執行SFS與SBS算法。
算法評價：可作為SFS與SBS的補充，用于跳出局部最優值。
B.????模擬退火算法( SA, Simulated Annealing )
算法評價：模擬退火一定程度克服了序列搜索算法容易陷入局部最優值的缺點，但是若最優解的區域太小（如所謂的“高爾夫球洞”地形），則模擬退火難以求解。
C.?????遺傳算法( GA,? Genetic Algorithms )
算法描述：首先隨機產生一批特征子集，并用評價函數給這些特征子集評分，然后通過交叉、突變等操作繁殖出下一代的特征子集，并且評分越高的特征子集被選中參加繁殖的概率越高。這樣經過N代的繁殖和優勝劣汰后，種群中就可能產生了評價函數值最高的特征子集。
隨機算法的共同缺點：依賴于隨機因素，有實驗結果難以重現。
4) 特征變換方法
A.????PCA
PCA(Principal ComponentAnalysis)，中文名為主成份變換，是一種坐標變換的方法，可以去除冗余特征。
具體特征變換過程中，去掉較小的特征值，從而達到去噪、去除相關性和特征減少的目的。
B.????小波變換
小波也是一種特征空間變換的方法，相較于傅立葉變換，小波變換能更好地適應劇烈的變換。
四、 評價函數??????
評價函數的作用是評價產生過程所提供的特征子集的好壞。
1) 獨立準則
獨立準則通常應用在過濾器模型的特征選擇算法中，試圖通過訓練數據的內在特性對所選擇的特征子集進行評價，獨立于特定的學習算法。通常包括：距離度置、信息度量，關聯性性度量和一致性度量。
在做比較通用的特征選擇方法時，建議采用這種方法，因為這是獨立于特定機器學習算法的，適用于大多數后續機器學習方法。
2) 關聯性度量
關聯準則通常應用在封裝器模型的特征選擇算法中，先確定一個學習算法并且利機器學習算法的性能作為評價準則。對于特定的學習算法來說，通常可以找到比過濾器模型更好的特征子集，但是需要多次調用學習算法，一般時間開銷較大，并且可能不適介其它學習算法。
在我們做模式分類算法時，可以根據自己的實際情況，采用關聯性度量方法，這樣能更好地和我們的分類方法相結合，通常能找到比較好的子集。
綜上，兩種種評價函數的優缺點和適用情況總結如下：
| 方法 | 獨立性準確 | 關聯性度量 |
| 優點 | 通用，獨立于特定算法 | 對于關聯分類算法可能是最優的 |
| 缺點 | 效果一般 | 對其他算法不適用 |
| 適用情況 | ? | ? |
表格1 兩種種評價函數的優缺點
3) 常見的評價函數
A.???? 卡方檢驗
卡方檢驗最基本的思想就是通過觀察實際值與理論值的偏差來確定理論的正確與否.具體做的時候常常先假設兩個變量確實是獨立的（“原假設”）,然后觀察實際值（觀察值）與理論值（這個理論值是指“如果兩者確實獨立”的情況下應該有的值）的偏差程度,如果偏差足夠小,我們就認為誤差是很自然的樣本誤差,是測量手段不夠精確導致或者偶然發生的,兩者確確實實是獨立的,此時就接受原假設；如果偏差大到一定程度,使得這樣的誤差不太可能是偶然產生或者測量不精確所致,我們就認為兩者實際上是相關的,即否定原假設,而接受備擇假設.
理論值為E,實際值為x,偏差程度的計算公式為：
這個式子就是開方檢驗使用的差值衡量公式.當提供了數個樣本的觀察值x1,x2,……xi,……xn之后,代入到式中就可以求得開方值,用這個值與事先設定的閾值比較,如果大于閾值（即偏差很大）,就認為原假設不成立,反之則認為原假設成立.[請參考我的另外一篇卡方檢驗的普及文章]
B.????相關性( Correlation)
?運用相關性來度量特征子集的好壞是基于這樣一個假設：好的特征子集所包含的特征應該是與分類的相關度較高（相關度高），而特征之間相關度較低的（冗余度低）。
可以使用線性相關系數(correlationcoefficient) 來衡量向量之間線性相關度。
C.?????距離(Distance Metrics )
運用距離度量進行特征選擇是基于這樣的假設：好的特征子集應該使得屬于同一類的樣本距離盡可能小，屬于不同類的樣本之間的距離盡可能遠。同樣基于此種思想的有fisher判別分類反法。
常用的距離度量（相似性度量）包括歐氏距離、標準化歐氏距離、馬氏距離等。
D.????信息增益( Information Gain )??????
假設存在離散變量Y，Y中的取值包括{y1，y2，....，ym} ，yi出現的概率為Pi。則Y的信息熵定義為：
信息熵是對不確定性的一種描述。具有如下特性：若集合Y的元素分布不均，則其信息熵越小；若Y分布越平均，則其信息熵越大。在極端的情況下：若Y只能取一個值，即P1=1，則H(Y)取最小值0；反之若各種取值出現的概率都相等，即都是1/m，則H(Y)取最大值log2m。
對于一個特征t,系統有它和沒它的時候信息量各是多少,兩者的差值就是這個特征給系統帶來的信息量.有它即信息熵,無它則是條件熵.
條件熵：計算當一個特征t不能變化時,系統的信息量是多少.
對于一個特征X,它可能的取值有n多種（x1,x2,……,xn）,計算每個值的條件熵,再取平均值.
在文本分類中,特征詞t的取值只有t（代表t出現）和（代表t不出現）.那么
最后,信息增益
但信息增益最大的問題[對于多分類存在這個問題，對于二分類則不存在]還在于它只能考察特征對整個系統的貢獻,而不能具體到某個類別上,這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合）,而無法做“本地”的特征選擇（每個類別有自己的特征集合,因為有的詞,對這個類別很有區分度,對另一個類別則無足輕重）.
同時，信息熵會偏向于特征的分布較多的特征，所以改進方法是可以嘗試信息增益率。
E.?????分類器錯誤率(Classifier error rate )
使用特定的分類器，用給定的特征子集對樣本集進行分類，用分類的精度來衡量特征子集的好壞。???
以上4種度量方法中，卡方檢驗、相關性、距離、信息增益、屬于篩選器，而分類器錯誤率屬于封裝器。?????
篩選器由于與具體的分類算法無關，因此其在不同的分類算法之間的推廣能力較強，而且計算量也較小。而封裝器由于在評價的過程中應用了具體的分類算法進行分類，因此其推廣到其他分類算法的效果可能較差，而且計算量也較大。
五、 應用實例
此處舉出一個實際應用中的栗子，基本方法為啟發式搜索(順序添加)+關聯性準則(卡方檢驗、最大熵)+準召停止準則。以下詳細介紹操作步驟。
Step1:統計每種特征的卡方值.
Step2:取topN的特征值.
Step3:帶入模型訓練，并在測試集合上計算準確和召回.
Step4:如果達標，停止，否則，gotostep2.
數據挖掘方法的提出，讓人們有能力最終認識數據的真正價值，即蘊藏在數據中的信息和知識。數據挖掘?(DataMiriing)，指的是從大型數據庫或數據倉庫中提取人們感興趣的知識，這些知識是隱含的、事先未知的潛在有用信息，數據挖掘是目前國際上，數據庫和信息決策領域的最前沿研究方向之一。因此分享一下很久以前做的一個小研究成果。也算是一個簡單的數據挖掘處理的例子。
1.數據挖掘與聚類分析概述?
數據挖掘一般由以下幾個步驟：?
(l)分析問題:源數據數據庫必須經過評估確認其是否符合數據挖掘標準。以決定預期結果，也就選擇了這項工作的最優算法。?
(2)提取、清洗和校驗數據:提取的數據放在一個結構上與數據模型兼容的數據庫中。以統一的格式清洗那些不一致、不兼容的數據。一旦提取和清理數據后，瀏覽所創建的模型，以確保所有的數據都已經存在并且完整。
(3)創建和調試模型:將算法應用于模型后產生一個結構。瀏覽所產生的結構中數據，確認它對于源數據中“事實”的準確代表性，這是很重要的一點。雖然可能無法對每一個細節做到這一點，但是通過查看生成的模型，就可能發現重要的特征。?
(4)查詢數據挖掘模型的數據:一旦建立模型，該數據就可用于決策支持了。?
(5)維護數據挖掘模型:數據模型建立好后，初始數據的特征，如有效性，可能發生改變。一些信息的改變會對精度產生很大的影響，因為它的變化影響作為基礎的原始模型的性質。因而，維護數據挖掘模型是非常重要的環節。?
聚類分析是數據挖掘采用的核心技術，成為該研究領域中一個非常活躍的研究課題。聚類分析基于”物以類聚”的樸素思想，根據事物的特征，對其進行聚類或分類。作為數據挖掘的一個重要研究方向，聚類分析越來越得到人們的關注。聚類的輸入是一組沒有類別標注的數據，事先可以知道這些數據聚成幾簇爪也可以不知道聚成幾簇。通過分析這些數據，根據一定的聚類準則，合理劃分記錄集合，從而使相似的記錄被劃分到同一個簇中，不相似的數據劃分到不同的簇中。
2.特征選擇與聚類分析算法
Relief為一系列算法，它包括最早提出的Relief以及后來拓展的ReliefF和RReliefF，其中RReliefF算法是針對目標屬性為連續值的回歸問題提出的，下面僅介紹一下針對分類問題的Relief和ReliefF算法。
2.1?Relief算法?
Relief算法最早由Kira提出，最初局限于兩類數據的分類問題。Relief算法是一種特征權重算法(Feature?weighting?algorithms)，根據各個特征和類別的相關性賦予特征不同的權重，權重小于某個閾值的特征將被移除。Relief算法中特征和類別的相關性是基于特征對近距離樣本的區分能力。算法從訓練集D中隨機選擇一個樣本R，然后從和R同類的樣本中尋找最近鄰樣本H，稱為Near?Hit，從和R不同類的樣本中尋找最近鄰樣本M，稱為NearMiss，然后根據以下規則更新每個特征的權重：如果R和Near?Hit在某個特征上的距離小于R和Near?Miss上的距離，則說明該特征對區分同類和不同類的最近鄰是有益的，則增加該特征的權重；反之，如果R和Near?Hit在某個特征的距離大于R和Near?Miss上的距離，說明該特征對區分同類和不同類的最近鄰起負面作用，則降低該特征的權重。以上過程重復m次，最后得到各特征的平均權重。特征的權重越大，表示該特征的分類能力越強，反之，表示該特征分類能力越弱。Relief算法的運行時間隨著樣本的抽樣次數m和原始特征個數N的增加線性增加，因而運行效率非常高。具體算法如下所示：
2.2 ReliefF算法
由于Relief算法比較簡單，但運行效率高，并且結果也比較令人滿意，因此得到廣泛應用，但是其局限性在于只能處理兩類別數據，因此1994年Kononeill對其進行了擴展，得到了ReliefF作算法，可以處理多類別問題。該算法用于處理目標屬性為連續值的回歸問題。ReliefF算法在處理多類問題時，每次從訓練樣本集中隨機取出一個樣本R，然后從和R同類的樣本集中找出R的k個近鄰樣本(near?Hits)，從每個R的不同類的樣本集中均找出k個近鄰樣本(near?Misses)，然后更新每個特征的權重，如下式所示：
Relief系列算法運行效率高，對數據類型沒有限制，屬于一種特征權重算法，算法會賦予所有和類別相關性高的特征較高的權重，所以算法的局限性在于不能有效的去除冗余特征。?
2.3 K-means聚類算法
由于聚類算法是給予數據自然上的相似劃法，要求得到的聚類是每個聚類內部數據盡可能的相似而聚類之間要盡可能的大差異。所以定義一種尺度來衡量相似度就顯得非常重要了。一般來說，有兩種定義相似度的方法。第一種方法是定義數據之間的距離，描述的是數據的差異。第二種方法是直接定義數據之間的相似度。下面是幾種常見的定義距離的方法：?
1.Euclidean距離，這是一種傳統的距離概念，適合于2、3維空間。?
2.Minkowski距離，是Euclidean距離的擴展，可以理解為N維空間的距離。?
聚類算法有很多種，在需要時可以根據所涉及的數據類型、聚類的目的以及具的應用要求來選擇合適的聚類算法。下面介紹?K-means聚類算法:?
K-means算法是一種常用的基于劃分的聚類算法。K-means算法是以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。K-means的處理過程為：首先隨機選擇k個對象作為初始的k個簇的質心；然后將余對象根據其與各個簇的質心的距離分配到最近的簇；最后重新計算各個簇的質心。不斷重復此過程，直到目標函數最小為止。簇的質心由公式下列式子求得：
在具體實現時，為了防止步驟2中的條件不成立而出現無限循環，往往定義一個最大迭代次數。K-means嘗試找出使平方誤差函數值最小的k個劃分。當數據分布較均勻，且簇與簇之間區別明顯時，它的效果較好。面對大規模數據集，該算法是相對可擴展的，并且具有較高的效率。其中，n為數據集中對象的數目，k為期望得到的簇的數目，t為迭代的次數。通常情況下，算法會終止于局部最優解。但用，例如涉及有非數值屬性的數據。其次，這種算法要求事先給出要生成的簇的數目k，顯然這對用戶提出了過高的要求，并且由于算法的初始聚類中心是隨機選擇的，而不同的初始中心對聚類結果有很大的影響。另外，K-means算法不適用于發現非凸面形狀的簇，或者大小差別很大的簇，而且它對于噪音和孤立點數據是敏感的。
3.一個醫學數據分析實例
3.1?數據說明?
本文實驗數據來自著名的UCI機器學習數據庫，該數據庫有大量的人工智能數據挖掘數據，網址為:http://archive.ics.uci.edu/ml/。該數據庫是不斷更新的，也接受數據的捐贈。數據庫種類涉及生活、工程、科學各個領域，記錄數也是從少到多，最多達幾十萬條。截止2010年底，數據庫共有199個數據集，每個數據集合中有不同類型、時間的相關數據。可以根據實際情況進行選用。?
本文選用的數據來類型為：Breast?Cancer?Wisconsin?(Original)?Data?Set，中文名稱為：威斯康星州乳腺癌數據集。這些數據來源美國威斯康星大學醫院的臨床病例報告，每條數據具有11個屬性。下載下來的數據文件格式為“.data”,通過使用Excel和Matlab工具將其轉換為Matlab默認的數據集保存，方便程序進行調用。
?下表是該數據集的11個屬性名稱及說明：
?
對上述數據進行轉換后，以及數據說明可知，可以用于特征提取的有9個指標，樣品編號和分類只是用于確定分類。本文的數據處理思路是先采用ReliefF特征提取算法計算各個屬性的權重，剔除相關性最小的屬性，然后采用K-means聚類算法對剩下的屬性進行聚類分析。
3.2 數據預處理與程序?
本文在轉換數據后，首先進行了預處理，由于本文的數據范圍都是1-10，因此不需要歸一化，但是數據樣本中存在一些不完整，會影響實際的程序運行，經過程序處理，將這一部分數據刪除。這些不完整的數據都是由于實際中一些原因沒有登記或者遺失的，以“?”的形式代表。?
本文采用Matlab軟件進行編程計算。根據第三章提到的ReliefF算法過程，先編寫ReliefF函數程序，用來計算特征屬性，再編寫主程序，在主程序中調用該函數進行計算，并對結果進行分析，繪圖，得到有用的結論。
程序統一在最后貼出。
3.3 乳腺癌數據集特征提取?
本文采用3.1節中的ReliefF算法來計算各個特征的權重，權重小于某個閾值的特征將被移除，針對本文的實際情況，將對權重最小的2-3種剔除。由于算法在運行過程中，會選擇隨機樣本R，隨機數的不同將導致結果權重有一定的出入，因此本文采取平均的方法，將主程序運行20次，然后將結果匯總求出每種權重的平均值。如下所示，列為屬性編號，行為每一次的計算結果：?
下面是特征提取算法計算的特征權重趨勢圖，計算20次的結果趨勢相同：
上述結果是否運行主程序所得的計算結果，看起來不直觀，下面將其按照順序繪圖，可以直觀顯示各個屬性權重的大小分布，如下圖所示：
按照從小到大順序排列，可知，各個屬性的權重關系如下：
??屬性9<屬性5<屬性7<屬性4<屬性2<屬性3<屬性8<屬性1<屬性6
我們選定權重閥值為0.02，則屬性9、屬性4和屬性5剔除。
從上面的特征權重可以看出，屬性6裸核大小是最主要的影響因素，說明乳腺癌患者的癥狀最先表現了裸核大小上，將直接導致裸核大小的變化，其次是屬性1和屬性8等，后幾個屬性權重大小接近，但是從多次計算規律來看，還是能夠說明其中不同的重要程度，下面是著重對幾個重要的屬性進行分析。下面是20次測試中，裸核大小（屬性6）的權重變化：
從上圖中可以看到該屬性權重大部分在0.22-0.26左右，是權重最大的一個屬性。下面看看屬性1的權重分布：
塊厚度屬性的特征權重在0.19-25左右變動，也是權重極高的一個，說明該特征屬性在乳腺癌患者檢測指標中是相當重要的一個判斷依據。進一步分析顯示，在單獨對屬性6，和屬性1進行聚類分析，其成功率就可以達到91.8%。本文將在下節中的Kmeans算法中詳細介紹。
3.4 乳腺癌數據集聚類分析?
上一節中通過ReliefF算法對數據集的分析，可以得到屬性權重的重要程度，這些可以對臨床診斷有一些參考價值，可以用來對實際案例進行分析，可以盡量的避免錯誤診斷，并提高診斷的速度和正確率。下面將通過K-menas聚類分析算法對數據進行分析。本小節將分為幾個步驟來進行對比，確定聚類分析算法的結果以及與ReliefF算法結合的結果等。
1.K-means算法單獨分析數據集?
下面將采用Kmeans算法單獨對數據集進行分析。Matlab中已經包括了一些常規數據挖掘的算法，例如本文所用到的K-means算法。該函數名為kmeans，可以對數據集進行聚類分析。首先本文對乳腺癌數據集的所有屬性列(除去身份信息和分類列)直接進行分類，由于數據集結果只有2種類型，所以首先進行分2類的測試，結果如下：總體將683條數據分成了2類，總體的正確率為94.44%，其中第一類的正確率為93.56%，第二類的正確率為96.31%。下面是分類后對按照不同屬性的繪制的屬性值分布圖：?
限于篇幅，只選擇了上述3個特征屬性進行圖像繪制，從結果來看，?可以很直觀的觀察到K-means算法分類后的情況，第一類與第一類的分類界限比較清晰。但是不容易觀察到正確和錯誤的情況。下表是分類結果中各個屬性的聚類中心：
從K-means算法的效果來看，能夠很準確的將數據集進行分類。一方面是由于該數據集，可能是該案例特征比較明顯，另一方面是由于K-menas算法對這種2類的作用較大。?
2.K-means結合ReliefF分析數據集?
單從分類正確率和結果方面來看，K-mens算法已經完全可以對乳腺癌數據集做出非常準確的判斷。但是考慮ReliefF算法對屬性權重的影響，本小節將結合ReliefF算法和K-means算法來對該數據集進行分析，一方面得到處理該問題一些簡單的結論，另外一方面可以得到一些對醫學處理數據的方法研究方法。?
首先，本小節首先根據3.2節中的一些結論，根據不同屬性的權重來對k-menas分類數據進行預處理，以得到更精確的結論和對該數據更深度的特征規律。?
從3.2節中，得知屬性9<屬性5<屬性7<屬性4<屬性2<屬性3<屬性8<屬性1<屬性6，根據ReliefF算法原理本文可以認為，對于這種屬性6和屬性1重要的特征屬性，應該對分類起到更加到的作用。所以下面將單獨對各個屬性的數據進行分類測試，詳細結果如下表：
總的分類正確率中，屬性9最低，屬性6最高，這與ReliefF算法測試的結果大致相似，但是由于ReliefFar算法中間部分權重接近，所以也區分不明顯。說明特征屬性權重的判斷對分類是有影響的。上述單獨分類中，只將需要分類的列數據取出來，輸入到K-means算法中即可。由于輸入數據的變化，K-means分類時結果肯定是有差距的，所以單獨從一個屬性判斷其類型是不可靠的。下面選擇了單個分類時最高和最低的情況，繪制其分類屬性值分布圖，如下圖所示：
下面將對特征權重按照從大到小的順序，選擇相應的數據，進行聚類分析，結論如下：
1.直接選擇全部9種屬性，分類成功率為：94.44%；
2.選擇屬性6，屬性1，分類成功率為：91.36%；
3.選擇屬性6，1，8，3，分類成功率為：93.85%；
4.選擇屬性6，1，8，3，2，4，分類成功率為：94.48%；
5.選擇屬性6，1，8，3，2，4，5，7，分類成功率為：95.02%；
從上面的測試可以看出，選擇特征權重最大的6個屬性，其正確率就達到選擇所有屬性的情況，因此我們可以認為特征權重最小的幾個屬性在乳腺癌診斷過程的作用實際可能比較小，實際有可能造成反作用，也就是這幾個屬性值與乳腺癌沒有必然的聯系。這一點可以給診斷參考，或者引起注意，進行進一步的研究，確認。?
3.?K-means分成3類的情況?
雖然從上述2小節的實驗中可以得到該數據集的大部分結果和結論。但是為了將相同類型的數據更加準確的分出，下面將嘗試分為3類的情況。一方面，可以分析在乳腺癌良性和惡性情況下的顯著特征屬性；另一方面也可以根據此結果找到更加合理的解決方法。?
還是采用Matlab中的kmeans函數，將分類數改為3，由于分為3類后數據類型增多，判斷較復雜，所以手動對數據進行分析，將所有特征屬性加入進去。運行結果如下，測試數據中總共683條，其中良性共444條，惡性共239條：?
1.分為第一類的記錄中，良性占96.88%；?
2.分為第二類的記錄中，惡性占?100%?；?
3.分為第三類的記錄中，惡性占?92%；?
根據上述結果可以認為第一類為良性的分類，第二類為惡性分類，第三類為混合類。對于混合類，說明里面的數據較其他數據更加接近于偏離病例的典型數據，所以進一步分析在第一類中和第二類中的分類正確率：?
1.第一類為良性，共448條數據，分類正確率為96.88%；
2.第二類為惡性，共99條數據，分類正確率為?100%?；?
3.第三類為混合類，共136條數據?
因此單獨從分類后的正確率來看，效果有提高，說明對典型的病例數據分類更準確，但是對于第三類數據，而無法區分，因此這種情況下，其意義不在于分類的整體正確率，而在于在一些特殊情況下，可以根據一些重要的特征屬性值就可以為患者確診，從而提高效率和準確率，減少誤診斷的幾率。?
上面是將所有屬性進行K-means變換，下面將結合ReliefF算法，先去掉一部分特征權重較小的特征屬性后，再進行K-means處理。根據4.2節中的結論，下面提取權重最大的6個屬性進行測試，分別是：屬性6，屬性?1，屬性?8，屬性?3，屬性2，屬性?4。?
1.第一類為良性，共281條數據，分類正確率為97.51%?；?
2.第二類為惡性，共211條數據，分類正確率為?97.16%?；?
3.第三類為混合類，共191條數據?
因此，對比可以看到，雖然良性的正確率增加了，但是檢測出的數據減少了。第三類混合的數量也增多了，說明提出了特種屬性較小的屬性，可以更加容易區分極端的病例數據，對極端數據的檢測更加準確。?
4.主要的Matlab源代碼?
1.ReliefF
?
?
?
1 %主函數 2 clear;clc; 3 load('matlab.mat') 4 D=data(:,2:size(data,2));% 5 m =80 ;%抽樣次數 6 k = 8; 7 N=20;%運行次數 8 for i =1:N 9 W(i,:) = ReliefF (D,m,k) ; 10 end 11 for i = 1:N %將每次計算的權重進行繪圖,繪圖N次，看整體效果 12 plot(1:size(W,2),W(i,:)); 13 hold on ; 14 end 15 for i = 1:size(W,2) %計算N次中，每個屬性的平均值 16 result(1,i) = sum(W(:,i))/size(W,1) ; 17 end 18 xlabel('屬性編號'); 19 ylabel('特征權重'); 20 title('ReliefF算法計算乳腺癌數據的特征權重'); 21 axis([1 10 0 0.3]) 22 %------- 繪制每一種的屬性變化趨勢 23 xlabel('計算次數'); 24 ylabel('特征權重'); 25 name =char('塊厚度','細胞大小均勻性','細胞形態均勻性','邊緣粘附力','單上皮細胞尺寸','裸核','Bland染色質','正常核仁','核分裂'); 26 name=cellstr(name); 27 28 for i = 1:size(W,2) 29 figure 30 plot(1:size(W,1),W(:,i)); 31 xlabel('計算次數') ; 32 ylabel('特征權重') ; 33 title([char(name(i)) '(屬性' num2Str(i) ')的特征權重變化']); 34 end?
?
2.ReliefF函數程序?
?
1 %Relief函數實現 2 %D為輸入的訓練集合,輸入集合去掉身份信息項目;k為最近鄰樣本個數 3 function W = ReliefF (D,m,k) 4 Rows = size(D,1) ;%樣本個數 5 Cols = size(D,2) ;%特征熟練,不包括分類列 6 type2 = sum((D(:,Cols)==2))/Rows ; 7 type4 = sum((D(:,Cols)==4))/Rows ; 8 %先將數據集分為2類，可以加快計算速度 9 D1 = zeros(0,Cols) ;%第一類 10 D2 = zeros(0,Cols) ;%第二類 11 for i = 1:Rows 12 if D(i,Cols)==2 13 D1(size(D1,1)+1,:) = D(i,:) ; 14 elseif D(i,Cols)==4 15 D2(size(D2,1)+1,:) = D(i,:) ; 16 end 17 end 18 W =zeros(1,Cols-1) ;%初始化特征權重，置0 19 for i = 1 : m %進行m次循環選擇操作 20 %從D中隨機選擇一個樣本R 21 [R,Dh,Dm] = GetRandSamples(D,D1,D2,k) ; 22 %更新特征權重值 23 for j = 1:length(W) %每個特征累計一次，循環 24 W(1,j)=W(1,j)-sum(Dh(:,j))/(k*m)+sum(Dm(:,j))/(k*m) ;%按照公式更新權重 25 end 26 end?
ReliefF輔助函數,尋找最近的樣本數K
?
?
?
1 %獲取隨機R 以及找出鄰近樣本 2 %D：訓練集;D1：類別1數據集;D2：類別2數據集; 3 %Dh：與R同類相鄰的樣本距離;Dm：與R不同類的相鄰樣本距離 4 function [R,Dh,Dm] = GetRandSamples(D,D1,D2,k) 5 %先產生一個隨機數，確定選定的樣本R 6 r = ceil(1 + (size(D,1)-1)*rand) ; 7 R=D(r,:); %將第r行選中，賦值給R 8 d1 = zeros(1,0) ;%先置0,d1是與R的距離，是不是同類在下面判斷 9 d2 = zeros(1,0) ;%先置0,d2是與R的距離 10 %D1,D2是先傳入的參數，在ReliefF函數中已經分類好了 11 for i =1:size(D1,1) %計算R與D1的距離 12 d1(1,i) = Distance(R,D1(i,:)) ; 13 end 14 for j = 1:size(D2,1)%計算R與D2的距離 15 d2(1,j) = Distance(R,D2(j,:)) ; 16 end 17 [v1,L1] = sort(d1) ;%d1排序， 18 [v2,L2] = sort(d2) ;%d2排序 19 if R(1,size(R,2))==2 %如果R樣本=2，是良性 20 H = D1(L1(1,2:k+1),:) ; %L1中是與R最近的距離的編號，賦值給H。 21 M = D2(L2(1,1:k),:) ; %v2(1,1:k) ; 22 else 23 H = D1(L1(1,1:k),:); 24 M = D2(L2(1,2:k+1),:) ; 25 end 26 %循環計算每2個樣本特征之間的特征距離：(特征1-特征2)/(max-min) 27 for i = 1:size(H,1) 28 for j =1 :size(H,2) 29 Dh(i,j) = abs(H(i,j)-R(1,j))/9 ; % 本文數據范圍都是1-10，所以max-min=9為固定 30 Dm(i,j) = abs(M(i,j)-R(1,j))/9 ; 31 end 32 end?
?
?
3.K-means算法主程序?
?
1 clc;clear; 2 load('matlab.mat')%加載測試數據 3 N0 =1 ; %從多少列開始的數據進行預測分類 4 N1 = size(data,1);%所有數據的行數 5 data=data(N0:N1,:);%只選取需要測試的數據 6 data1=data(:,[2,3,4,5,6,7,8,9]);% [2,4,7,9] 2:size(data,2)-1 7 opts = statset('Display','final');%控制選項 8 [idx,ctrs,result,D] = kmeans(data1,2,... %data1為要分類的數據,2為分類的類別數,本文只有2類 9 'Distance','city',... %選擇的距離的計算方式 10 'Options',opts); % 控制選項,參考matlab幫助 11 t=[data(:,size(data,2)),idx(:,1)];%把測試數據最后一列，也就是分類屬性 和 分類結果取出來：列 + 列 12 d2 = data(idx==1,11);%提取原始數據中屬于第1類的數據的最后一列 13 a = sum(d2==2) ; 14 b=a/length(d2) ; 15 totalSum = 0 ;%總的正確率 16 rate1 = 0 ;%第一類的判斷正確率.分類類別中數據的正確性 17 rate2 = 0 ;%第二類的判斷正確率. 18 if(b>0.5) %說明第1類屬于良性,則a的值就是良性中判斷正確的個數 19 totalSum = totalSum + a ; 20 rate1 = a/length(d2) ; 21 %然后加上惡性中判斷正確的比例 22 totalSum = totalSum + sum(data(idx==2,11)==4) ; 23 rate2 = sum(data(idx==2,11)==4)/length(data(idx==2,11)) ; 24 else %說明第1類屬于惡性 25 totalSum = totalSum + sum(data(idx==1,11)==4) ; 26 totalSum = totalSum + sum(data(idx==2,11)==2) ; 27 rate1 = sum(data(idx==2,11)==2)/length(data(idx==2,11)) ; 28 rate2 = sum(data(idx==1,11)==4)/length(data(idx==1,11)) ; 29 end 30 x1 =1;%第x1個屬性 31 x2 =1 ;%第x2個屬性 32 plot(1:sum(idx==1),data1(idx==1,x1),'r.','MarkerSize',12); 33 hold on ; 34 plot(sum(idx==1)+1:sum(idx==1)+sum(idx==2),data1(idx==2,x1),'b.','MarkerSize',12); 35 xlabel('記錄數'); 36 ylabel('屬性值'); 37 title('屬性9的值分布'); 38 legend('第一類','第二類'); 39 axis([0 640 0 10]) 40 rate = totalSum/size(t,1) %總的判斷準確率?
取
算法Matlab主程序
總結
以上是生活随笔為你收集整理的浅谈关于特征选择算法与Relief的实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c# 使用TCP连接（server）
- 下一篇： Unity TIP4: 带泛型参数的接口