数据挖掘中聚类中心问题的光滑化和填充函数方法

《数据挖掘中聚类中心问题的光滑化和填充函数方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y907733中圈分类号：022l单位代号：11903密级=学号：03720791●——--———————●——-—_叫—--——_·--_l。_l一上海大学⑧硕士学位论文。_。。-_。——’_。—●-—-____●---_--一●。SHANGHAIUNIVERSITYMASTER’SDissertation题’{数据挖掘中聚类中心问题目f的光滑化和填充函数方法作者学科专业祝丽华—。。--。___●。‘‘—__●。__●●-。__●—-—。●一系统分析与集成导痧塾坐堕夔攮完成日期2006，5摘要聚类中心问题是数据挖掘中一类重要问题，它可以定义为

2、在整个空间中的无约束全局最优化问题．由于这类问题在信息获得，文件获取及图象分块等生产和生活中有着十分广泛的应用，因此研究聚类中心问题的算法具有重要的现实意义．本文所讨论的聚类中心问题可以描述如下；(_P)蛐他1，⋯㈣=去薹。磐一妒训2st．z=(z1，．．，z。)∈Ⅱ≈“。9．这里，z·，⋯，一是g个要求的聚类中心，m是数据个数，ni∈Rn是数据库中的第i个数据．由于目标函数，(z)是非凸非光滑函数，所以问题(J))是非光滑全局优化问题，设计求解(_7))的全局最优解的算法具有极大的挑战性．本文根据问题(P)的结构特点，提出了先利用光滑化方法将

3、，(z)用光滑函数逼近，然后对光滑化问题利用填充函数搜索其全局最优点的方法．我们对不同的数据库进行了数值试验，数值结果表明，本文提出的算法对求解问题(P)是可行和有效的．本文总共分为四章，第一章简单地介绍了数据挖掘及聚类的概念，以及聚类中心问题的模型．第二章简单介绍了求解聚类中心问题的现有算法：分层聚类算法，分块聚类算法，k最临近算法，进化算法以及模拟退火法等等．第三章是本文的主要结果，我们提出了一种新的光滑化和填充函数方法求解聚类中心问题，并给出了数值试验结果，第四章总结了本文的主要结果并对未来的研究进行了展望．关键词：数据挖掘，聚类中心，全

4、局优化，光滑化函数，逐步求中心法，填充函数法AbstractClusteringcenterpr。blemisanimport村ltclassofDataMillingprogr锄mingproblemswhichcanbede丘nedastheminimizationofanunconstrainteddob出function．DuetoitswideapplicationsininformatiOnretrie州，矗leextracting，objectandcharacterrecognitionandimagesegmentation，

5、iti80fgreatiIlteresttostudydusteringceⅡterproblems．Aclusteringcenterproble珊canbeexpressedasfbl】ows：(』=))minm1⋯∽=去耋。璺划扎州7n，。，s=l，，口s．tz=(z1，．．．，z9)∈R”。g．wherez1，，．．，zqaren—dimensionalvariablerepresentingtheceⅡtersofthe口clus—ters，misthenumberofdata，n。∈R“isthei—thpointindatabaS

6、e．sincetheobjectivefunction，(茁)isnonconvexandnonsmooth，theprob．1em(P)isanonsmoothglobalopti】11iza七ionproblemInthisthesis，weproposeasmoothingandflⅡedfunctionmethodfor(P)byexploitingthespecialstructureofth8problem，weproposeasmoothjngandoftheproblem．Usingthesmooth_ingfIlnction，

7、weappr似imatethenonsm00thnonconvexobjectivefunctionbyasmoothfunctionFilledfunctionmethodisthenadoptedto8earchforaglo—be】optjmalsolutionof亡he印pro](imationpr。blemNumeric缸experimeⅡtsondiflbreIltd础abase盯ereported如rtheproposedmethod．Thethesisisorganizedasfollaws．InChapter1，we百veso

8、mebriefintr0．ductionofDataMiningandclusteringcenterproblem．Somegeneralmetho