搜索
迭代自组织数据分析算法迭代自组织数据分析算法（IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm，ISODATA）与K均值算法有相似之处，即聚类中心的位置同样是通过样本均值的迭代运算决定。不同的是，这种算法在运算的过程中聚类中心数目不是固定不变的，而是反复进行修改，以得到较合理的类别数K，这种修改通过模式类的合并和分裂来实现，合并和分裂在一组预先选定的参数指导下进行。ISODATA的特点是计算简单，适用于识别致密聚类。合并主要发生在某一类声样本数较少的情况下，或者两类声样本聚类中心之间距离太小的情况。为此，需要指定每一类中最少样本数和两类聚类中心之间的最小距离参数。类分裂主要发生在某一类的某分量出现类内方差过大的现象时，适合将其分裂成两类，使类内方差比较合理。为此，需要指定类内某个分量方差的参数，用以决定是否需要将某一类分裂成两类。ISODATA具体算法如下：设有N个模式样本12,,...,NXXX；K——期望的聚类中心数；Nθ——每一类中至少应包含的样本数；sθ——类内样本标准差阈值；cθ——两个聚类中心之间的最小距离阈值；L——一次迭代中允许合并的最多对数；I——允许迭代的次数。5.2.1算法流程详细的算法流程如下：第一步：任选c个聚类中心；定义算法参数12(1),(1),...,(1)czzz,,,,,NScKLIθθθ。其中c不要求等于希望的聚类中心数K。第二步：分配N个样本按最近邻规则分配到c个聚类中。若||||||||ijxzxz−−，，则1,2,...,,ici=≠jixX∈，其中iX表示分类到聚类中心的样本子集，为iziNiX中样本个数。第三步：若iNNθ，则去除iX，使1cc=−，也就是将样本数比Nθ少的样本子集删去。第四步：修正各聚类中心：iz1,1,2,...,iixXzxiN∈==∑c第五步：计算iX中样本与各聚类中心间的平均距离：1||||,1,2,...,iiixXidxziN∈=−=∑c第六步：计算总体的平均距离：1111||||icciiixXidxzNN=∈==−=∑∑∑iNd其中N为样本集中样本总数。第七步：判断分裂、合并及迭代运算步骤。（1）若迭代已达I次，置0cθ=，转到第十一步，算法结束。（2）若/2cK≤，即聚类中心小于或等于希望数的一半，转到第八步，将已有类分裂；（3）若迭代次数是偶数，或2cK≥，即聚类中心数目大于期望数的两倍，则转到第十一步，进行合并处理。（4）若（2）和（3）不满足则继续，转入第八步。第八步：计算每个聚类中样本距离的标准差向量。对第iX类有T12[,,...,],1,2,...,iiiinicσσσσ==其中各分量为()21,1,2,...,iijijijxXixzjNσ∈=−=∑n式中，n是样本维数，即ix是n维模式向量；ijx是iX类样本ix的第j个分量，是ijziX类聚类中心的第j个分量，所以izijσ是ix的第i个分量的标准差。第九步：求出iσ中最大分量max,1,2,...,iicσ=。第十步：若maxisσθ，，同时满足以下条件之一：1,2,...,i=c（1）idd和，即类内平均距离大于总体平均距离，并且(2iNNθ+)1iX类样本数过大；（2），即聚类数小于等于期望数的一半；/2cK≤则将iX分成两个新的聚类中心，iz+和iz−，删去，并使iz1cc=+。其中iz+这样构成：中对应izmaxiσ的分量加上maxiασ；iz−这样构成：中对应izmaxiσ的分量减去maxiασ；其中01α≤；选择α的基本要求是，使任意样本到这两个新的聚类中心和iz+iz−之间有一个足够可检测的距离差别，但又不能太大。如果完成分裂，则迭代次数加1，1ll=+，转到第二步。否则继续进行第十一步。第十一步：计算全部聚类中心的两两距离：ijd||||,;,1,2,...,ijijdzzijij=−≠=c第十二步：比较；如果ijcdθ，转到第十四步；否则如果ijcdθ，将ijcdθ的值升序排列，即，11ijiiljlddd22...jlL。第十三步：从开始，逐对合并，算出新的聚类中心：11ijd*1,1,2,...,lililjljliljlzNzNzlNN⎡⎤=+=⎣⎦+L删去和，并使。注意，只允许一对对合并，并且一个聚类中心只能合并一次。ilzjlz1cc=−第十四步：迭代处理；若是最后一次迭代，lI=，算法结束。否则有两种情况：（1）不修改参数，1ll=+，转到第二步；（2）需要人工输入参数，1ll=+，转到第一步。