SCMDFC算法研究與應用

SCMDFO算法研究與應用趙雙柱(蘭州文理學(xué)院電子信息工程學(xué)院甘肅730000)【摘要】針對SCMD算法存在的兩大不足提出了改進(jìn),改進(jìn)的半監督聚類(lèi)算法在原算法的基礎上添加對兩種問(wèn)題的處理,問(wèn)題一的解決方法是查找可能會(huì )丟失的簇,添加Es,以解決先驗約束不充分時(shí)不能檢測到所有的簇;問(wèn)題二的解決方法是分配邊界簇,以解決簇內多密度問(wèn)題。實(shí)驗證明 SCMDFC算法在處理多密度數據集時(shí)具有良妤的聚類(lèi)質(zhì)量?！娟P(guān)鍵詞】SCMD; SCMDFC;多密度數據集中圖分類(lèi)號:TP311.13;TP39141文獻標識碼:A文章編號:1009-6833(2014)03-085-02Research and application of SCMDFC algorithmAbstract: At proposing improvements of the two existing deficiencies of SCMD algorithm Improved semi-supervised clusteringalgorithm adds processing of two kinds problem based on the original algorithm Solution of the first problem is in search of the clusterthat can be lost and adding the Eps in order to solve the problem of hardly fully detecting all the cluster in the condition of insufficiencyof a priori constraint Solution of the second problem is to allocate boundaries to solve the problem of cluster-headsmultidimensional Experiment proofs that SCMDFC algorithm has better clustering quality in dealing with a multidimensional data setKeywords: SCMD: SCMDFC; multidimensional data se0引言類(lèi)算法 SCMDFC。該算法的主要思想是:在原算法的基礎上添DBSCAN算法[是聚類(lèi)分析中最經(jīng)典的基于密度的聚類(lèi)加對這兩種問(wèn)題的處理;問(wèn)題一的解決方法是:充分利用給定分析算法,但算法存在一些問(wèn)題:聚類(lèi)質(zhì)量對參數敏感;不能的先驗知識,從約束條件集合中挖掘與可能會(huì )被丟失的簇的相處理多密度數據集。針對 DBSCAN缺點(diǎn),學(xué)者們提出了改進(jìn)算關(guān)信息,從中提取其密度信息,從而查找出所有的簇。問(wèn)題法,如 GDBSCAN算法2], KNNCLUST算法,這些算法在執的解決方法是:簇內密度不均勻時(shí),該簇會(huì )被聚為多個(gè)子簇行過(guò)程中不能獲得任何關(guān)于數據項的類(lèi)屬信息,因而通常被看但在這些子簇中,有一個(gè)較大的簇是原來(lái)簇的主體部分,通過(guò)作是一種無(wú)監督學(xué)習。定的再分配準則將周?chē)男〉淖哟睾喜⒌捷^大的簇中,從而1半監督聚類(lèi)算法ScMD獲得自然的簇結構。1.1SCMD算法概述2.2算法詳細描迷半監督聚類(lèi)算法 SCMDI3]是 Yongqiang Yu等人針對多密度具體來(lái)說(shuō), SCMDFC算法主要增添了兩種方法來(lái)彌補數據集提出的。算法中的先驗信息以成對約束( must-link和SCMD算法的不足cannot-link)形式給出。算法中涉及到兩個(gè)定義:k最近鄰距離(1)查找可能會(huì )丟失的簇,添加Fps和k最近鄰列表,分別用 P-Kdistance和 P-Kneighbor表示由SCMD算法可知,如果一個(gè)簇中不包含有提供的SCMD算法主要包括三部分內容:首先根據 must-link集計 must-link約束,則這個(gè)簇可能不會(huì )出現在聚類(lèi)結果中,因為它算出參考Eps列表;然后根據 cannot-link條件從參考Eps列表的Eps沒(méi)有被計算出來(lái)所以本文試圖添加它的EpS到參考Eps中選擇不同密度分布的代表Eps;最后,以這些代表Eps為參列表中來(lái)解決這個(gè)問(wèn)題,關(guān)鍵是如何查找這樣的簇。這里,假數的多階段 DBSCAN算法運行于數據集,得到最終聚類(lèi)結果。定這個(gè)簇雖然不包含 must-link約束,但是包含 cannot-link約束12SCMD算法存在的缺點(diǎn)中的點(diǎn)。根據約束的傳遞性,(A,B)屬于must-link集表明數SCMD算法在一些數據集上確實(shí)有著(zhù)良好的性能,但是仍據點(diǎn)A和B屬于同一個(gè)簇,(B,C)也是一樣,我們可以得出存在兩個(gè)問(wèn)題數據點(diǎn)A和C屬于同一個(gè)簇。屬于 cannot-link集,表(1)先驗約束不充分時(shí)不能檢測到所有的簇明數據點(diǎn)A和B不可能在同一個(gè)簇中。如果(A,C)是一個(gè)SCMD算法在聚類(lèi)過(guò)程中用到的所有Eps都是從 must-link must-link約束,則數據點(diǎn)B和C也不可能在同一個(gè)簇中,我約束中計算而來(lái),所以,如果有一個(gè)簇不包含 must-link約束,以從約束集合中得到傳遞閉包,則只包含一個(gè)數據點(diǎn)P的則這個(gè)簇可能不會(huì )出現在最終的聚類(lèi)結果中。尤其是當這個(gè)不閉包就屬于在聚類(lèi)結果中可能會(huì )被丟失的簇,也就是 SCMDFC包含 must-link約束的簇是數據集中最稀疏的簇的時(shí)候,它一定算法要檢測的簇,然后,把 P-Kdistance定義為該簇相應的Eps會(huì )被丟失,而簇中的所有點(diǎn)被分配成噪聲。而實(shí)際情況是,專(zhuān)并將其加入到參考Fps列表中,這樣,簇結構將不會(huì )丟失。家或者用戶(hù)并不總能提供出數據集中所有簇的 must-link約束。(2)分配邊界簇,解決簇內多密度問(wèn)題(2)不能處理簇內多密度數據集定義1:(邊界簇)一個(gè)簇C中的數據點(diǎn)數目小于K時(shí),SCMD算法不能處理簇內密度不均的情況。而實(shí)際存在的這個(gè)簇是邊界簇。即,CκK數據集合中,簇中間密集而邊緣稀疏的情況又是很常見(jiàn)的,這為什么簇內數據點(diǎn)數目小于k的簇就是邊界簇呢?它不也是一種多密度表現形式。對于簇之間密度不同的數據集定就位于某個(gè)較大的簇的邊界,也許它是遠離其他簇的一個(gè)獨SCMD算法有良好的性能,因為它能夠計算不同密度的不同立的簇呢?本算法中是不可能出現這種情況。一個(gè)簇必然含有Eps。而同理,對于一個(gè)密度不均的簇,用SCMD算法可以得個(gè)或多個(gè)核心點(diǎn),因為簇是由核心點(diǎn)根據直接密度可達的規到兩個(gè)或多個(gè)Eps,這樣這個(gè)簇會(huì )被分割成幾個(gè)小的子簇則擴展來(lái)的中國煤化工 Minpts(本算法中2基于極少約束的多密度半監督聚類(lèi)算法 SCMDFC是k)個(gè)數捭則它的核心點(diǎn)不21算法主要思想可能有kCNMH小于k。所以該簇針對SCMD算法的不足,本文提出了一種改進(jìn)的半監督聚中沒(méi)有核心點(diǎn)。反證證得簇成員數目小于k的簇不是一個(gè)獨立20144國安度與畫(huà)用技術(shù)·應用的簇,而是位于某個(gè)較大的簇的邊界。中的數據被分配成了噪聲,如圖2所示,而算法 SCMDFC仍能邊界簇形成的原因是真實(shí)世界中的數據集是多密度的,簇精確地發(fā)現四個(gè)簇,如圖2所示。的密度不均勻,且通常是中間密度高邊界密度低。SCMD算法(2)簇內多密度情況的第三步,EpS值按升序排序,當較小的Eps作為參數用于擴數據集Data2包含1938個(gè)數據。該數據集具有三個(gè)自然的展簇時(shí),某個(gè)簇中間絕大多數點(diǎn)被分配為同一個(gè)簇標簽,而周簇結構且包含噪聲,每個(gè)簇中的數據都是高斯分布的,也就是說(shuō)簇中心密度高邊緣密度低。設置K=20,實(shí)驗結果顯示應用前被分配為噪聲的一個(gè)或多邊界點(diǎn)變成核心點(diǎn)開(kāi)始進(jìn)行簇擴SCMD算法聚類(lèi)三個(gè)簇中的大部分點(diǎn)都被正確分配,但簇邊界展,但這些要擴展的點(diǎn)之前已經(jīng)被標記,所以就形成了成員數的點(diǎn)被聚成了一些小的簇。改進(jìn)的算法可以有效地發(fā)現三個(gè)完目小于k的邊界簇整的簇,并正確的識別噪聲邊界簇就是 SCMDFC算法所要查找的需要再分配的小的3結論子簇。通過(guò)定義可以檢測邊界簇。查找到邊界簇后,算法把邊本文提出的 SCMDFC算法充分挖掘成對約束集中所包含界簇分別分配給距離它們相對較近的較大的簇。的信息,在 must-link集不充分的條件下,仍能完整査找到所有2.3實(shí)驗結果及分析的簇結構,而且通過(guò)一定的再分配準則解決簇內多密度問(wèn)題下面通過(guò)SCMD算法與改進(jìn)算法 SCMDFC的實(shí)驗對比,但也存在不足,在 must-link和 cannot-link約束均不充分的條件來(lái)分析 SCMDFC算法的優(yōu)越性。我們選擇了兩個(gè)數據集作為實(shí)下,不能查找到全部的簇結構。在今后的研究工作中,希望能驗數據集,均為多密度數據集,且含有噪聲。實(shí)驗結果中,不有進(jìn)一步的改進(jìn)。同的顏色結合不同的形狀代表不同的簇,其中黑色圓點(diǎn)代表噪參考文獻(1)成對約束( must-link)不充分情況[1]Martin Ester, Hans-Peter Kriegel, Jorg Sander, et al. ADensity-Based Algorithm for Discovering Clusters in Large SpatialDatabases with Noise[C]. In Proceedings of andInternationalConference on Knowledge Discovery and Data Mining( KDD深■■各96)1996:226-231[2Jorg Sander, Martin Ester, Hans-Peter Kriegel,etal Density-Based Clustering in Spatial Databases: The AlgorithmGDBSCAN and Its Applications[l Data Mining and Knowledge圖1SCMD算法運行于Data1圖2改進(jìn)的算法運行于 DatalDiscovery.1998,2(2):169-194數據集 Datal(如圖1和圖2所示),包含1707個(gè)數據,[3 JYang-QiangYu, Tian-QiangHuang Gong-De Guo,et具有三種密度分布、四個(gè)簇結構,且包含噪聲。其中兩個(gè)方形al Semi-supervised clustering algorithm for multi-density and的簇具有相同的密度分布,“∞”形的簇是最稀疏的。設置k=6complex shape dataset[C]. In Chinese Conference on Pattem如果 must-link約束充分,即每種密度分布的簇中都至少包含Recognition(CCPR08)2008:1-6個(gè) must-link約束,則SCMD算法和 SCMDFC算法均能有效作者簡(jiǎn)介:地發(fā)現簇結構。然而,當“∞形的簇中的 must-link約束沒(méi)有提雙柱(1972—),女,甘肅古浪,蘭州文理學(xué)院電子信息工程供時(shí),實(shí)驗結果顯示SCMD算法只能找到三個(gè)簇,“∞”形的簇學(xué)院講師,從事計算機教學(xué)。(上接第84頁(yè))同樣的個(gè)人計算機的處理能力也越來(lái)越出眾,哪怕現在一個(gè)小3.2P2P下載小的手機都比前幾年的PC處理速度要快很多,我們只需要很早期的下載技術(shù)不夠成熟的時(shí)候,人們只能從固定服務(wù)器短的時(shí)間就可以看到網(wǎng)絡(luò )帶給我們更多的便利。另外,雖然計載自己想要的東西,隨著(zhù)P2P技術(shù)的發(fā)展,實(shí)現了資源高度算機遠程網(wǎng)絡(luò )通信技術(shù)能夠帶給我們極大的便利,但是我們不共享,也減輕了服務(wù)器的負載能忽略計算機網(wǎng)絡(luò )安全方面的問(wèn)題,因為網(wǎng)絡(luò )通信技術(shù)已經(jīng)與3、3流媒體技術(shù)我們的生活息息相關(guān),倘若有人利用網(wǎng)絡(luò )漏洞,就會(huì )給我們的早期的視頻保存在服務(wù)器,人們只能通過(guò)下載到本機觀(guān)看,生活造成很大的麻煩,網(wǎng)絡(luò )通信改變生活,技術(shù)拯救世界?，F在隨著(zhù)流媒體技術(shù)的成熟,實(shí)現了在線(xiàn)看高清電影,可以邊參考文獻:下載邊看,不用等整整一部電影下載完畢再看。]李詢(xún)濤計算機遠程網(wǎng)絡(luò )通訊技術(shù)的研究計算機光盤(pán)軟件34電子公告板(BBS)與應用,2013(11)人們在網(wǎng)上公開(kāi)的發(fā)表自己言論,表達自己的看法,早期比凹2]周亞峰計算機遠程網(wǎng)絡(luò )技術(shù)探析計算機光盤(pán)軟件與應用,較有名的有貓撲、天涯等等,現在比較流行的就是百度貼吧了。2013(07)953.5博客、微博3]呂悅松計算機遠程網(wǎng)絡(luò )通訊技術(shù)在實(shí)際生活中的應用電實(shí)時(shí)發(fā)表自己的狀態(tài),關(guān)注自己朋友的信息子制作,2013,(05)36網(wǎng)絡(luò )游戲[4]周山計算機遠程網(wǎng)絡(luò )通訊技術(shù)在實(shí)際生活中的應用硅谷,早期的網(wǎng)絡(luò )游戲比較單一,玩起來(lái)需要打字輸入命令,沒(méi)2013(11)有圖形化界面,隨著(zhù)3D技術(shù)以及網(wǎng)絡(luò )技術(shù)的發(fā)展,人們實(shí)現作者簡(jiǎn)介:了大型3 DMMORPG網(wǎng)絡(luò )游戲,豐富了業(yè)余生活。俞星磊(1984—),男,江蘇太倉,本科,助理工程師,研究方4總結向:信息管理與信息技術(shù)。通過(guò)本文的介紹,相信讀者可以對現階段網(wǎng)絡(luò )技術(shù)的應用龐燕萍(194中國煤化工工程師,研究方有了一個(gè)初步的認識。其實(shí),網(wǎng)絡(luò )通信技術(shù)發(fā)展的速度非?？煜?計算機科學(xué)HCNMHG86丹敵真與用2014