本次目標(biāo)
密度聚類
DBSCAN算法
噪聲：特征還包括不能被其他樣本密度可達(dá)
課堂問答
問： 每個p都必須是核心對象么？
答：是的复颈，如果p1 -> p2 -> p3->...->pn -> q绩聘，所有p都是核心對象沥割，最后一個是不是不清楚。
問：核心對象怎么確定凿菩？
答：給定ε机杜，給定一個m值，只要樣本周邊的樣本個數(shù)>M值衅谷，這個樣本是核心對象椒拗。或者說一個樣本周邊有足夠樣本获黔，就是核心對象蚀苛，否則不是。
1.確定核心對象
- 確定密度可達(dá)的樣本集合玷氏，即在ε范圍堵未，確定集合
- UNION - FIND - SET
即并查集，這個是用于實(shí)現(xiàn)集合交的方式簡單盏触，速度較快的方法
從而實(shí)現(xiàn)聚類
課堂問答
問：如果密度可達(dá)渗蟹，就是密度相連的吧？
答：是的
問：一般的閾值如何確定耻陕？
答：需要調(diào)參
問：m和ε也是調(diào)參么拙徽？
答：是的刨沦，是調(diào)參
如果存在某個核心對象诗宣，能夠被兩個簇的中心樣本密度可達(dá)，這兩個簇想诅，往往也能連在一起召庞。即可以合并簇
問：感覺半徑r的設(shè)定，對結(jié)果影響很大来破？
答：是的
問：密度相連的兩個點(diǎn)篮灼，路徑不唯一？
答：是的
問：epoch能否再講解一遍徘禁？
答：線性回歸中的概念诅诱。如果對x1, x2, x3, ..., xn, 我們總是會用某種方式，下降其維度送朱，如果把所有樣本遍歷一遍娘荡，下降完了，這個叫做一個epoch驶沼。但我們往往會取若干個樣本炮沐，其個數(shù)，遠(yuǎn)遠(yuǎn)小于總樣本個數(shù)回怜，這稱之為mini-batch大年。如1000個樣本，我們的batch選擇50（個樣本），則完成20個mini-batch翔试，對1000個樣本完成一次epoch轻要。
問：1->2->3->4,1和4超出半徑r，還是一個簇么垦缅？
答：是一個簇伦腐，因為都是密度可達(dá)的。
問：這個算法對數(shù)據(jù)分布有要求么失都？
答：沒有
問：1和3是核心對象柏蘑，1->2, 3->2，123是一個簇么粹庞？
答：是不確定的咳焚。因為無法判斷123一定是一個簇，共同指向一個東西很難說庞溜，但反過來革半，1->2, 1->3，則123是一個簇流码。
問：如果123不是一個簇又官，2歸誰呢？
答：1與3不一定如何漫试，2歸1或2歸3都有道理六敬。
問：在DBSCAN中，指向不是相互的么驾荣？即1->2外构，等同于2->1么？
答：不是的播掷。不確定的审编。
問：并查集是什么？
答：并查集是在做基本數(shù)據(jù)結(jié)構(gòu)歧匈，總會要用的一個東西垒酬。
比如往往做最小生成樹，如Kruskal算法
附圖：
問：異常值怎么判斷件炉？
答：如果一個樣本不是核心對象勘究，并且沒有被其他核心對象密度可達(dá)，即可以判定為異常值妻率。
異常值被參數(shù)半徑：r與鄰域樣本數(shù)量參數(shù)影響乱顾。
如：
有可能需要做后處理。
問：如果2是核心對象宫静，那123是一個簇走净；如果2不是核心對象券时，是不是可以分為兩簇？
答：有可能伏伯，其實(shí)是待定的橘洞。可以通過雙向并查集嘗試说搅。
問：密度的定義是否可以處理多維數(shù)據(jù)炸枣？
答：可以。我們只是定義了ε鄰域弄唧，并沒有定義什么是ε鄰域适肠。
問：m值就是最小的簇元素的個數(shù)么？
答：如果周邊的樣本大于m個候引，則就是核心對象侯养。但是理論上最小的簇元素的個數(shù)就是m個
密度最大值聚類
課堂問答
問：高局部密度距離的兩個密度可以相等么？
答：
問：都小是不是表示邊界澄干？
答：都小逛揩，是噪聲的噪聲。其實(shí)ρ很小麸俘，δ很大的時候辩稽，一般是在邊界上。
舉例說明
通過密度聚類从媚，一定程度上可以看出簇的邊在什么位置逞泄，會給出是否屬于該簇的權(quán)值。通過EM算法静檬，能夠算出到底一個樣本炭懊，(x,y)屬于這個簇的概率
課堂問答
問：多大算大，多大算蟹鏖荨踱侣？
答：這個需要調(diào)參槽奕，如下圖
左下角聚類明顯不合理，因為m值太小覆致，所以需要將ε調(diào)的小一些
或者保持ε值愈涩，但需要將m值調(diào)大
ε比較大望抽，可以將更多的樣本納入到簇里面
反之ε比較小，m值又比較小履婉，有些樣本納入不到簇里面
如果發(fā)現(xiàn)噪聲較多煤篙，可以將ε與m值同時調(diào)大，則噪聲判斷就變得嚴(yán)格了毁腿。
相似度傳遞
通過矩陣計算辑奈，得出的兩個結(jié)論
通過吸引程度與依賴程度苛茂，二者之間在一起形成的相似度
推薦使用所有樣本相似度的中位數(shù)(1.0)，作為初值鸠窗，進(jìn)行迭代妓羊。
但是實(shí)踐發(fā)現(xiàn)使用中位數(shù)不一定好，如果用若干倍可能好一些稍计。
相似度越大躁绸，說明越想做聚類中心
相似度越小，說明越不想做聚類中心
該算法的時間復(fù)雜度太高臣嚣，為n2净刮，不見得合適。
數(shù)據(jù)只能是中小規(guī)模
課堂問答
問：怎么知道參數(shù)調(diào)好了呢硅则？
答：唯一的方案庭瑰，就是噪聲驗證。
問：為什么用歐式距離相反數(shù)抢埋？
答：應(yīng)都是有道理弹灭。用歐式距離倒數(shù)也可以
譜聚類
如果一個矩陣是對稱陣，并且是實(shí)數(shù)組成的揪垄，那么它的特征值一定是實(shí)數(shù)穷吮。
如果某個算法是基于譜的，往往就是求特征值或者特征向量饥努。
譜聚類捡鱼，即通過對樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進(jìn)行聚類
拉普拉斯矩陣(Lnxn) = 相似度的對角陣(D) - 相似度的對稱陣(W)
是從小到大排
L = 特征向量x特征值
如圖，對K維數(shù)據(jù)做聚類酷愧，可以選擇K-Means算法驾诈，喂給K維的K均值聚類，則最終結(jié)果就是我們想要的譜聚類的結(jié)果溶浴。
課堂問答
問：DW是什么乍迄？
答：D是我們的度矩陣，W是我們的權(quán)值矩陣士败，任何兩個樣本求相似度
問：不是從小到大么闯两？
答：是從小到大排列
問：奇異值分解？
答：確實(shí)非常像奇異值分解谅将，也像PCA（主成分分析）漾狼。
如圖，可以說明如何從n維降維到k維
問：前k大饥臂，這個k個維度選多少合適呢逊躁？
答：如果選擇性別，則分為男性隅熙，女性稽煤，未知核芽，三個即可。
如果選擇年齡段念脯，就麻煩很多狞洋。
在譜聚類中有從小到大排列的n個樣本，記為：
λ1绿店，λ2吉懊，...，λn
則δi = λi+1 - λi假勿，則能算出：
δ1借嗽，δ2， ...转培，δn-1
這n個值恶导，誰大，我們就認(rèn)為其后者-前者差值最大浸须，大的位置上惨寿，前面的i個應(yīng)該是一個部分，后面則是另外一部分删窒。則將k取i的值即可
問：W-D的理論基礎(chǔ)裂垦？
答：譜聚類應(yīng)該是切割圖推導(dǎo)的一個結(jié)論。
如圖肌索，對權(quán)值進(jìn)行簇的劃分蕉拢，需要使得樣本被切斷，且兩個簇的樣本個數(shù)不要差別太大诚亚。
左邊記為A晕换，右邊記為A'，則左邊簇的邊記為i站宗，右邊簇的邊記為j闸准。
對于Wij/|A| + Wij/|A'|，使得分割結(jié)果不會過分差異過大份乒。
如此繼續(xù)推恕汇，得到L = D - W
可以繼續(xù)推論：
D-1·L = D-1 (D - W) = I - D-1·W
此時是從小到大排
問：K_means和譜聚類要給k值，DBSCAN和密度聚類不需要是么或辖？
答：是的
額外講解
切割圖是了解譜聚類的一把鑰匙。
這三個拉普拉斯矩陣枣接，使用最多的是隨機(jī)游走拉普拉斯矩陣颂暇。
下圖是通過譜聚類實(shí)現(xiàn)的，但是K-Means算法搞不定
說明當(dāng)nxn更改為nxk之后但惶，丟掉一部分樣本耳鸯，降維之后效果反而還更好了湿蛔。從這個意義理解，PCA（主成分分析）干的是這個事情县爬，譜聚類也是干的這個事情阳啥。
課堂問答
問：在拉普拉斯矩陣的特征向量上做k-means，那么有沒有在拉普拉斯矩陣的特征值上做密度聚類的情況呢财喳？
答：本質(zhì)上做k-均值聚類察迟，本來求的拉普拉斯矩陣，應(yīng)該求在整數(shù)域上的解耳高，那才叫做聚類扎瓶。因為一個樣本，屬于且只屬于一個類別泌枪。我們先把整數(shù)域上的結(jié)論概荷，放在實(shí)數(shù)域的情況中去做，然后將它強(qiáng)制轉(zhuǎn)換為整數(shù)域上去做碌燕。
建議先應(yīng)用误证，再去推理論
往往是利用實(shí)際數(shù)據(jù)，求相似度修壕，然后將標(biāo)簽傳遞下去愈捅。
