python kmeans

หลาม-kmeans

การใช้หลามของการจัดกลุ่มแบบเคมีน เคมีนเป็นเทคนิคการเรียนรู้แบบไม่มีผู้ดูแลซึ่งพยายามจัดกลุ่มข้อมูลที่คล้ายกันเข้าเป็นกลุ่มตามจำนวนที่ผู้ใช้ระบุ ตัวอย่างด้านล่างแสดงความก้าวหน้าของคลัสเตอร์สำหรับชุดข้อมูล Iris โดยใช้อัลกอริธึมการเริ่มต้น k-means++ เซนทรอยด์

คำอธิบาย

k-means พยายามระบุจำนวนคลัสเตอร์ k(<N) ที่ผู้ใช้ระบุจากชุดของเวกเตอร์มูลค่าจริง N มิติ อัลกอริทึมจะดำเนินการโดยพยายามลดผลรวมของระยะทางกำลังสองจากศูนย์กลางคลัสเตอร์ไปยังสมาชิกคลัสเตอร์ อัลกอริธึม Canonical ดำเนินการในสามขั้นตอน:

1. เริ่มต้น k เซนทรอยด์สุ่ม (ศูนย์กลางคลัสเตอร์);
2. กำหนดจุดข้อมูลให้กับคลัสเตอร์ที่ใกล้ที่สุดตามการวัดระยะทาง (โดยทั่วไปคือระยะทางแบบยุคลิด)
3. อัพเดตเซนทรอยด์เป็นค่าเฉลี่ยของสมาชิกของคลัสเตอร์
4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่างานจากขั้นตอนที่ 2 จะไม่เปลี่ยนแปลง

ผลลัพธ์ของอัลกอริธึมคือการกำหนดคลัสเตอร์สำหรับแต่ละจุดข้อมูล และระดับสุดท้ายของ "การบิดเบือน" อัลกอริธึมไม่ได้สร้างโซลูชันที่เหมาะสมที่สุดที่พิสูจน์ได้ และศูนย์คลัสเตอร์เริ่มต้นอาจทำให้อัลกอริธึมติดค้างอยู่ในโซลูชันที่เหมาะสมที่สุดเฉพาะที่ซึ่งต่ำกว่าประสิทธิภาพที่เหมาะสมที่สุดอย่างชัดเจน (ดูตัวอย่าง 2d พื้นฐานในส่วนผลลัพธ์)

การวิจัยจำนวนมากมุ่งเน้นไปที่:

• การเลือกศูนย์คลัสเตอร์เริ่มต้น K-Means++ เป็นวิธีการที่รู้จักกันดี และรวมอยู่ในการใช้งานนี้ อัลกอริธึมมีรายละเอียดอยู่ในส่วนย่อยต่อไปนี้
• ระยะทางในการคำนวณ เช่น การใช้มาตรการอื่นที่ไม่ใช่แบบยุคลิด ดูที่นี่

เคมีนส์++

แทนที่จะเตรียมใช้งานเซนทรอยด์แบบสุ่มดังในขั้นตอนที่ 1 ข้างต้น k-means++ จะกระจายเซนทรอยด์เริ่มต้นอย่างน่าจะเป็นไปได้เพื่อหลีกเลี่ยงการกำหนดค่าเริ่มต้นที่ไม่ดี อัลกอริทึมคือ:

1. เลือกเซนทรอยด์ตัวแรกแบบสุ่ม
2. สำหรับแต่ละจุดข้อมูล x ให้คำนวณระยะทาง d(x) จาก x ไปยังจุดเซนทรอยด์ที่ใกล้ที่สุดซึ่งถูกเลือกไว้แล้ว
3. เลือกจุดข้อมูลที่จะเป็นจุดเซนทรอยด์ถัดไปโดยใช้ความน่าจะเป็นแบบถ่วงน้ำหนักตามสัดส่วน d(x)2

เทคนิคนี้ให้ความโปรดปรานกับจุดข้อมูลที่ไม่ใกล้กับเซนทรอยด์เริ่มต้นอื่น และใช้นโยบายการเลือกที่ชวนให้นึกถึงการเลือกวงล้อรูเล็ต (หรือสัดส่วนตามความเหมาะสม) ที่มักใช้ในอัลกอริทึมทางพันธุกรรม

ทรัพยากร

อัลกอริธึมพื้นฐาน

• K-Means ได้รับการอธิบายไว้ในอัลกอริทึม 10 อันดับแรกสำหรับการขุดข้อมูล

• K-Means มีรายละเอียดอยู่ในทฤษฎีสารสนเทศ การอนุมาน และอัลกอริทึมการเรียนรู้ ข้อความที่ตัดตอนมาที่นี่

• ศาสตราจารย์แอนดรูว์ มัวร์ แห่งมหาวิทยาลัยเชียงใหม่มีข้อสังเกตดีๆ ไว้ดังนี้

• ตัวอย่าง Edureka โดยใช้ข้อมูลอาชญากรรม

การเริ่มต้นของคลัสเตอร์

• K-Means++ และรายงานฉบับเต็ม ที่นี่

• การศึกษาเปรียบเทียบวิธีการเริ่มต้นที่มีประสิทธิภาพสำหรับอัลกอริธึมการจัดกลุ่ม K-Means

ทำไมไม่ใช้ SciPy?

SciPy มีการใช้งานแบบเคมีน วัตถุประสงค์ของงานนี้คือเพื่อสร้างการใช้งาน Python อย่างแท้จริงเพื่อจุดประสงค์ในการเรียนรู้ และช่วยให้ผู้อื่นเรียนรู้อัลกอริธึมเคมีน ผู้อ่านที่สนใจซึ่งมีประสบการณ์ Python เพียงเล็กน้อยจะสามารถอ่านและข้ามโค้ดนี้ได้โดยไม่ต้องเพิ่มความซับซ้อนของไลบรารีเช่น SciPy ไม่ได้มีวัตถุประสงค์เพื่อใช้ในการผลิตแต่อย่างใด :)

กำลังรันโค้ด

การพึ่งพาอาศัยกัน

• หลาม 3.6.3
• matplotlib 2.1.1 - ดูคำแนะนำในการติดตั้งที่นี่

การดำเนินการ

รันโค้ดด้วยล่ามหลาม:

python kmeans.py ./resources/<config.cfg>

โดยที่ config.cfg เป็นไฟล์การกำหนดค่าข้อความธรรมดา รูปแบบของไฟล์กำหนดค่าเป็น python dict โดยมีฟิลด์ต่อไปนี้:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

คุณต้องระบุ:

• ไฟล์ข้อมูล CSV;
• ชุดย่อยของฟิลด์ที่จะฉายภาพจากไฟล์
• จำนวนกลุ่มที่จะก่อตัว k;
• ชุดย่อยของคุณลักษณะที่ใช้ในกระบวนการจัดกลุ่ม
• ระบุ func คลัสเตอร์เริ่มต้น (ค่าเริ่มต้น = 'rand_init_centroids') ผู้เขียนที่สนใจได้เพิ่มของตนเองลงในโค้ดและระบุที่นี่
• การกำหนดค่าพล็อตที่มี
  • คำนำหน้าสำหรับไฟล์ PNG ที่สร้างขึ้นระหว่างกระบวนการในไดเร็กทอรีการทำงาน หากไม่ได้ระบุไว้ รูปภาพจะไม่ถูกสร้างขึ้น
  • การกำหนดค่าแต่ละพล็อต จำกัดไว้ที่ 2 มิติต่อพล็อต

ผลลัพธ์

ชุดข้อมูลไอริส

ชุดข้อมูล Iris (iris.config) จาก Lichman, M. (2013) พื้นที่เก็บข้อมูลการเรียนรู้ของเครื่อง UCI เออร์ไวน์, แคลิฟอร์เนีย: มหาวิทยาลัยแคลิฟอร์เนีย คณะวิชาสารสนเทศและวิทยาการคอมพิวเตอร์ เป็นชุดข้อมูลที่รู้จักกันดีในชุมชนแมชชีนเลิร์นนิง นี่คือผลลัพธ์ของกลุ่มเริ่มต้นแบบสุ่มของฉัน:

ข้อมูลสังเคราะห์ 2D พื้นฐาน

ข้อมูลนี้ถูกสร้างขึ้นเพื่อวัตถุประสงค์ในการแก้ไขข้อบกพร่อง (ดู basic2d.config) และแสดงให้เห็นถึงผลกระทบของการมีทางเลือกที่ไม่ดีสำหรับคลัสเตอร์สุ่มเริ่มต้น ผลลัพธ์ด้านล่างนี้แสดงให้เห็นถึงการกำหนดค่าเซนทรอยด์เริ่มต้นที่ป้องกันไม่ให้อัลกอริทึมเข้าถึงการกำหนดคลัสเตอร์ที่ชัดเจน ในกรณีนี้ การวางตำแหน่งเซนทรอยด์สีแดงหมายความว่าเซนทรอยด์สีน้ำเงินจับจุดข้อมูลทั้งหมดในด้านซ้ายล่าง และควอแดรนต์ด้านขวาล่าง

อาชญากรรม

ชุดข้อมูลอาชญากรรม (crime.config) มาจาก Edureka ที่นี่