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

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

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

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

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

ที่ไหน:

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

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

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

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

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

 

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

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

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

 

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

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

 

ทางการ:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

ที่ไหน:

• $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$} ถ่วงน้ําหนักด้วยจํานวนตัวอย่าง

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

 

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

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

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

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

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

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

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

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

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

$$ x_{s(i)} \leq x_{s(i+1)} $$

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

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

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

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

$$ \mathcal{O} ( m n \log^2 n ) $$

ที่ไหน:

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

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