似度的方法是通过调整相应邻接矩阵的表示法（Umeyama，1988）。
关系型数据：另一个吸引大量兴趣的方面是聚类关系型（网络）数据。不像以划分图集为不相交的组为目的的聚类图数据，这里的任务是划分一个大图（比如网络）为基于它们连接结构和节点属性的紧密结合的子图。这个问题当允许连接（对象之间的关系）为不同的类型时将变得更加复杂。对于关系型数据聚类来说，一个核心问题是要定义一个合适的聚类准则。（Taskar et al.,2001）第一次提出了关于关系型数据的通用概率模型，它依据受相互之间约束的分布对不同的相关实体进行建模。纽曼模块性函数（Newman和Girvan，2004；Newman，2006）是一个广泛用于寻找网络间群体结构的准则，但是它只考虑了连接结构而忽略了属性相似度。（White和Smyth，2005）提出了用于网络图聚类的纽曼格文目标函数（Newman和Girvan，2004）的谱松弛。因为实际的网络往往是动态的，另一个问题是要在考虑组成员关系和其它特征特性改变的情况下对网络演化行为的建模（Backstrom et al.,2006）。
5. 总结
对数据进行合理的分组问题很自然的出现在很多科学领域。因此见证数据聚类的不断流行并不令人惊讶。记住聚类分析是一种探索性的工具将非常重要。聚类算法的输出仅仅是一种建议性的假设。尽管大量的聚类算法已经出现或者正在出现，没有某一个聚类算法已经被证明在不同应用领域中优于其它算法。很多包括简单K-means在内的算法都是容许性算法。随着新应用的不断出现，人们渐渐的意识到寻找最好的聚类算法这个问题本身就是有问题的。比如，考虑企业知识管理这样一个应用领域。给定同一文档库，不同的用户群（比如法律、营销、管理等）也许就只对基于各自需要的文档划分有兴趣。一个满足一群用户需要的聚类方法也许就不满足另一群用户的需要。就像前面提到的“聚类结果在于观察者眼中”，所以实际数据聚类必须结合用户和应用需要。
聚类在数据分析领域有许多成功的案例。尽管如此，机器学习和模式识别领域还需要处理许多问题，用于提高我们对数据聚类的理解。从这一点而言，以下是一系列有价值的问题和研究方向。
(a)研究群体需要可用的一系列基准数据（有地面事实的）来测试评估聚类
方法。基准数据应该来自不同的领域（文档、图像、时间序列、消费者交易记录、生物序列、社交网络等）。基准数据还应该包括静态数据和动态数据（后者将对分析随时间变化的簇非常有用）、定性的和定量的属性以及连接和非连接的对象等。尽管提供基准数据的想法并不新鲜（比如UCI ML和KDD repository），但目前基准数据还主要是小的、静态的数据集。
(b)我们需要聚类算法和应用需要之间更加紧密的整合。比如，有些应用只需要产生一些紧密结合的簇（并不是紧密结合的簇可以被忽略），而有些应用需要获得对整个数据集进行最好的划分。在大部分应用中，并不一定要找到最佳的聚类算法，更重要的是选择用于识别数据潜在簇结构的正确特征提取方法。 (c)无论原则（或目标），大部分聚类方法最后都转化为组合优化问题，它的目的是找到优化目标的数据划分。因此，在涉及大规模数据时，计算问题就变得非常重要。比如，找到K-means的全局最优解就是一个NP困难问题。因此选择能够使得计算上有效率求解的聚类原则就变得非常重要。
(d)关于聚类的一个基本问题是它的稳定性和一致性。一个好的聚类原则应该使得在数据中有扰动情况下产生的数据划分是稳定的。我们需要开发出能够产生稳定解的聚类方法。
(e)根据对已有公设的满足来选择聚类原则。尽管有Kleinberg的不可能理论，有些研究已经表明可以通过放松一些设定来满足要求。因此，也许评估一种聚类原则的方式就是看它满足设定的程度。
(f)考虑到聚类本身的困难，这使得开发半监督聚类算法变得更有意义。它可以使用有标识的数据和（用户确定的）对间约束来决定（i）数据表示法（ii）用于数据聚类的合适的目标函数。
致谢
我要感谢国家科学基金和海军研究办公室对我关于数据聚类、降维、分类和半监督学习的研究工作的支持。我要感谢Rong Jin、Pang-Ning Tan和Pavan Mallapragada帮助我准备傅京孙演讲和这个手稿。我很享受和Eric Backer等在数据聚类上富有成效的合作，并且学到了很多。Joydeep Ghosh等为提高本文的的质量提供了很多有用的建议。
参考文献
[1] Aggarwal, Charu C., Han, Jiawei, Wang, Jianyong, Yu, Philip S., 2003. A framework for clustering evolving data streams. In: Proc. 29th Internat. Conf. on Very Large Data Bases, pp. 81–92.
[2] Agrawal, Rakesh, Gehrke, Johannes, Gunopulos, Dimitrios, Raghavan, Prabhakar,
1998. Automatic subspace clustering of high dimensional data for data mining applications. In: Proc. ACM SIGMOD, pp. 94–105.
[3] Anderberg, M.R., 1973. Cluster Analysis for Applications. Academic Press.
Andrews, Nicholas, O., Fox, Edward A., 2007. Recent developments in documentclustering. Technical report TR-07-35. Deparment of Computer Science, Virginia Tech.
[4]Arabie, P., Hubert, L., 1994. Cluster analysis in marketing research. In: Advanced Methods in Marketing Research. Blackwell, Oxford, pp. 160–189.
[5]Backer, Eric, 1978. Cluster Analysis by Optimal Decomposition of Induced Fuzzy Sets. Delft University Press.
[6]Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X., 2006. Group formation in large social networks: Membership, growth, and evolution. In: Proc. 12th KDD. [7]Baldi, P., Hatfield, G., 2002. DNA Microarrays and Gene Expression. Cambridge University Press.
[8]Ball, G., Hall, D., 1965. ISODATA, a novel method of data anlysis and pattern classification. Technical report NTIS AD 699616. Stanford Research Institute, Stanford, CA.
[9]Banerjee, Arindam, Merugu, Srujana, Dhillon, Inderjit, Ghosh, Joydeep. 2004. Clustering with bregman divergences. J. Machine Learn. Res., 234–245.
[10]Banerjee, Arindam, Basu, Sugato, Merugu, Srujana, 2007a. Multi-way clustering
on relation graphs. In: Proc. 7th SIAM Internat. Conf. on Data Mining.
[11]Banerjee, S., Ramanathan, K., Gupta, A., 2007b. Clustering short texts using
Wikipedia. In: Proc. SIGIR.
[12]Bar-Hillel, Aaron, Hertz, T., Shental, Noam, Weinshall, Daphna, 2003. Learning
distance functions using equivalence relations. In: Proc. 20th Internat. Conf. on Machine Learning, pp. 11–18.
[13]Basu, Sugato, Banerjee, Arindam, Mooney, Raymond, 2002. Semi-supervised
clustering by seeding. In: Proc. 19th Internat. Conf. on Machine Learning. [14]Basu, Sugato, Bilenko, Mikhail, Mooney, Raymond J., 2004. A probabilistic
framework for semi-supervised clustering. In: Proc. 10th KDD, pp. 59–68. [15]Basu, Sugato, Davidson, Ian, Wagstaff, Kiri (Eds.), 2008. Constrained Clustering:
Advances in Algorithms, Theory and Applications. Data Mining and Knowledge Discovery, vol. 3, Chapman & Hall/CRC.
[16]Bekkerman, Ron, El-Yaniv, Ran, McCallum, Andrew, 2005. Multi-way
distributional clustering via pairwise interactions. In: Proc. 22nd Internat. Conf. Machine Learning, pp. 41–48.
[17]Belkin, Mikhail, Niyogi, Partha, 2002. Laplacian eigenmaps and spectral
techniques for embedding and clustering. Advances in Neural Information Processing Systems, vol. 14. pp. 585–591.
[18]Ben-David, S., Ackerman, M., 2008. Measures of clustering quality: A working
set of axioms for clustering. Advances in Neural Information Processing Systems. [19]Bezdek, J.C., 1981. Pattern Recognition with Fuzzy Objective Function
Algorithms. Plenum Press.
[20]Bhatia, S., Deogun, J., 1998. Conceputal clustering in information retrieval. IEEE
Trans. Systems Man Cybernet. 28 (B), 427–436.
[21]Bishop, Christopher M., 2006. Pattern Recognition and Machine Learning.
Springer. Blake, Merz C.J., 1998. UCI repository of machine learning databases. [22]Blei, D.M., Ng, A.Y., Jordan, M.I., 2003. Latent dirichlet allocation. J. Machine
Learn. Res. 3, 993–1022.
[23]Bradley, P.S., Fayyad, U., Reina, C., 1998. Scaling clustering algorithms to large
databases. In: Proc. 4th KDD.
[24]Buhler, J., 2001. Efficient large-scale sequence comparison by locality-sensitive
hashing. Bioinformatics 17 (5), 419–428.
[25]Busse, Ludwig M., Orbanz, Peter, Buhmann, Joachim M., 2007. Cluster analysis
of heterogeneous rank data. In: Proc. 24th Internat. Conf. on Machine Learning, pp. 113–120.
[26]Cao, F., Ester, M., Qian, W., Zhou, A., 2006. Density-based clustering over an
evolving data stream with noise. In: Proc. SIAM Conf. Data Mining.
[27]Chapelle, O., Sch?lkopf, B., Zien, A. (Eds.), 2006. Semi-Supervised Learning.
MIT Press, Cambridge, MA.
[28]Cheng, Yizong, Church, George M., 2000. Biclustering of expression data. In:
Proc. Eighth Internat. Conf. on Intelligent Systems for Molecular Biology, AAAI Press, pp. 93–103.
[29]Connell, S.D., Jain, A.K., 2002. Writer adaptation for online handwriting
recognition. IEEE Trans. Pattern Anal. Machine Intell. 24 (3), 329–346.
[30]Critchlow, D., 1985. Metric Methods for Analyzing Partially Ranked Data.
Springer. Datta, Ritendra, Joshi, Dhiraj, Li, Jia, Wang, James Z., 2008. Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys 40 (2) (Article5).
[31]Dempster, A.P., Laird, N.M., Rubin, D.B., 1977. Maximum likelihood from
incomplete data via the EM algorithm. J. Roy. Statist. Soc. 39, 1–38.
[32]Dhillon, I., Modha, D., 1999. A data-clustering algorithm on distributed memory
multiprocessors. In: Proc. KDD’99 Workshop on High Performance Knowledge Discovery, pp. 245–260.
[33]Dhillon, Inderjit S., Mallela, Subramanyam, Guyon, Isabelle, Elisseeff, André,
2003. A divisive information-theoretic feature clustering algorithm for text classification. J. Machine Learn. Res. 3, 2003.
[34]Dhillon, Inderjit S., Guan, Yuqiang, Kulis, Brian, 2004. Kernel k-means: Spectral
clustering and normalized cuts. In: Proc. 10th KDD, pp. 551–556.
[35]Ding, Chris, He, Xiaofeng, Simon, Horst D., 2005. On the equivalence of
nonnegative matrix factorization and spectral clustering. In: Proc. SIAM Internat.