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