�����������ھ�������Ҫ�ļ���֮һ[1],�����ı��ھ�Ⱥܶ�����������Ҫ��Ӧ��[2]�������������ҪĿ���ǽ������Ķ������������������ֳ�������,ʹ��ͬһ���������˴�����,��ͬ���������˴�����[3]��K��ֵ(K-means)�㷨[4]�������ڴ��ģ���ݼ��ϵĸ�Ч��[5]�����㷺ʹ�á����ڴ��ۺ���������ǻ�����ֵ�����Ե�,����K-means�㷨ֻ�ܴ�����ֵ������,����������������������ڵĻ���������ݡ�Ȼ��,��ʵӦ���е����ݼ�����ͬʱ������ֵ�ͺ����������[6]��
��ĿǰΪֹ,һЩ�㷨�Ѿ�����������������ݵľ������⡣Huang[7]�����һ��Kԭ��(K-prototypes)�㷨,ͨ����չK-means�㷨�Ĵ��ۺ�����������������������ڵĻ���������ݾ������⡣Ϊ�˸��õؿ̻����ݼ��IJ�ȷ����,Bezdek��[8]�����ģ��K-prototypes�㷨��֮��,����������һЩ�㷨���,����߶Ի�����ݾ����Ч��,���бȽ��д����Ե���Ahmad��Dey[9]������㷨,�Լ�Chatzis[10]����Ļ����������Ϣ��ģ��C��ֵ�������㷨;Zheng��[11]���һ�ֻ��ڽ���������㷨;Li��Biswas[12]���һ�ֻ��ڲ�ξ���ܵ��㷨;Hsu��Chen[13]���һ�ֻ��ڷ�����ص��㷨;Ahmad��Dey[14]���һ�ֽ�K-means�㷨Ӧ�õ���������ϵķ�����
��ȻK-prototypes�㷨ͨ����չK-means�㷨ʹ���ܶԻ�������ݽ��о���,��һ���̶��ϼ̳���K-means�㷨�Դ��ģ���ݾ���ĸ�Ч��,������K-meansһ��,K-prototypesҲ��Ȼ�ؾ�����������ȱ��:��������������ȫ�ֲַ���Ϣ,���㷨ֻ�ܵõ��ֲ�����;�ھ���Ч���Գ�ʼ���ĵ��ѡ��dz����С�Ϊ�˸Ľ���ͳ����������ȱ��,���������һ��ȫ��K-prototypes(Global K-prototypes,GKP)�㷨,ͨ�����ѡ���㹻��ij�ʼԭ���������������ݵ�ȫ�ֲַ���Ϣ,Ȼ��ͨ�����ۺ�����������ȥ�����ԭ�͡�
���ȸ���������ݾ����������ʽ������,��X={X1,X2,��,Xn}��ʾn����������������,ÿ������Xi��m������A1,A2,��,Am,����ÿ������Aj��ֵ����ΪDom(Aj)�����Ե�ֵ��������ֵ�ͺͷ�������ɵĻ������,��ֵ������ֵ��������������ʾ,������������ֵ���ʾΪDom(Aj)={a1j,a2j,��,atj},����t��ʾ��j�����ԵĿ�ȡ��������ɴ�,�ɽ�Xi��ʾΪ����[xri,1,xri,2,��,xri,p,xci,p+1,xci,p+2,��,xci,m],����ǰp��Ԫ��Ϊ��ֵ������(���ϽDZ�r��ʾ),����Ϊ���������(���ϽDZ�c��ʾ)��
K-prototypes�㷨[7]��K-means�㷨�������Ƶ��㷨����,ͨ������ֵ�ͺ�����ͻ����ʽ�����ĵ��ʾ��ʽ����ԭ��(prototype)������K-means�еľ�ֵ(mean),��չ��K-meansֻ�ܴ�����ֵ�����ݵ�����,ʹ���㷨���ԶԻ�������ݽ��о��������K-prototypes�㷨�ǽ�������������X�ֳ�k�������ཻ����,��ʹ��ʽ(1)��������С:
ʽ��:Ql������l�������ԭ��(prototype);uil��һ��n��k��ʵ����������,��ʾ�۲����Xi�Ծ���ԭ��Ql��������,���캯��d(xi,Ql)��������:
ʽ��:��p=qʱ,��(p,q)=0;��p��qʱ,��(p,q)=1��xrij(xcij)��ʾ��i�������ĵ�j����,qrlj(qclj)��ʾ��l������ԭ�͵ĵ�j����,��lΪ��������Ե�Ȩ�ء�
�����㷨�������¡�
����1 ȷ��������Ŀk,��ѡ��k����ʼ��ԭ��(prototype)��
����2 �����ݼ��е�ÿ������,�����䵽��ԭ�͵ľ���,���������䵽���������ԭ�����ڵ���,�����¼�������ԭ�͡�
����3 ���¼����������k���µ�ԭ��֮��ľ���,��������������ԭ�͵ľ���ȵ���ǰ��ԭ�͵ľ������,���·����������������ԭ���������С�
����4 �ظ�����3,ֱ������������ٱ仯��
K-prototypes�㷨��ʼѡ���ԭ������ȷ����,��Ŀ�������Ŀ,��ʹ����ѡȡ�ij�ʼԭ�ͺܴ�̶����������ݼ������ķֲ���Ϣ,����ͬ�ij�ʼԭ��ѡ��ܿ��ܻ����յõ���һ�µľ����������������㷨������ȫ����Ϣ,����ֻ�ܱ�֤�ֲ����š�
Ϊ�˿˷����߸Ľ�K-prototypes�㷨ֻ�ܵõ��ֲ����Ž�ľ�����,�����һ��ȫ��K-prototypes(Global K-prototypes,GKP)�㷨��������·�����Ҫ����������������:�����ѡȡ�㹻��ij�ʼԭ��;��ͨ�����һ�����ۺ�����������ȥ�����ԭ�͡�
1.2.1ԭ�͵ij�ʼѡ��
�ڴ�ͳ��K-prototypes�㷨��,��ʼѡ��ԭ������Ŀ����������ͬ,�������ѡ����Ŀ���������ͬ�ij�ʼԭ��,��ʹ����Щ��ʵ���ڵľ����п���û�а�����ʼԭ��,���տ��ܵ�����Щ�������Ա�����,Ӱ�����Ч����Ϊ�˸Ľ���Щ����,GKP�������ѡȡ�㹻��ij�ʼԭ��,ʹ��ѡȡ�ij�ʼԭ���ܹ���������Ŀ�����,���������ݼ���ȫ�ֲַ���Ϣ��
������˵,�趨kini��ktar�ֱ������ʼѡ���ԭ����Ŀ�Լ�Ŀ�������Ŀ,����kini��ktar���ڱ�����,Ϊ�˷������,kini���趨ΪĿ��������ı���,�ں���������л�������۾����Ч�����ʼԭ����kini�Ĺ�ϵ��
1.2.2 ������ȥ�����ԭ��
�������Ĺ������㷨Ҫ��������ȥ�����kini��ktar��ԭ��(�����)����ÿ�εĵ���������ѡ��һ��ԭ����ȥ,����һ����ȥ���ۺ���E��ѡȡ��ÿ�ε�������ȥ��ԭ�͡�ij��ԭ�͵����ۺ���E��ֵ��ʾ���ԭ�����ھ�������������������ԭ�����������ԭ�;����,����Щ��������ԭ�͵ľ���͵IJ�ֵ������ȥһ��ԭ�ͺ�,ʣ�µ�k-1��ԭ��Ϊ��һ�ε����ij�ʼԭ�ͽ��еľ�������ڴﵽ����ʱ������F��ֵ,һ����k��ԭ������ʱ���������ڼ��������,��ԭ��������������ͬʱ,����F��ֵΪ0,����ԭ��ֻ��һ��ʱ,����F��ֵ�ﵽ�������,���ۺ���Eʵ�����Ƕ���ȥһ��ԭ��֮��,��������F����ֵ��һ�����ơ����ھ����Ŀ����ʹ��������Fֵ������ʱ������С,��С�ij�ʼ״̬�µ�Fֵ,�ڸ����ϻ�õ���С������״̬��Fֵ������,ѡ�����ۺ���Eֵ��С��ԭ����ȥ�����ۺ�����������:
ʽ��:Ql��Q,Ql��Qj;Cj��ʾ���༯��C�еĵ�j������(C=[C1,C2,��,Ck]��ʾ��ǰ���������е�k������);Q=[Q1,Q2,��,Qk]��ʾ����״̬�µ�k��ԭ��;d(xi,Qj)��ʾ������xi(xi��Cj)����j������Cj��ԭ��Qj�ľ���;mind(xi,Ql)��ʾ������xi����ԭ��Qj������ԭ�͵���С���롣�ɴ�ɾȥ������СEjֵ��ԭ��Qj,��ʣ�µ�k-1��ԭ����Ϊ�´ε����ij�ʼ���ĵ㡣
1.2.3 �㷨����
��α�����ʾ���㷨��������:
�㷨�AGKP�A
����:D:n�������������������
kini:��ʼԭ����Ŀ
ktar:Ŀ�������Ŀ
���:�������������ɵ�ktar��������
��ʼ��:�A��D�����ѡȡkini������Ϊ��ʼԭ��.
��������:�A��k��ǰ�������̵ľ�����Ŀ
for�Ak�A=�Akini�Ato�Aktar.
����K-prototypes�㷨�õ�����k��ԭ�͵ľ�������Ž�S(k),����Q=[Q1,Q2,��,Qk]ΪS(k)��k��ԭ�͡�
for�Ai�A=�A1�Ato�Ak.
��ÿ��ԭ��Qi,��������ȥ���ۺ���Ei
end
ɾ�����ۺ���ֵ��С��ԭ��Qj,����ʣ��k-1��ԭ����Ϊ�´ε����ij�ʼԭ�͡�
end
1.2.4 ��ʼԭ����Ŀ��ѡ��.
��������,GKP�㷨�Ĺؼ���ѡ���㹻��ij�ʼԭ�������������ռ��ȫ�ֲַ���Ϣ,��ktar��ʾĿ�������Ŀ,��ʼԭ����Ŀkini�ɱ�ʾΪ
ʽ��:��Ϊ��������ϵ������������˵,�ұ�ʾ��������ÿ��Ŀ������еij�ʼԭ����Ŀ,����ѡȡͨ�������ݼ��ķֲ���Ϣ�й�,���ĺ����ʵ�����,����=4ʱ,����Ч���Ѿ��ﵽ���,˵�����㷨�������ԡ�
1.2.5 �㷨�����Է���
��ͳK-prototype�㷨��ʱ�临����ΪO(t��k��m��n),��n��ʾ������Ŀ,m��ʾÿ��������������Ŀ,k��ʾ�������,t��ʾȫ�����ݼ��ĵ���������ͨ�������,t��k��m��n,����㷨��ʱ�临����ΪO(n)������GKPÿ��ԭ����ȥ�ĵ�������ֻ��Ҫ����һ��K-prototypes�㷨,��˹���Ҫ���ЦҪ�k��k+1=(�ң�1)k+1��K-prototype�㷨�������ᵽ,����ʵ���и����ݼ��ڦ�=4ʱ���ﵽ����õ�Ч��,���Կ���˵��ͨ������½�С�Ħ�ֵ����һ��Ӧ�ö����㹻��,����Ϊ(�ң�1)k+1��n,����GKP�㷨��ʱ�临����ΪO(n),˵���㷨��ʱ�临������������n�����������Ա仯�ġ�
Ϊ�������㷨��ȷ��,ʹ���˴�����ͨ�õ�UCI���ݼ�[15]�е�4�ֻ���������ݼ�,�ֱ�ΪZoo���ݼ���Acute Inflammations���ݼ���Heart Disease���ݼ���Credit Approval���ݼ���
Zoo���ݼ�����101�ֶ������̬��ϰ����Ϣ,ÿ�ֶ�����1����ֵ�����Ժ�16�����������������,���ݼ������һ��������Ը�������Щ�����7��������Ϣ��Acute inflammations���ݼ�����120��������֢���ߵIJ���������ָ��,ÿ��������1����ֵ��ָ��(����)��6�������ָ��,���ݼ������˻��ߵ��������ǡ�Heart disease���ݼ�����303�����ߵ���Ϣ,ÿ�����ߺ���6����ֵ�����Ժ�9����������ԡ�Credit approval���ݼ�����690���û������ÿ���Ϣ,ÿ���û���10����������Ժ�6����ֵ�����Կ̻�,�����û����ֳ����Ͳ������ࡣ
ʹ������[16]������ľ���ȷ�ȶ�����ʽ�����۱��ķ����ľ���Ч��,����ȷ��r�Ķ�������:
ʽ��:n��ʾ���ݼ��е�������Ŀ;ai��ʾ���ձ���ȷ�����������Ŀ;k��ʾĿ�������;rֵԽ���ʾ����ȷ��Խ�ߡ�
����ͨ����4��ͨ�õ����ݼ��Ͻ�����������ʵ��,�ֱ�������Ƕȶ�GKP�㷨��Ч������������:�ٲ�ͬ��ʼԭ����Ŀ�Ծ�����Ӱ���ʵ��;��GKP�㷨��KL-FCM-GM�㷨��EKP�㷨��SBAC�㷨�ʹ�ͳK-prototype�㷨�������ıȽ�ʵ�顣��ÿ�����ݼ�������100��ʵ��,ÿ��ʵ�鶼���ѡȡ��ʼԭ��,����100��ʵ��rֵ��ƽ��ֵ��Ϊ���յ��㷨����ȷ�ȡ�
Ϊ��������ͬ��ʼԭ�����Ծ���ȷ�ȵ�Ӱ��,�����ò�ͬ�����ij�ʼԭ��,����ͬ�Ħ�ֵ����GKP�㷨��ǰ���ᵽ,��Ϊһ��������,�����Ӹ�����ÿ�����յľ����а����ij�ʼԭ���������Ľ���ֵ�趨Ϊ2��10���ֱ�����4��UCI���ݼ�����1���г��˲�ͬ���ݼ��ڲ�ͬ��ֵ�µľ���ȷ��,����ÿһ��Ϊͬһ���ݼ��ڲ�ͬ���µľ���ȷ�ȡ��ر��,����=1ʱ,GKP�㷨��ͬ�ڴ�ͳ��K-prototypes�㷨������1�п��Կ���,��ȫ��4�����ݼ���,GKP�㷨(����[2,10])�ľ���ȷ�������K-prototypes�㷨(��=1)��ȷ����������ߡ�����1�����Է���,��ȫ��4�����ݼ���,���Ŧ�ֵ������,��ʼʱ����ȷ��һֱ���,ֱ����=4ʱ�ﵽ���ֵ,֮�����Ŧҵ�����,����ȷ�ȳ����²�������,����û���ٸ��ڦ�=4ʱ��ֵ,��˵���˾���ȷ�����ֵ���ӵ������ԡ�
![]() | ��1 ��ͬ��ֵ�ľ���ȷ��ʵ����Table 1 Clustering accuracy achieved by different values of�� on four data sets |
�������������,����ֵ�趨Ϊ4,��4��UCI���ݼ�������GKP�㷨,���������KL-FCM-GM�㷨��EKP�㷨��SBAC�㷨�ʹ�ͳK-prototype�㷨�Ƚ�,ʵ������ͼ1��ʾ����ͼ�п��Է���,�����GKP�㷨������4�����ݼ��ϵľ���ȷ������������㷨(KL-FCM-GM��EKP��SBAC��K-prototype)�����������,���Credit approvals���ݼ�,GKP�㷨�ľ���ȷ��Ϊ82.8%,�ȵڶ��ߵ�EKP�㷨ȷ�ȸ�21%;�����Zoo���ݼ�,GKP�㷨��ȷ��Ϊ91.2%,�ȵڶ��ߵ�KL-FCM-GM�㷨���5.5%������,����4���㷨ֻ�ڲ������ݼ����нϺõĽ��(��EKP�㷨��Credit approvals���ݼ���KL-FCM-GM��Zoo���ݼ���Heart disease���ݼ�),����������Щ���ݼ��Ͼ���Ч���Ͳ��Ǻ�����(��EKP��Acute inflammations��Heart disease���ݼ���KL-FCM-GM��Credit approvals���ݼ�),��GKP�㷨��ȫ��4�����ݼ��϶�ȡ����һ�µ�����Ч��,˵�����㷨�ڻ�������ݾ����ϵ����ơ�
![]() | ͼ1 ���㷨����ȷ�Ƚ���Ƚ�Fig.1 Clustering accuracy comparison of GKM and KM, NKM and FKM algoritm |
���������ھ�Ӧ���е���������Խ��Խ����,����������ݾ���������Ҫ���ս�ͻ��,�������һ��ȫ��K-prototypes�㷨(GKP)���Ľ���ͳ�㷨�Ի�����ݾ����ȷ�ȡ�GKP�㷨ͨ�����ѡȡ�㹻��ij�ʼԭ�������������ֲ���ȫ����Ϣ,��ͨ�����ۺ�����������ȥ�����ԭ�͡�UCI���ݼ��ϵ�ʵ��������,GKP�㷨����������㷨�ľ���ȷ�����������,��ʾ�˱����㷨�ڴ�������������ݾ��������ϵ����ơ�
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|