Data interpolation with SciPy
|
|
Polynom-InterpolationPolynom-Interpolation เป็นวิธีหาค่าของจุดที่ต้องการผ่านสมการพหุนาม (Polynom-Equation) โดยในขั้นแรกเราต้องแก้สมการพหุนาม เพื่อหาสัมประสิทธิ์ (Coefficients) ของพหุนามก่อน จากนั้นเราจึงสามารถแทนค่าตัวแปร ลงในฟังก์ชั่นพหุนาม (Polynom-Function) ได้ยกตัวอย่างเช่น f(x) เป็นพหุนามกำลัง 3 ซึ่งสามารถแจกแจงได้เป็น f(x) = p3 · x³ + p2 · x² + p1· x + p0 สิ่งที่เราต้องหาคือ p0 - p3 โดยที่เรามีค่า yn = f(xn) และ xn โดยที่ n เป็นจำนวนเต็มตั้งแต่ 0 ถึง N การที่เราจะหาค่า p0 - p3 ได้นั้นเราต้องมีค่า xn และ yn อย่างน้อย 4 ค่า ( N ≥4 ) เมื่อเราได้ค่าสัมประสิทธิ์ p0 - p3 แล้วเราจึงสามารถแทนค่าใด ๆ ในฟังก์ชั่นได้ (เฮ้อ... เหนื่อย เพิ่งรู้ว่าเขียนอะไรที่เป็นคณิตศาสตร์มาก ๆ มันเหนื่อยอย่างนี้นี่เอง) ภาคทฤษฏีผ่านไป ที่นี้มาถึงภาคทฤษฏีน้อยลงหน่อย นั่นคือการเขียนโปรแกรม (ก็ยังเป็นทฤษฏีอยู่ดี) ปกติแล้วการหาค่าสัมประสิทธิ์ด้วยมือนั้นยากมาก แค่สมการกำลังสามก็แย่แล้ว ดังนั้น การค่าสัมประสิทธิ์ที่มากกว่ากำลังสาม ก็จะหากันด้วย โปรแกรม ซึ่งใน NumPy เองก็มีโมดูลให้หาค่าสัมประสิทธิ์นั่นคือ polyfit(x, y, n) โดยที่ x, y คือเวคเตอร์ค่าของฟังก์ชั่นพหุนามที่เรารู้ (xn, yn ในสมการ) และ n คือ เลขกำลังของฟังก์ชั่นพหุนาม (N ในสมการ) polyfit จะคืนค่าเวคเตอร์สัมประสิทธิ์มาให้เรา ยกตัวอย่างเช่น โค้ดข้างล่างนี้ เรามีค่าที่เป็น discrete ทั้งหมด N ค่า เราจึงสามารถหาค่าที่เป็น continue ผ่านหพุนามกำลังที่ N-1 ได้ โดยค่า continue ระหว่างค่า discrete 2 ค่า จะมีจำนวนทั้งสิ้น 32 ค่า #!/usr/bin/python import numpy import pylab # Numbers of coefficients N = 5 # Random-point of polynom x = numpy.arange(0,N*32,32) y = numpy.random.randn(N) # Find polynom-coefficients p = numpy.polyfit(x,y,N-1) # Interpolate polynom mypolynom = lambda x : numpy.polyval(p,x) vecpolyval = numpy.vectorize(mypolynom) newx = numpy.arange(0,N*32) newy = vecpolyval(newx) # Plot pylab.grid(True) pylab.plot(x,y,'o') pylab.plot(newx, newy, linewidth=2) pylab.show()plain code คำอธิบาย บรรทัดที่ 7 : กำหนดจำนวนค่า discrete และเลขกำลังของพหุนาม บรรทัดที่ 10 : กำหนดแกน x ของค่า discrete บรรทัดที่ 11 : สุ่มหาค่าแกน y ของค่า discrete บรรทัดที่ 14 : หาค่าสัมประสิทธิ์ของพหุนาม บรรทัดที่ 17 - 20 : หาค่าแกน y ที่เป็นค่าต่อเนื่อง โดยผ่านโมดูล polyval แต่เนื่องจาก polyval รับ parameter ที่เป็น array ไม่ได้ ก็เลยต้องดัดแปลงกันนิดหน่อย บรรทัดที่ 23-26 : แสดงผล ผลที่ได้ หากกำหนด N = 3 ผลที่ได้ก็จะเป็นดังนี้ ![]() หากกำหนด N = 7 ผลที่ได้ก็จะเป็นดังนี้
หากกำหนด N = 15 ผลที่ได้ก็จะเป็นดังนี้
![]() Spline-InterpolationSpline-Interpolation หรือมีชื่อเรียกภาษาไทยว่า เส้นโค้งเบซิเยร์ นั้นมีพื้นฐานมาจาก Polynom-Interpolation โดยแทนที่จะใช้พหุนามกำลังสูง ๆ สำหรับ Interpolation ที่มีข้อมูลเฉพาะจุดมาก ๆ (ค่า N สูง) ก็จะใช้วิธีตัดแบ่ง ข้อมูลเฉพาะจุดออกเป็นหลาย ๆ ส่วน แล้ว Interpolate ข้อมูลแต่ละส่วนด้วยพหุนามกำลังต่ำ ๆ แทน ทำให้ข้อมูลที่ได้มีความเสถียรมากกว่า Polynom-Interpolation (ค่าสูงสุด และค่าต่ำสุด ไม่สูงหรือต่ำจนเกินไป) โดยทั่วไปก็จะใช้พหุนามกำลังสอง ( Cubic-Spline-Interpolation ) พหุนามกำลังสี่ (Quadratic-Spline-Interpolation)Spline-Interpolation เป็นวิธี Interpolate ข้อมูลที่ได้รับการนำมาใช้งานมากที่สุดก็ว่าได้ โดยเฉพาะอย่างยิ่ง ในส่วนของ Signal-Processing และ Image-Processing ทำให้ภาษาเขียนโปรแกรมเกือบทุกภาษา มี Spline-Interpolation ให้ใช้งาน ซึ่งใน Python เองก็มีอยู่ในโมดูล scipy.signal (SciPy ไม่ได้เป็น Builtins-Module แต่สามารถดาวน์โหลดได้ free like free speech ที่ SciPy-Download ) ในโมดูล scipy.signal มี Spline-Interpolation ให้เลือกใช้งานหลายตัวด้วยกัน ได้แก่ bspilne, cspline, qsline, gauss_spline แต่ที่ผมใช้งานบ่อย ๆ คือ cspline ( Cubic-Spline-Interpolation ) และ qspline (Quadratic-Spline-Interpolation) ซึ่งผลที่ได้ไม่ต่างกันมากนัก ตัวอย่างข้างล่าง เป็นตัวอย่างการใช้งาน cspline ที่มีโค้ดเหมือนตัวอย่างใน Polynom-Interpolation เกือบทุกอย่าง ยกเว้นในบรรทัดที่ 15-17 ที่เปลี่ยนจาก Polynome-Interpolation เป็น Cubic-Spline-Interpolation แทน #!/usr/bin/python import numpy import pylab from scipy.signal import cspline1d, cspline1d_eval # Dimension of signal N = 40 # Random-point of polynom x = numpy.arange(0,N*32,32) y = numpy.random.randn(N) # Cubic-Spline-Interpolation cs = cspline1d(y) newx = numpy.arange(0,N*32) newy = cspline1d_eval(cs, newx, dx=32, x0=0) # Plot pylab.grid(True) pylab.plot(x,y,'o') pylab.plot(newx, newy, linewidth=2) pylab.show()plain code
จะเห็นได้ว่าผลที่ได้จากการพลอท 40 จุด ต่างจากการใช้ Polynom-Interpolation ค่อนข้างมาก โดยที่ Cubic-Spline-Interpolation มีความเสถียร และความแม่นยำที่สูงกว่า แต่แม้กระนั้นก็ตาม Spline-Interpolation ก็มีข้อจำกัดอยู่ นั่นคือ ความยาวของข้อมูลที่ต้องการ interpolate มีความยาวได้ไดม่เกิน 32,768 (32 * 2**10) หาก interpolate ข้อมูลที่มีความยาวมากกว่านั้น ก็จะเกิดความผิดพลาดในการ interpolate ข้อมูล ซึ่งข้อผิดพลาดนี้ ผมเดาเอาว่าเกิดจากตัว Algorithm ไม่ได้เกิดจากการ Implement เพราะใน MATLAB เองก็มีปัญหาดังกล่าว (ที่รู้เพราะเพื่อนผมหาข้อผิดพลาดของโปแกรมที่เขียนด้วย MATLAB อยู่นานมาก แต่หาไม่เจอ แต่พอผมไปเล่าเรื่องนี้ให้ฟัง มันก็ถึงบางอ้อ แก้ไขโปรแกรมเสร็จ ใช้งานได้ตามปกติ) ดังนั้น ผมเลยต้องเขียนโมดูลเพิ่ม เพื่อตัดแบ่งข้อมูลเป็นหลาย ๆ Block โดยแต่ละ Block มีความยาวข้อมูลไม่เกิน 16,384 (ที่ไม่เอา 32,768 เพราะกันเหนียว) จากนั้นจึง interpolate ข้อมูลแต่ละ Block และที่สำคัญ สามารถ interpolate ข้อมูลที่เป็นเลขเชิงซ้อนได้ด้วย ในโค้ดข้างล่างนี้มีทั้งที่ใช้ Pyrex (spline_pyrex) และ CPython (spline) import numpy import scipy.signal def spline_pyrex(sigIn, int samp_pos, int samp) : cdef int i, j, block_length, nblock, dimen dimen = sigIn.shape[0] block_length = 32*512 nblock = dimen/block_length sigOut = numpy.zeros(dimen, dtype=numpy.complex64) for i from 0 <= i < nblock : to_spline = sigIn[i*block_length + samp_pos : (i+1) * block_length + samp_pos : samp] cs = scipy.signal.cspline1d(to_spline.real) interp_re = 1*scipy.signal.cspline1d_eval(cs, numpy.arange(block_length, dtype=numpy.int16), dx=samp,x0=samp_pos) cs = scipy.signal.cspline1d(to_spline.imag) interp_im = 1*scipy.signal.cspline1d_eval(cs, numpy.arange(block_length, dtype=numpy.int16), dx=samp,x0=samp_pos) sigOut[i*block_length : (i+1) * block_length] = interp_re + 1j * interp_im return sigOut def spline(sigIn, samp_pos, samp) : dimen = sigIn.shape[0] block_length = 32*512 nblock = dimen/block_length sigOut = numpy.zeros(dimen, dtype=numpy.complex64) for i in xrange(nblock) : to_spline = sigIn[i*block_length + samp_pos : (i+1) * block_length + samp_pos : samp] cs = scipy.signal.cspline1d(to_spline.real) interp_re = 1*scipy.signal.cspline1d_eval(cs, numpy.arange(block_length, dtype=numpy.int16), dx=samp,x0=samp_pos) cs = scipy.signal.cspline1d(to_spline.imag) interp_im = 1*scipy.signal.cspline1d_eval(cs, numpy.arange(block_length, dtype=numpy.int16), dx=samp,x0=samp_pos) sigOut[i*block_length : (i+1) * block_length] = interp_re + 1j * interp_im return sigOutplain code parameter sigIn : ข้อมูลที่ต้องการ interpolate samp_pos : อธิบายไม่ถูกครับ แต่มันย่อมาจาก Sample Position และมีค่าอยู่ระหว่าง 0 <= samp_pos < samp samp : อัตราส่วน ข้อมูล continue ต่อข้อมูล discrete (ปกติใช้ 32) ข้อมูลที่จะถูก interpolate หรือข้อมูลที่เป็น discrete จะถูก slice จาก sigIn ด้วย to_spline = sigIn[samp_pos::samp] นั่นคือเริ่มจาก samp_pos และเพิ่มครั้งละ samp (ดูบรรทัดที่ 12, 29 อีกที) Analogy of Interpolation to our Social-Structureผมคิดว่ามันมีปรัชญาแฝงบางอย่าง ที่ซ่อนอยู่ใน Polynom-Interpolation และ Spline-Interpolation ที่สามารถนำมาเทียบเคียงกับโครงสร้างทางสังคมได้Polynom-Interpolation นั้น เปรียบไปก็เหมือนโครงสร้างทางสังคม แบบรวมศุนย์ ที่เน้นเรื่องมหาภาค โดยที่ พยายามหายาสารพัดโรค มาแก้ทุกปัญหา (แก้สมการทุก ๆ จุดพร้อม ๆ กัน) ในกรณีที่สังคมมีขนาดเล็ก (N มีค่าน้อย) สิ่งที่ได้คือ วิธีการแก้สมการที่ง่าย ได้ผลเป็นที่น่าพอใจในระดับหนึ่ง แต่เมื่อใดที่คนมากขึ้น โครงสร้างของสังคมมีขนาดใหญ่ขึ้น (N มีค่ามาก) แม้ว่าวิธีการแก้สมการจะเหมือนเดิม แต่การแก้สมการก็จะยากขึ้น อีกทั้งผลที่ได้ยังขาดเสถียรภาพ มีความแตกต่างระหว่างคนในสังคมที่สูง (จุดสูงสุด และจุดต่ำสุดที่มีค่าสูงมาก ๆ) ทำให้เกิดความเหลื่อมล้ำทางสังคมที่สูง และเมื่อใดที่สังคมมีขนาดใหญ่ และซับซ้อนเกินกว่าที่จะใช้วิธีการเดิมในการแก้ปัญหาได้ แต่ก็ยังคงดึงดันใช้วิธีเดิมต่อไป (N > 20) ผลที่เกิดขึ้นจะรุนแรงเกินความควบคุม ความเหลื่อมล้ำทางสังคมที่สูงลิ่ว อีกทั้งปัญหาต่าง ๆ ที่คาดว่าจะได้รับการแก้ไข กลับเป็นการเพิ่มปัญหา (ค่า discrete กับ continue ไม่ตรงกัน) ส่วน Spline-Interpolation นั้น เป็นกระบวนการแก้ปัญหาแบบแยกส่วน โดยไม่ละเลยองค์ประกอบโดยรวม (แบ่งข้อมูลออกเป็นช่วง ๆ แล้วใช้สมการพหุนามกำลังต่ำแก้ โดยคำนึงถึงความสัมพันธ์ระหว่างข้อมูลแต่ละช่วง) ซึ่งวิธีการแบบนี้ คือ การสร้างความแข็งแรงให้ชุมชน และสร้างความสัมพันธ์ระหว่างชุมชนและรัฐ แน่นอนว่าการแก้ปัญหาแบบนี้ไม่ง่ายนัก และไม่เห็นผลทันที (Spline-Interpolation ถูกคิดขึ้นครั้งแรกปี 1946 เป็นเวลานับร้อยปีหลัง Polynom-Interpolation) แต่ผลที่ได้มีความเสถียรกว่า มีการกระจายตัวของผลประโยชน์ที่มากกว่า (ค่าสูงสุด และค่าต่ำสุดมีค่าไม่มากนัก) โดยที่ขนาด และความซับซ้อนของโครงสร้างทางสังคม ไม่ส่งผลกระทบต่อสังคมโดยรวม แม้ว่าวิธีการนี้จะเป็นวิธีการแก้ปัญหาที่ดีกว่า แต่ใช่ว่าจะเป็นวิธีแก้ปัญหาครอบจักรวาล ถึงจุดจุดหนึ่ง วิธีการแก้ปัญหาแบบนี้ก็จะไม่ได้ผล (ความยาวข้อมูลไม่เกิน 32,768) เราก็ต้องหาการแก้ปัญหาแบบอื่น มาใช้ควบคู่กันไปด้วย |
|
08 Jul 07 | by bow_der_kleine | tags เขียนโปรแกรม Python Scipy Mathematic Data-Interpolation Signal-Processing Image-Processing
bow_der_kleine
พี่แปง : เพราะข้อมูล N จุด แก้สมการได้ N สมการ หาก พหุนามกำลัง N จะมีสัมประสิทธิ์ N+1 (รวม p0) ดังนั้น หากต้องการสัมประสิทธิ์จำนวน N ก็ต้องแก้สมการพหุนามกำลัง N-1 ครับหมายเหตุ 1 : ผมอ่อนภาษาอังกฤษมาก Polynom เป็นภาษาเยอรมัน แสดงว่าเขียนผิดมาตลอดเลย
หมายเหตุ 2 : นึกว่าจะไม่มีคนอ่าน เนื้อหาข้างในแล้วครับ
พี่แปง
y = p0 + p1*x + p2*x^2 + p3*x^3โดยให้ y มี N ค่า เมตริกซ์
[1 x x^2 x^3
1 x x^2 x^3
: : :
1 x x^2 x^3]
เป็นเมตริกซ์ผอม แล้วแก้หาค่าสัมประสิทธิ์โดยใช้ least square
โดยปกติแล้ว ยิ่งเลขชี้กำลังของ x ยิ่งมีค่ามากยิ่งไม่ดี ไม่ใช่เหรอครับ
จะเพิ่มเลขชี้กำลังก็ต่อเมื่อ mean square error ยังมีค่ามากเกิดกว่า
ขอบบนที่กำหนดไว้
ผมยังไม่ค่อยเข้าใจว่าทำไมจะประมาณฟังก์ชันของข้อมูล N จุดถึง
้ต้องใช้ พหุนามกำลัง N-1 ด้วย เพราะถ้าค่า p ที่ได้มีความผิดพลาดในการปัดเศษ
เพียงเล็กน้อยคูณกับ x ที่เกิน 1 แล้วยกกำลัง N-1 ที่ว่าก็จะได้ความผิดพลาด
มหาศาล ตามผลที่แสดง
หรือตัวพี่แปงเองเข้าใจอะไรผิด
bow_der_kleine
หากจำนวนจุด มีมากกว่าจำนวนสัมประสิทธิ์ที่ต้องแก้ เส้นโค้งพหุนามที่ได้ก็จะไม่ผ่านจุดทุกจุดที่กำหนดครับ มันก็จะผ่านจุดที่เราใส่เข้าไปตอนแก้สมการพหุนามเท่านั้น
กราฟข้างบน มีจุดที่กำหนดเจ็ดจุด (สีน้ำเงิน) เส้นโค้งสีเขียวใช้พหุนามกำลังสองแก้ โดยใช้จุดสามจุดตรงกลาง ดังนั้นเส้นโค้งที่ได้จะไม่ลากผ่านสี่จุดที่อยู่ข้าง ๆ
ส่วนเส้นโค้งสีแดง ใช้พหุนามกำลังหกแก้สมการ (ใช้ทุกจุด) ทำให้เส้นโค้งลากผ่านทุกจุดที่ต้องการ
หากใช้พหุนามกำลังเจ็ดแก้สมการ โปรแกรมมันจะฟ้องมาอย่างนี้ครับ
RankWarning: Polyfit may be poorly conditionedเนื่องจากอ่อนภาษาอังกฤษเลยแปลไม่ค่อยออก แต่ผมเดา ๆ เอาว่า จุดมันไม่พอแก้สมการพหุนามกำลังเจ็ดครับ
พี่แปง
polynomial interpolation ถ้าใช้ least square estimate แก้หาค่าัสัมประสิทธินี่มันไม่จำเป็นต้องผ่านจุดทุกจุด ขอให้ (1/N)sum(error)^2
ต่ำที่สุดก็พอ ให้ลองนึกถึงข้อมูลที่มี noise ผสม ถ้าเราบังคับให้ฟังก์ัชัน
ลากผ่านทุกจุด มันก็จะรวม noise ไปด้วย เรียกว่า overfitting
ที่เขาบอกว่า N >= n+1 อันนี้มันไม่ใช่สูตรหา n หรือหรือเลขชี้กำลังสูง
สุดของ x นี่ครับ แต่หมายถึงว่า N อย่างน้อย ๆ ต้องมากกว่า n+1 คือต้อง
เป็นเมตริกซ์จตุรัสเป็นอย่างน้อยไม่งั้นหาค่า unique ไม่ได้ ในทางปฏิบัติ
ส่วนใหญ่แล้วก็ N >> n+1 ถึงจะมั่นใจได้ว่า เมตริกซ์มันต้อง full column rank
แน่นอน ที่โปรแกรมมันเตือนก็ถูกแล้วครับ มันไม่ full column rank
แต่งานของโบว์อาจจะต้องการให้ฟังก์ชันลากผ่านทุกจุด โดยมั่นใจว่าข้อมูล
ไม่มีสัญญาณรบกวน
บลอกนี้บอกได้เลยครับว่า Nerd & Geek สุด ๆ เพราะเอาเรื่องที่ทำงานอยู่มาเขียน หากเจอคนที่สนใจเรื่องนี้อยู่พอดี คงเป็นเรื่องบังเอิญมาก ๆ เพราะลำพังคนใช้ Python ก็น้อยเต็มที คนใช้ 




mk
ทิ้งท้ายได้เท่สุดๆ ไปเลยครับ09 Jul 07