【正文】 些被開發(fā)出來的應用程序能在 Windows 下運行， MFC 是微軟對 API 函數(shù)的專用C++封裝，這種結 合一方面讓用戶使用微軟的專業(yè) C++ SDK 來進行 Windows 下應用程序的開發(fā)變得容易，因為 MFC 是對 API 的封裝，微軟做了大量的工作，隱藏沈陽航空航天大學畢業(yè)設計（論文） 14 了很多程序開發(fā)人員在 Windows 下用 C++ amp。該類庫提供一組通用的可重用的類庫供開發(fā)人員使用。 MFC，微軟基礎類 （ Microsoft Foundation Classes） ，同 VCL 類似，是一種Application Framework，隨微軟 Visual C++ 開發(fā)工具發(fā) 布。這一階段 C++語言基本上是傳統(tǒng)類型上的面向對象語言，并且憑借著接近 C 語言的效率，在工業(yè)界使用的開發(fā)語言中占據(jù)了相當大份額； 第二階段從 1995 年到 2021 年，這一階段由于標準模板庫 （ STL） 和后來的 Boost等程序庫的出現(xiàn)，泛型程序設計在 C++中占據(jù)了越來越 多的比重性。 NxmNiik??? 1 () 其中的 mk代表第 k個簇的簇中心， N 代表第 k 個簇中數(shù)據(jù)對象的個數(shù)。這個過程反復進行直至平方誤差準則最小。 算法的輸出：使得平方誤差準則最小的 k個簇。為了達到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。 關鍵技術 本系統(tǒng)是由 C++和 MFC 技術在 Microsoft Visual Studio 環(huán)境下開發(fā)完成的，下面將分別予以介紹。 開 始輸 入 聚 類 個 數(shù) k , n初 始 化 k 個 聚 類中 心分 配 各 個 數(shù) 據(jù) 對 象 到距 離 最 近 的 類 中輸 出 聚 類 結 果重 新 計 算 各 個 聚 類 的中 心是 否 收 斂結 束是否 圖 Kmeans算法流程圖 沈陽航空航天大學畢業(yè)設計（論文） 12 Kmeans 算法優(yōu)點是可以處理大數(shù)據(jù)集， Kmeans 算法是相對可伸縮的和高效率的，因為它的計算復雜度為 O(nkt)，其中 n為對象個數(shù)， k 為聚類個數(shù)， t 為迭代次數(shù)，通常有 r≦ n， k≦ n，因此它的復雜度通常也用 O(n)表示。一般都采用均方差作為標準測度函數(shù)，具體定義如下： 21 11? ?? ? ?? ki cp mpE () 其中 E 為數(shù)據(jù)庫中所有對象的均方差之和； p 為代表對象的空間中的一個點；m1為聚類 c1的均值 （ p 和 m1均是多維的 ） 。 然后再計算每個 新聚類的聚類中心 （ 該聚類中所有對象的均值 ） 。 (5)輸出聚類結果。 (3)所有對象分配完成后，重新計算 k個聚類的中心。 (1)從 n個數(shù)據(jù)對象中任意選取 k個對象作為初始的聚類中心。 Kmeans 算法的核心思想是把 n個數(shù)據(jù)對象劃分為 k個聚類，使每個聚類中的數(shù)據(jù)點到該聚類中 心的平方和最小，算法處理過程： 輸入：聚類個數(shù) k，包含 n個數(shù)據(jù)對象的數(shù)據(jù)集。下面重點介紹 Kmeans 算法的運算過程。 沈陽航空航天大學畢業(yè)設計（論文） 10 3 關鍵問題及分 析 研究設計中要解決的問題 本系統(tǒng)主要是根據(jù) Kmeans 算法的基本思想，設計實現(xiàn)一個基于 Kmeans 算法下的平面點集聚類系統(tǒng)，并通過系統(tǒng)界面輸入和輸出結果 。 以上是理論方面的目標，在實踐方面要做到編碼較優(yōu)，運行程序耗時較短，占內存較少。 設計目標 基于 Kmeans 算法的平面點集聚類系統(tǒng)是對已知的多個平面點根據(jù)用戶對聚類中心的數(shù)量設置后通過 Kmeans 聚類算法的分析后得出相應結果。 樣品之間的距離有不同的定義方法，類與類之間也同樣有不同的距離的定義方法，這樣就產生了不同的層次聚類方法。 2. 層次聚類法 層次聚類法也稱系統(tǒng)聚類法，是目前實際工作中用得最多的一類算法。 CLARANS方法的復雜度是 O(N2)。 CLARANS 方法的思想是：任意從 k 個中心點中取出一個點，從 N－ k 中任意取一個點去替換它，如果替換成功則重新開始。 CLARA 方法結果的優(yōu)劣依賴于采樣方法。比較 5 組的平方 誤差，選取最小的作為輸出結果。 CLARA(Clustering LARge Application)方法：是 PAM 方法的增強版，專門用于處理大量數(shù)據(jù)。 PAM 方法對于小 數(shù)據(jù)庫處理能得到很好的結果，但是它的計算代價非常高。 PAM 方法首先隨機選擇 k 個對象作為簇的中心，對于每一個中心點 O[j]， PAM 方法試圖用所有 N－ k個非中心點替換它。 Kmeans 算法后面我們會重點介紹。它根據(jù)標準統(tǒng)計方法并考慮到噪聲或異常數(shù)據(jù) ， 可以自動沈陽航空航天大學畢業(yè)設計（論文） 8 確定聚類個數(shù) ； 因而它可以產生很多的聚類方法。 STING 就是一個典型的基于網格的方法 ； (5)基于模型的方法。基于網格方法將對象空間劃分為有限數(shù)目的單元以形成網格結構。 DBSCAN 是一個有代表性的基于密度的方法。將循環(huán)再定位與層次方法結合起來使用常常是有效的 ， 如 BIRCH 和 CURE， 就是基于這種組合方法設計的 ； (3)基于密度的方法。該方法就是通過分解所給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。其中每個子集均代表一個聚類 ( k=n )。 大體上 ， 聚類算法可以劃分為如下幾類 ： (1)劃分方法。聚類分析被廣泛研究了許多年。 聚類方法分析 聚類分析是直接比較各事物之間的性質 ， 將性質相近的歸為一類 ， 將性質差別較大的歸入不同的類。馬氏距離是明氏距離的改進，它對于一切線性變換是不變的，克服了明氏距離受量綱影響的缺點；馬氏距離也部分克服了多重相關性。本系統(tǒng)所應用的距離算法是歐氏距離。 1. 明氏 （ Minkowski） 距離 qqi iiqYXYX1}{),(D ? ?? () 當 q 取 1， 2， ∞。通常 kn 且 tn； (3) 當結果簇是密集的，而簇與簇之間的區(qū)別明顯時，它的效果較好 。 Kmeans 的 優(yōu)點 K means 算法有 三個優(yōu)點 ： (1) 是解決聚類問題的一種經典算法，簡單、快捷 ； (2) 對處理大數(shù)據(jù)集，該算法是相對可伸縮和 高效率的 。算法采用迭代更新的方法，通過判定給定的聚類目標函數(shù)，每一次迭代過程都向目標函數(shù)值減少的方向進行。但是這些算法都存在著不足， 所以就存在如何選擇 參數(shù)的問題，不適當?shù)倪x擇將會大大影響算法的結果。因此，對聚類的要求也越來越高，提出準確且又高效的聚類算法刻不容緩。其結果就是一個個由數(shù)據(jù)對象組成的簇，每個簇內的對象之間具有很高的相似性， 而簇間的對象則很不相似。因此，應用目標如何影響聚類方法的選擇也是一項重要的研究課題。有些聚類算法對于這樣的數(shù)據(jù)敏感，將會導致質量較低的聚類結果 ； (8)基于約束的聚類：在實際 應用中有可能需要在各種約束條件下進行聚類。通常最多在三維的情況下能夠很好地判斷聚類的質量。研究和開發(fā)對數(shù)據(jù)輸入順序不敏感的算法具有重要的意義 ； (6)高維性：一個數(shù)據(jù)庫可能含有若干維或者屬性。要求入工輸入參數(shù)不但加重了用戶的負擔，而且也使聚類質量難以控制 ； 沈陽航空航天大學畢業(yè)設計（論文） 5 (5)對于輸入記錄順序不敏感：一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的。但一個簇可能是任意形狀的，提出能發(fā)現(xiàn)任意形狀簇的算法非常重要 ； (4)用于決定輸入參數(shù)的領域知識最小化：在聚類分析中，許多聚類算法要求用戶輸入一定的參數(shù)，如希望簇的數(shù)目。在概念聚類中，一組對象只有當它們可以被一個概念描述時才形成一個簇，這不同于基于幾何距離度量相似度的傳統(tǒng)聚類。與分類不同，聚類和無指導學習不依賴預先定義的類和帶類標號的訓練實例?；?K 均值、 kmedoids(k中心點 )和其他一些方法的聚類分析工具已經被加入到許多統(tǒng)計分析軟件包或系統(tǒng)中。 沈陽航空航天大學畢業(yè)設計（論文） 3 本文目的 本文所研究的 Kmeans聚類技術是聚類算法中劃分方法里面應用最廣泛的一種方案，通過對 Kmeans 聚類算法的理解應用，體會其 優(yōu)點和缺點， 并將其進行系統(tǒng)實現(xiàn)。 系統(tǒng)設 計要求 本系統(tǒng)主要是通過對 Kmeans 算法的理解，實現(xiàn)利用 Kmeans 聚類技術對平面點集進行聚類 。與其他數(shù)據(jù)挖掘方法不同，在進行聚類分析前用戶一般并不知道數(shù)據(jù)集的特征。聚類分析在客戶分類、基因識別、文本分類、空間數(shù)據(jù)處理、衛(wèi)星照片分析、醫(yī)療圖像自動檢測等領域有著廣泛的應用，而其本身的研究也是一個蓬勃發(fā)展的領域，數(shù)據(jù)挖掘、統(tǒng)計學、機器學習、空間數(shù)據(jù)庫技術、生物學和市場學的發(fā)展推動著聚類分析研究的進展，使它已成為數(shù)據(jù)挖掘研究中的一個熱點，在市場分析中，通過聚類分析能幫助決策者識別不同特征的客戶群以及各客 戶群的行為特征在生物工程研究中，聚類分析能夠用于推導動植物的分類，按照功能對基因進行劃分并獲取種群中的固有結構特征在非關系數(shù)據(jù)庫領域如空間數(shù)據(jù)庫領域，聚類分析能夠識別具有相同地理特征的區(qū)域以及該區(qū)域的環(huán)境和人的特征在信息檢索領域，聚類分析能夠對文檔進行分類，提高檢索效率。 聚類是數(shù)據(jù)挖掘技術研究中的重要技術的一種，能有效的通過分析數(shù)據(jù)并從中發(fā)現(xiàn)有用的信息。因此，數(shù)據(jù)挖掘是一門交叉學科，涉及人工智能技術、統(tǒng)計技術與數(shù)據(jù)庫技術等多種技術。挖掘出的知識可以被用于信息管理。原始數(shù)據(jù)可以是結構化的，如關系數(shù)據(jù)庫中的數(shù)據(jù)，也可以是半結構化的 ，如文本、圖形、圖像數(shù)據(jù)，甚至是分布在網絡上的異構型數(shù)據(jù)。 數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。 由于數(shù)據(jù)庫中收集了大量的數(shù)據(jù)，聚類分析已經成為數(shù)據(jù)挖掘領域的重要技術之一 ，本文中介紹的 Kmeans 算法就是聚類分析中應用最廣泛的一種聚類算法 。 目前是在大量的數(shù)據(jù)中發(fā)現(xiàn)人們感興趣的知識 。 Kmeans 沈陽航空航天大學畢業(yè)設計（論文） III 目 錄 1 緒論 .................................................................................................................................... 1 研究意義及背景 ......................................................................................................... 1 系統(tǒng)設計要求 ............................................................................................................. 2 本文目的 ..................................................................................................................... 3 2 研究現(xiàn)狀及設計目標 ........................................................................................................ 4 國內外相關研究現(xiàn)狀 ...........................................................................................