7. 分類(Classification)

分類(Classification) 是指根據已知的資料及其類別屬性來建立資料的分類模型。分類模型的建立可以讓我們了解屬於各種類別屬性的資料

 具備哪些特徵,同時也可以用來預測新進資料的類別屬性。

 分類的目的與應用

兩個主要的目的:

(1)分析影響資料歸類的因素:從分類法所建立的分類模型當中,可以整理出分類的規則,而這些規則正是影響資料歸類的因素。

(2)預測資料所屬的類別(class label):當用來建立分類模型得資料筆數足夠多的時候,分類模型的代表性變具有統計上的意義,可以用來

   預測一筆位分類的資料將會落在哪一個類別之中。

分類的程序分三個階段:

 (1)建立模型:所謂的建立模型就是指利用現有得資料將資料的分類規則找出來。

    分類模型的表達方式很多種,例如決策樹

(2)評估模型:在建立模型的時候,通常不會使用所有的資料。現有得資料會被分為兩組:training samples和testing samples。

    第一階段只利用訓練樣本來建立模型,而將測試樣本留給第二階段來評估分類模型的準確性。當分類模型建立好之後,即可用testing

    samples來測試這個分類模型是否能正確地判斷出測試樣本所屬的類別。分類模型的準確度通常可用該模型預測測試樣本所屬類別的正

   確比率來評估。

(3)使用模型:確認分類模型符合要求後,即可開始使用模型。使用模型的方式有兩種:一種是根據所建立出的模型來找出資料分類的原因,

  另一種就是利用這個模型來預測新進得資料所屬的類型。

所謂決策樹是指一個樹狀結構,樹的中間節點(non-leaf nodes)代表測試的條件,樹的分支(branches)代表條件測試的結果,而樹的葉節點(leaf nodes)則代表分類後所得到的分類標記,也就是表示分類的結果。

決策樹的產生程序

包含兩個步驟:

step1:建立樹狀結構

   一開始將所有的training samples放在根節點的位置,接著再根據所選擇的testing samples條件將training samples分成不同得子集合,若是分在某子集合內的training samples全部都屬於同一個分類標記,便產生一個葉節點來代表這群樣本的分類標記,結束分類的動作,否則便重複選取測試條件,直到所有的樣本都可以分成屬於同一分類標記的子集合為止,此時樹狀結構及建立完。

step2:修剪樹狀結構

  當樹狀結構建立完成之後,接下來要針對所產生的決策樹進行修剪的動作,也就是將這個樹狀結構當中代表雜訊或是特例的分支剪掉,以避免所產生的決策樹過度遷就特定資料樣本。

貝式分類法是一種或然率的學習法(Probailistic learning),也就是一種以機率、統計學為基礎的分類法,此法最大的優點是具有漸增性(incremental)。

前面所介紹的決策樹分類法必須使用全部的樣本來建立分類模型,因此當分類模型建立之後,若有新樣本要加入,則必須利用舊樣本重新建立一株新的決策樹之後,才能利用到新樣本對分類模型的貢獻;也就是說,決策樹的建立並無法以漸進的方式,逐步將資料加入,使決策樹漸次成長,可見決策樹分類法不具有漸增性

貝式分類法利用事件發生的機率來推測為之資料的類別,由於機率的計算是可隨著已知樣本的增加而逐次調整的,在新樣本加入時只需局部調整某些機率值,即可得到新的分類效能。不過以機率值構成的分類模型也有不意解釋分類原因的缺點,因此貝式分類法較適合用在預測未知樣本的類別,而不適合用來找出資料分類的原因。

支撐向量機法(Support Vector Machine, SVM)是以核心函數(Kernel Function)
為基礎的學習方法,可運用在分類與非線性迴歸上。在分類的問題方面,SVM
的主要概念是建構一個最佳的超平面作為分類決策的界面,透過此界面能有效分
類Positive example 和Negative example。從SVM 簡單的類型來看,如圖1,
圓圈代表為正例(Positive example),星星 代表為負例(Negative example)。在此例子
中,我們可以直接以線性超平面去分割這些資料,但大部份的資料形式所待解決
的問題,多屬於非線性分割的問題,我們是無法用簡單線性去分割,因此必須藉
由從物件空間(Instance space)中將資料轉換到特徵空間(Feature space)。則圖2
呈現非線性分割的狀態。

對於分類為兩類的例子中,X 為輸入空間(Input space/Instances),Y 則為輸
出值(Output values), x 為物件(Instance), a 為物件的屬性,其表示如下:

透過對物件的判斷可以將其分類為Y = 1 (Positive class)和Y = -1 (Negative
class)。而資料由輸入空間轉換至特徵空間其想法如下所示:
想法:

目的:在特徵空間中找最佳分割超平面
例如:

透過在輸入空間中多項式核心函數且d=2 的轉換而找出在特徵空間中的最適分
割超平面。
假設輸入空間Input Space:
則特徵空間Feature Space:

在圖形上資料的輸
入與特徵空間中的轉換有助於尋找最適分割平面與分類資料,圖示如下:

資料在輸入空間

資料在特徵空間

Support Vector Machine 簡介 1. 資料分群 (Data Classification)對於一群資料而言,有時候我們會希望依據資料的一些特性來將這群資料 分為兩群。而就資料分群而言,我們已知有一些效果不錯的方法。例如:NearestNeighbor、類神經網路(Neural Networks)Decision Tree 等等方式,而如果在正 

確的使用的前提之下,這些方式的準確率相去不遠,然而,SVM 的優勢在於使用上較為容易。

2. Support Vector Machine 概念 對於一群在Rd 空間中的資料,希望能夠在該空間之中找出一Hyper-plan,並且,希望此Hyper-plan 可以將這群資料切成兩群(:群組A、群組B)。而屬於群組A 的資料均位於Hyper-plan 的同側,而群組B 的資料均位於Hyper-plan 的另一側。 

 

 

-馬可夫鏈的簡介-

在一般及常用的統計中,彼此相互「獨立」大概是最有用的一個觀念。用簡單的術語來說,互相「獨立」就是彼此毫不相干,一點牽涉都沒有。好比說:大黃在台北早上不是吃海鮮和老馬在基隆晚上是不是吃海鮮是兩件互相獨立的事件。互相獨立的概念之所以有用,最重要的原因之一就是因為它簡單,幾乎任何人都很容易明白。但我們今天要談的馬可夫鏈可就不是這樣了。馬可夫鏈是要討論不是互相獨立的一些事件。以大黃和老馬吃海鮮的例子來說,如果大黃和老馬是住在一個屋簷下的話,早上吃海鮮和晚上吃海鮮就不是完全無關的兩件事了!有的時候海鮮吃出了癮,非要連吃好幾頓才行;這樣的話如果大黃、老馬早上吃了海鮮,他們晚上還是吃海鮮的機會就很大了。當然也有可能就是早上吃了海鮮覺得晚上換一種口味比較可口,這樣的話早上吃了海鮮,那麼晚上再吃的機會又比較小了。總之,這個例子只是要說明不是互相獨立的事件也是很容易在日常生活碰到的,更不用說再稍微複雜一點的統計中更是會經常碰到的。但再這樣一個籠統的名辭「不是互相獨立」下,我們要怎樣了解它呢?「不是互相獨立」也就是說互相關聯的意思,但是要樣相關呢?如何在相關中作一些簡單的分類呢?馬可夫鏈就是要描述在「相關」這個概念中最簡單的一種。但即使如此,有關馬可夫鏈的理論已經相當豐富了。在機率的理論中,它幾乎佔了絕大的部分。以下我們就慢慢的說明它的一些性質。

設想我們再作一連串的試驗,而每次試驗所可能發生的結果定為 E1,E2,… En,…。(可能是有限也可能是無限)。每一個結果 Ek,我們若能給定一個出現的可能性 pk(即機率),則對某一特定樣本之序列 Ej1Ej2Ejn,我們知道它出現的機率是 p(Ej1Ej2Ejn) =pj1Pjn。這個是試驗與試驗彼此互相獨立的基本精神。但在馬可夫鏈的理論中,我們的目的就是要擺脫「獨立」的這個假設,因此我們沒有辦法知道(也就是沒有辦法給定)每一個事件出現的可能性;也就是說「pk」是不存在的。不過我們總得要知道一些東西才能討論,所以在馬可夫鏈中我們考慮最簡單的「相關」性。在這種情況下,我們不能給任一個事件 Ej 一個機率 pj 但我們給一對事件 (Ej,Ek) 一個機率 pjk,這個時候 pjk 的解釋是一種條件機率,就是假設在某次試驗中 Ej 已經出現,而在下一次試驗中 Ek 出現的機率。除了 pjk 之外,我們還須要知道第一次試驗中 Ej 出現的機率 aj。有了這些資料後,一個樣本序列 Ej0Ej1Ejn(也就是說第零次試驗結果是Ej0,第一次試驗是 Ej1……第 n 次試驗是 Ejn)的機率就很清楚的是 P(Ej0,Ej1,Ejn) =ajpj0j1pj1j2pjn-1jn

有了以上的概念後,現在讓我們用一些數學符號來表示這些數量。在常用的術語中,用 S 來表示狀態空間,也就是一個試驗所有可能出現的狀態所成的集合。令 Xn 表示在第 n 次試驗的結果。所以 Xn 是一個隨機變數,它的取值是在狀態空間S中。

定義1:
一組值在 S 中的隨機變數 X0,X1,X2 $\cdots\cdots$ 稱為馬可夫鏈。如果它滿足以下的條件:

 

\begin{displaymath} P(X_{n+1}=x_{n+1} \vert X_0=x_0 \cdots X_n = x_n) =P(X_{n+1}=x_{n+1} \vert X_n =x_n) \eqno{(1)} \end{displaymath}
其中 x0, x1,…,xn+1 皆屬於 S
1)式的意思是說我們以 PxyP(x,y) 表示 P ( $X_{n+1} =y \mid X_n=x$),假設我們知道第 0 次到第 n 次的試驗結果,則第 n+1 次的試驗結果僅僅和第 n 次有關,我們舉一些例子來看:(為了簡單起見,本文只討論平穩的馬可夫鏈。也就是說(1)中的轉換機率和狀態有關但和時間無關。)
例一:
設有一賭徒甲帶了現金若干去賭場賭博。如果他每贏一次則贏一元而每輸一次也輸一元,同時贏的機率是 p(輸的機率就是 q=1-p),則 X0,X1,X2, $\cdots\cdots$ 顯然是一個馬可夫鏈。(Xn 表示他賭 n 次後手中所有的資金)為什麼呢?因為僅僅需要知道 Xn 的值就足以預測 Xn+1 的值,另外 $X_0 X_1 \cdots X_{n-1}$ 並不能幫助我們做更好的預測

分類(Classification)-基因演算法

遺傳學概述:

1975年 John Holland提出以基因遺傳演算法來解決數學最佳化的問題,主要啟發來自於達爾文的進化論『物競天擇、強者生存』的定律,主要內容為選擇(Selection)較好特性的母代,再將母代隨機性交配(Cross over),有時候交配出來的子代基因會有突變(mutation),再挑選出適應力高的子代,一代一代演化,最後可得適應力高的物種。

應用:
        data mining著重是分類、預測的問題,而遺傳演算法主要解決優化結果的問題兩者之間有重覆的部份,以下是data mining 典型的問題。例如 是根據某項產品前一週的銷售量及其特性等等,預測其存貨量。換成最優化的方式,問題就變:『哪一種函數與存貨曲線是最吻合,可用來預測。』,若只是用傳統演算法去歸納分類或預測的結果可能會使決策過程變得非常複雜,而基因演算法則提供了另一種參考結果。

實作步驟:

        1、隨機產生初始族群。
        2、針對基因進行編碼。
        3、基因進行交配與突變。
        4、比對是否符合適應函數值。
        5、留下符合的子代。
        6、重覆2、3、4步驟,直到子代無法再優化或符合終止條件。

優點:
(1)   可依使用者設定突變率與適應函數求得結果。
(2)   適合用在極大量族群中找出合適的子代。
(3)   可避免傳統演算法陷入區域最佳解的問題。

缺點:
(1)編碼與適應函數不好設計。
(2)運算成本高。

參考文獻

http://www2.nkfust.edu.tw/~rffung/lab/data/lab09.html

http://el.mdu.edu.tw/datacos//09422332004A/Ch4%20%E5%9F%BA%E5%9B%A0%E6%B...

http://www.taai.org.tw/taai2005/Local/papers/T5/LS8(G)/taai2005-paper-216.pdf

回應

所謂決策樹是指一個樹狀結構,樹的中間節點(non-leaf nodes)代表測試的條件,樹的分支(branches)代表條件測試的結果,而樹的葉節點(leaf nodes)則代表分類後所得到的分類標記,也就是表示分類的結果。

決策樹的產生程序

包含兩個步驟:

step1:建立樹狀結構

   一開始將所有的training samples放在根節點的位置,接著再根據所選擇的testing samples條件將training samples分成不同得子集合,若是分在某子集合內的training samples全部都屬於同一個分類標記,便產生一個葉節點來代表這群樣本的分類標記,結束分類的動作,否則便重複選取測試條件,直到所有的樣本都可以分成屬於同一分類標記的子集合為止,此時樹狀結構及建立完。

step2:修剪樹狀結構

  當樹狀結構建立完成之後,接下來要針對所產生的決策樹進行修剪的動作,也就是將這個樹狀結構當中代表雜訊或是特例的分支剪掉,以避免所產生的決策樹過度遷就特定資料樣本。

 

貝式分類法是一種或然率的學習法(Probailistic learning),也就是一種以機率、統計學為基礎的分類法,此法最大的優點是具有漸增性(incremental)。

前面所介紹的決策樹分類法必須使用全部的樣本來建立分類模型,因此當分類模型建立之後,若有新樣本要加入,則必須利用舊樣本重新建立一株新的決策樹之後,才能利用到新樣本對分類模型的貢獻;也就是說,決策樹的建立並無法以漸進的方式,逐步將資料加入,使決策樹漸次成長,可見決策樹分類法不具有漸增性

貝式分類法利用事件發生的機率來推測為之資料的類別,由於機率的計算是可隨著已知樣本的增加而逐次調整的,在新樣本加入時只需局部調整某些機率值,即可得到新的分類效能。不過以機率值構成的分類模型也有不意解釋分類原因的缺點,因此貝式分類法較適合用在預測未知樣本的類別,而不適合用來找出資料分類的原因。

支撐向量機法(Support Vector Machine, SVM)是以核心函數(Kernel Function)
為基礎的學習方法,可運用在分類與非線性迴歸上。在分類的問題方面,SVM
的主要概念是建構一個最佳的超平面作為分類決策的界面,透過此界面能有效分
類Positive example 和Negative example。從SVM 簡單的類型來看,如圖1,
圓圈代表為正例(Positive example),星星 代表為負例(Negative example)。在此例子
中,我們可以直接以線性超平面去分割這些資料,但大部份的資料形式所待解決
的問題,多屬於非線性分割的問題,我們是無法用簡單線性去分割,因此必須藉
由從物件空間(Instance space)中將資料轉換到特徵空間(Feature space)。則圖2
呈現非線性分割的狀態。

對於分類為兩類的例子中,X 為輸入空間(Input space/Instances),Y 則為輸
出值(Output values), x 為物件(Instance), a 為物件的屬性,其表示如下:

透過對物件的判斷可以將其分類為Y = 1 (Positive class)和Y = -1 (Negative
class)。而資料由輸入空間轉換至特徵空間其想法如下所示:
想法:

目的:在特徵空間中找最佳分割超平面
例如:

透過在輸入空間中多項式核心函數且d=2 的轉換而找出在特徵空間中的最適分
割超平面。
假設輸入空間Input Space:
則特徵空間Feature Space:

在圖形上資料的輸
入與特徵空間中的轉換有助於尋找最適分割平面與分類資料,圖示如下:

資料在輸入空間

資料在特徵空間