ประเภทของ Partitional Algorithm (อัลกอริทึมแบ่งส่วน)

ประเภทของ Partitional Algorithms

มีสองประเภทของ partitional algorithms:

1. K-means Clustering

K-means clustering เป็น partitioning algorithm ที่ common ที่สุด K-means reassigns แต่ละ data ใน dataset ให้กับ only one ของ new clusters ที่สร้างขึ้น Record/data point กำหนดให้ nearest cluster โดยใช้ measure ของ distance หรือ similarity

ขั้นตอน K-means clustering:

Select K initial cluster centroids c₁, c₂, c₃ ... cₖ
Assign แต่ละ instance x ใน S cluster ที่ centroid ใกล้ x มากที่สุด
สำหรับแต่ละ cluster recompute centroid จาก elements ใน cluster นั้น
Go to (b) จน convergence เสร็จ
Separate objects (data points) เป็น K clusters
Cluster center (centroid) = average ของ all data points ใน cluster
Assign แต่ละ point ให้ cluster ที่ centroid ใกล้ที่สุด (ใช้ distance function)

ค่าเริ่มต้นสำหรับ means กำหนด arbitrary สุ่มหรือใช้ค่าจาก k input items แรก Convergence criterion อาจ base on squared error แต่ไม่จำเป็น ตัวอย่าง algorithm assigned ไป different clusters วิธีหยุดอื่น: fixed number of iterations Max iterations ใส่เพื่อ ensure termination แม้ไม่ converge

Algorithm: K-means

Input: D = {t₁, t₂, ... tₙ} (set of elements), k (number of desired clusters)

Output: K (set of clusters)

K-means algorithm
assign initial values for means m₁, m₂, ... mₖ
repeat
  assign each item tᵢ to the cluster which has the closest mean
  calculate the new mean for each cluster
until convergence criteria are met

2. Nearest Neighbour Algorithm (อัลกอริทึมเพื่อนบ้านใกล้สุด)

Algorithm ที่คล้าย single link technique เรียกว่า nearest neighbour algorithm ด้วย serial algorithm นี้ items ถูกรวมเข้า current clusters ที่ใกล้ที่สุดแบบ iterative Threshold t กำหนดว่า items จะ inserted เข้า existing clusters หรือสร้าง new cluster

Algorithm: Nearest Neighbour

Input: D = {t₁, t₂, ... tₙ} (set of elements), A (Adjacency matrix showing distance between elements)

Output: K (set of clusters)

Nearest neighbour algorithm
K₁ = {t₁}; K = {K₁}; k = 1;
for i = 2 to n do
  find tₘ in some cluster Kₘ in K such that dis{tᵢ, tₘ} is the smallest;
  If dis{tᵢ, tₘ} ≤ t then
    Kₘ = Kₘ ∪ tᵢ
  else
    k = k + 1; Kₖ = {tᵢ}