����������ݾ�����·���
�� ��1,2, ������1, �μ���1, �ܴ���1
1.���ִ�ѧ �������ѧ�뼼��ѧԺ,���� 130012
2.������������ѧ �����ϵ,��������,NJ 08901
ժҪ
�����һ����ֵ�ͺ�����ͻ���������ݾ����ȫ���㷨���㷨ͨ�����ѡȡ�㹻��ij�ʼԭ�����������ݼ���ȫ�ֲַ���Ϣ,Ȼ��ͨ������������������ȥ�����ԭ�͡����Ա����㷨��������֤,֤���˸��㷨����Ч�Ժ������ԡ�������������ͬ�����㷨�ľ��������бȽ�,˵�������㷨�Ի���������ݾ��и��ߵľ���׼ȷ��,Ϊ�����������ݾ��������ṩ��һ����;����
�ؼ���: �˹�����; ���ݾ���; �����ھ�; Kԭ���㷨; �����������
New clustering method of mixed-attribute data
BAI Tian1,2, JI Jin-chao1, HE Jia-liang1, ZHOU Chun-guang1
1.College of Computer Science and Technology, Jilin University, Changchun 130022, China
2.Department of Computer Science, Rutgers, the State University of New Jersey, New Jersey, NJ 08901, USA
Abstract
A new Global k-Prototype (GKP) algorithm is proposed for clustering mixed numeric and categorical data. First, the algorithm randomly selects a sufficiently large number of initial prototypes to account for the global distribution of the data sets. Then, it progressively eliminates the redundant prototypes using an iterative optimization process with an elimination criterion function. Systematic experiments were carried out with data from widely used datasets in this area. Experimental results and comparative evaluation show the high performance and consistency of the proposed algorithm. Compared with other well-known mixed data clustering algorithms, the proposed algorithm significantly improves the clustering accuracy.
Keyword: artificial intelligence; clustering; data mining; K-prototypes algorithm; mixed attribute data

�����������ھ�������Ҫ�ļ���֮һ[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�ʼԭ���������������ݵ�ȫ�ֲַ���Ϣ,Ȼ��ͨ�����ۺ�����������ȥ�����ԭ�͡�

1 �����
1.1 K-prototypes�㷨

���ȸ���������ݾ����������ʽ������,��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�ʼԭ��ѡ��ܿ��ܻ����յõ���һ�µľ����������������㷨�޷�����ȫ����Ϣ,����ֻ�ܱ�֤�ֲ����š�

1.2 ȫ��K-prototypes�㷨

Ϊ�˿˷����߸Ľ�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�����������Ա仯�ġ�

2 ʵ���������
2.1 ���ݼ�

Ϊ�������㷨��׼ȷ��,ʹ���˴�����ͨ�õ�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����ֵ�����Կ̻�,�����û����ֳ���׼�Ͳ���׼���ࡣ

2.2 ���۱�׼

ʹ������[16]������ľ���׼ȷ�ȶ�����ʽ�����۱��ķ����ľ���Ч��,����׼ȷ��r�Ķ�������:

ʽ��:n��ʾ���ݼ��е�������Ŀ;ai��ʾ���ձ���ȷ�����������Ŀ;k��ʾĿ�������;rֵԽ���ʾ����׼ȷ��Խ�ߡ�

����ͨ����4��ͨ�õ����ݼ��Ͻ�����������ʵ��,�ֱ�������Ƕȶ�GKP�㷨��Ч������������:�ٲ�ͬ��ʼԭ����Ŀ�Ծ�����Ӱ���ʵ��;��GKP�㷨��KL-FCM-GM�㷨��EKP�㷨��SBAC�㷨�ʹ�ͳK-prototype�㷨�������ıȽ�ʵ�顣��ÿ�����ݼ�������100��ʵ��,ÿ��ʵ�鶼���ѡȡ��ʼԭ��,����100��ʵ��rֵ��ƽ��ֵ��Ϊ���յ��㷨����׼ȷ�ȡ�

2.3 ��ͬ��ʼԭ�����Ծ���Ч����Ӱ��

Ϊ��������ͬ��ʼԭ�����Ծ���׼ȷ�ȵ�Ӱ��,�����ò�ͬ�����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
2.4 ���㷨����ʵ����׼ȷ�ȱȽ�

�������������,����ֵ�趨Ϊ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
3 ������

���������ھ�Ӧ���е���������Խ��Խ����,����������ݾ���������Ҫ���ս�ͻ��,�������һ��ȫ��K-prototypes�㷨(GKP)���Ľ���ͳ�㷨�Ի�����ݾ����׼ȷ�ȡ�GKP�㷨ͨ�����ѡȡ�㹻��ij�ʼԭ�������������ֲ���ȫ����Ϣ,��ͨ�����ۺ�����������ȥ�����ԭ�͡�UCI���ݼ��ϵ�ʵ��������,GKP�㷨����������㷨�ľ���׼ȷ�����������,��ʾ�˱����㷨�ڴ�������������ݾ��������ϵ����ơ�

�����
[1] Jain A K, Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys, 1999, 31��3��: 264-323. [��������:1]
[2] ��ɭ, ¬־ï, �˹���. ���K��ֵ�ͷǸ�����ֽ⼯���ı������㷨[J]. ���ִ�ѧѧ��: ��ѧ��, 2011, 41��4��: 1077-1082.
Xu Sen, Lu Zhi-mao, Gu Guo-chang. Integrating K-means and non-negative matrix factorization to ensemble document clustering[J]. Journal of Jilin University��Engineering and Technology Edition��, 2011, 41��4��: 1077-1082. [��������:1]
[3] Han J, Kamber M. Data Mining Concepts and Techniques[M]. San Francisco: Morgan Kaufmann, 2001. [��������:1]
[4] MacQueen J. Some methods for classification and analysis of multivariate observation[C]��Proc 5th
Berkeley Symp on Mathematical Statistics and Probability, 1967: 281-297. [��������:1]
[5] Anderberg Michael R. Cluster Analysis for Applications[M]. New York: Academic Press, 1973. [��������:1]
[6] Hsu C C, Huang Y P. Incremental clustering of mixed data based on distance hierarchy[J]. Expert Systems with Applications, 2008, 35��3��: 1177-1185. [��������:1] [JCR: 2.203]
[7] Huang Z. Clustering large data sets with mixed numeric and categorical values[C]��Proceedings of the First Pacific Asia Knowledge Discovery and Data Mining Conference, World Scientific, Singapore, 1997: 21-34. [��������:2]
[8] Bezdek J C, Keller J, Krisnapuram R. Fuzzy Models and Algorithms for Pattern Recognition and Image Processing[M]. Boston: Kluwer Academy Publishers, 1999. [��������:1]
[9] Ahmad A, Dey L. Algorithm for fuzzy clustering of mixed data with numeric and categorical attributes[J]. LNCS, 2005, 3816: 561-572. [��������:1]
[10] Chatzis Sotirios P. A fuzzy c-means-type algorithm for clustering of data with mixed numeric and categorical attributes employing a probabilistic dissimilarity functional[J]. Expert Systems with Applications, 2011, 38��7��: 8684-8689. [��������:1]
[11] Zheng Z, Gong M G, Ma J J, et al. Unsupervised evolutionary clustering algorithm for mixed type data[C]��IEEE Congress on Evolutionary Computation, 2010. [��������:1]
[12] Li C, Biswas G. Unsupervised learning with mixed numeric and nominal data[C]��IEEE Transactions on Knowledge and Data Engineering, 2002, 14��4��: 673-690. [��������:1]
[13] Hsu C C, Chen Y C. Mining of mixed data with application to catalog marketing[J]. Expert Systems with Applications, 2007, 32��1��: 12-27. [��������:1] [JCR: 2.203]
[14] Ahmad A, Dey L. A k-mean clustering algorithm for mixed numeric and categorical data[J]. Data & Knowledge Engineering, 2007, 63��2��: 503-527. [��������:1]
[15] Merz C, Murphy P, Aha D. UCI repository of machine learning databases[D]. Irvine: Department of Information and Computer Science, University of California, 1997. [��������:1]
[16] Huang Z, Ng M K. A fuzzy k-modes algorithm for clustering categorical data[J]. IEEE Trans Fuzzy System, 1999, 7��4��: 446-452. [��������:0]