بایگانی برچسب برای: hg’

الگوریتم Canny

لبه یاب کنی توسط جان اف کنی در سال 1986 ایجاد شد و هنوز یک لبه یاب استاندارد و با دقت و کیفیت بالا میباشد.الگوریتم لبه یابی کنی یکی از بهترین لبه یابها تا به امروز است. در ادامه روش کار این الگوریتم و هم چنین کد الگوریتم Canny در C را بررسی خواهیم کرد. این الگوریتم لبه یابی از سه بخش اصلی زیر تشکیل شده است:

  • تضعیف نویز
  • پیدا کردن نقاطی که بتوان آنها را به عنوان لبه در نظر گرفت
  • جذب نقاطی که احتمال لبه بودن آنها کم است

 

معیارهایی که در لبه یاب کنی مطرح می باشد:
1 -پایین آوردن نرخ خطا- یعنی تا حد امکان هیچ لبه ای در تصویر نباید گم شود و هم چنین هیچ چیزی که لبه نیست نباید به جای لبه فرض شود. لبه هان پیدا شده تا حد ممکن به لبه ها اصلی
نزدیک باشند.

2 -لبه در مکان واقعی خود باشد- یعنی تا حد ممکن لبه ها کمترین فاصله را با مکان واقعی خود داشته باشند.
3 -بران هر لبه فقط یک پاسخ داشته باشیم.

4 -لبه ها کمترین ضخامت را داشته باشند- (در صورت امکان یک پیکسل).
لبه یاب کنی بخاطر توانایی در تولید لبه های نازک تا حد یک ییکسل برای لبه های پیوسته معروف شده است. این لبه یاب شامل چهار مرحله و چهار ورودی زیر است:
یک تصویر ورودی
یک پارامتر به نام سیگما جهت مقدار نرم کنندگی تصویر
یک حد آستانه بالا (Th)
یک حد آستانه پایین (Tl)

 

مراحل الگوریتم Canny:

1- در ابتدا باید تصویر رنگی را به جهت لبه یابی بهتر به یک تصویر سطح خاکسترن تبدیب کرد.

2- نویز را از تصویر دریافتی حذف کرد. بدلیل اینکه فیلتر گاوسین از یک ماسک ساده برای حذف نویز استفاده می کند لبه یاب کنی در مرحله اول برای حذف نویز آن را بکار می گیرد.

3- در یک تصویر سطح خاکستر جایی را که بیشترین تغییرات را داشته باشند به عنوان لبه در نظر گرفته می شوند و این مکانها با گرفتن گرادیان تصویر با استفاده عملگر سوبل بدست می آیند. سپس لبه های مات یافت شده به لبه های تیزتر تبدیل می شوند.

4- برخی از لبه های کشف شده واقعا لبه نیستند و در واقع نویز هستند که باید آنها توسط حد آستانه هیسترزیس فیلتر شوند.هیسترزیس از دو حد آستانه بالاتر (Th) و حد آستانه پایین تر (Tl) استفاده کرده و کنی پیشنهاد می کند که نسبت استانه بالا به پایین سه به یک باشد.

 این روش بیشتر به کشف لبه های ضعیف به درستی می پردازد و کمتر فریب نویز را می خورد و از بقیه روش ها بهتر است.

 

الگوریتم Canny    عملکرد الگوریتم Canny

 

 

کد الگوریتم Canny در C :

برنامه زیر یک فایل BMP سیاه و سفید 8 بیت در هر پیکسل را می خواند و نتیجه را در ‘out.bmp’ ذخیره می کند.با `-lm ‘ کامپایل می شود.

 

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
 
#define MAX_BRIGHTNESS 255
 
// C99 doesn't define M_PI (GNU-C99 does)
#define M_PI 3.14159265358979323846264338327
 
/*
 * Loading part taken from
 * http://www.vbforums.com/showthread.php?t=261522
 * BMP info:
 * http://en.wikipedia.org/wiki/BMP_file_format
 *
 * Note: the magic number has been removed from the bmpfile_header_t
 * structure since it causes alignment problems
 * bmpfile_magic_t should be written/read first
 * followed by the
 * bmpfile_header_t
 * [this avoids compiler-specific alignment pragmas etc.]
 */
 
typedef struct {
 uint8_t magic[2];
} bmpfile_magic_t;
 
typedef struct {
 uint32_t filesz;
 uint16_t creator1;
 uint16_t creator2;
 uint32_t bmp_offset;
} bmpfile_header_t;
 
typedef struct {
 uint32_t header_sz;
 int32_t width;
 int32_t height;
 uint16_t nplanes;
 uint16_t bitspp;
 uint32_t compress_type;
 uint32_t bmp_bytesz;
 int32_t hres;
 int32_t vres;
 uint32_t ncolors;
 uint32_t nimpcolors;
} bitmap_info_header_t;
 
typedef struct {
 uint8_t r;
 uint8_t g;
 uint8_t b;
 uint8_t nothing;
} rgb_t;
 
// Use short int instead `unsigned char' so that we can
// store negative values.
typedef short int pixel_t;
 
pixel_t *load_bmp(const char *filename,
 bitmap_info_header_t *bitmapInfoHeader)
{
 FILE *filePtr = fopen(filename, "rb");
 if (filePtr == NULL) {
 perror("fopen()");
 return NULL;
 }
 
 bmpfile_magic_t mag;
 if (fread(&mag, sizeof(bmpfile_magic_t), 1, filePtr) != 1) {
 fclose(filePtr);
 return NULL;
 }
 
 // verify that this is a bmp file by check bitmap id
 // warning: dereferencing type-punned pointer will break
 // strict-aliasing rules [-Wstrict-aliasing]
 if (*((uint16_t*)mag.magic) != 0x4D42) {
 fprintf(stderr, "Not a BMP file: magic=%c%c\n",
 mag.magic[0], mag.magic[1]);
 fclose(filePtr);
 return NULL;
 }
 
 bmpfile_header_t bitmapFileHeader; // our bitmap file header
 // read the bitmap file header
 if (fread(&bitmapFileHeader, sizeof(bmpfile_header_t),
 1, filePtr) != 1) {
 fclose(filePtr);
 return NULL;
 }
 
 // read the bitmap info header
 if (fread(bitmapInfoHeader, sizeof(bitmap_info_header_t),
 1, filePtr) != 1) {
 fclose(filePtr);
 return NULL;
 }
 
 if (bitmapInfoHeader->compress_type != 0)
 fprintf(stderr, "Warning, compression is not supported.\n");
 
 // move file point to the beginning of bitmap data
 if (fseek(filePtr, bitmapFileHeader.bmp_offset, SEEK_SET)) {
 fclose(filePtr);
 return NULL;
 }
 
 // allocate enough memory for the bitmap image data
 pixel_t *bitmapImage = malloc(bitmapInfoHeader->bmp_bytesz *
 sizeof(pixel_t));
 
 // verify memory allocation
 if (bitmapImage == NULL) {
 fclose(filePtr);
 return NULL;
 }
 
 // read in the bitmap image data
 size_t pad, count=0;
 unsigned char c;
 pad = 4*ceil(bitmapInfoHeader->bitspp*bitmapInfoHeader->width/32.) - bitmapInfoHeader->width;
 for(size_t i=0; i<bitmapInfoHeader->height; i++){
 for(size_t j=0; j<bitmapInfoHeader->width; j++){
 if (fread(&c, sizeof(unsigned char), 1, filePtr) != 1) {
 fclose(filePtr);
 return NULL;
 }
 bitmapImage[count++] = (pixel_t) c;
 }
 fseek(filePtr, pad, SEEK_CUR);
 }
 
 // If we were using unsigned char as pixel_t, then:
 // fread(bitmapImage, 1, bitmapInfoHeader->bmp_bytesz, filePtr);
 
 // close file and return bitmap image data
 fclose(filePtr);
 return bitmapImage;
}
 
// Return: true on error.
bool save_bmp(const char *filename, const bitmap_info_header_t *bmp_ih,
 const pixel_t *data)
{
 FILE* filePtr = fopen(filename, "wb");
 if (filePtr == NULL)
 return true;
 
 bmpfile_magic_t mag = {{0x42, 0x4d}};
 if (fwrite(&mag, sizeof(bmpfile_magic_t), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 
 const uint32_t offset = sizeof(bmpfile_magic_t) +
 sizeof(bmpfile_header_t) +
 sizeof(bitmap_info_header_t) +
 ((1U << bmp_ih->bitspp) * 4);
 
 const bmpfile_header_t bmp_fh = {
 .filesz = offset + bmp_ih->bmp_bytesz,
 .creator1 = 0,
 .creator2 = 0,
 .bmp_offset = offset
 };
 
 if (fwrite(&bmp_fh, sizeof(bmpfile_header_t), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 if (fwrite(bmp_ih, sizeof(bitmap_info_header_t), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 
 // Palette
 for (size_t i = 0; i < (1U << bmp_ih->bitspp); i++) {
 const rgb_t color = {(uint8_t)i, (uint8_t)i, (uint8_t)i};
 if (fwrite(&color, sizeof(rgb_t), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 }
 
 // We use int instead of uchar, so we can't write img
 // in 1 call any more.
 // fwrite(data, 1, bmp_ih->bmp_bytesz, filePtr);
 
 // Padding: http://en.wikipedia.org/wiki/BMP_file_format#Pixel_storage
 size_t pad = 4*ceil(bmp_ih->bitspp*bmp_ih->width/32.) - bmp_ih->width;
 unsigned char c;
 for(size_t i=0; i < bmp_ih->height; i++) {
 for(size_t j=0; j < bmp_ih->width; j++) {
 c = (unsigned char) data[j + bmp_ih->width*i];
 if (fwrite(&c, sizeof(char), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 }
 c = 0;
 for(size_t j=0; j<pad; j++)
 if (fwrite(&c, sizeof(char), 1, filePtr) != 1) {
 fclose(filePtr);
 return true;
 }
 }
 
 fclose(filePtr);
 return false;
}
 
// if normalize is true, map pixels to range 0..MAX_BRIGHTNESS
void convolution(const pixel_t *in, pixel_t *out, const float *kernel,
 const int nx, const int ny, const int kn,
 const bool normalize)
{
 assert(kn % 2 == 1);
 assert(nx > kn && ny > kn);
 const int khalf = kn / 2;
 float min = FLT_MAX, max = -FLT_MAX;
 
 if (normalize)
 for (int m = khalf; m < nx - khalf; m++)
 for (int n = khalf; n < ny - khalf; n++) {
 float pixel = 0.0;
 size_t c = 0;
 for (int j = -khalf; j <= khalf; j++)
 for (int i = -khalf; i <= khalf; i++) {
 pixel += in[(n - j) * nx + m - i] * kernel;
 c++;
 }
 if (pixel < min)
 min = pixel;
 if (pixel > max)
 max = pixel;
 }
 
 for (int m = khalf; m < nx - khalf; m++)
 for (int n = khalf; n < ny - khalf; n++) {
 float pixel = 0.0;
 size_t c = 0;
 for (int j = -khalf; j <= khalf; j++)
 for (int i = -khalf; i <= khalf; i++) {
 pixel += in[(n - j) * nx + m - i] * kernel;
 c++;
 }
 
 if (normalize)
 pixel = MAX_BRIGHTNESS * (pixel - min) / (max - min);
 out[n * nx + m] = (pixel_t)pixel;
 }
}
 
/*
 * gaussianFilter:
 * http://www.songho.ca/dsp/cannyedge/cannyedge.html
 * determine size of kernel (odd #)
 * 0.0 <= sigma < 0.5 : 3
 * 0.5 <= sigma < 1.0 : 5
 * 1.0 <= sigma < 1.5 : 7
 * 1.5 <= sigma < 2.0 : 9
 * 2.0 <= sigma < 2.5 : 11
 * 2.5 <= sigma < 3.0 : 13 ...
 * kernelSize = 2 * int(2*sigma) + 3;
 */
void gaussian_filter(const pixel_t *in, pixel_t *out,
 const int nx, const int ny, const float sigma)
{
 const int n = 2 * (int)(2 * sigma) + 3;
 const float mean = (float)floor(n / 2.0);
 float kernel[n * n]; // variable length array
 
 fprintf(stderr, "gaussian_filter: kernel size %d, sigma=%g\n",
 n, sigma);
 size_t c = 0;
 for (int i = 0; i < n; i++)
 for (int j = 0; j < n; j++) {
 kernel = exp(-0.5 * (pow((i - mean) / sigma, 2.0) +
 pow((j - mean) / sigma, 2.0)))
 / (2 * M_PI * sigma * sigma);
 c++;
 }
 
 convolution(in, out, kernel, nx, ny, n, true);
}
 
/*
 * Links:
 * http://en.wikipedia.org/wiki/Canny_edge_detector
 * http://www.tomgibara.com/computer-vision/CannyEdgeDetector.java
 * http://fourier.eng.hmc.edu/e161/lectures/canny/node1.html
 * http://www.songho.ca/dsp/cannyedge/cannyedge.html
 *
 * Note: T1 and T2 are lower and upper thresholds.
 */
pixel_t *canny_edge_detection(const pixel_t *in,
 const bitmap_info_header_t *bmp_ih,
 const int tmin, const int tmax,
 const float sigma)
{
 const int nx = bmp_ih->width;
 const int ny = bmp_ih->height;
 
 pixel_t *G = calloc(nx * ny * sizeof(pixel_t), 1);
 pixel_t *after_Gx = calloc(nx * ny * sizeof(pixel_t), 1);
 pixel_t *after_Gy = calloc(nx * ny * sizeof(pixel_t), 1);
 pixel_t *nms = calloc(nx * ny * sizeof(pixel_t), 1);
 pixel_t *out = malloc(bmp_ih->bmp_bytesz * sizeof(pixel_t));
 
 if (G == NULL || after_Gx == NULL || after_Gy == NULL ||
 nms == NULL || out == NULL) {
 fprintf(stderr, "canny_edge_detection:"
 " Failed memory allocation(s).\n");
 exit(1);
 }
 
 gaussian_filter(in, out, nx, ny, sigma);
 
 const float Gx[] = {-1, 0, 1,
 -2, 0, 2,
 -1, 0, 1};
 
 convolution(out, after_Gx, Gx, nx, ny, 3, false);
 
 const float Gy[] = { 1, 2, 1,
 0, 0, 0,
 -1,-2,-1};
 
 convolution(out, after_Gy, Gy, nx, ny, 3, false);
 
 for (int i = 1; i < nx - 1; i++)
 for (int j = 1; j < ny - 1; j++) {
 const int c = i + nx * j;
 // G = abs(after_Gx) + abs(after_Gy);
 G = (pixel_t)hypot(after_Gx, after_Gy);
 }
 
 // Non-maximum suppression, straightforward implementation.
 for (int i = 1; i < nx - 1; i++)
 for (int j = 1; j < ny - 1; j++) {
 const int c = i + nx * j;
 const int nn = c - nx;
 const int ss = c + nx;
 const int ww = c + 1;
 const int ee = c - 1;
 const int nw = nn + 1;
 const int ne = nn - 1;
 const int sw = ss + 1;
 const int se = ss - 1;
 
 const float dir = (float)(fmod(atan2(after_Gy,
 after_Gx) + M_PI,
 M_PI) / M_PI) * 8;
 
 if (((dir <= 1 || dir > 7) && G > G[ee] &&
 G > G[ww]) || // 0 deg
 ((dir > 1 && dir <= 3) && G > G[nw] &&
 G > G[se]) || // 45 deg
 ((dir > 3 && dir <= 5) && G > G[nn] &&
 G > G[ss]) || // 90 deg
 ((dir > 5 && dir <= 7) && G > G[ne] &&
 G > G[sw])) // 135 deg
 nms = G;
 else
 nms = 0;
 }
 
 // Reuse array
 // used as a stack. nx*ny/2 elements should be enough.
 int *edges = (int*) after_Gy;
 memset(out, 0, sizeof(pixel_t) * nx * ny);
 memset(edges, 0, sizeof(pixel_t) * nx * ny);
 
 // Tracing edges with hysteresis . Non-recursive implementation.
 size_t c = 1;
 for (int j = 1; j < ny - 1; j++)
 for (int i = 1; i < nx - 1; i++) {
 if (nms >= tmax && out == 0) { // trace edges
 out = MAX_BRIGHTNESS;
 int nedges = 1;
 edges[0] = c;
 
 do {
 nedges--;
 const int t = edges[nedges];
 
 int nbs[8]; // neighbours
 nbs[0] = t - nx; // nn
 nbs[1] = t + nx; // ss
 nbs[2] = t + 1; // ww
 nbs[3] = t - 1; // ee
 nbs[4] = nbs[0] + 1; // nw
 nbs[5] = nbs[0] - 1; // ne
 nbs[6] = nbs[1] + 1; // sw
 nbs[7] = nbs[1] - 1; // se
 
 for (int k = 0; k < 8; k++)
 if (nms[nbs[k]] >= tmin && out[nbs[k]] == 0) {
 out[nbs[k]] = MAX_BRIGHTNESS;
 edges[nedges] = nbs[k];
 nedges++;
 }
 } while (nedges > 0);
 }
 c++;
 }
 
 free(after_Gx);
 free(after_Gy);
 free(G);
 free(nms);
 
 return out;
}
 
int main(const int argc, const char ** const argv)
{
 if (argc < 2) {
 printf("Usage: %s image.bmp\n", argv[0]);
 return 1;
 }
 
 static bitmap_info_header_t ih;
 const pixel_t *in_bitmap_data = load_bmp(argv[1], &ih);
 if (in_bitmap_data == NULL) {
 fprintf(stderr, "main: BMP image not loaded.\n");
 return 1;
 }
 
 printf("Info: %d x %d x %d\n", ih.width, ih.height, ih.bitspp);
 
 const pixel_t *out_bitmap_data =
 canny_edge_detection(in_bitmap_data, &ih, 45, 50, 1.0f);
 if (out_bitmap_data == NULL) {
 fprintf(stderr, "main: failed canny_edge_detection.\n");
 return 1;
 }
 
 if (save_bmp("out.bmp", &ih, out_bitmap_data)) {
 fprintf(stderr, "main: BMP image not saved.\n");
 return 1;
 }
 
 free((pixel_t*)in_bitmap_data);
 free((pixel_t*)out_bitmap_data);
 return 0;
}

 

دانلود کد فوق از طریق لینک زیر:

Canny in C

رمز فایل : behsanandish.com

الگوریتم Canny

لبه یاب کنی توسط جان اف کنی در سال 1986 ایجاد شد و هنوز یک لبه یاب استاندارد و با دقت و کیفیت بالا میباشد.الگوریتم لبه یابی کنی یکی از بهترین لبه یابها تا به امروز است. در ادامه روش کار این الگوریتم و هم چنین کد الگوریتم Canny در Visual Basic را بررسی خواهیم کرد. این الگوریتم لبه یابی از سه بخش اصلی زیر تشکیل شده:

  • تضعیف نویز
  • پیدا کردن نقاطی که بتوان آنها را به عنوان لبه در نظر گرفت
  • حذب نقاطی که احتمال لبه بودن آنها کم است

 

معیارهایی که در لبه یا کنی مطرح است:
1 -پایین آوردن نرخ خطا- یعنی تا حد امکان هیچ لبه ای در تصویر نباید گم شود و هم چنین هیچ چیزی که لبه نیست نباید به جای لبه فرض شود. لبه هان پیدا شده تا حد ممکن به لبه ها اصلی
نزدیک باشند.

2 -لبه در مکان واقعی خود باشد- یعنی تا حد ممکن لبه ها کمترین فاصله را با مکان واقعی خود داشته باشند.
3 -بران هر لبه فقط یک پاسخ داشته باشیم.

4 -لبه ها کمترین ضخامت را داشته باشند- (در صورت امکان یک پیکسل).
لبه یاب کنی بخاطر توانایی در تولید لبه های نازک تا حد یک ییکسل برای لبه های پیوسته معروف شده است. این لبه یاب شامل چهار مرحله و چهار ورودی زیر است:
یک تصویر ورودی
یک پارامتر به نام سیگما جهت مقدار نرم کنندگی تصویر
یک حد آستانه بالا (Th)
یک حد آستانه پایین (Tl)

 

مراحل الگوریتم Canny:

1- در ابتدا باید تصویر رنگی را به جهت لبه یابی بهتر به یک تصویر سطح خاکسترن تبدیب کرد.

2- نویز را از تصویر دریافتی حذف کرد. بدلیل اینکه فیلتر گاوسین از یک ماسک ساده برای حذف نویز استفاده می کند لبه یاب کنی در مرحله اول برای حذف نویز آن را بکار میگیرد.

3- در یک تصویر سطح خاکستر جایی را که بیشترین تغییرات را داشته باشند به عنوان لبه در نظر گرفته می شوند و این مکانها با گرفتن گرادیان تصویر با استفاده عملگر سوبل بدست می آیند. سپس لبه های مات یافت شده به لبه های تیزتر تبدیل می شوند.

4- برخی از لبه های کشف شده واقعا لبه نیستند و در واقع نویز هستند که باید آنها توسط حد آستانه هیسترزیس فیلتر شوند.هیسترزیس از دو حد آستانه بالاتر (Th) و حد آستانه پایین تر (Tl) استفاده کرده و کنی پیشنهاد می کند که نسبت استانه بالا به پایین سه به یک باشد.

 این روش بیشتر به کشف لبه های ضعیف به درستی می پردازد و کمتر فریب نویز را می خورد و از بقیه روش ها بهتر است.

 

الگوریتم Canny    عملکرد الگوریتم Canny

 

الگوریتم Canny در Visual Basic:

کد زیر یک کد تکمیل نشده است.تکمیل آن به عنوان تمرین به خواننده واگذار می شود.

 

Imports System.Drawing
Imports System.Drawing.Imaging

Public Class clsEdges

    Public Sub EdgeDetectDifference(ByVal b As Bitmap, ByVal threshold As Byte)
        ' first we create a clone o the image we want to find the edges on
        Dim b2 As Bitmap = b.Clone
        ' we create bitmapdata of the images at the same time locking them
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        ' the stride describes the distance between image bytes
        Dim stride As Integer = bmData2.Stride
        ' scan0 is some sort of OS handle or something to identify the actual data in the memory
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        ' we need to know how big the data is so that we can create the correct size for the file
        Dim bytes As Integer = b.Height * b.Width * 3
        ' we create the byte arrays so that we can edit them
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte
        ' put the images into the byte arrays
        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)

        ' the nWidth describes the width of the actual image multiplied by three for each byte in the pixel (3 bytes per pixel 24 bits ;))
        Dim nWidth As Integer = b2.Width * 3
        ' for some reason although the original code show a formula to come up with the offset this doesn't work very well.
        ' I found that it is just easier to make the offset 0 and so all bits are handled. Basically the problem comes when 
        ' using this on files that don't have
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(p2minusplus)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(p2plusplus)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2minusstride)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2plus)) - CInt(p02(p2minus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    If npixelmax < CInt(threshold) Then npixelmax = 0
                    p01(pos1) = CByte(npixelmax)
                End If
                pos1 += 1
                pos2 += 1

            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub
    Public Sub EdgeDetectHomogenity(ByVal b As Bitmap, ByVal threshold As Byte)
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3

        Dim p2plusminus As Integer, p2plusstride As Integer, p2plusplus As Integer, p2minusstride As Integer, _
        p2minusminus As Integer, p2minusplus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2plusminus = pos2 + stride - 3
                p2plusstride = pos2 + stride
                p2plusplus = pos2 + stride + 3
                p2minusstride = pos2 - stride
                p2minusminus = pos2 - stride - 3
                p2minusplus = pos2 - stride + 3

                If p2plusminus < p02.Length And p2plusminus >= 0 And p2plusstride < p02.Length And p2plusstride >= 0 And _
                p2plusplus < p02.Length And p2plusplus >= 0 And p2minusstride < p02.Length And p2minusstride >= 0 And _
                p2minusstride < p02.Length And p2minusstride >= 0 And p2minusminus < p02.Length And p2minusminus >= 0 And _
                p2minusplus < p02.Length And p2minusplus >= 0 Then

                    npixelmax = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel


                    If npixelmax < threshold Then npixelmax = 0

                    p01(pos1) = CByte(npixelmax)

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub


    Public Function EdgeEnhance(ByVal b As Bitmap, ByVal threshold As Byte) As Boolean
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(pos2 - stride + 3)) - CInt(p02(pos2 + stride - 3)))
                    nPixel = Math.Abs(CInt(p02(pos2 + stride + 3)) - CInt(p02(pos2 - stride - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 - stride)) - CInt(p02(pos2 + stride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 + 3)) - CInt(p02(pos2 - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    If npixelmax > threshold And npixelmax > p01(pos1) Then
                        p01(pos1) = CByte(Math.Max(CInt(p01(pos1)), npixelmax))
                    End If

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

        Return True
    End Function

End Class

 

 

این کد کامل نیست!

دانلود کد فوق از طریق لینک زیر:

CannyInVisualBasic

رمز فایل : behsanandish.com

 

3-5-انواع روش‌هاي فرا ابتكاري برگرفته از طبيعت

1-3-5-الگوريتم ژنتيك

الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته مي‌باشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند (Holland) و در سال 1989 توسط  گولدبرگ (Goldberg) ابداع شده است.

اين روش نوعي روش جستجوي همسايه است كه عملكردي مشابه ژن دارد. در طبيعت، فرايند تكامل هنگامي ايجاد مي‌شود كه چهار شرط زير برقرار باشد:

الف) يك موجود توانايي تكثير داشته باشد (قابليت توليد مثل).

ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.

پ) چنين وضعيتي داراي تنوع باشد.

ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.

در طبيعت، گونه‌هاي متفاوتي از يك موجود وجود دارند كه اين تفاوت‌ها در كروموزوم‌هاي اين موجودات ظاهر مي‌شود و باعث تنوع در ساختار و رفتار اين موجودات مي‌شود.

اين تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثير مي‌گذارد. موجوداتي كه قابليت‌ها و توانايي بيشتري براي انجام فعاليت‌ها در محيط دارند (موجودات متكامل‌تر)، داراي نرخ زاد و ولد بالاتري خواهند بود و طبعاً موجوداتي كه سازگاري كمتري با محيط دارند، از نرخ زاد و ولد پايين‌تري برخوردار خواهند بود. بعد از چند دوره زماني و گذشت چند نسل، جمعيت تمايل دارد كه موجوداتي را بيشتر در خود داشته باشد كه كروموزوم‌هايشان با محيط اطراف سازگاري بيشتري دارد.

در طي زمان، ساختار افراد جامعه به علت انتخاب طبيعي تغيير مي‌كند و اين نشانه تكامل جمعيت است.

6- آنيلينگ شبيهسازي شده

اين روش توسط متروپوليس (Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک (kirkpatrick ) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفني كاربرد دارد.

الگوريتم آنيلينگ شبيه‌سازي شده (Simulated Annealing) در شکل عمومي، بر اساس شباهت ميان سرد شدن جامدات مذاب و حل مسائل بهينه‌سازي تركيبي به وجود آمده است. در فيزيك مواد فشرده، گرم و سرد كردن فرايندي است فيزيكي كه طي آن يك ماده جامد در ظرفي حرارت داده مي‌شود تا مايع شود؛ سپس حرارت آن بتدريج كاهش مي‌يابد. بدين ترتيب تمام ذرات فرصت مي‌يابند تا خود را در پايين‌ترين سطح انرژي منظم كنند. چنين وضعي در شرايطي ايجاد مي‌شود كه گرمادهي كافي بوده و سرد كردن نيز به آهستگي صورت گيرد. جواب حاصل از الگوريتم گرم و سرد كردن شبيه‌سازي شده، به جواب اوليه وابسته نيست و مي‌توان توسط آن جوابي نزديك به جواب بهينه به دست آورد. حد بالايي زمان اجراي الگوريتم نيز قابل تعيين است. بنابراين الگوريتم گرم و سرد كردن شبيه‌سازي شده، الگوريتمي است تكراري كه اشكالات روش‌هاي عمومي مبتني بر تكرار را ندارد.

در روش آنيلينگ شبيه‌سازي شده، به صورت پي در پي از جواب جاري به يكي از همسايه‌هاي آن انتقال صورت مي‌گيرد. اين سازوکار توسط زنجيره ماركوف به صورت رياضي قابل توصيف است. در اين روش، يك مجموعه آزمون انجام مي‌گيرد؛ اين آزمون‌ها به نحوي است كه نتيجه هر يك به نتيجه آزمون قبل وابسته است. در روش آنيلينگ شبيه‌سازي شده، منظور از يك آزمون، انتقال به نقطه جديد است و روشن است كه نتيجه انتقال به نقطه جديد تنها وابسته به مشخصات جواب جاري است.

روش جستجوي همسايه و روش آنيلينگ شبيه‌سازي شده، هر دو روش‌هاي تكراري هستند. در الگوريتم آنيلينگ شبيه‌سازي شده، هر بار كه شاخص كنترل‌كننده به مقدار نهايي خود مي‌رسد، در حقيقت يك عمليات تكراري انجام شده است. در الگوريتم جستجوي همسايه، هنگامي كه تعداد تكرارها به سمت بي‌نهايت ميل مي‌كند، روش به جواب بهينه نزديك مي‌شود. اما عملكرد الگوريتم آنيلينگ شبيه‌سازي شده سريع‌تر است.

7-شبکه‌های عصبی

شبکه‌های عصبی (Neural Networks) مصنوعی سيستم‌هاي هوشمندی هستند که از شبکه‌هاي عصبي طبيعي الهام گرفته شده‌اند. شبکه‌هاي عصبي مصنوعي در واقع تلاشي براي حرکت از سمت مدل محاسباتي فون نيومن به سمت مدلي است که با توجه به عملکرد و ويژگي‌هاي مغز انسان طراحي شده است. مدل فون نيومن گرچه هم اکنون بسيار استفاده می‌شود، اما از کمبودهايي رنج مي‌برد که تلاش شده است اين کمبودها در شبکه‌هاي عصبي مصنوعي برطرف شود.

در سال 1943 مدلی راجع به عملکرد نورون‌ها (Neuron) نوشته شد که با اندکی تغيير، امروزه بلوک اصلی سازنده اکثر شبکه‌های عصبی مصنوعی می‌باشد. عملکرد اساسی اين مدل مبتنی بر جمع کردن ورودی‌ها و به دنبال آن به وجود آمدن يک خروجی است. ورودی‌های نورون‌ها از طريق دنريت‌ها که به خروجی نورون‌های ديگر از طريق سيناپس متصل است، وارد می‌شوند. بدنه سلولی کليه اين ورودی‌ها را دريافت می‌کند و چنانچه جمع اين مقادير از مقداری که به آن آستانه گفته می‌شود بيشتر باشد، در اصطلاح برانگيخته شده يا آتش می‌کند و در اين صورت، خروجی نورون روشن يا خاموش خواهد شد.

مدل پایه ای نرون

مدل پايه‌اي نورون به صورت شکل 1-3 تعريف می‌شود.

مدل پایه ای نرون

مدل پایه ای نرون

اين مدل و برخی از کارهای مربوط به آن را بايد به عنوان شروع مطالعات تحليلی در نظر گرفت. گر چه اين مدل ساده فاقد ويژگی‌های پيچيده بدنه سلولی نورون‌های بيولوژيکی است، اما می‌توان به آن به صورت مدلی ساده از آنچه که واقعاً موجود است نگريست.

جستجوي ممنوع

روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.

روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.

شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جواب كه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.

ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب مي‌شود؛ سپس براي جواب مربوط، بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته مي‌شود.

در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب مي‌شود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار مي‌شود تا زماني كه شرط خاتمه تحقق يابد.

در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام مي‌شود كه در فهرست تابو قرار نداشته باشد. در غير اين صورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.

در روش جستجوي ممنوع بعد از هر جابه‌جايي، فهرست تابو بهنگام مي‌شود، به نحوي كه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n  تكرار مشخص در فهرست بوده است، از آن حذف مي‌شود. نحوه انتخاب مي‌تواند با توجه به شرايط و نوع مسأله متفاوت باشد.

سيستم مورچه (Ant System)

اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) و کولورنی (Colorni) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.

الگوريتم بهينه‌سازي كلوني مورچه‌ها از عامل‌هاي ساده‌اي كه مورچه ناميده مي‌شوند، استفاده مي‌كند تا به صورت تكراري جواب‌هايي توليد كند. مورچه‌ها می‌توانند كوتاه‌ترين مسير از يك منبع غذايي به لانه را با بهره‌گيري از اطلاعات فرموني پيدا کنند. مورچه‌ها در هنگام راه رفتن، روي زمين فرمون مي‌ريزند و با بو كشيدن فرمون ريخته شده بر روي زمين راه را دنبال مي‌كنند؛ چنانچه در طي مسير به سوي لانه به يك دوراهي برسند، از آن جايي كه هيچ اطلاعي درباره راه بهتر ندارند، راه را به تصادف برمي‌گزينند. انتظار مي‌رود به طور متوسط نيمي از مورچه‌ها مسير اول و نيمي ديگر مسير دوم را انتخاب كنند.

فرض مي‌شود كه تمام مورچه‌ها با سرعت يكسان مسير را طي كنند. از آنجا كه يك مسير كوتاه‌تر از مسير ديگر است، مورچه‌هاي بيشتري از آن مي‌گذرند و فرمون بيشتري بر روي آن انباشته مي‌شود. بعد از مدت كوتاهي مقدار فرمون روي دو مسير به اندازه‌اي مي رسد كه روي تصميم مورچه‌هاي جديد براي انتخاب مسير بهتر تأثير مي‌گذارد. از اين به بعد، مورچه‌هاي جديد با احتمال بيشتري ترجيح مي‌دهند از مسير كوتاه‌تر استفاده كنند، زيرا در نقطه تصميم‌گيري مقدار فرمون بيشتري در مسير كوتاه‌تر مشاهده مي‌كنند. بعد از مدت كوتاهي تمام مورچه‌ها اين مسير را انتخاب خواهند كرد.

منبع


مقدمه ای بر بهینه سازی و الگوریتم های موجود

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال، زمان سفر يا هزينه از جمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل و نقل مي‌باشد. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف  به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n  بعدي x  نشان داده مي‌شوند.

هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

مسائل مختلف بهينه‌سازي  به دو دسته زير تقسيم مي‌شود:

الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.

ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.

معادلات معرف محدوديت‌ها ممكن است  به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

فرايند بهينه ­سازي

فرموله كردن مسئله: در اين مرحله، يك مسئله ­ي تصميم ­گيري، همراه با يك ساختار كلي از آن تعريف مي‌شود. اين ساختار كلي ممكن است خيلي دقيق نباشد اما وضعيت كلي مسئله را، كه شامل فاكتورهاي ورودي و خروجي و اهداف مسئله است، بيان مي­ كند. شفاف­ سازي و ساختاردهي به مسئله، ممكن است براي بسياري از مسايل بهينه­ سازي، كاري پيچيده باشد.

مدل­ سازي مسئله:

در اين مرحله يك مدل رياضي كلي براي مسئله، ساخته مي­ شود. مدل­سازي ممكن است از مدل­ هاي مشابه در پيشينه ­ي موضوع كمك بگيرد. اين گام موجب تجزيه مسئله به يك يا چند مدل بهينه‌سازي مي­ گردد.

بهينه­ سازي مسئله:

پس از مدل سازي مسئله، روال حل، يك راه ­حل خوب براي مسئله توليد مي­ كند. اين راه‌حل ممكن است بهينه يا تقريباً بهينه باشد. نكته ­اي كه بايد به آن توجه داشت اين است كه راه ­حل به دست آمده، راه­ حلي براي مدل طراحي شده است، نه براي مسئله ­ي واقعي. در هنگام فرموله كردن و مدلسازي ممكن است تغييراتي در مسئله واقعي به وجود آمده و مسئله­ ي جديد، نسبت به مسئله­ ي واقعي تفاوت زيادي داشته باشد.

استقرار مسئله:

راه ­حل به دست آمده توسط تصميم گيرنده بررسي مي­ شود و در صورتي كه قابل قبول باشد، مورد استفاده قرار مي­ گيرد و در صورتي كه راه­حل قابل قبول نباشد، مدل يا الگوريتم بهينه­ سازي بايد توسعه داده شده و فرايند بهينه­ سازي تكرار گردد.

الگوریتم­ های بهینه­ سازی

هدف الگوریتم­ های اکتشافی، ارائه راه حل در چارچوب یک زمان قابل قبول است که برای حل مسئله مناسب باشد، ممکن است الگوریتم اکتشافی، بهترین راه حل واقعی برای حل مسئله نبوده ولی می­ تواند راه حل نزدیک به بهترین باشد. الگوریتم ­های اکتشافی با الگوریتم­ های بهینه­ سازی برای اصلاح کارایی الگوریتم می‌توانند ترکیب شوند. الگوریتم فرا اکتشافی ترکیبی است از الگوریتم ­های اکتشافی که برای پیدا کردن، تولید یا انتخاب هر اکتشاف در هر مرحله طراحی می­شود و راه حل خوبی برای مسائلی که مشکل بهینه‌سازی دارند ارائه می‌دهد. الگوریتم­ های فرا اکتشافی برخی از فرضیات مسائل بهینه­ سازی که باید حل شود را در نظر می ­گیرد.

 روش‌هاي فرا ابتكاري برگرفته از طبيعت

الگوريتم ­هاي فراابتكاري الگوريتم ­هايي هستند كه با الهام از طبيعت، فيزيك و انسان طراحي شده ­اند و در حل بسياري از مسايل بهينه­ سازي استفاده می­ شوند. معمولاً از الگوريتم­ هاي فراابتكاري در تركيب با ساير الگوريتم­ ها، جهت رسيدن به جواب بهينه يا خروج از وضعيت جواب بهينه محلي استفاده مي­گردد. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.

در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به صورت زير تشكيل شده‌اند:

–         استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري

–          استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)

–          عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت

–          ايجاد روش‌هاي خود تغييري و خود تبديلي

طبيعت داراي دو تدبير بزرگ مي‌باشد:

1-    انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛

2-     جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد.

از خصوصيات روش‌هاي ابتكاري  برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:

1-    پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.

2-     بدون قطع مي‌باشند.

3-     اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.

4-     تطبيق‌پذير هستند.

خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حلمناسب مسائل بهينه‌سازي تركيبي منجر می‌شود.

برخی الگوریتم های بهینه سازی مهم عبارت انداز:

 الگوریتم بهینه سازی ازدحام ذرات

در سال 1995 ابرهارت و کنیدی براي اولین بار PSOبه عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعیپرندگانی که به دنبال غذا می­باشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا مي­گردند. تنها يك تكه غذا در فضاي مورد بحث وجود دارد. هيچ يك از پرندگان محل غذا را نمي­دانند. يكي از بهترين استراتژي­ها مي­تواند دنبال كردن پرنده­اي باشد كه كمترين فاصله را تا غذا داشته باشد.  ايناستراتژي در واقع جانمايه الگوريتم است. هر راه­حل كه به آن يك ذره گفته مي­شود،PSO  در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان مي­باشد.هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شايستگي محاسبه مي­شود. هر چه ذره در فضا­ي جستجو به هدف – غذا در مدل حركت پرندگان-  نزدیكتر باشد،شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است كه هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خوددر فضاي مساله ادامه مي­دهد.

الگوریتم کرم شب­ تاب

الگوریتم کرم شب ­تاب به عنوان الگوریتم ذهنی مبتنی بر ازدحام، برای وظایف بهینه­سازی محدود، ارائه شده است. در این الگوریتم از رفتار تابشی کرم­های شب تابالهام گرفته شده است. کرم­های شب تاب در طبیعت به طور دسته جمعی زندگی می­کنند و همواره کرم کم نورتر به سمت کرم پرنور تر حرکت می‌کند. این الگوریتم یکرویه تکراری مبتنی بر جمعیت را با عوامل بی­شمار (تحت عنوان کرم­های شب­تاب) به کار می‌گیرد. به این عوامل امکان داده می­شود تا فضای تابع هزینه را به صورتموثرتری نسبت به جستجوی تصادفی توزیع شده، بررسی کنند. تکنیک بهینه­سازی هوشمند، مبتنی بر این فرضیه است که راه­حل یک مشکل بهینه­سازی را، می­توان بهعنوان عاملی (کرم شب­تاب) در نظر گرفت که به صورت متناسب با کیفیت آن در یک محیط تابیده می­شود. متعاقباً هر کرم شب­تاب، همتایان خود را (صرف نظر ازجنسیتشان) جذب می­کند که فضای جستجو را به صورت موثرتری بررسی می­کند. الگوریتم­های کرم شب­تاب نورهای ریتمیک و کوتاه تولید می­کنند. الگوی نوری هر کدام از کرم­های شب­تاب با یکدیگر متفاوت می­باشند. الگوریتم­های کرم شب­تاب از این نورها به دو منظور استفاده می­کنند. 1- پروسه جذب جفت­ها 2- جذب شکار. به علاوه این نورها می­توانند به عنوان یک مکانیزم محافظتی برای کرم­های شب­تاب باشند.

الگوریتم کلونی مورچگان

بهینه‌سازی گروه مورچه‌ها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.

 الگوریتم ژنتیک

الگوریتم‌های ژنتیک، تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هنری هالند معرفی شد. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حلها تبدیل می‌شود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند.

منبع
بهينه‌سازی و معرفي روش‌های آن قسمت 1
بهينه‌سازی و معرفي روش‌های آن قسمت 2
بهينه‌سازی و معرفي روش‌های آن قسمت 3

از مهم‌ترین تکنیک‌های عملی داده‌کاوی که کاربرد زیادی در علوم مختلف دارد، می توان به «خوشه بندی k-میانگین» (K-means Clustering)  اشاره کرد، که با توجه به بار محاسباتی زیاد آن، استفاده از کامپیوتر در انجام این فرآیند، کمک شایانی به کاربران می‌کند. در این راستا زبان برنامه‌نویسی و محاسباتی R قابلیت انجام این گونه محاسبات را دارد و به محققین در تحلیل خوشه‌بندی تفکیکی بر مبنای روش K-میانگین، کمک شایانی می‌کند. در این متن به بررسی روش خوشه‌بندی با استفاده از دستورات مربوط به این زبان برنامه‌نویسی می‌پردازیم و با البته با مفاهیم اولیه خوشه‌بندی k-میانگین نیز آشنا می‌شویم.

خوشه‌بندی k-میانگین

روش‌‌ها و الگوریتم‌های متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود.

معمولا در حالت چند متغیره، باید از ویژگی‌های مختلف اشیا به منظور طبقه‌بندی و خوشه‌ کردن آن‌ها استفاده کرد. به این ترتیب با داده‌های چند بعدی سروکار داریم که معمولا به هر بعد از آن، ویژگی یا خصوصیت گفته می‌شود. با توجه به این موضوع، استفاده از توابع فاصله مختلف در این جا مطرح می‌شود. ممکن است بعضی از ویژگی‌های اشیا کمی و بعضی دیگر کیفی باشند. به هر حال آنچه اهمیت دارد روشی برای اندازه‌گیری میزان شباهت یا عدم شباهت بین اشیاء است که باید در روش‌های خوشه‌بندی لحاظ شود.

الگوریتم خوشه‌بندی k-میانگین از گروه روش‌های خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب می‌شود و درجه پیچیدگی محاسباتی آن برابر با O(ndk+1) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O(nkdi) است، که البته منظور از i‌ تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است.

در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده می‌شود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند.

خوشه‌بندی k-میانگین روش‌‌ها و الگوریتم‌های متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود. معمولا در حالت چند متغیره، باید از ویژگی‌های مختلف اشیا به منظور طبقه‌بندی و خوشه‌ کردن آن‌ها استفاده کرد. به این ترتیب با داده‌های چند بعدی سروکار داریم که معمولا به هر بعد از آن، ویژگی یا خصوصیت گفته می‌شود. با توجه به این موضوع، استفاده از توابع فاصله مختلف در این جا مطرح می‌شود. ممکن است بعضی از ویژگی‌های اشیا کمی و بعضی دیگر کیفی باشند. به هر حال آنچه اهمیت دارد روشی برای اندازه‌گیری میزان شباهت یا عدم شباهت بین اشیاء است که باید در روش‌های خوشه‌بندی لحاظ شود. الگوریتم خوشه‌بندی k-میانگین از گروه روش‌های خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب می‌شود و درجه پیچیدگی محاسباتی آن برابر با O ( n d k + 1 ) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O ( n k d i ) است، که البته منظور از i‌ تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است. در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده می‌شود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند. معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز می‌نامند. روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه‌ دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا می‌شود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار می‌گیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتم‌های خوشه‌بندی k-میانگین می‌نامند. روش خوشه‌بندی k-میانگین فرض کنید مشاهدات ( x 1 , x 2 , … , x n ) که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام S = { S 1 , S 2 , … , S k } می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود. بنابراین، تابع هدف در این الگوریتم به صورت زیر نوشته می‌شود. a r g m i n S k ∑ i = 1 ∑ x ∈ S i ∥ x − μ i ∥ 2 = a r g m i n S k ∑ i = 1 | S i | Var S i در اینجا منظور از μ i میانگین خوشه S i و | S i | تعداد اعضای خوشه iام است. البته می‌توان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش می‌یابد، زیرا واریانس کل ثابت است. در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم. خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm) به عنوان یک الگوریتم استاندارد برای خوشه‌بندی k-میانگین از الگوریتم لوید بخصوص در زمینه علوم کامپیوتر، استفاده می‌شود. ابتدا به علائمی که در این رابطه به کار می‌رود، اشاره می‌کنیم. m ( i ) j : میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم. S ( i ) j : مجموعه اعضای خوشه jام در تکرار iام الگوریتم. الگوریتم لوید را با توجه به نمادهای بالا می‌توان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ( A s s i g n m e n t S t e p )، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی m ( 1 ) 1 , m ( 1 ) 2 , ⋯ , m ( 1 ) k داده شده‌اند. بخش مقدار دهی: هر مشاهده یا شی را به نزدیکترین خوشه نسبت می‌دهیم. به این معنی که فاصله اقلیدسی هر مشاهده از مراکز، اندازه گرفته شده سپس آن مشاهده عضو خوشه‌ای خواهد شد که کمترین فاصله اقلیدسی را با مرکز آن خوشه دارد. این قانون را به زبان ریاضی به صورت S ( t ) i = { x p : ∥ ∥ x p − m ( t ) i ∥ ∥ 2 ≤ ∥ ∥ x p − m ( t ) j ∥ ∥ 2 ∀ j , 1 ≤ j ≤ k } می‌نویسیم. بخش به روز رسانی: میانگین خوشه‌های جدید محاسبه می‌شود. در این حالت داریم: m ( t + 1 ) i = 1 | S ( t ) i | ∑ x j ∈ S ( t ) i x j توجه داشته باشید که منظور از | S ( t ) i | تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف می‌شود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا،‌ فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است. نکته: ممکن است فاصله اقلیدسی یک مشاهده از دو مرکز یا بیشتر، برابر باشد ولی در این حالت آن شئ فقط به یکی از این خوشه‌ها تعلق خواهد گرفت. تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب می‌شود که مراحل اجرا در آن دیده می‌شود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی می‌رسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا می‌کند. K-means_convergence همگرایی الگوریتم k-میانگین نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته می‌شود. ممکن است این نقطه یکی از مشاهدات یا غیر از آن‌ها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی می‌کند. خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong) یکی از روش‌های پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود. ϕ ( S j ) : از این نماد برای نمایش «تابع هزینه» برای خوشه S j استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با: ϕ ( S i ) = ∑ x ∈ S j ( x − μ j ) 2 S j : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، S = { S 1 , S 2 , ⋯ , S k } . μ j : برای نمایش میانگین خوشهjام از این نماد استفاده می‌شود. بنابراین خواهیم داشت: μ j = ∑ x ∈ S j x n j n j : این نماد تعداد اعضای خوشه jام را نشان می‌دهد. بطوری که j = { 1 , 2 , ⋯ , k } است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k‌ نشان داده‌ایم. مراحل اجرای الگوریتم در خوشه‌بندی k-میانگین با الگوریتم هارتیگان می‌توان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه ( A s s i g n m e n t S t e p ) ، ۲- بخش به روز رسانی ( U p d a t e S t e p )، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته می‌شود. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم می‌شوند. به این کار مجموعه S با اعضایی به صورت { S j } j ∈ { i , ⋯ , k } مشخص می‌شود. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع Δ ( m , n , x ) = ϕ ( S n ) + ϕ ( S m ) − Φ ( S n ∖ { x } ) − ϕ ( S m ∪ { x } ) را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل می‌شود. به این ترتیب شی مورد نظر در S m قرار گرفته و خواهیم داشت x ∈ S m . بخش نهایی: زمانی که به ازای همه n,m,x مقدار Δ ( m , n , x ) بزرگتر از صفر باشد، الگوریتم خاتمه می‌یابد. نکته: منظور از نماد ϕ ( S n ∖ { x } ) محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه S n خارج شده باشد. همچنین نماد ϕ ( S m ∪ { x } ) به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه S m اضافه شده باشد. در تصویر زیر مراحل اجرای الگوریتم هارتیگان به خوبی نمایش داده شده است. هر تصویر بیانگر یک مرحله از اجرای الگوریتم است. نقاط رنگی نمایش داده شده، همان مشاهدات هستند. هر رنگ نیز بیانگر یک خوشه است. در تصویر اول مشخص است که در بخش اول از الگوریتم به طور تصادفی خوشه‌بندی صورت پذیرفته. ولی در مراحل بعدی خوشه‌ها اصلاح شده و در انتها به نظر می‌رسد که بهترین تفکیک برای مشاهدات رسیده‌ایم. در تصویر آخر نیز مشخص است که مراکز خوشه‌ها، محاسبه و ثابت شده و دیگر بهینه‌سازی صورت نخواهد گرفت. به این ترتیب پاسخ‌های الگوریتم با طی تکرار ۵ مرحله به همگرایی می‌رسد. hartigan algorithm الگوریتم هارتیگان بخش مقدار دهی اولیه hartigan algorithm الگوریتم هارتیگان تکرار ۱ hartigan algorithm الگوریتم هارتیگان تکرار ۲ hartigan algorithm الگوریتم هارتیگان تکرار ۳ hartigan algorithm الگوریتم هارتیگان تکرار ۴ hartigan algorithm الگورییتم هارتیگان تکرار ۵ اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی R برای استفاده از دستورات و فرمان‌های مربوط به خوشه‌بندی k-میانگین، باید بسته یا Package مربوط به خوشه‌بندی kmeans به اسم stats را در R نصب کرده باشد. البته از آنجایی این بسته بسیار پرکاربرد است،‌ معمولا به طور خودکار فراخوانی شده است. کدهای زیر نشانگر استفاده از الگوریتم خوشه‌بندی توسط روش‌های مختلف آن است. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 با توجه به داده‌های iris که مربوط به اندازه و ابعاد کاسبرگ و گلبرگ سه نوع گل مختلف است، خوشه‌بندی به سه دسته انجام شده است. اطلاعات مربوط به ۱۰ سطر اول این مجموعه داده،‌ به صورت زیر است. با اجرای کدهای نوشته شده، خوشه‌بندی انجام شده و نتابج تولید می‌شوند. به عنوان مثال می‌توان خروجی را برای kresult1 که انجام خوشه بندی توسط الگوریتم هارتیگان است به صورت زیر مشاهده کرد: iris clustering همانطور که دیده می‌شود، در سطر اول تعداد اعضای هر خوشه، نمایش داده شده است. در بخش دوم که با سطر ۱ و ۲ و ۳ مشخص شده،‌ مراکز هر سه خوشه برحسب ویژگی‌های (طول و عرض کاسبرگ و طول و عرض گلبرگ) محاسبه شده و در قسمت Cluster Vector نیز برچسب خوشه هر کدام از مشاهدات دیده می‌شود. در انتها نیز مجموع مربعات فاصله درون خوشه‌ای (مجموع فاصله هر مشاهده از مرکز خوشه) استخراج شده و درصد یا شاخص ارزیابی خوشه‌بندی بر اساس نسبت مربعات بین خوشه‌ها به مربعات کل دیده می‌شود. این مقدار برای این حالت برابر ۸۸.۴٪ است که نشان می‌دهد بیشتر پراکندگی (total_ss) توسط پراکندگی بین خوشه‌ها (between_ss) بیان شده است. پس به نظر خوشه‌بندی مناسب خواهد بود. پس اختلاف بین گروه‌ها ناشی از خوشه‌های است که مشاهدات را به دسته‌‌های جداگانه تفکیک کرده. همچنین در کدها مشخص است که تعداد خوشه‌های در متغیر k ثبت و به کار رفته است. در شکل دیگری از دستور kmeans می‌توان به جای معرفی تعداد خوشه‌ها از مراکز دلخواه که با تعداد خوشه‌ها مطابقت دارد، استفاده کرد. برای مثال اگر برنامه به صورت زیر نوشته شود، الگوریتم ابتدا نقاط معرفی شده را به عنوان نقاط مرکزی (Centroids) به کار گرفته و سپس مراحل بهینه سازی را دنبال می‌کند. از آنجا که سه نقطه مبنا قرار گرفته، الگوریتم متوجه می‌شود که باید مشاهدات به سه خوشه تفکیک شود. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روش‌های آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده می‌شود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد. کاربردها از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها می‌توان از این الگوریتم‌ها استفاده کرد. در تصویر بالا گل رز زرد رنگی دیده می‌شود که در یک محیط سبز قرار گرفته است. با استفاده از الگوریتم‌های خوشه‌بندی می‌توان تعداد رنگ‌ها را کاهش داده و از حجم تصاویر کاست. در تصویر زیر دسته بندی رنگ‌های گل رز دیده می‌شود. در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی می‌تواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان می‌کند. معایب و مزایای خوشه‌بندی k-میانگین از آنجایی که در این روش خوشه‌بندی، محاسبه فاصله بین نقاط توسط تابع فاصله اقلیدسی انجام می‌شود، از این الگوریتم‌ها به صورت استاندارد، فقط برای مقدارهای عددی (و نه ویژگی‌های کیفی) می‌توان استفاده کرد. از طرف دیگر با توجه به محاسبات ساده و سریع آن‌ها،‌ پرکاربرد و موثر است. از طرف دیگر نسخه‌های تعمیم یافته از روش خوشه بندی k-میانگین نیز وجود دارد که با توابع فاصله دیگر مانند فاصله منهتن و یا فاصله‌هایی که برای داده‌های باینری قابل استفاده است، مراحل خوشه‌بندی را انجام می‌دهد. به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته می‌شود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب می‌شوند. معمولا به این برچسب‌ها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark می‌گویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است. از طرف دیگر اگر هیچ اطلاعات اولیه از ساختار و دسته‌بندی مشاهدات وجود نداشته باشد، فقط ملاک ارزیابی، می‌تواند اندازه‌هایی باشد که میزان شباهت درون خوشه‌ها و یا عدم شباهت یا فاصله بین خوشه‌ها را اندازه می‌گیرند. بنابراین برای انتخاب بهتر و موثرترین روش خوشه‌بندی از میزان شباهت درون خوشه‌ها و شباهت بین خوشه‌ها استفاده می‌شود. روشی که دارای میزان شباهت بین خوشه‌ای کم و شباهت درون خوشه‌ای زیاد باشد مناسب‌ترین روش خواهد بود. این معیارها را به نام شاخص‌های ارزیابی درونی می‌شناسیم. به عنوان مثال شاخص نیم‌رخ (silhouette) یکی از این معیارها است که شاخصی برای سنجش مناسب بودن تعلق هر مشاهده به خوشه‌اش ارائه می‌دهد. به این ترتیب معیاری برای اندازه‌گیری کارایی الگوریتم خوشه‌بندی بدست می‌آید. اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند: مجموعه آموزش‌های یادگیری ماشین و بازشناسی الگو مجموعه آموزش‌های آمار، احتمالات و داده‌کاوی آموزش خوشه بندی K میانگین (K-Means) با نرم افزار SPSS آموزش خوشه بندی تفکیکی با نرم افزار R آموزش خوشه بندی سلسله مراتبی با SPSS آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای درونی (Internal Index) روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای بیرونی (External Index) ^^ telegram twitter به اشتراک بگذارید: منبع وبلاگ فرادرسWikipedia بر اساس رای 1 نفر آیا این مطلب برای شما مفید بود؟ بلیخیر نظر شما چیست؟ نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند * متن نظر * نام شما * ایمیل شما * پایتخت ایران کدام شهر است؟ برچسب‌ها clusterClusteringclustering algorithmcost functiondata miningforgy algorithmhartigan-wong algorithmk-meanslloyd algorithmmaximizationMcQueen algorithmminimizationpartitioning algorithmunsupervise learningتابع هدفتابع هزینهتعداد خوشهخوشه بندیخوشه بندی K میانگینخوشه بندی در آمارخوشه‌بندیخوشه‌بندی k-میانگینمربعات بین خوشهمربعات درون خوشهمعیارهای ارزیابی خوشه عضویت در خبرنامه ایمیل * آموزش برنامه نویسی آموزش متلب Matlab نرم‌افزارهای مهندسی برق نرم‌افزارهای مهندسی عمران نرم‌افزارهای مهندسی مکانیک نرم‌افزارهای مهندسی صنایع

 

معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز می‌نامند.

روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه‌ دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا می‌شود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار می‌گیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتم‌های خوشه‌بندی k-میانگین می‌نامند.

روش خوشه‌بندی k-میانگین

فرض کنید مشاهدات  که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام  می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود.

بنابراین، تابع هدف در این الگوریتم به صورت زیر نوشته می‌شود.

الگوریتم K-means

در اینجا منظور از  میانگین خوشه  و   تعداد اعضای خوشه iام است. البته می‌توان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش می‌یابد، زیرا واریانس کل ثابت است.

در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم.

خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm)

به عنوان یک الگوریتم استاندارد برای خوشه‌بندی k-میانگین از الگوریتم لوید بخصوص در زمینه علوم کامپیوتر، استفاده می‌شود. ابتدا به علائمی که در این رابطه به کار می‌رود، اشاره می‌کنیم.

mj(i): میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم.

Sj(i): مجموعه اعضای خوشه jام در تکرار iام الگوریتم.

الگوریتم لوید را با توجه به نمادهای بالا می‌توان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ()، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی  داده شده‌اند.

  1. بخش مقدار دهی: هر مشاهده یا شی را به نزدیکترین خوشه نسبت می‌دهیم. به این معنی که فاصله اقلیدسی هر مشاهده از مراکز، اندازه گرفته شده سپس آن مشاهده عضو خوشه‌ای خواهد شد که کمترین فاصله اقلیدسی را با مرکز آن خوشه دارد. این قانون را به زبان ریاضی به صورت  فرمول 2  می‌نویسیم.
  2. بخش به روز رسانی: میانگین خوشه‌های جدید محاسبه می‌شود. در این حالت داریم:  فرمول 3

توجه داشته باشید که منظور از Si(t| تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف می‌شود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا،‌ فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است.

نکته: ممکن است فاصله اقلیدسی یک مشاهده از دو مرکز یا بیشتر، برابر باشد ولی در این حالت آن شئ فقط به یکی از این خوشه‌ها تعلق خواهد گرفت.

تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب می‌شود که مراحل اجرا در آن دیده می‌شود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی می‌رسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا می‌کند.

 

K-means_convergence

همگرایی الگوریتم k-میانگین

 

نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته می‌شود. ممکن است این نقطه یکی از مشاهدات یا غیر از آن‌ها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی می‌کند.

خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong)

یکی از روش‌های پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود.

فرمول 4  از این نماد برای نمایش «تابع هزینه» برای خوشه فرمول 5 استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با:

فرمول 6

 

فرمول 5 : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، فرمول 7

فرمول 8: برای نمایش میانگین خوشهjام از این نماد استفاده می‌شود. بنابراین خواهیم داشت:

فرمول 9

فرمول 11این نماد تعداد اعضای خوشه jام را نشان می‌دهد. بطوری که فرمول 10  است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k‌ نشان داده‌ایم.

مراحل اجرای الگوریتم

در خوشه‌بندی k-میانگین با الگوریتم هارتیگان می‌توان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه (Assignment Step(   ،- ۲ بخش به روز رسانی (Update Step)، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته می‌شود.

  1. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم می‌شوند. به این کار مجموعه S با اعضایی به صورت فرمول 12  مشخص می‌شود.
  2. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع  فرمول 13 را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل می‌شود. به این ترتیب شی مورد نظر در  فرمول 20 قرار گرفته و خواهیم داشت  فرمول 15 .
  3. بخش نهایی: زمانی که به ازای همه n,m,x مقدار  فرمول 16  بزرگتر از صفر باشد، الگوریتم خاتمه می‌یابد.

نکته: منظور از نماد  فرمول 17  محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه  فرمول 18  خارج شده باشد. همچنین نماد  فرمول 19 به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه  فرمول 20  اضافه شده باشد.

در تصویر زیر مراحل اجرای الگوریتم هارتیگان به خوبی نمایش داده شده است. هر تصویر بیانگر یک مرحله از اجرای الگوریتم است. نقاط رنگی نمایش داده شده، همان مشاهدات هستند. هر رنگ نیز بیانگر یک خوشه است.

در تصویر اول مشخص است که در بخش اول از الگوریتم به طور تصادفی خوشه‌بندی صورت پذیرفته. ولی در مراحل بعدی خوشه‌ها اصلاح شده و در انتها به نظر می‌رسد که بهترین تفکیک برای مشاهدات رسیده‌ایم.

در تصویر آخر نیز مشخص است که مراکز خوشه‌ها، محاسبه و ثابت شده و دیگر بهینه‌سازی صورت نخواهد گرفت. به این ترتیب پاسخ‌های الگوریتم با طی تکرار ۵ مرحله به همگرایی می‌رسد.

 

hartigan-step-1

الگوریتم هارتیگان بخش مقدار دهی اولیه

hartigan-step-2

الگوریتم هارتیگان تکرار 1

 

hartigan-step-3

الگوریتم هارتیگان تکرار 2

 

hartigan-step-5

الگوریتم هارتیگان تکرار 3

 

hartigan-step-4

الگوریتم هارتیگان تکرار 4

 

hartigan-step-6

الگوریتم هارتیگان تکرار 5

 

اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی R

برای استفاده از دستورات و فرمان‌های مربوط به خوشه‌بندی k-میانگین، باید بسته یا Package مربوط به خوشه‌بندی kmeans به اسم stats را در R نصب کرده باشد. البته از آنجایی این بسته بسیار پرکاربرد است،‌ معمولا به طور خودکار فراخوانی شده است. کدهای زیر نشانگر استفاده از الگوریتم خوشه‌بندی توسط روش‌های مختلف آن است.

library(stats)
data=iris[,1:4]
method=c(&quot;Hartigan-Wong&quot;, &quot;Lloyd&quot;,
&quot;MacQueen&quot;)
k=3
kresults1=kmeans(data,k,algorithm = method[1])
kresults2=kmeans(data,k,algorithm=method[2])
kresults3=kmeans(data,k,algorithm=method[3])

kresults1
kresults2
kresults3
با توجه به داده‌های iris که مربوط به اندازه و ابعاد کاسبرگ و گلبرگ سه نوع گل مختلف است، خوشه‌بندی به سه دسته انجام شده است. اطلاعات مربوط به ۱۰ سطر اول این مجموعه داده،‌ به صورت زیر است.

با اجرای کدهای نوشته شده، خوشه‌بندی انجام شده و نتابج تولید می‌شوند. به عنوان مثال می‌توان خروجی را برای kresult1 که انجام خوشه بندی توسط الگوریتم هارتیگان است به صورت زیر مشاهده کرد:

iris clustering

همانطور که دیده می‌شود، در سطر اول تعداد اعضای هر خوشه، نمایش داده شده است. در بخش دوم که با سطر ۱ و ۲ و ۳ مشخص شده،‌ مراکز هر سه خوشه برحسب ویژگی‌های (طول و عرض کاسبرگ و طول و عرض گلبرگ) محاسبه شده و در قسمت Cluster Vector نیز برچسب خوشه هر کدام از مشاهدات دیده می‌شود. در انتها نیز مجموع مربعات فاصله درون خوشه‌ای (مجموع فاصله هر مشاهده از مرکز خوشه) استخراج شده و درصد یا شاخص ارزیابی خوشه‌بندی بر اساس نسبت مربعات بین خوشه‌ها به مربعات کل دیده می‌شود. این مقدار برای این حالت برابر ۸۸.۴٪ است که نشان می‌دهد بیشتر پراکندگی (total_ss) توسط پراکندگی بین خوشه‌ها (between_ss) بیان شده است. پس به نظر خوشه‌بندی مناسب خواهد بود. پس اختلاف بین گروه‌ها ناشی از خوشه‌های است که مشاهدات را به دسته‌‌های جداگانه تفکیک کرده.

همچنین در کدها مشخص است که تعداد خوشه‌های در متغیر k ثبت و به کار رفته است. در شکل دیگری از دستور kmeans می‌توان به جای معرفی تعداد خوشه‌ها از مراکز دلخواه که با تعداد خوشه‌ها مطابقت دارد، استفاده کرد. برای مثال اگر برنامه به صورت زیر نوشته شود، الگوریتم ابتدا نقاط معرفی شده را به عنوان نقاط مرکزی (Centroids) به کار گرفته و سپس مراحل بهینه سازی را دنبال می‌کند. از آنجا که سه نقطه مبنا قرار گرفته، الگوریتم متوجه می‌شود که باید مشاهدات به سه خوشه تفکیک شود.

 

library(stats)
data=iris[,1:4]
method=c(&quot;Hartigan-Wong&quot;, &quot;Lloyd&quot;,
         &quot;MacQueen&quot;)
c1=c(6,4,5,3)
c2=c(5,3,1,0)
c3=c(6,2,4,2)
centers=rbind(c1,c2,c3)
kresults1=kmeans(x = data,centers = centers,algorithm = method[1])
kresults2=kmeans(x = data,centers = centers,algorithm=method[2])
kresults3=kmeans(x = data,centers = centers,algorithm=method[3])

kresults1
kresults2
kresults3
در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روش‌های آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده می‌شود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد.

کاربردها

از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها می‌توان از این الگوریتم‌ها استفاده کرد.

 

در تصویر بالا گل رز زرد رنگی دیده می‌شود که در یک محیط سبز قرار گرفته است. با استفاده از الگوریتم‌های خوشه‌بندی می‌توان تعداد رنگ‌ها را کاهش داده و از حجم تصاویر کاست. در تصویر زیر دسته بندی رنگ‌های گل رز دیده می‌شود.

 

 

در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی می‌تواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان می‌کند.

 

خوشه بندی k میانگین (k-means Clustering) قسمت 1
خوشه بندی k میانگین (k-means Clustering) قسمت 2

مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.

اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

مسئله n وزیر در صورتی جواب دارد که n مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.

تاریخچه

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آن را کامل نمود. در سال ۱۹۷۹، Edsger Dijkstra Nauck این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد.

حل مسئله

هشت وزیر را می‌توان با الگوریتم‌های مختلفی مانند تپه نوردی و روش ارضای محدودیت(csp) حل کرد که در زیر روش ارضای محدودیت را بررسی می‌کنیم. هر وزیری در هر ستونی هدفی دارد که همان مکانش در هرستون می‌شود یک گره .در کد زیر تعریف مکان‌ها را داریم:

Variables: { Q1, Q2, Q3, Q4 }

Domain: { (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4) }

Constraints: Alldifferent( Q1, Q2, Q3, Q4 ) and 
for i = 0...n and j = (i+1)...n, k = j-i, Q[i] != Q[j] + k and Q[i] != Q[j] - k

و این الگوریتم که برای جواب هر خانه‌است به دست می‌آید که یک csp است

min-conflicts(csp, max):
initial := complete assignment ;jamiyate avaliye
for 1..max do: ;az 1 .. akharin khane
if initial is a solution: ;if jamiyate tolide javab bod 
return initial ;barmigardanad
var := nextVar() ;da ghire indorat yek motaghair be jelo
value := leastConflicts( var ) ;taeein meghdar
var := value in initial ;gharar dadan meghdar dar motaghair
return failure ;bargash be ebtedaye algoritm

صورت مسئله

هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است، به‌طوری‌که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره‌ای نباید در یک سطر، ستون یا قطر یکسان باشند. وزیر در خانه‌های شطرنج به صورت عرضی، طولی و قطری می‌تواند حرکت کند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود

شمردن تعداد جواب‌ها

جدول زیر تعداد راه حل‌ها برای قرار دادن n وزیر بر روی صفحه n × nنشان می‌دهد. هر دو منحصر به فرد و متمایز، برای تعداد ۱-۱۴،۲۴-۲۶ است.

مسئله ی چند وزیر

  • توجه:

حالت شش وزیر جواب‌های کمتری نسبت به پنج وزیر دارد و فرمول صریحی برای یافتن تعداد جواب‌ها وجود ندارد.

روش‌های حل مسئله

الگوریتم عقبگرد

از تکنیک عقبگرد Backtracking برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به‌طوری‌که این دنباله، ملاکی را در بر می‌گیرد. عقبگرد حالت اصلاح شدهٔ جستجوی عمقی یک درخت است. این الگوریتم همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشد و در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره‌گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند.

برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می‌کنیم که خانه‌های شطرنج ۴x۴ و تعداد وزیرها نیز ۴ باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می‌کنیم.

مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم.

در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم.

همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. می‌بینیم که چنین خانه‌ای موجود نیست. پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد.

دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.

همانند قبل، در ردیف چهارم به دنبال اولین خانه‌ای می‌گردیم که مورد تهدید وزیران پیشین نباشد. چنین خانه‌ای موجود نیست. به ردیف قبل یعنی ردیف سوم باز می‌گردیم تا خانه‌ای دیگر برای وزیر سوم بیابیم. خانه دیگری وجود ندارد. به ردیف قبل یعنی ردیف دوم بر می‌گردیم تا خانه دیگری برای وزیر دوم پیدا کنیم. به آخرین ستون رسیده‌ایم و خانه دیگری نیست. به ردیف قبل یعنی ردیف اول بر می‌گردیم و وزیر اول را یک ستون به جلو می‌بریم.

در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم.

در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.

در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می‌دهیم.

به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالاً” می‌توانیم جوابهای دیگری نیز بیابیم.

شبه کد پیاده‌سازی الگوریتم عقبگرد برای مسئله n وزیر

void queens (index i)
{
	index j;
	if (promising(i))
		if (i == n)
			cout &amp;amp;amp;amp;lt;&amp;amp;amp;amp;lt; col[1] through col[n];
		else
			for (j = 1; j &amp;amp;amp;amp;lt;= n; j++) {
				col[i + 1] = j;
				queens(i + 1);
			}
}
bool promising (index i)
{
	index k;
	bool Switch;
	k = 1;
	Switch = true ;
	while (k &amp;amp;amp;amp;lt; i &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; switch) {
		if (col[i] == col[k] || abs(col[i] – col[k] == i - k))
			switch = false;
		k++;
	}
	return Switch;
}

برنامه زبان C به صورت غیر بازگشتی

# include &amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt;

int b[8];

inline static int unsafe(int y) {
        int i, t, x;
        x = b[y];
        for (i = 1; i &amp;amp;amp;amp;lt;= y; i++) {
                t = b[y - i];
                if ((t == x) ||
                     (t == x - i) ||
                     (t == x + i)) {
                        return 1;
               }
       }

        return 0;
}

static void putboard(void) {
        static int s = ۰;
        int x, y;
        printf("\n\nSolution #٪i\n", ++s);
        for (y = 0; y &amp;amp;amp;amp;lt; 8; y++) {
                for (x = 0; x &amp;amp;amp;amp;lt; 8; x++) {
                        printf((b[y] == x) ? "|Q": "|_");
               }
                printf("|\n");
       }
}

int main(void) {
        int y = ۰;
        b[۰] = -۱;
        while (y &amp;amp;amp;amp;gt;= ۰) {
                do {
                        b[y]++;
               } while ((b[y] &amp;amp;amp;amp;lt; 8) &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; unsafe(y));
                if (b[y] &amp;amp;amp;amp;lt; 8) {
                        if (y &amp;amp;amp;amp;lt; 7) {
                                b[++y] = -۱;
                       } else {
                                putboard();
                       }
               } else {
                        y--;
               }
       }

        return 0;
}

برنامه زبان ++C به صورت بازگشتی

  • برنامه زیر برای هشت وزیر نوشته شده‌است با انتخاب اعداد دیگر به جای هشت در define MAXSIZE 8 # می‌توان برای تعداد دیگری وزیر نیز استفاده کرد.
# include &amp;amp;amp;amp;lt;assert.h&amp;amp;amp;amp;gt;
# include &amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt;

# define MAXSIZE 8
class EightQueens
{
    int m_size;				
    int m_solution_count;		
    int m_attempt_count;		
    int m_queen[MAXSIZE];		
    bool m_row_inuse[MAXSIZE]; 		
    bool m_diag_rise[MAXSIZE*2];	
    bool m_diag_fall[MAXSIZE*2];	

public:

    EightQueens(int size, bool is_alt) {

	assert(size &amp;amp;amp;amp;lt;= MAXSIZE);

	m_size = size;
	m_solution_count = 0;
	m_attempt_count = 0;

	for (int i = 0; i &amp;amp;amp;amp;lt; m_size; i++) {
	    m_queen[i] = i;
	    m_row_inuse[i] = 0;
	}

	for (int j = 0; j &amp;amp;amp;amp;lt; m_size*2; j++) {
	    m_diag_rise[j] = 0;
	    m_diag_fall[j] = 0;
	}

	if (is_alt) SearchAlt(0);
	else        Search(0);

   }

    int GetSolutionCount() {
	return m_solution_count;
   }

    int GetAttemptCount() {
	return m_attempt_count;
   }

private:

    void SearchAlt(int col){

	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int row = 0; row &amp;amp;amp;amp;lt; m_size; row++) {
	    m_attempt_count++;
	    if (m_row_inuse[row] == 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; IsDiagValid(col, row)) {
		m_queen[col] = row;
		m_row_inuse[row] = 1;
		SetDiags(col, 1);
		SearchAlt(col+1);
		SetDiags(col, 0);
		m_row_inuse[row] = 0;
		m_queen[col] = -1;
	   }
	}

   }

    void Search(int col) {
	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int i = col; i &amp;amp;amp;amp;lt; m_size; i++) {
	    if (SwapQueenIfDiagValid(col, i)) {
		Search(col+1);
		UnSwapQueen(col, i);
	   };
	}
   }

    void SwapQueenBasic(int i, int j) {
	    int hold = m_queen[i];
	    m_queen[i] = m_queen[j];
	    m_queen[j] = hold;
   }

    void SetDiags(int col, int val) {
	assert(m_diag_rise[m_queen[col] + col]!= val);
	       m_diag_rise[m_queen[col] + col] =  val;
	assert(m_diag_fall[m_queen[col] - col + m_size]!= val);
	       m_diag_fall[m_queen[col] - col + m_size] =  val;
   }

    bool IsDiagValid(int col, int row) {
	return (m_diag_rise[row + col] == 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;
		m_diag_fall[row - col + m_size] == 0);
   }

    bool SwapQueenIfDiagValid(int i, int j) {
	m_attempt_count++;
	if (IsDiagValid(i, m_queen[j])) {
	    SwapQueenBasic(i, j);
	    SetDiags(i, 1);
            return true;
	}
        return false;
   }

    void UnSwapQueen(int i, int j) {
	SetDiags(i, 0);
	SwapQueenBasic(i, j);
   }

};

void
do_work(bool is_alt)
{
    int size = 8;

    EightQueens puzzle(size, is_alt);
    int soln = puzzle.GetSolutionCount();
    int attempt = puzzle.GetAttemptCount();
    assert(size!= 8 || soln == 92);
    const char* style = is_alt ? "cartesian": "permutation";
    printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search. \n", size, soln, attempt, style);
}

int main()
{
    printf("We should have 92 solutions for 8x8. \n");
    do_work(0);
    do_work(1);
}

انیمیشن روش بازگشتی

 

مسئله چند وزیر

 

الگوریتم مونت کارلو

از الگوریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگرد استفاده می‌شود. الگوریتم‌های مونت کارلو، احتمالی هستند، یعنی دستور اجرایی بعدی گاه به‌طور تصادفی تعیین می‌شوند. در الگوریتم قطعی چنین چیزی رخ نمی‌دهد. الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می‌شود، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می‌کند. تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می‌یابد.

شبه کد پیاده‌سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر

  int ostimate _ n_ queens (int n)
   {
          index i , j , col [1..n];
          int m , mprod , numnodes ;
          set _of_ index  prom _children;
          i = ۰;
          numnodes =۱ ;
          m = ۱;

        mprod  = ۱ ;
        while  (m!= 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; i!= n) {
        mprod = mprod * m ;
        numnodes  = numnodes + mprod * n;
        i ++;
        m = ۰ ;
        prom_childern  = Ø;
        for (j = 1 ; j ≤ n ; j++;) {
                col [i]  = j ;
                if (promising(i)) {

         m++;
         prom_children = prom _ children U {i};
                }
            }
             if (m!= ۰)  {
                 j = random selection from prom _childeren;
                 col [i];
             }
        }
         return numnodes;
     }

روش مکاشفه‌ای

برای حل این مسئله که دارای ۹۲ جواب است، باید تکنیکهایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها انجام شود. تعداد همه حالاتی که می‌تواند در روش Brute Force چک شود برابر ۱۶٬۷۷۷٬۲۱۶ یا هشت به توان هشت است! یکی از روش‌های حل این مسئله برای n>=4 یا n=1 استفاده از روش مکاشفه‌ای ( heuristic)است:

1- عدد n را بر عدد ۱۲ تقسیم کن و باقی‌مانده را یادداشت کن

۲- به ترتیب اعداد زوج ۲ تا n را در لیستی بنویس

۳- اگر باقی‌مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده.

۴- به لیست اعداد فرد ۱ تا n را به ترتیب اضافه کن، اما اگر باقی‌مانده ۸ بود اعداد را دو به دو باهم عوض کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه)

۵- اگر باقی‌مانده ۲ بود جای ۱ و۳ را با هم عوض کن و ۵ را به انتهای لیست ببر.

۶- اگر باقی‌مانده ۳ یا ۹ بود، اعداد ۱ و ۳ را به انتهای لیست ببر.

۷- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و…

این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روش‌های دیگری می‌توان استفاده کرد. روش حل مسئله ۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و چرخش به ۹۲ حالت قابل تبدیل است.

روش‌های جستجوی محلی

می‌توان به مسئله ۸ وزیر به عنوان یک مسئله بهینه‌سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد.

به عنوان مثال فرض کنید در صفحه شطرنج معمولی، ۸ وزیر را به دو روش زیر قرار دهیم:

مسئله ی چند وزیرمسئله ی چند وزیر

در روش چینش سمت چپ ۳ وزیر و در روش چینش سمت راست ۴ وزیر همدیگر را گارد می‌دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می‌توان مسئله بهینه‌سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب‌های ممکن برای مسئله باشد. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جواب‌های موجود در S، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله ۸ وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد.

روش‌های جستجوی محلی همگی حالت‌های همسایه حالت فعلی را برای رسیدن به بهینه‌ترین جواب بررسی می‌کنند. از این رو وجود دو تابع در همه این روش‌های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می‌کند و تابع دوم یکی از حالت‌های همسایه حالت فعلی را انتخاب می‌کند.

نحوه پیاده‌سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش‌های جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله ۸ وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد:

۱) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.

۲) یکی از وزیرها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.

۳) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

ماشین بردار پشتیبانی

ماشین بردار پشتیبان (Support vector machines – SVMs) یکی از روش‌های یادگیری بانظارت است که از آن برای طبقه‌بندی و رگرسیون استفاده می‌کنند.

این روش از جملهٔ روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاریدسته‌بندی کنندۀ SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های QP که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد. قبل از تقسیمِ خطی برای اینکه ماشین بتواند داده‌های با پیچیدگی بالا را دسته‌بندی کند داده‌ها را به وسیلهٔ تابعِ phi به فضای با ابعاد خیلی بالاتر می‌بریم. برای اینکه بتوانیم مسئله ابعاد خیلی بالا را با استفاده از این روش‌ها حل کنیم از قضیه دوگانی لاگرانژ برای تبدیلِ مسئلهٔ مینیمم‌سازی مورد نظر به فرم دوگانی آن که در آن به جای تابع پیچیدهٔ phi که ما را به فضایی با ابعاد بالا می‌برد، تابعِ ساده‌تری به نامِ تابع هسته که ضرب برداری تابع phi است ظاهر می‌شود استفاده می‌کنیم. از توابع هسته مختلفی از جمله هسته‌های نمایی، چندجمله‌ای و سیگموید می‌توان استفاده نمود.

یکی از معروفترین خودآموزها مربوط به است.

کاربردهای SVM

الگوریتم SVM، جز الگوریتم‌های تشخیص الگو دسته بندی می‌شود.از الگوریتم SVM، در هر جایی که نیاز به تشخیص الگو یا دسته بندی اشیا در کلاس‌های خاص باشد می‌توان استفاده کرد.در ادامه به کاربردهای این الگوریتم به صورت موردی اشاره می‌شود:

سیستم آنالیز ریسک، کنترل هواپیما بدون خلبان، ردیابی انحراف هواپیما، شبیه‌سازی مسیر، سیستم راهنمایی اتوماتیک اتومبیل، سیستم‌های بازرسی کیفیت، آنالیز کیفیت جوشکاری، پیش‌بینی کیفیت، آنالیز کیفیت کامپیوتر، آنالیز عملیاتهای آسیاب، آنالیز طراحی محصول شیمیایی، آنالیز نگهداری ماشین، پیشنهاد پروژه، مدیریت و برنامه‌ریزی، کنترل سیستم فرایند شیمیایی و دینامیکی، طراحی اعضای مصنوعی، بهینه‌سازی زمان پیوند اعضا، کاهش هزینه بیمارستان، بهبود کیفیت بیمارستان، آزمایش اتاق اورژانس، اکتشاف روغن و گاز، کنترل مسیر در دستگاه‌های خودکار، ربات، جراثقال، سیستم‌های بصری، تشخیص صدا، اختصار سخن، کلاسه بندی صوتی، آنالیز بازار، سیستم‌های مشاوره‌ای محاسبه هزینه موجودی، اختصار اطلاعات و تصاویر، خدمات اطلاعاتی اتوماتیک، مترجم لحظه‌ای زبان، سیستم‌های پردازش وجه مشتری، سیستم‌های تشخیص ترمز کامیون، زمانبندی وسیله نقلیه، سیستم‌های مسیریابی، کلاسه بندی نمودارهای مشتری/بازار، تشخیص دارو، بازبینی امضا، تخمین ریسک وام، شناسایی طیفی، ارزیابی سرمایه، کلاسه بندی انواع سلول‌ها، میکروبها و نمونه ها، پیش‌بینی فروشهای آینده، پیش‌بینی نیازهای محصول، پیش‌بینی وضعیت بازار، پیش‌بینی شاخصهای اقتصادی، پیش‌بینی ملزومات انرژی، پیش‌بینی واکنش‌های دارویی، پیش‌بینی بازتاب محصولات شیمیایی، پیش‌بینی هوا، پیش‌بینی محصول، پیش‌بینی ریسک محیطی، پیش‌بینی جداول داوری، مدل کردن کنترل فرایند، آنالیز فعالیت گارانتی، بازرسی اسناد، تشخیص هدف، تشخیص چهره، انواع جدید سنسورها، دستگاه کاشف زیر دریایی بوسیله امواج صوتی، رادار، پردازش سیگنالهای تصویری شامل مقایسه اطلاعات، پیگیری هدف، هدایت جنگ افزارها، تعیین قیمت وضعیت فعلی، جلوگیری از پارازیت، شناسایی تصویر /سیگنال، چیدمان یک مدار کامل، بینایی ماشین، مدل کردن غیر خطی، ترکیب صدا، کنترل فرایند ساخت، آنالیز مالی، پیش‌بینی فرایندهای تولید، ارزیابی بکارگیری یک سیاست، بهینه‌سازی محصول، تشخیص ماشین و فرایند، مدل کردن کنترل سیستم‌ها، مدل کردن ساختارهای شیمیایی، مدل کردن سیستم‌های دینامیکی، مدل کردن سیگنال تراکم، مدل کردن قالب‌سازی پلاستیکی، مدیریت قراردادهای سهام، مدیریت وجوه بیمه، دیریت سهام، تصویب چک بانکی، اکتشاف تقلب در کارت اعتباری، ثبت نسیه، بازبینی امضا از چکها، پیش‌بینی ارزش نسیه، مدیریت ریسک رهن، تشخیص حروف و اعدا، تشخیص بیماری و…..

تاریخچه

الگوریتم SVM اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شدو در سال ۱۹۹۵ توسط Vapnik و Corinna Cortes برای حالت غیرخطی تعمیم داده شد.

خلاصه استفاده عملی از SVM

ماتریس الگو را آماده می کنیم. تابع کرنلی را برای استفاده انتخاب می کنیم. پارامتر تابع کرنل و مقدار C را انتخاب می کنیم. برای محاسبه ی مقادیرα_i الگوریتم آموزشی را با استفاده از حل‌کننده‌های QP اجرا می کنیم. داده‌های جدید با استفاده از مقادیرα_i و بردارهای پشتیبان می‌توانند دسته بندی شوند.

مزایا و معایب SVM

آموزش نسبتاً ساده است برخلاف شبکه‌های عصبی در ماکزیمم‌های محلی گیر نمی‌افتد. برای داده‌های با ابعاد بالا تقریباً خوب جواب می‌دهد. مصالحه بین پیچیدگی دسته بندی‌کننده و میزان خطا به‌طور واضح کنترل می‌شود. به یک تابع کرنل خوب و انتخاب پارامتر C نیاز دارد.

ماشین بردار پشتیبان خطی

شکل 1

ما مجموعه داده‌های آزمایش {\displaystyle {\mathcal {D}}} شامل n عضو(نقطه)را در اختیار داریم که به صورت زیر تعریف می‌شود:

{\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}

جایی که مقدار y برابر ۱ یا -۱ و هر {\displaystyle \mathbf {x} _{i}} یک بردار حقیقی p-بعدی است. هدف پیدا کردن ابرصفحه جداکننده با بیشترین فاصله از نقاط حاشیه‌ای است که نقاط با {\displaystyle y_{i}=1} را از نقاط با {\displaystyle y_{i}=-1} جدا کند. هر ابر صفحه می‌تواند به صورت مجموعه‌ای از نقاط {\mathbf {x}} که شرط زیر را ارضا می‌کند نوشت:

{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,\,} جایی که . علامت ضرب است. {\displaystyle {\mathbf {w} }} بردار نرمال است، که به ابرصفحه عمود است. ما می خواهیم {\displaystyle {\mathbf {w} }} و {\displaystyle {\mathbf {b} }} را طوری انتخاب کنیم که بیشترین فاصله بین ابر صفحه‌های موازی که داده‌ها را از هم جدا می‌کنند، ایجاد شود. این ابرصفحه‌ها با استفاده از رابطه زیر توصیف می‌شوند.
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=1\,}

و

شکل 2
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=-1.\,}
اگر داده‌های آموزشی جدایی پذیر خطی باشند، ما می‌توانیم دو ابر صفحه در حاشیه نقاط به‌طوری‌که هیچ نقطه مشترکی نداشته باشند، در نظر بگیریم و سپس سعی کنیم، فاصله آن‌ها را، ماکسیمم کنیم. با استفاده از هندسه، فاصله این دو صفحه {\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}} است. بنابراین ما باید {\displaystyle \|\mathbf {w} \|} را مینیمم کنیم. برای اینکه از ورود نقاط به حاشیه جلوگیری کنیم، شرایط زیر را اضافه می کنیم: برای هر i
of the first class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad {\text{ for }}\mathbf {x} _{i}}

یا

of the second class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad {\text{ for }}\mathbf {x} _{i}}

این می‌تواند به صورت زیر نوشته شود:

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.\qquad \qquad (1)}

با کنار هم قرار دادن این دو یک مسئله بهینه‌سازی به دست می‌آید:

Minimize (in {\displaystyle {\mathbf {w} ,b}})

{\displaystyle \|\mathbf {w} \|}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,}

فرم اولیه

مسئله بهینه‌سازی مشاهده شده در قسمت قبل، مسئله سختی، برای حل کردن است، زیرا به||w|| وابسته است (نرم w ) . خوشبختانه می‌توانیم، بدون تغییر در مسئله||w|| را با{\displaystyle {\tfrac {1}{2}}\|\mathbf {w} \|^{2}}جانشین کنیم( عبارت ½ برای آسودگی در محاسبات ریاضی آورده شده). این یک مسئله بهینه سازی (OP)برنامه‌ریزی غیرخطی(QP) است. به‌طور واضح تر :

Minimize (in {\displaystyle {\mathbf {w} ,b}}) c

{\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.}

می توان عبارت قبل را با استفاده از ضرایب نا منفی لاگرانژ به صورت زیر نوشت که در آن ضرایب لاگرانژ هستند {\displaystyle \alpha _{i}}:

{\displaystyle \min _{\mathbf {w} ,b,{\boldsymbol {\alpha }}}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

اما فرمول فوق اشتباه است . فرض کنید ما بتوانیم خانواده‌ای از ابرصفحات که نقاط را تقسیم می‌کنند پیدا کنیم . پس همه {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1\geq 0} . بنا بر این ما می‌توانیم مینیمم را با فرستادن همه {\displaystyle \alpha _{i}} به{\displaystyle +\infty } پیدا کنیم. با این حال شرط پیش گفته می‌تواند به صورت پایین بیان شود:

{\displaystyle \min _{\mathbf {w} ,b}\max _{\boldsymbol {\alpha }}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

ما به دنبال نقاط saddle میگردیم.حالا می‌توان این مسئله را به کمک برنامه‌ریزی غیرخطی استاندارد حل کرد. جواب می‌تواند به صورت ترکیب خطی از بردارهای آموزشی بیان شود :

{\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }}

تنها چند{\displaystyle \alpha _{i}} بزرگتر از صفر خواهد بود.{\displaystyle \mathbf {x_{i}} } متناظر، دقیقاً همان بردار پشتیبان خواهد بود و به شرط را ارضا خواهد کرد. از این می‌توان نتیجه گرفت که بردارهای پشتیبان شرط زیر را نیز ارضا می‌کنند: {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1} که اجازه می دهد مفدار b تعریف شود. در عمل الگوریتم مقاوم تر خواهد بود اگر از تمام {\displaystyle N_{SV}} بردار پشتیبان میانگین گرفته شود:

{\displaystyle b={\frac {1}{N_{SV}}}\sum _{i=1}^{N_{SV}}{(\mathbf {w} \cdot \mathbf {x_{i}} -y_{i})}}

فرم دوگان

استفاده از این واقعیت که {\displaystyle \|\mathbf {w} \|^{2}=w\cdot w} و جانشینی {\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }} می‌توان نشان داد که دوگان SVM به مسئله بهینه‌سازی زیر ساده می‌شود:

Maximize (in {\displaystyle \alpha _{i}} )

{\displaystyle {\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}\mathbf {x} _{i}^{T}\mathbf {x} _{j}=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})}

subject to (for any}{\displaystyle i=1,\dots ,n})

{\displaystyle \alpha _{i}\geq 0,\,}

and to the constraint from the minimization in {\displaystyle b}

{\displaystyle \sum _{i=1}^{n}\alpha _{i}y_{i}=0.}

در اینجا هسته به صورت {\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}} تعریف می‌شود. عبارت \alpha  تشکیل یک دوگان برای بردار وزن‌ها مجموعه آموزشی می دهد:

{\displaystyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\mathbf {x} _{i}.}

ماشین بردار پشتیبان چند کلاسی

SVM اساساً یک جداکننده دودویی است. در بخش قبلی پایه‌های تئوری ماشین‌های بردار پشتیبان برای دسته بندی دو کلاس تشریح شد. یک تشخیص الگوی چند کلاسی می‌تواند به وسیله ی ترکیب ماشین‌های بردار پشیبان دو کلاسی حاصل شود. به‌طور معمول دو دید برای این هدف وجود دارد. یکی از آن‌ها استراتژی “یک در مقابل همه ” برای دسته بندی هر جفت کلاس و کلاس‌های باقی‌مانده‌است. دیگر استراتژی “یک در مقابل یک” برای دسته بندی هر جفت است. در شرایطی که دسته بندی اول به دسته بندی مبهم منجر می‌شود.برای مسائل چند کلاسی٬رهیافت کلی کاهش مسئله ی چند کلاسی به چندین مسئله دودویی است. هریک از مسائل با یک جداکننده دودویی حل می‌شود. سپس خروجی جداکننده‌های دودویی SVM با هم ترکیب شده و به این ترتیب مسئله چند کلاس حل می‌شود.

ماشین‌های بردار پشتیبان غیرخطی

شکل 3

ابرصفحه جداکننده بهینه اولین بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که یک دسته‌کننده خطی بود. در سال ۱۹۹۲ ،Bernhard Boser ، Isabelle GuyonوVapnik راهی را برای ایجاد دسته بند غیرخطی، با استفاده قرار دادن هسته برای پیدا کردن ابرصفحه با بیشتر حاشیه، پیشنهاد دادند. الگوریتم نتیجه شده ظاهراً مشابه است، به جز آنکه تمام ضرب‌های نقطه‌ای با یک تابع هسته غیرخطی جایگزین شداند. این اجازه می‌دهد، الگوریتم، برای ابرصفحه با بیشترین حاشیه در یک فضای ویژگی تغییرشکل داده، مناسب باشد. ممکن است، تغییرشکل غیرخطی باشد و فضای تغییر یافته، دارای ابعاد بالاتری باشد. به هر حال دسته‌کننده، یک ابرصفحه در فضای ویژگی با ابعاد بالا است، که ممکن است در فضای ورودی نیز غیرخطی باشد.

اگر از هسته با تابع گوسیین استفاده شود، فضای ویژگی متناظر، یک فضای هیلبرت نامتناهی است. دسته‌کننده ی بیشترین حاشیه، خوش ترتیب است، بنابراین ابعاد نامتناهی، نتیجه را خراب نمی‌کند. هسته‌های متداول به صورت زیر هستند:

  • چندجمله‌ای (همگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} )^{d}}
  • چندجمله‌ای (ناهمگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} +1)^{d}}
  • گوسیین Radial Basis Function:  {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\exp(-\gamma \|\mathbf {x_{i}} -\mathbf {x_{j}} \|^{2})}، for {\displaystyle \gamma >0.} Sometimes parametrized using {\displaystyle \gamma =1/{2\sigma ^{2}}}
  • تانژانت هذلولی: {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x_{i}} \cdot \mathbf {x_{j}} +c)}، for some (not every) {\displaystyle \kappa >0} and {\displaystyle c<0}

هسته با انتقال {\displaystyle \varphi (\mathbf {x_{i}} )} با تساوی {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\varphi (\mathbf {x_{i}} )\cdot \varphi (\mathbf {x_{j}} )} در ارتباط است. همچنین مقدار wدر فضای انتقال یافته برابر{\displaystyle \textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i}).} است. ضرب نقطه‌ای با w می‌تواند توسط هسته محاسبه شود یعنی {\displaystyle \textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}. به هر حال در حالت عادی w’ وجود ندارد، به‌طوری‌که {\displaystyle \mathbf {w} \cdot \varphi (\mathbf {x} )=k(\mathbf {w'} ,\mathbf {x} ).}

 

منبع

 

 

ماشین بردار پشتیبان (svm) قسمت 1
ماشین بردار پشتیبان (svm) قسمت 2
ماشین بردار پشتیبان (svm) قسمت 3