ตัวแยกการทํางานแบบตรงสําหรับการแยกประเภทไบนารีด้วยฟีเจอร์ตัวเลข

ในหน่วยโฆษณานี้ คุณจะได้สํารวจอัลกอริทึมตัวแยกที่ง่ายที่สุดในการใช้งานมากที่สุด ซึ่งจะสร้างเงื่อนไขของรูปแบบ featureit ในการตั้งค่าต่อไปนี้

  • งานการแยกประเภทไบนารี
  • ไม่มีค่าในตัวอย่าง
  • ไม่มีดัชนีที่คํานวณไว้ล่วงหน้าในตัวอย่าง

สมมติว่ามีตัวอย่าง n พร้อมฟีเจอร์ตัวเลขและป้ายกํากับไบนารี "orange" และ "blue" อธิบายอย่างเป็นทางการว่าชุดข้อมูล D มีลักษณะดังนี้

D={(xi,yi)}i[1,n]

ที่ไหน:

  • xi คือค่าของฟีเจอร์ตัวเลขใน R (ชุดตัวเลขจริง)
  • yi เป็นค่าป้ายกํากับการแยกประเภทไบนารีใน {orange, blue}

วัตถุประสงค์ของเราคือการค้นหาค่าเกณฑ์ t (เกณฑ์) ดังกล่าว เช่น การแบ่งตัวอย่าง D ไปยังกลุ่ม T(rue) และ F(alse) ตามเงื่อนไข xit ช่วยแบ่งค่าป้ายกํากับ เช่น ตัวอย่างเพิ่มเติม "orange" ตัวอย่าง $t;&t.;blue&&t.

Shannon entropy เป็นเครื่องวัดความผิดปกติ สําหรับป้ายกํากับไบนารี

  • เอนโทรปี Shannon มีค่าสูงสุดเมื่อป้ายกํากับในตัวอย่างมีความสมดุล (สีฟ้า 50% และสีส้ม 50%)
  • เอนโทรปี Shannon มีค่าขั้นต่ํา (ค่า 0) เมื่อป้ายกํากับในตัวอย่างเป็น เฉพาะ (สีฟ้า 100% หรือสีส้ม 100%)

แผนภาพ 3 ภาพ แผนภาพเอนโทรปีสูงแสดงให้เห็นการผสมผสานระหว่าง 2 คลาสที่ต่างกัน แผนภาพด้านล่างแสดงการผสมผสานกันเล็กน้อยระหว่าง 2 ชั้นเรียน แผนภาพ "ไม่มีเอนโทรปี" จะไม่แสดงการมิกซ์คลาสต่างๆ จาก 2 คลาส กล่าวคือ แผนภาพไม่มีเอนโทรปีจะแสดงเพียงคลาสเดียว

รูปที่ 8 ระดับเอนโทรปี 3 ระดับ

 

ก่อนหน้านี้เราต้องการหาเงื่อนไขที่ลดผลรวมที่ถ่วงน้ําหนักของการกระจายป้ายกํากับใน T และ F คะแนนที่เกี่ยวข้องคือการได้ข้อมูล ซึ่งเป็นความแตกต่างระหว่างเอนโทรปี D&#39 และเอนโทรปี {T,F} ความแตกต่างนี้เรียกว่าการได้ข้อมูล

รูปต่อไปนี้แสดงการแยกส่วนที่ไม่ถูกต้องซึ่งเอนโทรปียังสูงอยู่และข้อมูลต่ํา

แผนภาพ 2 ภาพ แผนภาพทั้ง 2 รูปแสดงการผสมระหว่าง 2 คลาสที่เกือบจะเหมือนกันทุกประการ

รูปที่ 9 การแยกที่ไม่ถูกต้องไม่ลดเอนโทรปีของป้ายกํากับ

 

ในทางตรงกันข้าม ตัวเลขต่อไปนี้แสดงการแยกที่ดีกว่าซึ่งเอนโทรปีต่ํา (และข้อมูลมีค่าสูง)

แผนภาพ 2 ชุด แผนภาพหนึ่งประกอบด้วยกลุ่มสีส้มประมาณ 95% และชั้นสีน้ําเงิน 5% แผนภาพอื่นๆ ประกอบด้วยชั้นสีน้ําเงิน 95% และ 5% ของชั้นสีส้ม

รูปที่ 10 การแยกส่วนที่ถูกต้องจะลดเอนโทรปีของป้ายกํากับ

 

ทางการ:

T={(xi,yi)|(xi,yi)D with xit}F={(xi,yi)|(xi,yi)D with xi<t}R(X)=|{x|xX and x=pos}||X|H(X)=plogp(1p)log(1p) with p=R(X)IG(D,T,F)=H(D)|T||D|H(T)|F||D|H(F)

ที่ไหน:

  • IG(D,T,F) คือผลพลอยได้ของการแบ่ง D เป็น T และ F
  • H(X) คือเอนโทรปีของชุดตัวอย่างที่ X
  • |X| คือจํานวนองค์ประกอบในชุด X
  • t คือค่าเกณฑ์
  • pos คือค่าป้ายกํากับบวก เช่น "blue" ในตัวอย่างด้านบน การเลือกป้ายกํากับอื่นเป็น "ป้ายกํากับเชิงบวก" จะไม่เปลี่ยนค่าของเอนโทรปีหรือข้อมูลที่ได้
  • R(X) คืออัตราส่วนของค่าป้ายกํากับเชิงบวกในตัวอย่าง X
  • D คือชุดข้อมูล (ตามที่กําหนดไว้ก่อนหน้านี้ในหน่วยโฆษณานี้)

ในตัวอย่างต่อไปนี้ เราพิจารณาชุดข้อมูลการจัดประเภทแบบไบนารีที่มีฟีเจอร์ตัวเลข x ตัวเลขเดียว ตัวเลขต่อไปนี้แสดงค่าเกณฑ์ t (แกน x) ที่แตกต่างกัน

  1. ฮิสโตแกรมของฟีเจอร์ x
  2. อัตราส่วนของ "blue" ตัวอย่างในชุด D, T และ F ตามค่าเกณฑ์
  3. เอนโทรปีใน D, T และ F
  4. ข้อมูลที่ได้คือ เดลต้าเอนโทรปีระหว่าง D ถึง {T,F} ถ่วงน้ําหนักด้วยจํานวนตัวอย่าง

พล็อตค่าเกณฑ์ 4 แบบ
เทียบกับพารามิเตอร์อื่นๆ รายการที่สรุปตัวเลขนี้สรุปถึงพล็อตแต่ละรายการเหล่านี้

รูปที่ 11 พล็อตเกณฑ์ 4 ข้อ

 

แปลงเหล่านี้จะแสดงข้อมูลต่อไปนี้

  • พล็อต "ความถี่" แสดงให้เห็นว่าการสังเกตการณ์จะกระจายไปได้ดีโดยมีความเข้มข้นระหว่าง 18-60 การกระจายมูลค่าที่กว้างหมายความว่ามีการแบ่งส่วนที่เป็นไปได้จํานวนมาก ซึ่งเป็นประโยชน์ในการฝึกโมเดล
  • อัตราส่วนของป้ายกํากับ "blue" ในชุดข้อมูลอยู่ที่ประมาณ 25% &อัตราส่วนของป้ายกํากับสีฟ้า&;;พล็อตแสดงให้เห็นว่าสําหรับค่าเกณฑ์ที่อยู่ระหว่าง 20 ถึง 50:

    • ชุด T มีตัวอย่างป้ายกํากับเกิน "blue" (สูงสุด 35% สําหรับเกณฑ์ 35)
    • ชุด F มีตัวอย่างป้ายกํากับ ""blue" รวมไม่สมบูรณ์ (เพียง 8% สําหรับเกณฑ์ 35)

    ทั้ง "อัตราส่วนของป้ายกํากับสีน้ําเงิน" และพล็อต "entropy" ระบุว่าป้ายกํากับต่างๆ สามารถแยกกันได้ในช่วงที่ใช้เกณฑ์นี้

  • การสังเกตการณ์นี้ได้รับการยืนยันในพล็อต "info" ข้อมูล เราจะเห็นได้ว่าข้อมูลที่ได้คือ t~=28 ซึ่งได้มาซึ่งค่าโดยประมาณคือ 0.074 ดังนั้น เงื่อนไขที่แสดงผลโดยตัวคั่นคือ x28

  • การได้ข้อมูลจะเป็นค่าบวกหรือเป็นค่าว่างเสมอ เส้นนี้บรรจบกันเป็น 0 เนื่องจากค่าเกณฑ์จะบรรจบกับค่าสูงสุด / ค่าต่ําสุด ในกรณีดังกล่าว F หรือ T จะว่างเปล่าในขณะที่อีกรายการมีชุดข้อมูลทั้งหมดและแสดงเอนโทรปีเท่ากับชุดข้อมูลใน D ข้อมูลที่ได้อาจเป็น 0 เมื่อ H(T) = H(F) = H(D) เกณฑ์ขั้นต่ําที่ 60 อัตราส่วนของ &quot.F

ค่าผู้สมัครสําหรับ t ในชุดของตัวเลขจริง (R) ไม่มีที่สิ้นสุด อย่างไรก็ตาม ในตัวอย่างมีจํานวนจํากัด จะมีเพียงส่วนย่อยของ DD TFt$ เพียงไม่กี่อย่างเท่านั้นในการทดสอบ

วิธีการคลาสสิกคือการจัดเรียงค่า xi เพื่อเรียงลําดับ xs(i) เพิ่มขึ้น ดังนี้

xs(i)xs(i+1)

จากนั้นทดสอบ t กับค่าทุกๆ ครึ่งหนึ่งระหว่างค่าที่จัดเรียงติดกันของ xi เช่น สมมติว่าคุณมีค่าลอยตัว 1,000 ค่าของฟีเจอร์หนึ่งๆ หลังจากจัดเรียง สมมติว่าค่า 2 ค่าแรกคือ 8.5 และ 8.7 ในกรณีนี้ ค่าเกณฑ์แรกที่จะทดสอบคือ 8.6

เราพิจารณาค่าตัวเลือกต่อไปนี้สําหรับเงื่อนไขต่อไปนี้

X={xs(i)+xs(i+1)2|xs(i)xs(i+1)}

ความซับซ้อนของอัลกอริทึมในช่วงเวลานี้คือ O(nlogn) ที่มี n ของจํานวนตัวอย่างในโหนด (เนื่องจากการจัดเรียงค่าฟีเจอร์) เมื่อใช้ในโครงสร้างการตัดสินใจ อัลกอริทึมการแยกจะใช้กับแต่ละโหนดและแต่ละฟีเจอร์ โปรดทราบว่าแต่ละโหนดจะได้รับตัวอย่างระดับบนสุดประมาณ 1/2 ดังนั้น ตามทฤษฎีบทของปรมาจารย์ ความซับซ้อนของการฝึกกําหนดการตัดสินใจด้วยการแยกนี้คือ

O(mnlog2n)

ที่ไหน:

  • m คือจํานวนฟีเจอร์
  • n คือจํานวนตัวอย่างในการฝึกอบรม

ในอัลกอริทึมนี้ ค่าของฟีเจอร์ไม่สําคัญ แต่จะมีเพียงลําดับเท่านั้น ด้วยเหตุนี้ อัลกอริทึมนี้จะทํางานโดยอิสระจากสเกลหรือการกระจายของค่าฟีเจอร์ ด้วยเหตุนี้ เราจึงไม่จําเป็นต้องปรับค่าฟีเจอร์ตัวเลขให้เท่ากันหรือปรับให้เป็นมาตรฐานเมื่อฝึกแผนผังการตัดสินใจ