資料挖掘作為一門新興的多學科交叉應用技術，正在各行各業的決策支援活動中扮演着越來越重要的角色。資料挖掘概念的定義描述有若幹版本，本文采用的是一個普遍接受的定義:資料挖掘，又稱為資料庫中的知識發現(KDD)，它是一個從大量資料中抽取出未知的、有價值的模式或規律等知識的複雜過程。一個完整的資料挖掘過程主要包含資料選擇、資料預處理、資料挖掘以及知識的表達和解釋幾個步驟。
資料挖掘方法的提出，讓人們有能力最終認識資料的真正價值，即蘊藏在資料中的資訊和知識。資料挖掘 (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特征提取算法Matlab主程式
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) %總的判斷準确率 .NET資料挖掘與機器學習，作者部落格:
http://www.cnblogs.com/asxinyu
E-mail:[email protected]