Cluster：
Cluster: a collection of data objects
Similar to one another within the same cluster
Dissimilar to the objects in other clusters
Cluster analysis：根據(jù)數(shù)據(jù)的特征找出數(shù)據(jù)間的相似性雪位，將相似的數(shù)據(jù)分成一個類供炎。
Unsupervised learning: no predefined classes
Examples of Clustering Applications：
Marketing:幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群回窘，并且用購買模式來刻畫不同的客戶群的特征
Land use:在地球觀測數(shù)據(jù)庫中用以確定相似地區(qū)
City-planning:根據(jù)房子的類型孵户，價值北戏，和地理位置對一個城市中的房屋分組
好的聚類方法能產(chǎn)生高質(zhì)量的聚類。所謂高質(zhì)量雄卷，指：類中的對象高度相似熄驼，類間的對象高度不相似
聚類方法的好壞也可以按照它是否能夠發(fā)現(xiàn)更多的隱含模式來度量
Dissimilarity/Similarity metric: 相似性通常用距離函數(shù)來表示，typically metric: d(i, j)
距離函數(shù)的定義對于不同的數(shù)據(jù)通常是不同的劝赔，如：interval-scaled誓焦、Boolean、Categorical望忆、ordinal ratio罩阵、vector variables.
根據(jù)應用背景或者數(shù)據(jù)語義的不同，對不同的變量可以適當加權
Data matrix（數(shù)據(jù)矩陣启摄，或稱為對象屬性結構）：用p個變量（也稱為屬性）來表現(xiàn)n個對象稿壁，例如用年齡，身高歉备，性別傅是，種族等屬性來表現(xiàn)對象“人”。這種數(shù)據(jù)結構是關系表的形式蕾羊，或者看為n*p維（n個對象*p個屬性）的矩陣喧笔。
Dissimilarity matrix（相異度矩陣，或稱為對象-對象結構）：存儲n個對象兩兩之間的近似性龟再，表現(xiàn)形式是一個n*n維的矩陣书闸。
d(i,j)是對象i和對象j之間相異性的量化表示，通常它是一個非負的數(shù)值利凑，當對象i 和j越相似浆劲，其值越接近0；兩個對象越不同哀澈，其值越大牌借。既然d(i,j) = d(j,i)，而且d(i,i)=0割按，可以得到如下矩陣：
聚類分析中的數(shù)據(jù)類型：
nInterval-scaled variables（區(qū)間標度 ）
nBinary variables（二元變量 ）
nNominal, ordinal, and ratio variables（標稱型膨报、序數(shù)型和比例標度型 ）
nVariables of mixed types（混合型 ）
區(qū)間標度變量的典型的例子包括重量和高度，經(jīng)度和緯度坐標，以及大氣溫度等现柠。
選用的度量單位將直接影響聚類分析的結果院领。例如，將高度的度量單位由“米”改為“英尺”晒旅，或者將重量的單位由“千克”改為“磅”栅盲，可能產(chǎn)生非常不同的聚類結構。
為了避免對度量單位選擇的依賴废恋，數(shù)據(jù)應當標準化谈秫。為了實現(xiàn)度量值的標準化，一種方法是將原來的度量值轉(zhuǎn)換為無單位的值鱼鼓。
給定一個變量f的度量值域庇，可以進行如下的變換：
計算平均的絕對偏差（mean absolute deviation）Sf
其中：
計算標準化的度量值援制，或z-score：
計算對象間的相異度?
對象間的相異度（或相似度）是基于對象間的距離來計算的
通常使用明考斯基距離：
其中i = (xi1, xi2, …, xip) 寒跳，j = (xj1, xj2, …, xjp) 分別代表兩個p-維的對象, q是一個正整數(shù)
q = 1的時候胚委，d稱為曼哈頓距離?
當q =2表示歐幾里得距離
距離函數(shù)具有如下屬性：
1．d（i，j）≥0：距離是一個非負的數(shù)值嘉赎。
2．d（i置媳，i）=0：一個對象與自身的距離是0。
3．d（i公条，j）= d（j拇囊，i）：距離函數(shù)具有對稱性。
4．d（i靶橱，j）≤ d（i寥袭，h）+d（h，j）：從對象I到對象j的直接距離不會大于途徑任何其他對象的距離关霸。
可以對每個變量根據(jù)其重要性賦予一個權重
二元變量只有兩個狀態(tài)：0或1
0表示該變量為空传黄、1表示該變量存在
例如，給出一個描述病人的變量smoker队寇，1表示病人抽煙膘掰，而0表示病人不抽煙。
像處理區(qū)間標度變量一樣來對待二元變量會誤導聚類結果佳遣，所以要采用特定的方法來計算其相異度炭序。
二元變量的可能性
假設所有的二元變量有相同的權重，得到一個兩行兩列的可能性表
a是對對象i和j值都為1的變量的數(shù)目苍日，b是在對象i中值為1，在對象j中值為0的變量的數(shù)目窗声，是在對象i中值為0相恃，在對象j中值為1的變量的數(shù)目，是在對象i和j中值都為0的變量的數(shù)目笨觅。變量的總數(shù)是a+b+c+d
對稱的二元變量
如果二元變量的兩個狀態(tài)有相同的權重, 那么該二元變量是對稱的拦耐，也就是兩個取值0或1沒有優(yōu)先權耕腾。例如，“性別”
基于對稱二元變量的相似度稱為恒定的相似度杀糯，即當一些或者全部二元變量編碼改變時扫俺，計算結果不會發(fā)生變化。
對恒定的相似度來說固翰，評價兩個對象i和j之間相異度的最著名的系數(shù)是簡單匹配系數(shù)狼纬，其定義如下：
不對稱的二元變量
如果兩個狀態(tài)的輸出不是同樣重要，那么該二元變量是不對稱的骂际。例如一個疾病檢查的肯定和否定的結果疗琉。根據(jù)慣例，我們將比較重要的輸出結果歉铝，通常也是出現(xiàn)幾率較小的結果編碼為1盈简，而將另一種結果編碼為0。
給定兩個不對稱的二元變量太示，兩個都取值1的情況（正匹配）被認為比兩個都取值0的情況（負匹配）更有意義柠贤。基于這樣變量的相似度被稱為非恒定的相似度类缤。
對非恒定的相似度臼勉，最著名的評價系數(shù)是Jaccard系數(shù)，在它的計算中呀非，負匹配的數(shù)目被認為是不重要的坚俗，因此被忽略。
標稱型岸裙、序數(shù)型猖败、比例標度型 略
聚類算法
1、基于劃分的方法
給定一個n個對象或元組的數(shù)據(jù)庫降允，劃分方法構建數(shù)據(jù)的k個劃分恩闻，每個劃分表示一個聚類，并且k<=n剧董。也就是說幢尚，它將數(shù)據(jù)劃分為k個組，同時滿足如下的要求：（1）每個組至少包含一個對象翅楼；（2）每個對象必須屬于且只屬于一個組尉剩。
2、基于層次的聚類方法
主要思想是把數(shù)據(jù)對象排列成一個聚類樹毅臊，在需要的層次上對其進行切割理茎，相關聯(lián)的部分構成一個cluster。基于層次的聚類方法有兩種類型：
（1）聚合層次聚類皂林。最初每個對象是一個cluster朗鸠，然后根據(jù)它們之間的相似性，對這些原子的cluster進行合并础倍。大多數(shù)層次方法屬于這一類烛占，它們的主要區(qū)別是cluster之間的相似性的定義不同。
（2）劃分層次聚類沟启，它與上面的過程正好相反忆家。
用戶可以指定算法終止的條件，例如美浦，聚類的個數(shù)或每個cluster的半徑低于某個閥值弦赖。
n弱點在于合并或分裂點的選取問題，因為一組對象一旦合并或分裂浦辨，就不能有undo的操作
時間復雜度為O（N2）蹬竖，對于處理大數(shù)據(jù)量有性能問題。
3流酬、基于密度的方法
?絕大多數(shù)劃分方法基于對象之間的距離進行聚類币厕。這樣的方法只能發(fā)現(xiàn)凸狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難芽腾。
基于密度的聚類方法的主要思想是：只要臨近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閾值旦装，就繼續(xù)聚類。也就是說摊滔，對給定類中的每個數(shù)據(jù)點阴绢，在一個給定范圍的區(qū)域中必須包含至少某個數(shù)目的點。這樣的方法可以用來過濾“噪音”數(shù)據(jù)艰躺，發(fā)現(xiàn)任意形狀的簇呻袭。
4、基于方格的方法
把多維數(shù)據(jù)空間劃分成一定數(shù)目的單元腺兴，然后在這種數(shù)據(jù)結構上進行聚類操作左电。
該類方法的特點是它的處理速度，因為其速度與數(shù)據(jù)對象的個數(shù)無關页响，而只依賴于數(shù)據(jù)空間中每個維上單元的個數(shù)篓足。
5、基于模型的方法
神經(jīng)網(wǎng)絡方法
基于統(tǒng)計的方法
K-means算法
K-Means方法是MacQueen1967年提出的闰蚕。給定一個數(shù)據(jù)集合X和一個整數(shù)K（￡n）栈拖，K-Means方法是將X分成K個聚類并使得在每個聚類中所有值與該聚類中心距離的總和最小。
K-Means聚類方法分為以下幾步：
[1] 給K個cluster選擇最初的中心點没陡，稱為K個Means辱魁。
[2] 計算每個對象和每個中心點之間的距離烟瞧。
[3] 把每個對象分配給距它最近的中心點做屬的cluster。
[4] 重新計算每個cluster的中心點染簇。
[5] 重復2，3强岸，4步锻弓，直到算法收斂。
Example：
把14個人分成3組蝌箍，只有一個屬性青灼，年齡，初始的centroids是1, 20, , 40
下邊的表是完成步驟1妓盲，2后的結果
重新計算centroid 杂拨，得到5,12, 和 48
重新計算每個實例與3個Cluster的距離
P5 更接近 C2
需要重新計算C1 和 C2的centroid，C3 沒有變化不需要重新計算
3個Cluster的centroid 是4,11, 和 48
計算每個實例到Cluster的距離
P4 更接近 C2
需要重新計算C1 和 C2的centroid悯衬，C3 沒有變化不需要重新計算
3個Cluster的 centroid 是3,10和 48
計算每個實例到Cluster的距離
沒有任何變化
算法不再迭代
K-Means方法具有下面的優(yōu)點
（1）對于處理大數(shù)據(jù)量具有可擴充性和高效率弹沽。算法的復雜度是O（tkn），其中n是對象的個數(shù)筋粗，k是cluster的個數(shù)策橘，t是循環(huán)的次數(shù)，通常k娜亿，t<<n丽已。
（2）可以實現(xiàn)局部最優(yōu)化,如果要找全局最優(yōu)，可以用退火算法或者遺傳算法
K-Means方法也有以下缺點
（1）Cluster的個數(shù)必須事先確定买决，在有些應用中沛婴，事先并不知道cluster的個數(shù)。
（2）K個中心點必須事先預定督赤，而對于有些字符屬性嘁灯，很難確定中心點。
（3）不能處理噪音數(shù)據(jù)够挂。
（4）不能處理有些分布的數(shù)據(jù)（例如凹形）
K-Means方法的變種
? (1)K-Modes ：處理分類屬性
? (2)K-Prototypes：處理分類和數(shù)值屬性
? (3)K-Medoids
它們與K-Means方法的主要區(qū)別在于：
（1）最初的K個中心點的選擇不同旁仿。
（2）距離的計算方式不同。
（3）計算cluster的中心點的策略不同孽糖。
Classification vs.Clustering
Classification： Supervised learning.??Learns a method for predicting the instance class frompre-labeled (classified)? instances
Unsupervised learning：Finds “natural” grouping of instances given un-labeled data
