FCM算法用于灰度图像分割的初始化方法的研究

模糊C均值聚类(FCM)算法是一种经典的模糊聚类分析方法，但其算法初始聚类中心集是随机选取的，从而造成算法的性能强烈的依赖聚类中心集的初始化。提出了一种改进的基于多项式求解的FCM(PFCM)算法，该算法基于求解多项式的根来确定数据集初始聚类中心集，很好地解决了数据初始聚类中心集问题，使数据初始聚类中心集代表了数据集类别的特征，在此基础上，采用FCM算法得到聚类中心集的近似最优解。     

基于聚类分解的WCDMA基站布局规划算法

针对大规模WCDMA无线网络基站布局规划问题，提出一种基于聚类分解的分层算法．在聚类分解中，以测试点信号增益矩阵构造聚类分解数据，并给出了收敛判定函数和相似度计算方法．在分层算法中，首先用K均值聚类将原问题分解为K个子规划问题，然后对各子问题求解整数规划问题，最后对各子问题的基站布局结果进行全局调整．仿真计算验证了该算法的有效性．     

基于约束的混合属性增量聚类算法

为解决大规模数据集聚类过程中内存容量受限问题,提出了一种基于聚类个数约束的快速聚类算法,只需扫描一趟原始数据集,半径阈值随聚类过程动态变化;同时定义了一种包含分类属性取值频率信息的类间差异性度量,可用于混合属性数据集,时间复杂度与空间复杂度同数据集大小,属性个数近似成线性关系.在KDDCUP99数据集上的实验结果表明,提出的算法输入参数少,具有良好的聚类特性,可用于大规模数据集.     

基于聚类的基础设施选址方案研究及应用

基础设施选址是精准化农业需要解决的重要课题之一.采用基于迭代自组织数据分析技术(ISODATA)的聚类方法、图论方法以及地理信息系统(GIS)空间分析方法相结合,解决了当聚类个数不可预知,无法使用传统设施选址方法中的k-means聚类方法和当没有设施位置备选集而无法使用离散模型选址方法的问题,也有效规避了选址方案实际操作可行性不强等问题,为精准化农业中基础设施选址提供了一种可行的解决方案.     

基于先验信息和谱分析的聚类融合算法

在聚类过程中利用先验信息能显著提高聚类算法的性能,但已存在的聚类融合算法很少考虑到数据集的先验信息。基于先验信息和谱分析,提出一种聚类融合算法,将成对限制信息引入到谱聚类算法中,用受限的谱聚类算法产生聚类成员,再采用基于互联合矩阵的集成方法生成最后的聚类结果。实验结果表明,利用先验信息能有效提高聚类的效果。     

一种基于局部密度的网格排序聚类算法

针对复杂及带噪声的数据集的聚类问题, 提出了一种基于局部密度的网格排序策略(GSS-LD)并以其作为网格聚类的组织模式. GSS-LD一方面利用聚类的局部性质进行网格单元排序, 将基于网格的聚类问题转化为网格的排序问题;另一方面运用相对局部密度变化率的概念, 克服了传统网格聚类算法中全局性参数的局限性, 使其可以适应多密度数据集的聚类. 通过3组具有不同拓扑结构的数据集测试GSS-LD的聚类性能并同其它两种方法进行比较, 结果表明GSS-LD可以对复杂数据集进行有效聚类, 它的时间复杂度分别与数据规模及网格结构具有线性关系, 同时具有较强的噪声处理能力.     

基于层次策略的半监督K-medoids算法研究

针对现有基于K-means的半监督聚类算法存在的共同问题,即对离群点敏感、在非凸数据集与不平衡数据集上表现差,提出了一种基于层次策略的散布种子半监督中心聚类算法。首先通过基于影响空间的样本边缘因子将数据集分为核心层与边缘层,然后应用一种改进的K-medoids算法完成核心层聚类,最后采用一种递进半监督分配策略对边缘层进行分配得到最终聚类结果。算法通过层次策略解决了离群点干扰问题、半监督子簇聚类及合并策略实现了在不同分布数据集上有效聚类。通过与几种半监督聚类方法在人工数据集以及真实数据集上进行的对比实验证明,该算法能够解决现存问题,提升了聚类性能与鲁棒性。     

稳定的K-多均值聚类算法

指定K个聚类的多均值聚类算法在K-均值算法的基础上设置了多个次类,以改善K-均值算法在非凸数据集上的劣势,并将多均值聚类问题形式化为优化问题,可以得到更优的聚类效果。但是该算法对初始原型敏感,且随机选取原型的方式使聚类结果不稳定。针对上述问题,提出一种稳定的K-多均值聚类算法,并对该算法的复杂度与收敛性进行了简要讨论。该算法先基于数据样本的最邻近关系构造图,根据图的连通分支将数据分为若干组,取每组数据的均值点作为初始原型,再用交替迭代的方法对优化问题进行求解,得到最后的聚类结果。在人工数据集和真实数据集上的实验表明,该算法具有更稳定更优越的聚类效果。     

一种基于双聚类的缺失数据填补方法

针对现实数据集的数据缺失问题,提出了一种基于双聚类的缺失数据填补新方法.该算法利用双聚类簇内平均平方残值越小簇内数据相似性越高的这一特性,将缺失数据的填补问题转换为求解特定双聚类簇最小平均平方残值的问题,进而实现了数据集中缺失元素的预测;再利用二次函数求解极小值的思想对包含有缺失数据的特定双聚类簇最小平均平方残值的问题进行求解,并进行了数学上的分析证明.最后进行仿真验证,通过观察UCI数据集的实验结果可知,提出的算法具有较高的填补准确性.     

基于谱分析的密度峰值快速聚类算法

针对密度峰值快速聚类（CFSFDP）算法对不同数据集聚类效果的差异，利用谱聚类对密度峰值快速聚类算法加以改进，提出了一种基于谱分析的密度峰值快速聚类算法CFSFDP-SA。首先，将高维非线性的数据集映射到低维子空间上实现降维处理，将聚类问题转化为图的最优划分问题以增强算法对数据全局结构的适应性；然后，利用CFSFDP算法对处理后的数据集进行聚类。结合这两种聚类算法各自的优势，能进一步提升聚类算法的性能。在5个人工合成数据集（2个线性数据集和3个非线性数据集）与4个UCI数据库中真实数据集上的聚类结果显示，相比CFSFDP算法，CFSFDP-SA算法的聚类精度有一定提升，在高维数据集的聚类精度上最多提高了14%，对原始数据集的适应性更强。     

基于自控粒子群优化的入侵数据分析

基于异常的入侵检测方法难以有效地获得一个用于建立正常行为模式的正常数据训练集,而粒子群优化模糊聚类算法的初始化聚类数目一般凭经验确定,准确性不高。为此,提出一种自控粒子群优化模糊聚类算法。从网络数据中提取训练集,并初始化具有不同聚类数目的粒子群,在迭代过程中,根据不同粒子群的聚类有效性函数,通过列控制向量对各粒子群规模进行调整,由此实现聚合。实验结果表明,该方法的聚类结果准确率高,可以为基于异常的入侵检测方法提供可靠的训练数据。     

基于Tabu搜索的聚类算法研究

聚类分析的两个基本任务是分析数据集中簇的数量以及这些簇的位置。大多数的聚类方法通常只关注后一个问题。为了在聚类数不确定的情况下实现聚类分析,本文提出了一种新的结合人工免疫网络和Tabu搜索的动态聚类算法—DCBIT。新算法主要包含两个阶段：先使用人工免疫网络算法获得一个候选聚类中心集,然后使用Tabu搜索在候选聚类中心集上实现动态聚类。仿真实验结果表明与现有方法相比,新方法具有更好的收敛概率和收敛速度。     

多区间速度约束下的时序数据清洗方法

为进一步优化推广大数据及人工智能技术,作为数据管理与分析的基础,数据质量问题日益成为相关领域的研究热点.通常情况下,数据采集及记录仪的物理故障或技术缺陷等会导致收集到的数据存在一定的错误,而异常错误会对后续的数据分析以及人工智能过程产生不可小视的影响,因此在数据应用之前需要对数据进行相应的数据清洗修复.现存的平滑修复方法会导致大量原本正确的数据点过度修复为异常值,而基于约束的顺序依赖方法以及SCREEN方法等也因为约束条件较为单薄而无法对复杂的数据情况进行精确修复.本文基于最小修复原则进一步提出了多区间速度约束下的时间序列数据修复方法,并采用动态规划方法来求解最优修复路径.具体来说,本文提出了多个速度区间来对时序数据进行约束,并根据多速度约束对各数据点形成一系列修复候选点,进而基于动态规划方法从中选取最优修复解.为验证上述方法的可行性和有效性,本文采用一个人工数据集,两个真实数据集以及一个带有真实错误的数据集在不同的异常率及数据量下对上述方法进行实验.由实验结果可知,相较于其他现存的修复方法,本文方法在修复结果及时间开销方面均有着较好的表现.进一步,本文对多个数据集通过聚类及分类精确率的验证来表明数据质量问题对后续数据分析及人工智能的影响至关重要,本方法可以提升数据分析及人工智能结果的质量.     

Clustering high dimensional data: A graph-based relaxed optimization approach

There is no doubt that clustering is one of the most studied data mining tasks. Nevertheless, it remains a challenging problem to solve despite the many proposed clustering approaches. Graph-based approaches solve the clustering task as a global optimization problem, while many other works are based on local methods. In this paper, we propose a novel graph-based algorithm “GBR” that relaxes some well-defined method even as improving the accuracy whilst keeping it simple. The primary motivation of our relaxation of the objective is to allow the reformulated objective to find well distributed cluster indicators for complicated data instances. This relaxation results in an analytical solution that avoids the approximated iterative methods that have been adopted in many other graph-based approaches. The experiments on synthetic and real data sets show that our relaxation accomplishes excellent clustering results. Our key contributions are: (1) we provide an analytical solution to solve the global clustering task as opposed to approximated iterative approaches; (2) a very simple implementation using existing optimization packages; (3) an algorithm with relatively less computation time over the number of data instances to cluster than other well defined methods in the literature.     

基于模体的目标区域网络拓扑划分方法

随着信息社会的发展,网络安全的重要性日益凸显,准确获取网络实体的地理位置有助于更好地实施网络管理。现有经典的基于拓扑启发式聚类的网络实体定位方法,采用基于网络结构的集群划分对网络实体进行聚类,由于没有考虑网络拓扑的具体特性,导致最后的结果误差较大。为解决这一问题,提出一种基于模体的目标区域网络拓扑划分方法。该方法根据目标网络拓扑呈现局部节点高聚类性的特点,创新性地引入"模体"的概念,在目标网络拓扑中挖掘模体结构并进行分析;然后借鉴复杂网络研究领域内局部社团发现方法中初始种子扩展的思路,以模体结构为初始种子进行相应扩展,将拓扑中与模体紧密相连的节点划分为多个集合;最后分别根据地标和公开的IP地理位置数据库对划分的节点集合进行定位,将集合的位置作为集合内节点的地理位置,从而实现网络实体的批量定位。基于香港和台湾两个地区网络拓扑的实验结果表明,该方法与经典的HC-Based方法、NNC方法相比,在网络实体定位准确率上分别能提高25%和16%左右,并且可批量定位的网络实体更多。     

采用离群点检测技术的混合型数据聚类初始化方法

近年来,混合型数据的聚类问题受到广泛关注。作为处理混合型数据的一种有效方法,K-prototype聚类算法在初始化聚类中心时通常采用随机选取的策略,然而这种策略在很多实际应用中难以保证聚类结果的质量。针对上述问题,采用基于离群点检测的策略来为K-prototype算法选择初始中心,并提出一种新的混合型数据聚类初始化算法(initialization of K-prototype clustering based on outlier detection and density, IKP-ODD)。给定一个候选对象,IKP-ODD通过计算其距离离群因子、加权密度以及与已有初始中心之间的加权距离来判断候选对象是否是一个初始中心。IKP-ODD通过采用距离离群因子和加权密度,防止选择离群点作为初始中心。在计算对象的加权密度以及对象之间的加权距离时,采用邻域粗糙集中的粒度邻域熵来计算每一个属性的重要性,并根据属性重要性的大小为不同属性赋予不同的权重,有效地反映不同属性之间的差异性。在多个UCI数据集上的实验表明,相对于现有的初始化方法,IKP-ODD能够更好地解决K-prototype聚类的初始化问题。     

Applied p-median and p-center algorithms for facility location problems

Facility location problems with the objective to minimize the sum of the setup cost and transportation cost are studied in this paper. The setup and transportation costs are considered as a function of the number of opened facilities. Three methods are introduced to solve the problem. The facility location model with bounds for the number of opened facility is constructed in this work. The relationship between setup cost and transportation cost is studied and used to build these methods based on greedy algorithm, p-median algorithm and p-center algorithm. The performance of the constructed methods is tested using 100 random data sets. In addition, the networks representing the road transportation system of Chiang Mai city and 5 provinces in Northern Thailand are illustrated and tested using all presented methods. Simulation results show that the method developed from greedy algorithm is suitable for solving problems when the setup cost is higher than transportation cost while the opposite cases are more efficiently solved with the method developed by the p-median problem.     

Capacity constrained maximizing bichromatic reverse nearest neighbor search

When planning a new development (facility/service site), location decisions are always the major issue. In this paper we introduce a novel query capacity constraint MaxBRNN, which can solve the facility location selection problem efficiently.The MaxBRNN (maximizing BRNN) query is based on bichromatic reverse nearest neighbor (BRNN) query which uses the number of reverse nearest customers to model the influence of a facility location. The MaxBRNN query has been appreciated extensively in spatial database studies because of its great potential in real life applications, such as, markets decision, sensor network clustering and the design of GSM (global system for mobile communication). The existing researches mostly suppose that the service facility's capacity is unlimited. However, in real cases, facilities are inevitably constrained by designed capacities. For example, if the government wants to select a new place to set up an emergency center to share the existing centers’ patients, they need to know the current emergency centers’ capacity so that they can estimate the new center's scale. Thus, the capacity constrained MaxBRNN query is significantly important in planning a new development. As far as we know, the capacity constrained MaxBRNN query has not been studied yet, so, we formulate this problem, propose a basic solution and develop some efficient algorithms for the query.Our major contributions are as follows: (1) we propose a novel query capacity constraint MaxBRNN which can solve the facility location selection problem effectively and efficiently; (2) we develop a basic algorithm CCMB and two improved algorithms which can find out the optimal region in terms of building a new facility, maximize its impact and deal with the complicated reassignment when adding new facilities into the dataset; (3) we prove the algorithms’ effectiveness and efficiency by extensive experiments using both real and synthetic data sets.     

一种基于位置语义和概率的人群分类方法

针对现有的人群分类方法忽略地理位置隐含的功能特征及其访问概率的问题,提出了一种基于位置语义和概率的人群分类方法。该方法主要包括位置语义发现和访问概率向量聚类两部分：首先,采用位置语义发现方法得到位置词汇所隐含的位置语义;其次根据位置语义分配情况获得移动用户对位置语义空间的访问概率向量;最后将其作为聚类分析的权向量,实现人群分类。实验结果表明,该方法提取出的位置语义与现实相符,得到的同类用户在位置语义空间的访问概率向量相似。与现有的人群分类方法相比,本文提出的人群分类方法F-measure值提高了4%,实验效果更优。     

Solving large immobile location–allocation by affinity propagation and simulated annealing. Application to select which sporting event to watch

Immobile Location-Allocation (ILA) is a combinatorial problem which consists in, given a set of facilities and a set of demand points, determining the optimal service each facility has to offer and allocating the demand to such facilities. The applicability of optimization methods is tied up to the dimensionality of the problem, but since the distance between data points is a key factor, clustering techniques to partition the data space can be applied, converting the large initial problem into several simpler ILA problems that can be solved separately. This paper presents a novel method that combines clustering and heuristic methods to solve an ILA problem, which reduces the elapsed time keeping the quality of the solution found compared with other heuristics methods.