With the formation, development and deepening of fuzzy set theory, RusPini first proposed the concept of fuzzy division. Based on this, fuzzy clustering theory and method developed rapidly. According to different application, people put forward many fuzzy clustering algorithm, typically with the method based on similarity relation and fuzzy relation, the transitive closure method based on fuzzy equivalence relation, the largest support tree method based on fuzzy graph theory, and based on the data set is convex decomposition method, the relationship between dynamic programming and difficult to identify. However, none of the above methods can be applied to the case of large data volume, and it is difficult to meet the occasions with high real-time requirements, so the practical application is not widespread.
Fuzzy clustering analysis can be roughly divided into three categories according to different clustering processes:
(1) Classification method based on fuzzy relation: including pedigree clustering algorithm (also called system clustering method), clustering algorithm based on equivalence relation, clustering algorithm based on similarity relation and graph theory clustering algorithm, etc. It is an early method, but it is not widely used in practice because it can not be applied to the case of large data volume.
(2) Fuzzy clustering algorithm based on objective function: The clustering analysis is reduced to a constrained nonlinear programming problem, and the optimal fuzzy division and clustering of the data set are obtained by optimizing the solution. This method is simple to design and has a wide range of problems to solve. It can also be transformed into an optimization problem and solved by the nonlinear programming theory of classical mathematics, and is easy to be implemented by computer. Therefore, with the application and development of computer, fuzzy clustering algorithm based on objective function becomes a new research hotspot.
(3) Fuzzy clustering algorithm based on neural network: it is a relatively late emerging algorithm, mainly using competitive learning algorithm to guide the network clustering process.
Before introducing the algorithm, let’s introduce the knowledge of fuzzy sets.
HCM clustering algorithm
First, the concept of membership function is explained. Membership degree function is A function representing the degree to which an object X belongs to set A, usually denoted as μA(x). The range of its independent variable is all objects that may belong to set A(that is, all points in the space where set A resides), and the range of value is [0,1], that is, 0<=μA(x), μA(x)<=1. μA(x)=1 means that x completely belongs to set A, which is equivalent to x∈A in the traditional set concept. A membership function defined in the space X={X} defines A fuzzy set A, or A fuzzy subset A 'defined in the domain X={X}. For a finite number of objects X1, x2... , the xn fuzzy set A 'can be expressed as:Copy the code
FCM algorithm is a popular fuzzy clustering algorithm. The reasons are as follows: First, the fuzzy C-mean functional Jm is still a natural extension of the traditional hard C-mean functional J1; Hard C-mean functional J1 is a widely used clustering criterion, and its theoretical research has been quite perfect, which provides a good condition for the study of Jm. Mathematically, Jm is closely related to the Hilbert space structure of RS (orthogonal projection and mean square approximation theory), so it has a deeper mathematical foundation than other functional functions. Finally, and most importantly, this objective function has not only been successfully applied in many fields, but also a large number of FCM types of fuzzy clustering algorithms based on other prototypes have been proposed based on FCM algorithm: Such as fuzzy C one line (FCL), fuzzy C one side (FCP) and other clustering algorithms, respectively, to realize the linear, hyperplanar structure pattern subset (or clustering) detection.
FCM algorithm is applied to color migration
Qian Xiaoyan et al. applied clustering algorithm to color transfer and proposed an adaptive color transfer algorithm based on image fuzzy color clustering. The algorithm firstly transform, each source image and target image to l alpha beta color space: using the FCM algorithm the source image and the target image is divided into different color characteristics of clustering, then analyzing the characteristic of the image of the color, respectively, calculate the weights of each domain matching, matching weight of each target image, pick up one of the most close to the domain from the source image as the best matching domain; Finally, according to the relationship between the clustering domain of the target image and the matching domain of the source image, the membership factor is introduced, and the weighted average of the processing results of the two domains is obtained to obtain the color migration results. The idea of using FCM to divide image clustering domain is as follows: Suppose the size of image I to be processed is S×H, that is, the number of color clustering color analysis is N, N = S×H, then image I can be expressed as a set, I={p1,p2... , pn}. The image is divided into C class, and the cluster center of each class is V={v1,v2... Vc}, uIK is used to represent the membership degree of pixel PK to the cluster center Vi, and the membership degree matrix U of the image is defined. The specific algorithm is as follows:Copy the codeStep 1: Convert the source image and target image from RGB to L αβ space respectively.
Step 2: Determine the number of clustering domains c of the image to be processed, and then initialize the clustering center. Assuming that the weighted index m=2, the maximum iteration number of processing is set to be 50.
Step 3: When the number of iterations T is less than 50, the membership matrix is calculated according to the initialized clustering center. If pk≠vi, then for all vi (I =1,2… C), the membership matrix is calculated using the following formula.
Clear CLC % comments preceded by numbers are areas where you may need to change. xls_name ='road24shiyan0604.xlsx'; % 1.Df = xlsread(xls_name); data = df(:,2:4);
time = df(:,1)'; %% clustering processing % weighted weight in this part a = 0; b = 0; c = 0; For k1 = 1:10a = a + 0.1; For k2 = 1 (10-10*a) b = b + 0.1; c = 1 - a - b; weight = [a,b,c]; [U,V,objFun] = myfcm(weight, data, 3); U = [U; time; zeros(1,length(data))]; for i = 1:length(data) u = U(1:3,i); idx = find(u == max(u)); U(5,i) = idx(1); end xlswrite(xls_name, U(5,:)'['E2:E',num2str(length(data)+1)]) %% colors = ['y'.'m'.'c'.'r'.'g'.'b'.'w'.'k'];
count = 0;
figure
for j = 1:length(data)
count = count + 1;
leibie = U(5,j);
x = data(j,1);
y = data(j,2);
z = data(j,3);
color = colors(ceil(count/36));
if leibie == 1
shape = The '*';
elseif leibie == 2
shape = 'o';
elseif leibie == 3
shape = 'd';
end
F1 = plot3(x,y,z,[color,shape], 'MarkerSize'.15); Function [U, V,objFcn] = myfcm(weight, data, c, T, m, EPSM) % fuzzy C-means algorithm % Data: data to be clustered, n rows and S columns, n is the number of data, s is the number of features of each data % C: number of cluster centers % m: fuzzy coefficient % output: U: Membership degree matrix, c row n column, element UIj represents the degree to which the JTH data belongs to the ith class % V: cluster center vector, C row S column, there are C centers, each center has S-dimensional features % written by Zhang Jin % see also: mydistif nargin < 4
T = 100; % The default number of iterations is100
end
if nargin < 6
epsm = 1.0 e-6; % Default convergence precision endif nargin < 5
m = 2; % The default value of fuzziness is2end [n, s] = size(data); % Initialize the membership matrix U(0), and normalize U0 = RAND (c, n); temp = sum(U0,1);
for i=1:n
U0(:,i) = U0(:,i)./temp(i);
end
iter = 0;
V(c,s) = 0;
U(c,n) = 0;
distance(c,n) = 0;
while( iter<T )
iter = iter + 1; % U = U0; V(t) Um = U0.^m; V = Um*data./(sum(Um,2)*ones(1,s)); % MATLAB matrix multiplication ah, good thing % update U(t)for i = 1:c
for j = 1:n distance(i,j) = mydist(data(j,:),V(i,:),weight); End end U=1./(distance.^m.*(ones(c,1)*sum(distance.^(-m))));
objFcn(iter) = sum(sum(Um.*distance.^2)); % FCM algorithm stop conditionif norm(U-U0,Inf)<epsm
end
% myplot(U,objFcn);
Copy the codeThird, the operation result 
