تحقيق خوارزمية kMeans في Python

التجميع هو تعلم غير مساعد، يضع الأجسام المشابهة في نفس المجموعة، يشبه نوعاً ما تصنيف تلقائي، كلما كانت الأجسام داخل المجموعة متشابهة، كلما كانت الاختلافات بين الأجسام في المجموعات الأخرى أكبر، كلما كان تأثير التجميع أفضل.

خوارزمية التحصيل المتوسط

التحصيل المتوسط للمعجم يقسم البيانات إلى k مجموعات، ويصف كل مجموعة عن طريق مركزها، أي مركز جميع النقاط في المجموعة. أولاً، يتم تحديد كائنات بدائية كأعمدة مركزية، ثم يتم توزيع مجموعة البيانات على المجموعات الأقرب. ثم يتم تحديث مركز كل مجموعة إلى متوسط جميع البيانات. ثم يتم تقسيم مجموعة البيانات مرة أخرى، حتى لا تتغير نتائج التجميع.

البرنامج الخيالي هو

إنشاء كمراكز فصائل عشوائية k
عندما يحدث تغيير في توزيع الفصائل لأي نقطة:
　　　 للفترة لكل نقطة في مجموعة البيانات:
　　　　　　　 للفترة لكل مركز:
　　　　　　　　　　　 حساب المسافة بين مجموعة البيانات والمركز
　　　　　　　 توزيع مجموعة البيانات على الفصائل التي تكون الأقرب إلى المركز
　　　 للفترة لكل فصيلة، احسب المتوسط لكل نقطة في الفصيلة وأخذ المتوسط كنقطة مركزية

تنفيذ python

استيراد numpy كـ np
استيراد matplotlib.pyplot كـ plt
تعريف دالة loadDataSet(fileName): 
 dataMat = [] 
 مع فتح ملف fileName كـ f:
  للفترة في f.readlines():
   line = line.strip().split('\t')
   dataMat.append(line)
 dataMat = np.array(dataMat).astype(np.float32)
 يعود dataMat
تعريف دالة distEclud(vecA,vecB):
 يعود np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
 m = np.shape(dataSet)[1]
 center = np.mat(np.ones((k,m)))
 for i in range(m):
  centmin = min(dataSet[:,i])
  centmax = max(dataSet[:,i])
  center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
 return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroids = createCent(dataSet,k)
 clusterChanged = True
 while clusterChanged:
  clusterChanged = False
  for i in range(m):
   minDist = np.inf
   minIndex = -1
   for j in range(k):
    distJI = distMeans(dataSet[i,:],centroids[j,:])
    if distJI < minDist:
     minDist = distJI
     minIndex = j
   if clusterAssment[i,0] != minIndex:
    clusterChanged = True
   clusterAssment[i,:] = minIndex,minDist**2
  for cent in range(k):
   ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A == cent)[0]]
   centroids[cent,:] = np.mean(ptsInClust,axis = 0)
 return centroids,clusterAssment
data = loadDataSet('testSet.txt')
muCentroids, clusterAssing = kMeans(data,4)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A)
plt.show()
print(clusterAssing)

2- خوارزمية K-means الثنائية

قد يت收敛 خوارزمية K-means إلى أدنى القيم المحلية وليس أدنى القيم العالمية. إحدى مؤشرات قياس تأثير التجميع هي مجموع الأخطاء المربعة (SSE). لأننا نأخذ الصيغة الصحيحة، فإننا نعطي اهتماماً أكبر للنقاط القريبة من المركز. من أجل التغلب على مشكلة قد تت收敛 خوارزمية K-means إلى أدنى القيم المحلية، قدم بعض الباحثون خوارزمية K-means الثنائية.
أولاً، قم باتصال جميع النقاط كفصيلة واحدة، ثم قم بتقسيم هذه الفصيلة إلى نصفين، ثم اختر الفصيلة التي يمكن تقسيمها لتقليل SSE إلى أقصى حد، حتى تصل إلى عدد الفصائل المطلوب.

البرنامج الخيالي

اتصال جميع النقاط كفصيلة واحدة
حساب SSE
بينما يكون عدد الفصائل أقل من k:
　　　 للفترة لكل فصيلة:
　　　　　　　 حساب مجموع الأخطاء
　　　　　　　 تطبيق تحليل k-means على الفصيلة المقدمة (k=2)
　　　　　　　 حساب مجموع الأخطاء التي تحدث عند تقسيم الفصيلة إلى نصفين
　　　 اختيار الفصيلة التي تقلل من الخطأ إلى أقل حد ممكن

تنفيذ python

استيراد numpy كـ np
استيراد matplotlib.pyplot كـ plt
تعريف دالة loadDataSet(fileName): 
 dataMat = [] 
 مع فتح ملف fileName كـ f:
  للفترة في f.readlines():
   line = line.strip().split('\t')
   dataMat.append(line)
 dataMat = np.array(dataMat).astype(np.float32)
 يعود dataMat
تعريف دالة distEclud(vecA,vecB):
 يعود np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
 m = np.shape(dataSet)[1]
 center = np.mat(np.ones((k,m)))
 for i in range(m):
  centmin = min(dataSet[:,i])
  centmax = max(dataSet[:,i])
  center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
 return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroids = createCent(dataSet,k)
 clusterChanged = True
 while clusterChanged:
  clusterChanged = False
  for i in range(m):
   minDist = np.inf
   minIndex = -1
   for j in range(k):
    distJI = distMeans(dataSet[i,:],centroids[j,:])
    if distJI < minDist:
     minDist = distJI
     minIndex = j
   if clusterAssment[i,0] != minIndex:
    clusterChanged = True
   clusterAssment[i,:] = minIndex,minDist**2
  for cent in range(k):
   ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A == cent)[0]]
   centroids[cent,:] = np.mean(ptsInClust,axis = 0)
 return centroids,clusterAssment
def biKmeans(dataSet,k,distMeans = distEclud):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroid0 = np.mean(dataSet,axis=0).tolist()
 centList = [centroid0]
 for j in range(m):
  clusterAssment[j,1] = distMeans(dataSet[j,:],np.mat(centroid0))**2
 while (len(centList)<k):
  lowestSSE = np.inf
  for i in range(len(centList)):
   ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A == i)[0],:]
   centroidMat,splitClustAss = kMeans(ptsInCurrCluster,2,distMeans)
   sseSplit = np.sum(splitClustAss[:,1])
   sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A != i)[0],1])
   if (sseSplit + sseNotSplit) < lowestSSE:
    bestCentToSplit = i
    bestNewCents = centroidMat.copy()
    bestClustAss = splitClustAss.copy()
    lowestSSE = sseSplit + sseNotSplit
  print('the best cent to split is ',bestCentToSplit)
#  print('the len of the bestClust')
  bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
  bestClustAss[np.nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
  clusterAssment[np.nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss.copy()
  centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
  centList.append(bestNewCents[1,:].tolist()[0])
 return np.mat(centList),clusterAssment
data = loadDataSet('testSet2.txt')
muCentroids, clusterAssing = biKmeans(data,3)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A,cmap=plt.cm.Paired)
ax.scatter(muCentroids[:,0],muCentroids[:,1])
plt.show()
print(clusterAssing)
print(muCentroids)

تحميل الشيفرة والمجموعة البيانية:كما أنس

هذا هو نهاية محتويات هذا المقال، نأمل أن تكون قد ساعدتكم في التعلم، ونأمل أن تشجعوا دائمًا على دعم دليل التدريب.

بيان: محتويات هذا المقال تم جمعها من الإنترنت، ملكية المحتويات تتبع المالك الأصلي، المحتويات قدمت من قبل مستخدمي الإنترنت الذين قاموا بتحميلها بشكل تلقائي، هذا الموقع لا يملك حقوق الملكية، لم يتم تعديل المحتويات بشكل يدوي، ولا يتحمل أي مسؤولية قانونية متعلقة بذلك. إذا كنت قد وجدت محتويات مشكوك فيها فيما يتعلق بالحقوق الطبع والنشر، فيرجى إرسال بريد إلكتروني إلى: notice#oldtoolbag.com (يرجى استبدال # ب @ عند إرسال البريد الإلكتروني) لإبلاغنا، وقدم أدلة الدليل المتعلقة بالمشكلة، إذا تم التحقق من ذلك، سيتم حذف المحتويات المشكوك فيها على الفور.