10.2
（a）第一輪執(zhí)行后的三個簇分別是：（1）{A1}（2）{B1，A3，B2，B3，C2}（3）{C1，A2}
三個簇的中心分別是（1）（2,10）（2）（6,6）（3）（1.5,3.5）。
（b）最后的三個簇是（1）{A1,C2,B1}（2）{A3,B2,B3}（3）{C1,A2}
10.3
（0,2）（2,2）（4,2）
（0,1）（2,1）（4,1）
（0,0）（2,0）（4,0）
列和列之間距離大，行與行之間距離小，聚成三類的最優(yōu)結果應該是每一列為一類，此時，類內(nèi)方差最小。
但如果初始點選成中間的三個點，聚類結果就成了每一行為一類，顯然是局部最優(yōu)，不是全局最優(yōu)。
10.6
（a）當存在噪聲和離群點時，k -中心點方法比k -均值具有更強的魯棒性，這是因為中心點不像均值那樣容易受離群點或其他極端值影響。然而，當n（待聚類的對象數(shù)）和k的值較大時，k -中心點算法的計算開銷遠高于k -均值方法。
（b）k -均值和k -中心點都是劃分方法。這種劃分方法的優(yōu)點是，可以撤銷之前的聚類步驟（通過迭代遷移），而在層次聚類方法中，一旦執(zhí)行了一次合并或分裂，就不能做出調(diào)整，下一步的處理將在新產(chǎn)生的簇上進行。因此，如果合并或分裂選擇不當，層次聚類方法可能會導致低質(zhì)量的簇。劃分方法能夠很好地找到球形簇，一般地，對于中小型數(shù)據(jù)庫，它的聚類質(zhì)量都不錯。但是劃分方法的一個弱點是需要在聚類之前指定聚類的數(shù)量。分層聚類方法可以自動地在聚類過程中決定聚類的數(shù)量，但是這種方法不具有很好地可伸縮性，因為每次合并或分裂的決定都需要考察和評估許多對象和簇。另外，層次方法可以與其他聚類方法集成（比如BIRCH，ROCK,Chameleon等），改進聚類結果。
10.7
假設用ε指定每個對象的領域半徑，用MinPts指定稠密區(qū)域的密度（可以簡單地用鄰域內(nèi)的對象數(shù)度量）閾值。則密度相連的概念：給定一個對象集D，如果存在對象q，p1,p2∈D，并且對象p1和P2都是從q關于ε和MinPts密度可達的，則對象p1,p2是關于ε和MinPts密度相連的。因為密度相連的兩個對象并不要求為核心對象，所以當對象p1和p2關于對象q密度相連時，p2是從q關于ε和MinPts密度可達的，p1也是從q關于ε和MinPts密度可達的，所以p2和p1是關于ε和MinPts密度相連的。所以，密度相連滿足對稱性；又因為可以認為某一點和它自身是密度相連的，所以密度相連滿足自反性；容易證明，對于對象o1、o2和o3，如果o1和o2是密度相連的，并且o2和o3是密度相連的，則o1和o3也是密度相連的，所以密度相連滿足傳遞關系。因為密度相連滿足對稱性、自反性和傳遞性，所以密度相連是等價關系。
10.8
假設一個對象集合D，取稠密區(qū)域的閾值為MinPits值和鄰域半徑為閾值ε1時對任一滿足核心對象條件的數(shù)據(jù)對象p，數(shù)據(jù)庫D中所有從p密度可達的數(shù)據(jù)對象o所組成的集合構成了一個完整的聚類C，且p屬于C；其中對象p在ε1鄰域內(nèi)的樣本點數(shù)大于等于MinPts；
如果簇C中存在核心對象P，且P不屬于簇C'，則點對象P的ε2鄰域的樣本點數(shù)小于MinPts，若對象P的ε2鄰域的樣本點數(shù)小于MinPts，由于ε1<ε2，那么對象P的ε1鄰域的樣本點數(shù)小于MinPts，這與P是簇C的核心對象矛盾，所以簇C中的核心對象一定是簇C’中核心對象的子集；
如果簇C中存在非對象N，且N不屬于簇C'，則對象N不是從對象P關于ε2和MinPts密度可達的，由于ε1<ε2,那么對象N也不是從對象P關于ε1和MinPts密度可達的，這與N屬于簇C矛盾，所以簇C中的非核心對象一定是簇C'中非核心對象的子集；
因此，當ε1<ε2時，關于ε1和MinPits的簇C一定是關于ε2和MinPits的簇C'的子集。
10.18
約束算法可以通過以下幾個方面的修改得到滿足題目要求的基于約束的聚類：
（1）微簇。為降低兩個對象或點間距離計算的開銷，可以使用一些預處理或者優(yōu)化技術。一種方法是把鄰近的點首先聚集到一些微簇中。此過程可以先用三角劃分的方法把區(qū)域R分為若干三角形（對于此題而言，可以把障礙物視為劃分邊界，得到一個個小三角區(qū)域），然后使用類似于DBSCAN的方法把同一個三角形中相近的點劃分到微簇中。通過處理這些微簇而不是個體點，降低總的計算量。
（2）距離度量。如果兩個對象之間存在障礙物，則應該調(diào)整它們之間的距離。在這種情況下，可達距離比直線距離更合理。因為在實際問題中障礙物往往很難跨越甚至根本無法跨越，此時使用直線距離相當于忽略了障礙物，不符合實際。在本題中，如果兩點之間不存在障礙物，那么兩點之間的可達距離等于它們之間的直線距離；如果兩點之間存在障礙物，那么這兩點的可達距離為避開障礙物從一點至另一點的最短距離。
（3）基于中心點方法。在障礙物存在的情況下，如果選擇K均值方法，簇中心可能是不可達的。例如，簇均值有可能會落在河流或者公路上。而k中心點方法選擇簇中的對象作為簇中心，保證了簇中心的可達性。在本題中，對于給定的一個區(qū)域R，可以先初始化為k個聚類（k介于可以分配給此區(qū)域ATM的最大數(shù)量和最小數(shù)量之間）；通過考察每個聚類中障礙物的數(shù)量，家庭的數(shù)量等信息，對各個聚類進行合并和分裂操作，直至聚類穩(wěn)定；如果此時聚類滿足指定的約束（如每個ATM能為10000戶家庭服務），并且聚類數(shù)小于或等于計劃分配的ATM數(shù)量，則在各個聚類的中心點安裝ATM。如果不滿足約束，或者聚類數(shù)過大，則需要選擇次優(yōu)聚類方案進行聚類，使得聚類滿足指定的約束（聚類數(shù)不超過計劃分配的ATM數(shù)量，每個ATM應該能為10000戶家庭服務）。
10.19
我們可以根據(jù)約束作用于何處對約束分類，可以分為：實例上的約束、簇上的約束和相似性度量上的約束。
實例上的約束說明一對或一組實例如何在聚類分析中被分組。如：必須聯(lián)系約束，指定兩個對象必須聚類到同一個簇中；不能聯(lián)系約束，指定兩個對象必須聚類到不同的簇中。
簇上的約束使用簇的屬性，說明簇的要求。例如，指定每個簇中的客戶的最大數(shù)目、指定每個簇中客戶的平均收入。
相似性度量上的約束，例如規(guī)定采用歐式距離度量兩個對象之間的相似性。
也可以考慮約束必須遵守的程度，將約束劃分為硬性的和軟性的。一個約束是硬性的，如果違反該約束的聚類是不可接受的。一個約束是軟性的，如果違反該約束的聚類是不可取的，但是在找不到更好的解時還可以接受。
在聚類的指派過程中，硬性約束必須嚴格遵守。如指定了數(shù)據(jù)集上的必須聯(lián)系約束，可以先計算一個必須聯(lián)系約束的傳遞閉包，該閉包給出一個或多個對象子集，其中一個子集中的所有對象必須要分配到同一個簇中。
而處理軟性約束時，可以對違反軟性約束的聚類施加一個罰，將尋找最優(yōu)聚類問題轉化為一個優(yōu)化問題。
補充：證明密度相連的傳遞性（歡迎交流）
首先：我們先證明一個小問題，對于a,b,c∈D，a->c,b->c,則ab均為核心對象且c均在鄰域中，
