結合K近鄰的改進密度峰值聚類算法總結
解決的問題：
解決了處理維數(shù)較高奕扣，含噪聲及結構復雜數(shù)據(jù)集時聚類性能不佳等問題。
DPC優(yōu)點：
不僅能夠檢測出樣本集中存在的聚類數(shù)目统阿，而且能夠有效地處理不規(guī)則形狀的簇以及異常樣本缭贡。
DPC缺點：
（1）對于大小不同的數(shù)據(jù)集强品，采用的局部密度計算方式不同，這無形中降低了算法的靈活性塔嬉；
（2）對剩余點的分配策略易造成誤差傳播?
隱患：
對于分布稀疏的數(shù)據(jù)玩徊，ρ?-?δ?決策圖難以確定聚類中心〗骶浚可以用γ?=?ρ?×?δ?決策圖來代替恩袱。
改進的點：
改進點1:密度計算方式的改進
由距離?δ?定義可知，δ?值的大小與密度?ρ?也密切相關胶哲，故?ρ?對于聚類中心的選取至關重要畔塔。由于?DPC?算法的密度計算方法不一致且深受截斷距離?dc?影響，其不能夠保證與當前點距離小于?dc?的點的數(shù)目鸯屿，故有不少成果對該算法中的密度公式進行了改進?所以首先改進密度公式：
相當?shù)陀诎裠c換掉了澈吨，換成了K，盡管K相對有更容易確定些寄摆，但面對類?間?樣?本?數(shù)?不?均?衡?以?及?疏?密?度?不?一?的?數(shù)?據(jù)?谅辣，使?用γ?=?ρ?×?δ?方式選取聚類中心時，類中心點與其他點的區(qū)分度并不高?
為了解決這一問題婶恼，從數(shù)據(jù)整體分布出發(fā)屈藐，引入了相似性調(diào)節(jié)系數(shù)榔组，給出了一種帶有相似性系數(shù)的高斯核函數(shù)來計算局部密度。
其中联逻，σ?取數(shù)據(jù)量的2%搓扯，r(人工給，仍然存在隱患)?為相似性系數(shù)包归，表示密度函數(shù)與數(shù)據(jù)點間相似度的關系程度锨推，該值越大，距離點?xi越近的點對其密度?ρi?的貢獻權重越大公壤。
改進點2：分配方式的改進
引入核心點的概念：
由于聚類中心往往出現(xiàn)在高密度區(qū)域换可，故將各聚類中心某鄰域內(nèi)的點看作核心點，而將其他點看作非核心點厦幅。
核心點的獲取方法：
1沾鳄，先求出簇中心
2，將剩下的點分配到距離其最近的聚類中心所在的類中
3确憨，計算類中所有點到簇中心的距離译荞，求出平均距離。
4休弃，若點在平均距離之內(nèi)吞歼，叫做核心點。?
分配剩余點（非核心點）：
兩種方式：（全局搜索策略和統(tǒng)計學習分配策略）
全局搜索策略：
以核心點的中心塔猾，不斷搜索未分配KNN點篙骡，并將其分配到核心點所在的簇中。
統(tǒng)計學習分配策略：
通過學習每個剩余點被分配的至各個簇的概率來將其歸類丈甸。
注：每點的歸屬由其KNN分布信息決定糯俗，若?xi?的KNN（KNNi）中屬于某個簇的點越多且與?xi?的距離越近，則兩點之間相似度越大睦擂，此時xi?被分配到這個類的概率也越大叶骨。?
論文中算法步驟：
輸入：數(shù)據(jù)集?X?，相似性系數(shù)?r?祈匙，最近鄰個數(shù)?K?。
輸出：類標簽?labels?天揖。
步驟1?計算每點的?δ?與?ρ?（新的方式）值夺欲。
步驟2?通過決策圖獲取聚類中心。
步驟3?提取核心點今膊，并采用全局搜索分配策略將待分類點歸類：
（1）將核心點集合?Xcore?置入隊列?Q?些阅。
（2）取隊列頭?xa?，并將之從?Q?中刪除斑唬，然后查找其K?個最近鄰?KNNa?市埋。
（3）若?x′?∈?KNNa?未被分配黎泣，則將?x′?分配到?xa?所在的類中，并將?x′?添加至?Q?尾部缤谎；否則轉（2）抒倚。
（4）若?Q?=???，終止該策略坷澡。
步驟4?采用統(tǒng)計學習策略分配剩余?k?個點：
（1）依式（9）和（10）計算每點的?Pim(i?=?1,2,…,k)?托呕，并將該值存至矩陣?P?k?×?M，同時將?max(Pim)?的值以及類別號?m?分別存至向量?MP?和?MI??
（2）若?MP?中有非零值频敛，則將?Pom?值最大的點?xo?歸入?MI(o)?所表示的類中项郊，轉（3）；否則終止該策略斟赚。
（3）更新?P着降、MP、MI?拗军，令?MP(o)?=?0?任洞。對于未分配點xp?∈?KNNo?，更新?P[p][m]?食绿、MP(p)?及?MI(p)?侈咕。
（4）若?MP?中所有元素均為0，則終止器紧；否則轉（3）耀销。
步驟5?仍未被處理的點可看作噪聲點，并將之歸入到其最近鄰所在的類中?
