Support Vector Machines (SVMs) have been dominant learning techniques for more than ten years, and mostly applied to supervised learning problems. Recently nice results are obtained by two-class unsupervised classification algorithms where the optimization problems based on Bounded
-SVMs and Lagrangian SVMs respectively are relaxed to Semi-definite Programming. In this paper we propose another approach to solve unsupervised classification problem, which directly relaxes a modified version of primal problem of SVMs with label variables to a semi-definite programming. The preliminary numerical results show that our new algorithm often obtains more accurate results than other unsupervised classification methods, although the relaxation has no tight bound, as shown by an example where its approximate ratio of optimal values can be arbitrarily large.