第7章聚類分析基本概念聚類分析聚類是將物理或抽象對象的集合劃分成為由類似的對象組成的多個屬類的過程。比較相近比較相似比較相像如何衡量簇間最大化簇內最小化聚類分析聚類是將物理或抽象對象的集合劃分成為由類似的對象組成的多個屬類的過程。聚類分析按照一定的算法規(guī)則，將判定為較為相近和相似的對象，或具有相互依賴和關聯(lián)關系的數(shù)據(jù)聚集為自相似的組群，構成不同的簇。物以類聚人以群分聚類分析將數(shù)據(jù)劃分成有意義或有用的組群，在各種應用中，一個簇中的數(shù)據(jù)對象可以被作為一個整體來對待應用商務

-從客戶信息庫中發(fā)現(xiàn)不同的客戶群，以購買模式來刻畫不同的客戶群的特征，進行有針對性的精準營銷聚類分析將數(shù)據(jù)劃分成有意義或有用的組群，在各種應用中，一個簇中的數(shù)據(jù)對象可以被作為一個整體來對待應用生物學-通過對基因進行類別劃分，推導動植物的分類，獲得對種群中固有結構的認識聚類分析將數(shù)據(jù)劃分成有意義或有用的組群，在各種應用中，一個簇中的數(shù)據(jù)對象可以被作為一個整體來對待應用地理-從地球觀測數(shù)據(jù)庫中的數(shù)據(jù)確定地理上相似的地區(qū)房地產

-根據(jù)房屋的類型、價值和地理位置對商品房進行分組，區(qū)別處理聚類分析將數(shù)據(jù)劃分成有意義或有用的組群，在各種應用中，一個簇中的數(shù)據(jù)對象可以被作為一個整體來對待應用信息-對Web上的文檔進行處理分類，以便于進行分類檢索和發(fā)現(xiàn)信息與分類相區(qū)別分類訓練數(shù)據(jù)

產生規(guī)則（提取模型）

標注Supervised有監(jiān)督的聚類數(shù)據(jù)

發(fā)現(xiàn)相似

簇Unsupervised無監(jiān)督的聚類的復雜性簇類型明顯分離的(Well-Separated)每個點到同簇中任一點的距離比到不同簇中所有點的距離更近。3個分離簇聚類的復雜性簇類型基于原型的每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近。對于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質心，即簇中所有點的平均值。當質心沒有意義時，原型通常是中心點，即簇中最有代表性的點?；谥行牡模–enter-Based）的簇：每個點到其簇中心的距離比到任何其他簇中心的距離更近。4個基于中心的簇聚類的復雜性簇類型基于圖的簇可以定義為連通分支（connectedcomponent）互相連通但不與組外對象連通的對象組。基于近鄰的（Contiguity-Based）其中兩個對象是相連的，僅當它們的距離在指定的范圍內。這意味著，每個對象到該簇某個對象的距離比到不同簇中任意點的距離更近。8個“連通”簇圖論的圖！如果數(shù)據(jù)用圖表示，其中節(jié)點是對象，而邊代表對象之間的聯(lián)系。聚類的復雜性簇類型基于密度的(Density-Based)簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。6個基于密度的簇聚類的復雜性簇類型基于密度的(Density-Based)簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞?；诿芏鹊拇鼐垲惖膹碗s性簇類型概念簇(ConceptualClusters)可以把簇定義為有某種共同性質的對象的集合。例如：基于中心的聚類。還有一些簇的共同性質需要更復雜的算法才能識別出來。2個交疊簇聚類的復雜性分為幾個簇?分為4個簇分為2個簇分為6個簇聚類算法分類聚類算法K均值，k-medoids及其擴展算法層次聚類算法基于密度的聚類基于網(wǎng)絡的聚類其他聚類算法劃分聚類算法CLARA，CLARANSCURE算法，ROCK算法BIRCH算法等DBSCAN算法GDBSCAN，DBCLASD算法OPTICS算法FDC算法BANG算法WaveCluster算法STING算法聚類算法分類按分類方法劃分聚類聚類算法分類按分類方法劃分聚類層次聚類聚類算法分類按分類方法劃分聚類層次聚類基于密度的聚類聚類算法分類按劃分方法分類互斥聚類聚類算法分類按劃分方法分類互斥聚類非互斥聚類聚類算法分類按劃分方法分類互斥聚類非互斥聚類模糊聚類聚類算法分類按劃分范圍分類完全聚類(completeClustering)部分聚類(partialClustering)“距離”度量聚類的實質是“近朱者赤近墨者黑”定義距離函數(shù)，基于屬性值進行計算非負性對于任意x，y，兩者之間的距離d(x，y)≥0，當x

=y時，等號成立。對稱性對于任意x，y，兩者之間的距離d(x，y)=d(y，x)，即距離是標量而不是向量。三角不等式對于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即對象x到對象y的距離小于等于途經(jīng)其他任何對象z的距離之和。？怎樣才算近？也稱為相似性“距離”度量歐幾里得距離EuclideanDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其歐幾里得距離為在二維空間中的歐幾里得距離就是平面中兩點之間的實際距離。在三維空間中的歐幾里得距離就是立體（三維）空間中兩點之間的實際距離?！熬嚯x”度量曼哈頓距離對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈頓距離為(6,6)(2,2)歐幾里得距離=5.66曼哈頓距離=(6-2)+(6-2)=844xy“距離”度量明可夫斯基距離MinkowskiDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距離為相似系數(shù)余弦相似度對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即對于x，y兩個向量，有：cos(x,y)=(x?y)/‖x‖?‖y‖

余弦相似度【例如】分析以下兩個句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。1)可以將兩個句子進行分詞：句子A：我/喜歡/看電視/不/喜歡/看/電影句子B：我/不/喜歡/看/電視/也/不/喜歡/看/電影2)對所出現(xiàn)的各個詞匯（我

喜歡

看

電視

電影

不

也），計算其詞頻：句子A：我1，喜歡2，看2，電視1，電影1，不1，也0句子B：我1，喜歡2，看2，電視1，電影1，不2，也1余弦相似度【例如】分析以下兩個句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。3)將詞頻轉換為向量：句子A：x=(1221110)句子B：y=(1221121)4)計算其余弦相似度，有：余弦相似度由此，我們就得到了“找出相似文章”的一種算法：使用TF-IDF算法，找出兩篇文章的關鍵詞；每篇文章各取出若干個關鍵詞（比如20個），合并成一個集合，計算每篇文章對于這個集合中的詞的詞頻（為了避免文章長度的差異，可以使用相對詞頻）；生成兩篇文章各自的詞頻向量；計算兩個向量的余弦相似度，值越大就表示越相似。相似系數(shù)余弦相似度相關系數(shù)反映變量之間相關關系密切程度的統(tǒng)計指標相關系數(shù)按積差的方法計算，以兩變量與各自平均值的離差為基礎，通過兩個離差相乘來反映兩變量之間相關程度。x與y之間的協(xié)方差x,y的均方差相似系數(shù)余弦相似度相關系數(shù)Jaccard相似系數(shù)(JaccardSimilarityCoefficient)用于比較有限樣本集之間的相似性與差異性A、B的相似性：Jaccard距離：余弦相似度TF-IDF算法TF-IDF通過統(tǒng)計方法，對字詞對于語料庫中的一份文件或文件集的重要程度進行評估。字詞的重要性隨其在文件中出現(xiàn)的次數(shù)正比增加，隨其在語料庫中出現(xiàn)的頻率成反比下降，即如果某字在一篇文章中出現(xiàn)的頻率TF高，而在其他文章中很少出現(xiàn)，則認為該字詞具有很好的類別區(qū)分能力，適合用于分類。這里TF為詞頻(TermFrequency)，表示詞條在文檔d中出現(xiàn)的頻率；IDF為逆向文件頻率(InverseDocumentFrequency)，表示包含詞條的文檔的數(shù)量，值越大，表明詞條具有很好的類別區(qū)分能力。TF-IDF加權的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。除了TF-IDF以外，因特網(wǎng)上的搜索引擎還會使用基于鏈接分析的評級方法，以確定文件在搜尋結果中出現(xiàn)的順序。誤差平方和(SSE)在對兩組數(shù)據(jù)的誤差情況進行估計的時候，如原始數(shù)據(jù)和擬合數(shù)據(jù)之間的誤差，或者是理論數(shù)據(jù)和觀測數(shù)據(jù)之間的誤差，會用其誤差值取平方后求和來衡量誤差的大小。計算公式為：

誤差平方和(SSE）誤差平方和（sumof