Posted on 2005-12-07 10:41
inwind 閱讀(652)
評論(0) 編輯 收藏 引用
距離近：在一些重要的屬性上比較相似
聚集（clustering）：是把相似的記錄放在一起。
用途
聚集
讓用戶在較高的層次上觀察數據庫。常被用來做商業上的顧客分片（segmentation）。
找到不能與其他記錄集合在一起的記錄，做例外分析。
最近鄰居
預測，距離相近的對象通常他們的預測值也相似，因此只要知道一個對象的預測值，就可以用他來預測他的鄰居的值。
分數卡
基本思想
一般來說一個數據庫沒有一種最好的分類方法。聚集要在類中對象的相似程度和類的數目之間找到一個最佳的結合點。
N
維空間和距離
變量（字段）的個數作為空間的維數。
基本的距離定義有兩種：Manhatan距離 ∑∣a-b∣、歐氏距離（∑（a–b）2）1/2
決定變量權重的方法：
按照實際問題中各個變量對預測值的影響程度
用進化的辦法，修改各個變量的權重，看是否能提高預測的準確率。
在文本挖掘中：1 用單詞出現頻率的倒數；2 按照各個單詞對要檢索內容的相關程度
怎樣計算兩個類的距離：
- 單連通方法（single-link method）：取兩個類中最近記錄的距離為類的距離。此種方法可以生成細長的蛇形類，不適于應用在典型的一堆堆記錄集合在一起的情況。
- 完全連通方法（
complete-link method）：取兩個類中最遠記錄的距離為類的距離。同第1中方法相反，此種方法易生成很小的記錄都聚集在一起的類。
- 平均連通方法（
group-average link）：計算兩個類中所有記錄對的距離平均值。效果介于1、2種算法之間。
- Ward
方法（Ward’s method）：計算兩個類中所有記錄的距離的和。易于用在生成類層次的情況，對例外的數據（outliers）很敏感，很難應用于生成蛇形類。
聚集的分類和算法流程
分層的聚集（
hierarchy）：生成一個從小到大的聚集層次樹。用戶可以自由剪切這棵樹，得到對數據的不同劃分方法
合并（Agglomerative）：從下到上，最初每個記錄都是一類，逐步合并，直到合并成一個大類。
- 令數據庫中的每一條記錄都是一個類
- 把距離最近的類合并
- 重復2直到只含唯一的一個類為止
分割（Divisive）：從上到下，一開始所有記錄屬于一個大類，逐步分割每一個類，直到不能分割為止。因選擇分割哪一個類需要很大的計算量，此種方法很少使用。
- 令數據庫中的所有記錄都屬于一個類
- 在所有的類中找到一個類中數據相似性最小的一個類，把他一分為二
- 重復2直到每個類中記錄的個數都是1或達到一個預先設定的閾值，或類的個數已達到預先設定的最大個數
不分層聚集：速度更快，但需要用戶在使用前設定一些參數，如類的個數、同一類中記錄的最大距離。有時要反復修改參數才能得到一種滿意的分類方法。
一次通過法（single-pass methods）：只掃描數據庫一次，就可完成分類。
- 從數據庫中讀取一條記錄，判斷他距哪個類的距離最近
- 如果即使到最近的類的距離比我們設定的距離相比還遠，那么建立一個新的類，把此記錄放到此類中去。
- 如果數據庫中還有記錄轉1。
問題：數據庫中記錄的輸入順序和類內最大距離的設定，對分類的結果影響很大。
再分配法（reallocation methods）：要把一條記錄從一個類拿出來重新分到另一個類。
- 預先設定想要把數據分成類的個數
- 為每個類隨機選取一條數據，作為類的中心或“種子”
- 一次讀取數據庫中的每一條記錄，將其歸到距離最近的類。
- 重新計算各個類的中心
- 重復3-4，直到類的中心不再變化或變化很小
問題：用戶設定的類的個數很難與實際數據中存在的類的個數正好相符
最近鄰居用于預測
方法
找到數據庫中距離最近記錄，將此記錄的值作為新記錄的預測值
找到最近的K個記錄，用這K個記錄按其到新記錄的距離作為權重，綜合得到新記錄的預測值。
缺點
- 模型太大，預測時要使用整個歷史數據庫
- 沒有正規的用于防止overfitting的方法（formal way）
模型的改進：刪除用于預言的歷史數據庫中多余的數據，以得到數據量小而且準確度高的數據。
- 合并相似的記錄，用一條記錄（稱為原型）代替相似的幾條記錄。要在不降低預測準確率的前提下。
- 只保留一組相似數據中的“邊界”數據（稱為“哨兵”），去掉“邊界”內部的無用數據。
發展方向
- 應用算法到新的領域
- 改進輸入變量權重的計算方法，和如何減小用于預測的歷史數據的大小
- 根據歷史記錄自動計算變量的權重