吉首大學(xué)大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性實驗計劃項目申請書

1、附件1：吉 首 大 學(xué)大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性實驗計劃項目申 請 書學(xué) 院 名 稱 數(shù)學(xué)與電腦科學(xué)學(xué)院 計劃項目名稱 基于密度的聚類算法研究 _計劃項目負(fù)責(zé)人 彭 浩 所 在 專 業(yè) 信息與計算科學(xué) 所 在 年 級 08級 聯(lián) 系 電 話電 子 郵 件 124898764qq 導(dǎo) 師 姓 名 段明秀 _導(dǎo) 師 職 稱 講 師 _填 寫 日 期 2011-4-20 吉首大學(xué)教務(wù)處制填寫說明及注意事項一、申報書逐項認(rèn)真填寫，填寫內(nèi)容必須實事求是，表達(dá)明確嚴(yán)謹(jǐn)?？杖表椧睢盁o”。二、表格中的字體小四號仿宋體，1.5倍行距；需簽字部分由相關(guān)人員以黑色鋼筆或水筆簽名。均用A4

2、紙雙面打印，于左側(cè)裝訂成冊。三、大學(xué)生研究性學(xué)心和創(chuàng)新實驗項目是本科學(xué)生個人或創(chuàng)新團隊在導(dǎo)師指導(dǎo)下，自主進(jìn)行研究性學(xué)習(xí)，自主進(jìn)行實驗方法的設(shè)計、組織設(shè)備和材料、實施實驗、調(diào)查、分析處理數(shù)據(jù)、撰寫總結(jié)報告等工作。四、項目實施原則：參與計劃的學(xué)生要對科學(xué)研究或創(chuàng)造發(fā)明有濃厚的興趣，并在導(dǎo)師指導(dǎo)下完成實驗過程；參與學(xué)生要自主設(shè)計實驗、自主完成實驗、自主管理實驗；注重創(chuàng)新性實驗項目實施過程，強調(diào)項目實施過程中學(xué)生在創(chuàng)新思維和創(chuàng)新實踐方面的收獲。五、參與大學(xué)生創(chuàng)新性實驗項目的學(xué)生不超過5人，項目執(zhí)行時間為1-2年。六、指導(dǎo)老師應(yīng)具有講師以上職稱，每個指導(dǎo)老師指導(dǎo)的項目數(shù)不超過2項。七、計劃項目必須先由導(dǎo)

3、師提出意見、由所在學(xué)院審核后再推薦上報。推薦上報的計劃項目表一式三份均為原件報送教務(wù)處，同時提交電子文檔。項目名稱基于密度的聚類算法研究項目主持人彭浩學(xué)號20084043032班級08信計年級08級Q124898764項目組其他成員學(xué)生性別學(xué)院名稱專業(yè)年級聯(lián)系 合作者簽名楊亞龍男數(shù)學(xué)與電腦科學(xué)學(xué)院信息與計算科學(xué)08勇男數(shù)學(xué)與電腦科學(xué)學(xué)院信息與計算科學(xué)08超林女?dāng)?shù)學(xué)與電腦科學(xué)學(xué)院信息與計算科學(xué)09永勝男數(shù)學(xué)與電腦科學(xué)學(xué)院信息與計算科學(xué)09導(dǎo)教師情況段明秀性別女民族漢出

4、生年月1975.5職稱講師專業(yè)電腦應(yīng)用研究方向數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò) 號-mailDuanmxq126 指導(dǎo)老師簽名一、前期基礎(chǔ)500字以內(nèi) 項目組成員均來自吉首大學(xué)數(shù)學(xué)與電腦科學(xué)學(xué)院的大二、大三的信息與計算科學(xué)專業(yè)，已系統(tǒng)進(jìn)行過數(shù)學(xué)理論方法訓(xùn)練尤其針對數(shù)值計算，信息論，數(shù)學(xué)建模等，曾獲得過校級數(shù)學(xué)建模大賽的三等獎，為設(shè)計高效聚類算法打下了扎實的數(shù)學(xué)基礎(chǔ)。電腦方面，已熟練掌握了C、C+ 、JAVA，matlab(數(shù)學(xué)工具軟件)等語言，并且在數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計、框架構(gòu)造等方面也有一些經(jīng)驗積累，對算法的優(yōu)化與測試具備良好的電腦基礎(chǔ)。項目組成員均具有良好的程序設(shè)計基礎(chǔ)及扎實的數(shù)

5、學(xué)功底，并且對編程及算法研究具有濃厚的興趣。多名成員已通過英語4、6級考試，具備了較強的英語讀寫能力，能夠閱讀相關(guān)的外文文獻(xiàn)。項目指導(dǎo)老師在相關(guān)領(lǐng)域從事了多年的教學(xué)和科研工作，比較全面的掌握了數(shù)據(jù)挖掘領(lǐng)域的相關(guān)文獻(xiàn)和研究現(xiàn)狀，并已經(jīng)在聚類算法領(lǐng)域進(jìn)行了較為深入的研究，取得了一些研究成果。在項目指導(dǎo)老師的積極指導(dǎo)與催促下，項目組成員已閱讀了大量的相關(guān)國內(nèi)外文獻(xiàn)，對聚類算法特別是基于密度的聚類算法有了一定的知識積累，對聚類算法的發(fā)展歷程和最新發(fā)展趨勢有一定了解，對算法的評價標(biāo)準(zhǔn)有了更深刻的認(rèn)識。二、項目立論依據(jù)2000字以內(nèi)1項目研究目的和意義數(shù)據(jù)挖掘是從海量數(shù)據(jù)中以高度精確和高度可靠的手段挖掘和

6、產(chǎn)生新的知識，這些新的知識將為決策者提供有力的科學(xué)決策依據(jù)。數(shù)據(jù)挖掘涉及多學(xué)科技術(shù)，包括數(shù)據(jù)庫技術(shù)、統(tǒng)計學(xué)、機器學(xué)習(xí)、高性能計算、模式識別、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)可視化、信息檢索、圖像與信號處理和空間數(shù)據(jù)分析等。已在醫(yī)學(xué)、電信、零售業(yè)等科學(xué)或商業(yè)領(lǐng)域得到了成功應(yīng)用。聚類分析是數(shù)據(jù)挖掘領(lǐng)域中一個非?；钴S的研究課題，它應(yīng)用于統(tǒng)計學(xué)、機器學(xué)習(xí)、空間數(shù)據(jù)庫、生物學(xué)以及市場營銷等領(lǐng)域，應(yīng)用于各個領(lǐng)域的聚類算法非常多。針對各行業(yè)不同的應(yīng)用，目前己經(jīng)提出了大量的聚類算法。這些算法在速度、效率、可伸縮性、處理能力、準(zhǔn)確度等方面有了不同程度的改良。聚類算法的聚類效果受數(shù)據(jù)集的分布情況影響很大，有的算法只能辨識凸形簇，有

7、的算法不能很好的處理數(shù)據(jù)中的離群點，有的算法的時間效率不能滿足大數(shù)據(jù)集的聚類要求等等，然而，現(xiàn)實中的數(shù)據(jù)集很多并不是凸形分布?；诿芏鹊木垲惙椒ǖ难芯拷鉀Q了這個問題，基于密度的聚類算法通過尋找密度連通區(qū)域來辨識任意形狀的簇。通過密度聚類，人們能夠識別密集的和稀疏的區(qū)域，從而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。在商務(wù)上，密度聚類能幫助市場分析人員從客戶基本信息庫發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群特征。在生物學(xué)上，密度聚類能用于推導(dǎo)植物與動物的分類，對基因進(jìn)行分類，獲得對種群固有結(jié)構(gòu)的認(rèn)識。密度聚類在地球觀測數(shù)據(jù)庫中對相似地區(qū)確實定，汽車保險持有者的分組，以及根據(jù)

8、房屋的類型，價值和地理位置對一個城市中房屋的分組上也可以發(fā)揮作用。但一些經(jīng)典的基于密度的聚類算法存在一些不足，比方時間性能，對于密度分布不均數(shù)據(jù)集聚類效果差等，科研者對這些問題也進(jìn)行了深入的研究，通過一些方法來改善基于密度的聚類算法存在的問題?；诿芏鹊木垲惙椒ㄔ趯嶋H中有廣泛的應(yīng)用，因此，對于基于密度的聚類算法的研究是很有理論和實際意義的。2國內(nèi)外研究現(xiàn)狀基于密度的聚類方法是聚類算法中一項研究重點，該方法是通過度量區(qū)域中所包含的對象數(shù)目來進(jìn)行聚類的，經(jīng)典的基于密度的方法主要有DBSCAN和 OPTIC。1996年，Ester等提出了DBSCAN，該算法具有將高密度的區(qū)域劃分為簇，并可以在帶有“

9、噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇。DBSCAN存在一些不足，科研者以DBSCAN為基礎(chǔ)研究了一系列的改良算法。 J.orgsander， MartinEste以DBSCAN為基礎(chǔ)提出了用于多維空間數(shù)據(jù)庫聚類的基于密度的空間聚類算法GDBSCAN。劉宗田等提出了可以用于大型空間數(shù)據(jù)庫的基于數(shù)據(jù)分區(qū)的并行DBSCAN算法。陳治平、王雷提出了基于密度梯度的聚類算法，通過分析數(shù)據(jù)樣本及其周邊的點密度變化情況，選擇沿密度變化大的方向?qū)ふ也粍狱c，以獲得聚類中心，然后利用邊界點的分布對類進(jìn)行合并。1999年Ankerst等提出了OPTIC聚類排序方法。算法生成代表基于密度的聚類結(jié)構(gòu)的一個參數(shù)化的數(shù)據(jù)庫的

10、排序，通過這種排序包含的信息及參數(shù)設(shè)置可以得到與基于密度聚類相同的聚類結(jié)果。陳燕俐，朱梧橙在DBSCAN和OPITC的基礎(chǔ)上在提出一種簡單有效的基于密度的聚類算法，該算法給出了一種簡單且效率較高的鄰域查詢方法一哈希表法，對整個數(shù)據(jù)集合或部分?jǐn)?shù)據(jù)做網(wǎng)格化處理。3主要參考文獻(xiàn) 1Jiawei Han，Micheline Kamber著范明，孟小峰等譯數(shù)據(jù)挖掘概念與技術(shù)北京：機械工業(yè)出版社，2004.1-262 2Anil K.Jain，Richard C.DubesAlgorithms for Clustering DataPrentice Hall，19881-334 3Pang Ning Ta

11、n，Michael Steinbach，Vipin KumarIntroduction to Data MiningPosts & Telecom Press，2004132-212 4Paolo Giudici著袁方，王煜，王麗娟等譯實用數(shù)據(jù)挖掘 北京：電子工業(yè)出版社，20031-232 5Margaret HDunham著郭崇慧，田鳳占等譯數(shù)據(jù)挖掘教程北京：清華大學(xué)出版社，20041-201 6Mehmed Kantardzic著閃四清，陳茵，程雁等譯數(shù)據(jù)挖掘-概念、模型、方法和算法北京：清華大學(xué)出版社，20031-5 7 C.M. Bishop and M.E. TippingA

12、 Hierarchical Latent Variable Model for Data VisualisationIEEE TPAMI3，1998(20):281-293 8田盛豐，黃厚寬人工智能與知識工程長沙：中國鐵道出版社，1999123 9C. WilliamsA MCMC Approach to Hierarchical Mixture Modelling Advances in NIPS，2000(1):680-686 10 C. FraleyAlgorithms for Model-Based Hierarchical ClusteringSIAM J. Sci. Comput，

13、1998(1)：279-281 11 David PollardStrong Consistency of Kmeans ClusteringAnnals of Statistics，1981(9)：135-140 12劉同明數(shù)據(jù)挖掘技術(shù)及其應(yīng)用長沙：國防工業(yè)出版社，20011-65 13張穎數(shù)據(jù)采掘的研究與應(yīng)用：博士學(xué)位論文北京：中國科學(xué)院計算技術(shù)研究所，1999 14Fayyad UMining Databases：Towards algorithm for konwledge discoveryIEEE Bulletin of the Technical Committee on Dat

14、a Engineering，1998，21(1)：39-48 15Fayyad U，Piatesky Shapiro G，Smyth PThe KDD process for extracting useful knowledge form volumes of dataCommunication of the ACM，1996，39(11)：27-35 16Fayyad U，Piatetsky Shapiro et alFrom data mining to knowledge discovery： An overviewAdvances in Knowledge Discovery and

15、 Data Mining. Menlo Park，CA： AAAI/MIT Press，199634-56 17 陳燕俐，洪龍，金達(dá)文等一種簡單有效的基于密度的聚類分析算法南京郵電學(xué)院學(xué)報，200525(4)：24-29 18 谷淑化，呂維先，馬于濤關(guān)于數(shù)據(jù)挖掘中聚類分析算法的比較現(xiàn)代電腦： 20053：26-29 19 湯效琴，戴汝源數(shù)據(jù)挖掘中聚類分析的技術(shù)方法微電腦信息，200319：3-4 20 黃修丹數(shù)據(jù)挖掘領(lǐng)域中的聚類分析及應(yīng)用閩江學(xué)院學(xué)報，200425：44-47 21 趙法信，王國業(yè)數(shù)據(jù)挖掘中聚類分析算法研究通化師范學(xué)院學(xué)報，200526：11-13 22 ：/三、項目實施方案2

16、500字以內(nèi)1項目研究目標(biāo)、研究內(nèi)容和擬解決的關(guān)鍵問題在各研究成員的興趣驅(qū)動以及指導(dǎo)老師的認(rèn)真耐心指導(dǎo)下，通過對基于密度的聚類算法研究與實現(xiàn)，自主管理自主完成項目的研究，注重在項目的實施過程中對各成員的創(chuàng)新思維培養(yǎng)和對問題的剖析能力進(jìn)行有意識的鍛煉，并期望在對現(xiàn)有算法實現(xiàn)的基礎(chǔ)上，進(jìn)一步對算法進(jìn)行優(yōu)化。研究目標(biāo)：(1)鑒于基于密度的聚類算法中所存在的密度函數(shù)計算效率不高以及對參數(shù)十分敏感兩個問題，進(jìn)行深入的研究與分析，通過改良算法，并對其進(jìn)行優(yōu)化提高密度函數(shù)的計算效率，并實現(xiàn)對參數(shù)的一般化，使算法實現(xiàn)更有效，更可行。(2)選擇一些經(jīng)典實例解析，針對實際問題運用基于密度的聚類算法進(jìn)行解答，用程序

17、流程圖把解題過程表示出來，編程實現(xiàn)，提高分析問題，解決問題的能力。(3)借助各種工具和已經(jīng)寫好的代碼和數(shù)據(jù)結(jié)構(gòu)中所學(xué)的知識，檢驗改良后算法的效率、分析算法的時間復(fù)雜度和空間復(fù)雜度。(4)將基于密度的聚類算法應(yīng)用到具體的應(yīng)用領(lǐng)域。研究內(nèi)容：1聚類分析前對數(shù)據(jù)預(yù)處理方法的研究。2列舉目前常用的基于密度的聚類算法，并對算法進(jìn)行詳細(xì)的描述和分析。指出各算法的適用領(lǐng)域及局限性。3重點研究經(jīng)典的DBSCAN算法、OPTICS算法、DENCLUE算法算法思想、算法缺陷、算法改良、算法實現(xiàn)、算法性能分析并進(jìn)行編程實現(xiàn)。4就其中的某種算法的缺陷進(jìn)行改良。擬解決的關(guān)鍵問題：(1)對基于密度的聚類算法中的經(jīng)典算法分

18、進(jìn)行分析，從而對算法進(jìn)行改良與優(yōu)化，并提出自己的見解與想法。(2)分析算法的時間復(fù)雜度和空間復(fù)雜度。(3)通過對算法的研究與實現(xiàn)，注重在項目的實施過程中對各成員的創(chuàng)新思維和分析解決問題能力的培養(yǎng)。(4)運用基于密度的聚類算法解決實際問題。2擬采取的研究方法、技術(shù)路線、實驗方案及可行性分析 采取理論與實踐相結(jié)合的研究方法。先從理論上對基于密度的聚類算法中的經(jīng)典算法進(jìn)行時間和空間復(fù)雜度分析，并針對某種算法的缺陷，從理論上提出改良方案，算法擬采用c語言實現(xiàn)，并用matlab進(jìn)行仿真,通過比照試驗，從聚類的正確性、精度、算法執(zhí)行時間、參數(shù)設(shè)置、數(shù)據(jù)輸入順序、數(shù)據(jù)及密度等方面對算法進(jìn)行測試、分析、評價。

19、 3本項目的創(chuàng)新之處 (1) 對目前常用的基于密度的聚類算法進(jìn)行比較和分析，比較各種算法的優(yōu)缺點。 (2) 針對現(xiàn)有算法的不足，提出改良方法。 (3) 結(jié)合具體的應(yīng)用環(huán)境，從可行性和執(zhí)行效率角度考察改良算法的實際應(yīng)用價值。4項目研究計劃及預(yù)期進(jìn)展 第一階段：2011年6月2011年8月 全面搜集相關(guān)書籍、文獻(xiàn)資料、網(wǎng)絡(luò)資料數(shù)據(jù)。 學(xué)習(xí)相關(guān)科研知識、科研技能，提高科研基本素質(zhì)。 對已搜集的文獻(xiàn)資料數(shù)據(jù)進(jìn)行匯總、整理與篩選。第二階段：2011年9月2012年2月 根據(jù)基于密度的聚類算法的基本原理，對基于密度的聚類算法進(jìn)行詳細(xì)的描述。并借助各種文獻(xiàn)、材料，以及前輩的總結(jié)與經(jīng)驗，借助我們對基于密度的聚

20、類算法的了解。對基于密度的聚類算法進(jìn)行改良與優(yōu)化，并提出自己的見解。第三階段：2012年2月2012年4月總結(jié)所得的分析結(jié)果，結(jié)合對一些實際問題的分析、解答，把改良的基于密度的聚類算法以偽碼的形式寫出。同時對算法中的數(shù)據(jù)結(jié)構(gòu)、所用函數(shù)進(jìn)行說明，并繪制程序流程圖，隨后分析改良后算法的時間復(fù)雜度和空間復(fù)雜度，并與原算法進(jìn)行比較。最后用Visual C+ 6.0 編程實現(xiàn)該算法。第四階段：2012年5月2012年6月通過做各種比照試驗對基于密度的聚類算法的正確性、精度、參數(shù)設(shè)置、數(shù)據(jù)輸入順序以及數(shù)據(jù)密度等進(jìn)行比照分析，對改良的基于密度的聚類算法進(jìn)行測試、評估。選出最優(yōu)的、可行性法案，并認(rèn)真完成項目論

21、文5項目研究的預(yù)期成果 通過團隊成員的分工合作，艱苦探索，辛勤研究，搜集各種資料，借鑒別人的經(jīng)驗與所得，可到達(dá)以下預(yù)期成果:(1)在省級以上學(xué)術(shù)刊物上公開發(fā)表1-2篇與該課題相關(guān)的學(xué)術(shù)論文；(2)增強項目組成員獨立思考，團結(jié)合作的能力，激發(fā)探究新知的興趣，培養(yǎng)良好的科學(xué)素養(yǎng)。(3)提高團體合作能力，為今后的學(xué)習(xí)和科研項目開發(fā)提供堅實的知識基礎(chǔ)。 4進(jìn)行課題總結(jié)，形成總結(jié)報告。四、項目保障機制800字以內(nèi)1經(jīng)費預(yù)算及經(jīng)費使用計劃經(jīng)費開支項目經(jīng)費預(yù)算萬元用途簡要說明資料費0.3用于購買或復(fù)印一些相關(guān)書籍和文獻(xiàn)學(xué)術(shù)交流費0.4同相關(guān)領(lǐng)域?qū)＜疫M(jìn)行學(xué)術(shù)交流論文版面費0.2發(fā)表項目論文所需的版面費和審稿費存儲設(shè)備0.1購買移動硬盤等設(shè)備存儲程序與論文總計萬元12條件保障實驗室、設(shè)備、場地、設(shè)施等具體情況 學(xué)院及學(xué)校領(lǐng)導(dǎo)十分支持該項目研究，我院將向參與項目的學(xué)生免費提供專業(yè)教室和專業(yè)教學(xué)儀器設(shè)備等。課題組成員都來自吉首