程式是指為了完成某種計算或控制過程，按指令系統的規定，為計算機寫出的一連串依次執行的步驟(即指令或語句)。在計算機科學中，有很多問題需要進行分類並歸併。分類歸併程式是指對有關問題進行分類並將不同類進行歸併的程式。分類歸併程式有著廣泛套用，例如，在大數據分析中，經常需要對對象或屬性進行分類歸併。
基本介紹
- 中文名：分類歸併程式
- 外文名：sort-merge program
- 學科：計算機
- 定義：問題進行分類並將不同類進行歸併
- 有關術語：程式
- 領域：數據分析、程式設計
簡介,決策樹,哈希表,有關定義,聚類,概述,聚類要求,
簡介
決策樹
決策樹（Decision tree）由一個決策圖和可能的結果（包括資源成本和風險）組成，用來創建到達目標的規劃。決策樹建立並用來輔助決策，是一種特殊的樹結構。決策樹是一個利用像樹一樣的圖形或決策模型的決策支持工具，包括隨機事件結果，資源代價和實用性。它是一個算法顯示的方法。決策樹經常在運籌學中使用，特別是在決策分析中，它幫助確定一個能最可能達到目標的策略。如果在實際中，決策不得不在沒有完備知識的情況下被線上採用，一個決策樹應該平行機率模型作為最佳的選擇模型或線上選擇模型算法。決策樹的另一個使用是作為計算條件機率的描述性手段。分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。
在機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關係。樹中每個節點表示某個對象，而每個分叉路徑則代表某個可能的屬性值，而每個葉節點則對應從根節點到該葉節點所經歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。 數據挖掘中決策樹是一種經常要用到的技術，可以用於分析數據，同樣也可以用來作預測。
從數據產生決策樹的機器學習技術叫做決策樹學習，通俗說就是決策樹。
一個決策樹包含三種類型的節點：
決策節點：通常用矩形框來表示
機會節點：通常用圓圈來表示
終結點：通常用三角形來表示
決策樹學習也是數據挖掘中一個普通的方法。在這裡，每個決策樹都表述了一種樹型結構，它由它的分支來對該類型的對象依靠屬性進行分類。每個決策樹可以依靠對源資料庫的分割進行數據測試。這個過程可以遞歸式的對樹進行修剪。 當不能再進行分割或一個單獨的類可以被套用於某一分支時，遞歸過程就完成了。另外，隨機森林分類器將許多決策樹結合起來以提升分類的正確率。
決策樹同時也可以依靠計算條件機率來構造。
哈希表
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函式叫做散列函式，存放記錄的數組叫做散列表。
給定表M，存在函式f(key)，對任意給定的關鍵字值key，代入函式後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函式f(key)為哈希(Hash) 函式。
有關定義
若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為散列函式，按這個思想建立的表為散列表。
對不同的關鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現象稱為碰撞（英語：Collision）。具有相同函式值的關鍵字對該散列函式來說稱做同義詞。綜上所述，根據散列函式f(k)和處理碰撞的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。
若對於關鍵字集合中的任一個關鍵字，經散列函式映象到地址集合中任何一個地址的機率是相等的，則稱此類散列函式為均勻散列函式（Uniform Hash function），這就是使關鍵字經過散列函式得到一個“隨機的地址”，從而減少碰撞。
聚類
概述
聚類分析（Cluster analysis，）是對於統計數據分析的一門技術，在許多領域受到廣泛套用，包括機器學習，數據挖掘，模式識別，圖像分析以及生物信息。聚類是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離等。聚類（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個度量（Measurement）的向量，或者是多維空間中的一個點。
聚類要求
可伸縮性
許多聚類算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。
我們需要具有高度可伸縮性的聚類算法。
不同屬性
許多算法被設計用來聚類數值類型的數據。但是，套用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。
任意形狀
許多聚類算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的算法是很重要的。
領域最小化
許多聚類算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。
記錄順序
一些聚類算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的算法具有重要的意義。
高維度（high dimensionality）
一個資料庫或者數據倉庫可能包含若干維或者屬性。許多聚類算法擅長處理低維的數據，可能只涉及兩到三維。人類的眼睛在最多三維的情況下能夠很好地判斷聚類的質量。在高維空間中聚類數據對象是非常有挑戰性的，特別是考慮到這樣的數據可能分布非常稀疏，而且高度偏斜。
基於約束
現實世界的套用可能需要在各種約束條件下進行聚類。假設你的工作是在一個城市中為給定數目的自動提款機選擇安放位置，為了作出決定，你可以對住宅區進行聚類，同時考慮如城市的河流和公路網，每個地區的客戶要求等情況。要找到既滿足特定的約束，又具有良好聚類特性的數據分組是一項具有挑戰性的任務。
