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