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