模糊聚类计算的最佳算法
作者:
基金项目:

国家863高科技发展计划资助项目(863-306-ZT06-01-4);山东省自然科学基金资助项目(Z99G01)


An Optimal Algorithm for Fuzzy Classification Problem
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [8]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n2).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n3logn)计算时间相比,新算法至少降低了O(n

    Abstract:

    In this paper, the geometric meaning of the transitive closure of a fuzzy relation in corresponding fuzzy graph is first given. An optimal algorithm, which is based on the computation of graph connected components, for fuzzy classification problem is proposed. For any given n samples, the worst case time complexity T(n) of the algorithm satisfies that O(n)≤T(n)≤O(n2). Compared with the classic fuzzy classification algorithm, which is based on the computation of the transitive closure of a given relative matrix and of the O(n3log n) time, the new algorithm decreases O(nlog n) time factor at least. The theoretic analysis and computer performance show that the real computing time of the new algorithm is acceptable when it is used for fuzzy classification on large data.

    参考文献
    [1] 汪培庄,李洪兴.模糊系统理论与模糊计算机.北京:科学出版社,1996.166~191.
    [2] 贺仲雄.模糊数学及其应用.天津:天津科学技术出版社,1984.76~185.
    [3] 何新贵.模糊知识处理的理论与技术(第2版).北京:国防工业出版社,1998.414~421.
    [4] 张跃.模糊数学方法及其应用.北京:煤炭工业出版社,1992.273~333.
    [5] 陈文伟.智能决策技术.北京:电子工业出版社,1998.9~21.
    [6] 沈清,汤霖.模式识别导论.长沙:国防科学技术大学出版社,1991.30~154.
    [7] Floyd, R.W. Algorithm 97: shortest path. Communications of the ACM, 1962,35(5,6):345.
    [8] Aho, A.V., Hopcroft, J.E., Ullman, J.D. The Design and Analysis of Computer Algorithms. New York: Addison-Wesley Publishing Company, 1974. 189~195.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

马军,邵陆.模糊聚类计算的最佳算法.软件学报,2001,12(4):578-581

复制
分享
文章指标
  • 点击次数:3812
  • 下载次数: 4535
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1999-09-14
  • 最后修改日期:1999-12-08
文章二维码
您是第19793870位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号