Có hai loại thuật toán từng phần như sau -
K-means clustering - K-mean clustering là thuật toán phân vùng phổ biến nhất. K-mean chỉ định lại mỗi dữ liệu trong tập dữ liệu cho một trong các cụm mới được hình thành. Một bản ghi hoặc điểm dữ liệu được gán cho cụm gần nhất bằng cách sử dụng thước đo khoảng cách hoặc độ tương tự. Có các bước sau được sử dụng trong phân cụm K-mean:
-
Nó có thể chọn K cụm đầu tiên centroid c 1 , c 2 , c 3 ... c k .
-
Nó có thể gán từng phiên bản x trong cụm S có tâm gần nhất với x.
-
Đối với mỗi cụm, hãy tính toán lại trung tâm của nó dựa trên các phần tử được chứa trong cụm đó.
-
Chuyển đến (b) cho đến khi quá trình hội tụ hoàn tất.
-
Nó có thể tách đối tượng (điểm dữ liệu) thành K cụm.
-
Nó được sử dụng để phân cụm trung tâm (centroid) =điểm trung bình của tất cả các điểm dữ liệu trong cụm.
-
Nó có thể gán từng điểm cho cụm có tâm gần nhất (sử dụng chức năng khoảng cách).
Các giá trị ban đầu cho các phương tiện được gán tùy ý. Chúng có thể được chỉ định ngẫu nhiên hoặc có thể có thể sử dụng các giá trị từ chính k mục đầu vào đầu tiên. Phần tử hội tụ có thể dựa trên sai số bình phương, nhưng chúng không được yêu cầu. Ví dụ, thuật toán được gán cho các cụm khác nhau. Các kỹ thuật kết thúc khác chỉ đơn giản là khóa ở một số lần lặp lại cố định. Có thể bao gồm số lần lặp lại tối đa để đảm bảo mua sắm ngay cả khi không có sự hội tụ.
Thuật toán
Đầu vào
D = {t1t2 ... tn} // Set of elements
k // Number of desired clusters Đầu ra
K // Set of clusters
Thuật toán K-mean -
gán giá trị ban đầu cho phương tiện m 1 m 2 ... m k
lặp lại
gán từng mục cho cụm có giá trị trung bình gần nhất
tính giá trị trung bình mới cho mỗi cụm
cho đến khi các tiêu chí hội tụ được đáp ứng
Thuật toán láng giềng gần nhất - Một thuật toán tương tự như kỹ thuật liên kết đơn được gọi là thuật toán láng giềng gần nhất. Với thuật toán nối tiếp này, các mục được kết hợp lặp đi lặp lại thành các cụm hiện tại gần nhau nhất. Trong thuật toán này, một ngưỡng t có thể xác định xem các mục sẽ được chèn vào các cụm hiện có hoặc nếu một cụm mới được tạo.
Thuật toán
Đầu vào
D = {t1t2 ... tn} // Set of elements
A // Adjacency matrix showing distance between elements Đầu ra
K // Set of clusters
Nearest neighbour algorithm
K1 = {t1};
K = {K1};
k = 1;
for i = 2 to n do
find the tm in some cluster Km in K such that dis {ti, tm} is the smallest;
If dis {ti, tm} $\leqslant$ t then
Km = Km $\cup$ ti
else
k = k + 1;
Kk = {ti}