March 14, 2010 .NET, C#, Concurrency No comments
March 14, 2010 .NET, C#, Concurrency No comments
Here I have code that provides some explanations to the multithreading in .NET. Wrote it to refresh what I know on concurrency.
March 14, 2010 Book Reviews, Design No comments
Designing is “dry”, non-deterministic and heuristic process.
I just read one chapter from S. McConnell’s “Clean Code” book, and want make some review and summary without taking a look back into book. This should help me reinforce memories of what I’ve learnt.
When you are designing you always should keep in mind that you will not be able to make design good for all situations of life. Thus overthinking on problems could lead to overengineering, so you will get complex system with lot of unneeded tails. Future developers will not be able to work with your design. And project could even fail at some point of time.
To avoid this you should keep building system on easy to understand interfaces, that define how system behaves on different levels and that provide loose coupling.
Building your application like one solid system will lead to situation when you have everything coupled. I’m familiar with system, which is done like single exe file with more than 50 Mb size. You could not even imagine how everything there is coupled – you can get access to any part of the system from any other part. I understand that it is a legacy system and some things where done cause of ‘old school’ and so on and I understand that developers take this into account, but how on earth new guy will know how to work in that system? But how could it be sweet when you have system divided into subsystems, which of them has own responsibilities and depends only on one-two other subsystems, but at the same time provides functionality to good portion of other subsystems.
So, here we talk about low coupling, high cohesion and subsystems ordering. Here is how I do understand this terms:
Low coupling means that parts of the system should interact with each other by clearly defined interfaces, and you should work on decreasing number of interaction. Few characteristics that lead to low coupling are: Volume of connections should be low, Visibility of how two parts connects to each other should be high, Flexibility of changing connection should be also high.
High cohesion means that inside of one part of the system everything should be done compactly, part should have one responsibility well encapsulated inside.
Subsystems ordering means that once you have A and B, and B uses A, then A should not use B. If you need to grow your system you should decrease number of subsystems that you depend on and you should increase number of subsystems that depends on current subsystem. So you are getting tree.
When designing use Design Patterns. Why? Because they are found heuristically and if you think that you have a better decision to the same problem that known design pattern solves it is very possible that your solution will fail.
When designing ask Questions. Why? Designing is iterational process, you always can improve your solution. Just ask yourself if your current design is enough good and if so how could you prove that. Ask if there are other solutions to problem and why did you select your. Ask a lot. Invite a friend let he ask you.
You can design top-bottom and bottom-top ways. Use both. Why and how? Because they have advantages and disadvantages – you can get stuck with top-bottom if you will not have tech solution to some problem, that was defined at the top or solution is very cumbersome, also you can lost vision of what you do with bottom-top and will lost how to clue everything. We are all now far from waterfall so I think that nowadays it is possible to combine those two ways to design.
March 14, 2010 ASP.NET, Environment, QuickTip No comments
I’ve upgraded my system to Windows 7 couple of months ago, but I haven’t used web development.
The Problem
Few days ago, I created empty web application, added new page and added <p>bla-bla<p>, then I hit Ctrl+F5 and my default browser opened, but nothing happened. I was thinking that it is because of my browser, so I switched over 3 browsers and nothing helped, I also thought that it VS2010 broke something causing asp.net development server issues, so uninstalled it and installed back, but nothing helped.
I even had a thought to reinstall system, but decided to search over the internet more deeper and found that:
Reason
Reason is that when system uses IPv6 browsers could have issues with resolving localhost.
Solution
Disabling IPv6 is solution for this problem.
You can disable IP 6 in your system by ensuring that you have this in your registry:
HKEY_LOCAL_MACHINESYSTEMCurrentControlSetServicesTcpip6ParametersDisabledComponents set to 0xffffffff
Firefox settings change
Also when searching I found for myself that we can change settings of Firefox with writing about:config in address bar.
March 11, 2010 Education, Pedagogic Practice No comments
Привітання та дуже загальний вступ
Привіт. Мене звати Андрій Будай і сьогодні я вестиму цю пару, темою якої є k-means алгорим. Some parts will be in English, so please do not scare if I switch to English unexpectedly, like I just did.
As you all know we are talking about the clustering of data. Human brains are very good at finding similarity in things. For example, biologists have discovered that things belong to one of two types: things are either brown and run away or things are green and don’t run away. The first group they call animals, and the second is plants.
Процес групування речей по певних ознаках ми називаємо кластеризацією. Якщо ми говоримо про то, що біологи почали поділяти тварин на ряди, роди та види, то ми говоримо про ієрархічну класифікацію. Яку я передбачаю ви вже розглянули, зоокрема підхід ієрархічної кластиризації згори-вниз та знизу-вгору.
Розуміння Partitioning алгоритмів
А що якщо ми хочемо групувати дані не в порядку збільшення або зменшення об”єму груп, якщо ми хочемо погрупувати N векторів даних на K кластерів за один логічний хід? Такий різновид кластерізації називається Partitioning алгоритмами. Іншими словами ми розбиваємо множину.
Ще раз нагадаємо що таке розбиття множини:
Система множин S={X1 … Xn} називається розбиттям множини M, якщо ця система задовольняє наступним умовам:
Partitioning алгоритми розбивають множину на певну кількість груп за один крок, проте результати покращуються із процесом ітерування. До найвідоміших partitioning алгоритмів відносяться k-means та його модифікації із доповненнями, quality threshold алгоритм також для кластеризації можуть бути використані Locality-sensitive hashing та Graph-theoretic methods. Якщо буде час то ми поговорими і про них також.
K-means алгоритм
Отже, k-means. Насправді алгорим не є складним і я сподіваюся що всі із вас будуть розуміти суть алгоритму та будуть мати палке бажання його реалізувати. Це моя мета на сьогоднішню пару. []
Завданням алгоритму є здійснити розбиття N векторів даних на K груп. Причому число k є попередньо відомим – або є вхідним параметром алгоритму як і дані.
Опис
[Цю частину я збираюся продиктувати]
Маючи список даних спостережень (x1, x2, …, xn), де кожен x є вектором розмірності d, k-means кластеризація призначена для розбиття цього списку із n спостережень на k підмножин (k < n), в результаті чого ми повиння отримати таке розбиття S={S1, S2, …, Sk}, в якому внутрішньокластерна сума квадратів норм є мінімізованою:
де μi є центром Si.
Кроки алгоритму
Перш за все нам слід мати множину із k центрів m1(1),…,mk(1), які можуть бути визначені або випадковим чином, або евристичним шляхом. Алгоритм складається із двох основних кроків – кроку присвоєння та оновлення.
Демонстрація
[here I’m going to switch to English and demonstrate steps of the algo at board]
Оскільки алгоритм є емпіристичним, то немає гаранції, що він досягне глобального мінімуму. А також результат залежить від початкових вхідних кластерів. Оскільки алгоритм є досить швидким, то є така практика, як прогонка алгоритму деяку кількість раз із різними початковими центрами.
Other variations of the K-means algorithm
Because of some disadvantages of standard algorithm we’ve got few
different variations of it like Soft K-means, when data element is
fuzzy associated with mean, or like K-means++, which is additions to
the K-means to initialize cluster means better.
K-means++
With the intuition of spreading the k initial cluster centers away from
each other, the first cluster center is chosen uniformly at random from
the data points that are being clustered, after which each subsequent
cluster center is chosen from the remaining data points with
probability proportional to its distance squared to the point’s closest
cluster center.
Soft K-means алгоритм
В Soft K-means алгоритму кожен вектор має часткову приналежність до якогось кластеру, так як же і в розмитій логіці – існуть не тільки 1 та 0, а ще й 0.667. Таким чином, вектори, що знаходяться ближче до центру кластеру мають більшу приналежність до нього, а ті які знаходяться по краях мають дуже малу приналежність. Отже, для кожного вектора x ми маємо коефіцієнт який відповідає за приналежність до k-того кластеру uk(x). Звичайно, що сума коефіцієнтів для заданого вектора x є рівною 1:
Таким чином, центр кластеру вираховується як середнє всіх векторів, домножених на цей коефіцієнт приналежності до кластеру:
Коефіцієнт є обернено пропорційний до відстані до центру кластеру:
опісля коефіцієнти нормалізуються із використання параметра m > 1 щоб сума була рівною 1 за такою формулою:
Коли m
близьке до 1, кластери ближчі до центру мають більшу приналежність, а ті що дальше мають меншу приналежність. Для m = 2, це відповідає лінійній нормалізації коефіцієнтів, щоб отримати суму 1 і алгоритм подібний до звичайного k-means.
Кроки цього алгоритму є дуже подібними до звичайного:
Цей алгоритм також має деякі проблеми що й у звичайному алгоритму, зокрема залежність від початково вибраних кластерів, та не обов”язкове знаходження глобального мінімуму.
Можливий підхід до реалізації
Обов’язково розділяємо класи для зчитуванна та утримання даних, із класом, що буде здійснювати кроки алгоритму, якщо планується графічне зображення то воно також має бути відділене. Залишаємо можливість обирати норму.
[Не дуже хочу закидати реалізацію, щоб студенти завчасно не використали її]
He-he! I’ve got it in about 3.5 hours.
I would say that core algorithm code looks very good, at least take a look at method Process:
public void Process()
{
Initialize();
while (!ClustersRemainTheSame())
{
AssignStep();
UpdateStep();
}
}
I’ve also used realized algorithm in two applications – one is clusterization of animals by theirs properties and another is graphical demoing usage. Below is nice screenshoot:
Application
[If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.]
“The k-means clustering algorithm is commonly used in computer vision as a form of image segmentation. The results of the segmentation are used to aid border detection and object recognition. In this context, the standard Euclidean distance is usually insufficient in forming the clusters. Instead, a weighted distance measure utilizing pixel coordinates, RGB pixel color and/or intensity, and image texture is commonly used“
One of the application examples is clustering colors in image to compress image. A good article on this is written up here.
Завершення пари
Побажання зробити реалізацію алгоритму
Час на питання
P.S. So far I have some good plan for Friday… not 100% complete, but I’m satisfied with what I have. And tomorrow I’m going to work on this once again. Also not really good that I just translated a lot of stuff from wiki pages.
March 9, 2010 Education, Pedagogic Practice, Ukrainian No comments
On Friday, I will have my first teaching experience (or at least teaching students of my University). This is part of the Master Year pedagogic practice. Subject is called “Data Mining” and theme of Friday’s lesson will be “K-means” algorithm.
Few things here before I start
I will have this post mixed of English and Ukrainian. Why? Because the way I’ll be presenting algorithm in both languages and because I need some report in Ukrainian, so do not want to double write a lot – I’m lazy ass as someone said.
План уроку (Agenda)
1. Привітання та дуже загальний вступ
Даю знати хто я і про що буду розповідати. Also I have a nice joke in English that could grab attention of the students. Hope they will be able to recognize and understand my English.
2. Розуміння Partitioning алгоритмів
Тут я нагадаю що таке Cluster analysis та згадую про Hierarchical і Partitional різновиди. І дещо про різниці між ними.
3. K-means алгоритм
– завдання алгоритму
– введення позначень
– кроки алгоритму
– демонстрація алгоритму як на дошці так і на комп”ютері
– переваги та недоліки
4. Other variations of the K-means algorithm
Because of some disadvantages of standard algorithm we’ve got few different variations of it like Soft K-means, when data element is fuzzy associated with mean, or like K-means++, which is additions to the K-means to initialize cluster means better.
5. Soft K-means алгоритм
– різниця в кроках алгоритму
6. Можливий підхід до реалізації (можливо напишу програму ще раз)
7. Application
If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.
One of the application examples is clustering colors in image to compress image.
8. Побажання зробити реалізацію алгоритму
9. Час на питання
I hope tomorrow I’ll have article with whole lesson text, more structured and with examples, also hope to write k-means plus demo from scratch. Will see how fast am I.
March 3, 2010 IDE, WCF, Workaround No comments
If you have no “Edit WCF Configuration” in the context menu on right click on the App.config.
I’m talking about this one:
Go to Tools -> WCF Service Configuration Editor
Open it and then close.
This is funny and strange solution to our issue.
March 3, 2010 Revision of my activity, Success No comments
March 3, 2010 KohonenAlgorithm, MasterDiploma No comments
I already have some implementation of the parallelization in algorithm of SOM.
Let us quickly remind the main steps of the classical Kohonen learning algorithm.
As you see algorithm could be very expensive if we have big amounts of data.
Also, steps 3 and 4 takes the most of time, what if we execute 2-3-5 in separate threads? Yes, we could do this to some extend. Main issue is when we have overlapping of affected area by two best matched neurons wich we found in separate threads.
I’m bit tired to write a lot of explanations of this algorithm, so I prepared 3 images that says for themselves. Hope will have detailed explanations and different tuning things for this soon.
February 28, 2010 .NET, AutoMapper, Frameworks 4 comments
After I’ve posted this article one guy was really concerned about the performance of AutoMapper.
So, I have decided to measure execution time of the AutoMapper mapping and manual mapping code.
First of all I have code which returns me 100000 almost random Customers which goes to the customers list.
Measurement of AutoMapper mapping time:
Measurement of the manual mapping time:
I ran my tests many times and one of the possible outputs could be:
AutoMapper: 2117
Manual Mapping: 293
It looks like manual mapping is 7 times faster than automatical. But hey, it took 2 sec to map handrend thouthands of customers.
It is one of the situations where you should decide if the performance is so critical for you or no. I don’t think that there are a lot of cases when you really need to choice manual mapping exactly because of performance issue.
February 27, 2010 .NET, AutoMapper, Clean Code 2 comments
If you haven’t read my previous article on AutoMapper, please read it first.
I just read an article on the noisiness which could be introduced with AutoMapper.
My Mapping Code is Noisy
Accordingly to that article my code:
CustomerViewItem customerViewItem = Mapper.Map<Customer, CustomerViewItem>(customer);
is noisy code.
Why?
In few words that is because I’m coupled to the specific mapping engine and because I’m providing too much unneeded information on about how to map my objects.
Take a look on that line once again: we used Customer , but we already have customer, so we can know its type.
What to do to make it not so noisy?
In that article, that I pointed, there is proposition to change my code to:
CustomerViewItem customerViewItem = customer.Map<CustomerViewItem>();
So, I’ve got interested to apply it to my previous AutoMapper article’s code. As you already caught Map is just extension method for my Customer class.
Here it is:
Everything becomes simple if you are trying it.