[發明專利]一種基于Elkan算法在小分類中的改進方法

在審

• 申請號: 201710556383.4
• 申請日: 2017-07-10
• 公開（公告）號: CN107506784A
• 公開（公告）日: 2017-12-22
• 發明（設計）人: 匡振曦;陳平華
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廣東廣信君達律師事務所44329
• 代理人: 楊曉松

1.一種基于Elkan算法在小分類中的改進方法，具體按照以下步驟實施：

步驟0：采集數據；

步驟1：初始化質心；

步驟2：初始化每點屬于哪個質心；

步驟3：循環判斷每點屬于哪個質心。

2.基于權利要求1所述的改進方法，其特征在于：所述步驟0具體按照以下步驟實施：導入任意數據集，而且數據集的維度是在小于50維和分類個數小于20個。

3.基于權利要求2所述的改進方法，其特征在于：所述步驟1具體按照以下步驟實施：

首先利用已存在的k-means++初始化質心的方法生成k個質心，然后對是否收斂converge變量賦值為False，用于記錄每個點屬于哪個質心的變量assignment[n+1]初始化為-1，用于記錄每個質心有那幾個點的指針變量int**sumc初始化為NULL。

4.基于權利要求3所述的改進方法，其特征在于：所述步驟2具體按照以下步驟實施：

利用兩層for循環計算分別每點與所有質心的距離d，在第二層循環里就能利用if判斷出每點的上界u[x]和每點與所有質心的下界l[x][i]，跳出第二層循環就能將最近的質心索引賦值給每點的assignment變量，同時利用雙重指針在相應的質心c[i]的索引下添加點x[j]，到此第一次初始化點與質心間的關系結束。

5.基于權利要求4所述的改進方法，其特征在于：所述步驟3具體按照以下步驟實施：

當第一層for循環下i：1->n，首先使用兩層for循環，對每個質心間的距離逐一計算，用s[i][j]存儲這個距離，當i≠j時會得出一個最小值s_small＝1/2min(s[i][j])，判斷u(x)是否小于s_small，若小于則continue，因此下面循環不用再做；遍歷屬于c[i]的所有數據點，得到之間距離最大的距離m(c[i])；

然后第二層for循環，j：1->k，先用u(x)+d(c[i],x[j])≤1/2max(s[i][j])來判斷是否需要遍歷質心c[j]，若滿足再判斷u[i]<＝l[i][j])||u[i]<＝centerCenterDistDiv2[closest*k+j])，然后對u[i]＝sqrt(pointCenterDist2(i,closest))和l[i][closest]重新計算一遍，再判斷一遍u[i]<＝l[i][j])||u[i]<＝centerCenterDistDiv2[closest*k+j])，若還滿足則說明可能無法利用三角不等式避免計算點與其他質心間的距離，我們需要計算l[i][j]＝d(x[i],c[j])對點與所分配質心的實際距離。然后再判斷l[i][j]<upper[i]，若滿足則就要計算closet＝j,upper[i]＝l[i][j]，同時需要對數據點屬于哪個質心進行重新分配changeAssignment(i,closest)；

第三步利用循環每個質心的sumc[i]變量，xi＝(1/length(sumc[i]))求和x，更新k個質心的位置，并記錄每個質心移動的距離p[i]；

第四步，然后用一個for循環i：1->n，更新u[i]＝u[i]+p[assignment[i]]，和l[i]＝l[i]-p[r]來更新邊界；

重復第二，三，四步直到最大循環次數iterations或者收斂變量converge＝True則跳出循環，則標志著k個簇已經分好。